目次と前回の記事
Python のバージョンとこれまでに作成したモジュール
本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| mbtest.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
今回の記事では前回の記事のおさらいとまとめを行い、その後で強化学習において行われる最適化問題の性質について説明することにします。
なお、前回の記事の最後に述べたように、本当は今回の記事では「強化学習におけるマルコフ性の重要性」と、マルコフ性を持つ場合の強化学習の手法である「マルコフ決定過程」について説明する予定でしたが、そのことを理解するためには「最適化問題」の性質について説明する必要があると考えました。そのため、今回の記事で予定していた内容は次回の記事で説明することにします。
なお、しばらくの間は太字による強調を自粛していましたが、少しはあったほうが良い気がしましたので、ピンポイントに使いたいと思います。
前回の記事のおさらいとまとめ
前回の記事ではマルコフ性を満たす強化学習の定式化を行いました。そこで定義した数式や記号は引き続き頻繁に使用するので、最初に前回の記事のおさらいとまとめを行います。
記号の表記の使いわけ
機械学習では様々な用語をアルファベットやギリシャ文字などの記号で表し、その性質に応じて下記のように表記を使い分けます。なお、下記の説明では行動(action)を表す a という記号を具体例としました。
- 集合:飾り文字の $\mathcal{A}$ で表記する(例:行動の集合)
- 確率変数:大文字の $A$ で表記する(例:確率によって変化する行動)
- 実現値:小文字の $a$ で表記す(例:実際に選択された行動)
用語のまとめ
前回の記事で新しく紹介したいくつかの強化学習に関する用語についてまとめます。それ以外の用語については以前の記事を参照して下さい。
状態遷移(state transition)
エージェントの行動によって状態が変化することを状態遷移と呼びます。
決定論的(determinisitic)と確率的(stochastic)
前回の記事で説明したように状態遷移には大きく分けて 2 つの性質があります。
- 決定論的:同じ状態で同じ行動を取った時に「常に同じ状態に遷移する」性質
- 確率的:同じ状態で同じ行動を取っても、遷移する状態が「確率的に決まる」性質
なお、決定論的な状態遷移は「必ず遷移する状態への遷移確率を 1」、「そ以外の状態への遷移確率を 0」とした 確率的な状態遷移の一種 と考えることもできます。
「決定論的」と「確率的」という性質の区別は、即時報酬と方策にも同様に存在します。
〇× ゲームの場合の「状態遷移」と「即時報酬」は決定論的です。また、強化学習では学習を行う段階の「方策」は一般的に確率的なものとして扱いますが、学習の結果特定の状態で特定の行動のみを選択するという決定論的な方策が導かれることが良くあります。
マルコフ性(markov property)
前回の記事で説明したように、「マルコフ性」とは状態遷移、即時報酬、方策が「現在の状態のみに依存する」という性質のことです。なお、「マルコフ性」という性質と上記の「決定論的であるか」という性質は 互いに関係のない独立した性質 である点に注意して下さい。
多くの強化学習では状態遷移、即時報酬、方策がマルコフ性を持つことを前提としています。マルコフ性のより具体的な説明と、その重要性については次回の記事で説明します。
状態遷移関数、報酬関数、方策関数
強化学習における 3 つの主要な概念はそれぞれ以下の関数で表されます。
これらは「決定論的」であるか「確率的」であるかによって下記の表のように関数が異なります。表の記号は $s$ が現在の状態、$a$ が行動、$s'$ が状態遷移後の状態を表します。状態遷移が決定論的な場合の報酬関数は、$r(s, a)$ のように$s'$ を省略することがあります。
| 関数 | 決定論的 | 確率的 |
|---|---|---|
| 状態遷移関数 | $f(s, a)$ | $P(s' \mid s, a)$ |
| 報酬関数 | $r(s, a)$ $r(s, a, s')$ |
$P(r \mid s, a)$ $P(r \mid s, a, s')$ |
| 方策関数 | $μ(s) $ | $π(a \mid s)$ |
履歴(history)
強化学習のエピソードで得られた一連の「各ステップでの状態、行動、即時報酬を集めた集合」のことを履歴(history)または軌跡(trajectory)と呼びます。
ステップ数が $n$ のエピソードにおける、ステップ $t$ での状態、行動、即時報酬を $s_t$、$a_t$、$r_t$ と表記すると、履歴は下記のように表記されます。
$s_0$、$a_0$、$r_0$、$s_1$、$a_1$、$r_1$、$s_2$、・・・、$s_{n-1}$、$a_{n-1}$、$r_{n-1}$、$s_n$
累積報酬と収益(割引累積報酬)
エピソード全体で得られる即時報酬を単純に足し合わせた合計を「累積報酬」と呼びます。それに対して(ステップ数が大きな)遠い未来に得られる即時報酬を小さく(割引して)計算した合計のことを収益(割引累積報酬)と呼びます。強化学習では一般的にこの「累積報酬」と「収益」を明確に区別して扱います。
エピソードのステップ $t$ 以降に得られる累積報酬と収益は、いずれも $g$ という記号で表され、それぞれ下記の式で定式化されます。ただし、$γ$ は「割引率」を表す 0 以上 1 未満の実数です。
- 累積報酬:$g_t = \sum_{i=t}^{n-1}r_i$
- 収益(割引累積報酬):$g_t = \sum_{i=t}^{n-1}γ^{i-t}r_i$
また、即時報酬、累積報酬、割引累積報酬、収益を英語で下記のように表記します。
| 用語 | 英語表記 |
|---|---|
| 即時報酬 | reward |
| 累積報酬 | cumulative reward |
| 割引累積報酬 | discounted cumulative reward |
| 収益 | return |
状態価値(state value)と行動価値(action value)
方策に従って行動を行った場合に得られる「累積報酬または収益の期待値」のことを価値(value)と呼びます。強化学習の目的は「価値」を最大化する方策を見つけることです。
強化学習では解決したい問題の性質に応じて「累積報酬」と「収益」のどちらの期待値を最大化するかを使い分けます。例えば、〇× ゲームのような途中のステップで報酬が得られず、ゲーム終了時(最後のステップ)でのみ勝敗結果という報酬が得られる場合は、単純な「累積報酬」を用いた強化学習を行うのが一般的です。
価値には状況に応じて使い分けが行われる以下の 2 種類があります。
- 状態価値:ある状態 $s$ から方策 $Π$ に従って行動を選択し続けた場合に得られる累積報酬(または収益)の期待値
- 行動価値:ある状態 $s$で具体的な行動 $a$ を取り、その後方策 $Π$ に従って行動を選択し続けた場合に得られる累積報酬(または収益)の期待値
状態価値関数と行動価値関数
状態 $s$ での状態価値を表す関数のことを状態価値関数 と呼び $V_Π(s)$ と表記します。
また、状態価値は「状態 $s$ から方策 $Π$ に従って行動を取り続ける」という条件のもとで得られる累積報酬 $G$ の期待値であることから下記の式で表されます。
$V_Π(s) = E[G \mid s, Π]$
状態 $s$ で行動 $a$ を取った場合の行動価値を表す関数のことを行動価値関数と呼び、$Q_Π(s, a)$ と表記します。
また、行動価値関数は報酬関数と状態価値関数を用いた下記の式で定式化されます。ただし、下記の式は状態遷移が決定論的な場合の式です。
$Q_Π(s, a) = r(s, a) + V_Π(f(s, a))$
目的関数(objective function)と最適方策(optimal policy)
強化学習のような方策の最適化を求める問題において、最大化(または最小化)の対象となる関数のことを「目的関数」と呼びます。
強化学習における目的関数は、エピソードの最初の状態(初期状態)$s_0$ における状態価値を表す $V_Π(s_0)$ です。
この目的関数 を最大化する方策のことを「最適方策」と呼びます。本記事では最適方策を数学において最適な値や関数であることを表す *(スター) を の右肩につけた $Π^*$(パイスター)と表記することにします。
記号のまとめ
前回の記事で新しく紹介した記号をまとめます。
環境に関する記号
下記は環境に関する記号をまとめたものです。前回の記事のまとめでは決定論的な状態遷移関数と報酬関数のみを表でまとめましたが、今度の記事で確率的な場合を扱うことを考慮して、確率的な場合についても表記しました。また、下記ではエピソードのステップ数が $n$ であるものとします。
なお、前回の記事で説明し忘れましたが、強化学習では状態の集合や行動の集合のことを「状態空間」、「行動空間」と呼びます。
| 記号 | 意味 |
|---|---|
| $\mathcal{S}$ | 状態の集合(状態空間) |
| $\mathcal{A}$ | 行動の集合(行動空間) |
| $s$ | 特定の 1 つの状態 |
| $a$ | 特定の 1 つの行動 |
| $f(s, a)$ | 状態 $s$ で行動 $a$ を取った時に遷移する状態を表す、決定論的な状態遷移関数 |
| $P(s' \mid s, a)$ | 状態 $s$ で行動 $a$ を取った時に状態 $s'$ に遷移する確率を表す、確率的な状態遷移関数(確率質量関数) |
| $r(s, a)$ $r(s, a, s')$ |
状態 $s$ で行動 $a$ を取った時に得られる即時報酬を表す、決定論的な報酬関数。上段は状態遷移が決定論的、下段は確率的な場合を表す |
| $P(r \mid s, a)$ $P(r \mid s, a, s')$ |
状態 $s$ で行動 $a$ を取り状態 $s'$ に遷移した時に即時報酬 $r$ が得られる確率を表す、確率的な報酬関数(確率質量関数)。上段と下段の違いは上記と同様 |
状態の集合、行動の集合、状態遷移関数及び報酬関数は 原則として後から変更されることはありません。また、強化学習の大きな特徴として、エージェントはこれらの環境に関する具体的な情報(状態の集合、行動の集合、状態遷移関数、報酬関数)を 原則として知らされていない ものとして学習を行います。
エージェントに関する記号
エージェントに関する記号は以下の通りです。なお、特定の方策を小文字の $π$ で表記し、方策の集合(方策空間)を大文字の $Π$ で表記することが良くありますが、本記事では方策が「各状態で各行動を選択する方針を表す確率の集合」であることから特定の方策を大文字の $Π$ で表記することにしました。
| 記号 | 意味 |
|---|---|
| $Π$1 | 特定の方策 |
| $μ(s)$ | 状態 $s$ で選択する行動を表す、決定論的な方策関数 |
| $π(a \mid s)$ | 状態 $s$ で行動 $a$ をとる確率を表す、確率的な方策関数(確率質量関数) |
| $s_t$、$a_t$、$r_t$ | エピソードのステップ t における状態、行動、即時報酬 |
| $g_t$ | ステップ $t$ 以降に得られる累積報酬または収益 |
| $G、G_t$ | 累積報酬または収益を表す確率変数。エピソードのステップ $t$ 以降に得られたものであることを明確にしたい場合は $G_t$ と表記する |
| $V_Π(s)$ | 状態 $s$ から方策 $Π$ に従って行動を取り続けた場合に得られる、累積報酬(または収益)の期待値を表す状態価値関数 $V_Π(s) = E[G \mid s, Π]$ |
| $Q_Π(s, a)$ | 状態 $s$ で行動 $a$ を取った後で、方策 $Π$ に従って行動を取り続けた場合に得られる、累積報酬(または収益)の期待値を表す行動価値関数 $Q_Π(s, a) = r(s, a) + V_Π(f(s, a))$2 |
強化学習の定式化
これまでの定義をすべて組み合わせることで、下記のように、強化学習を数学的に定式化できます。ただし、下記は状態遷移、即時報酬、方策がマルコフ性を持ち、状態遷移と即時報酬が「決定論的」である場合の定式化です。
強化学習の目的は、環境によって下記の 5 つの要素が定義されているときに、エージェントと環境の相互作用によって得られた経験を元に、目的関数 $V_Π(s_0)$ を最大化する最適方策 $Π^*$ を見つけることである。
- 状態の集合(状態空間):$\mathcal{S}$
- 行動の集合(行動空間):$\mathcal{A}$
- 各組合せに関するルール:「すべての状態 $s \in \mathcal{S}$」と「その状態 $s$ で取りうるすべての行動 $a \in \mathcal{A}(s)$」に対する「状態遷移関数 $f(s, a)$」と「報酬関数 $r(s, a)$」
- 開始地点:エピソードの開始時の初期状態 $s_0$
- 終了地点:エピソードの終了条件(特定の状態への遷移、一定時間の経過など)
この目的を数式で表すと下記の式になります。
$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$
状態遷移と即時報酬が確率的な場合は、上記の状態遷移関数と報酬関数を確率的な表現である $P(s' \mid s, a)$ と $P(r \mid s, a, s')$ に置き換えるだけでそのまま成り立ちます。
最適化問題
強化学習の目的である、下記の式で表される最適方策 $Π^*$ を見つけるという問題は、数学の世界では「最適化問題(optimization problem)」と呼ばれる問題に分類されます。
$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$
今回の記事の冒頭で述べたように、強化学習におけるマルコフ性という制約の重要性を理解するためは最適化問題の性質について理解する必要があります。そこで、ここからは最適化問題の基本的な性質について詳しく説明します。
参考までに Wikipedia の最適化問題の項目のリンクを下記に示します。
最適化問題の定義
最適化問題とは、ある集合 $\mathcal{X}$ の要素を引数として持つ関数 $f(x)$ に対して、$\boldsymbol{f(x)}$ を最大化(または最小化)する最適な要素 $x^*$ を求める 問題のことです。
$f(x)$ を最大化する場合は、最適化問題は数学的に以下のように定義されます。なお、$\forall$ は以前の記事で説明した「任意(すべて)に対して成り立つ」という意味の全称記号です。
$\forall x \in \mathcal{X}, f(x^*) \ge f(x) \text{となる} x^* \in \mathcal{X} \text{を求めよ}$3
$f(x)$ を最小化する $x^*$ を求める場合の最適化問題の定義は、下記のように不等号を反転した形になります。
$\forall x \in \mathcal{X}, f(x^*) \le f(x) \text{となる} x^*\in \mathcal{X} \text{を求めよ}$
また、上記を $\operatorname{argmax}$ を用いた記法で定式化すると下記のようになります。1 つ目の式は $f(x)$ を最大化、2 つ目の式は最小化する場合のもので、$\operatorname{argmin}$ は $f(x)$ が最小となる $x$ と求めるという意味の記号です。
$\operatorname{argmax}_{x \in \mathcal{X}} f(x)$
$\operatorname{argmin}_{x \in \mathcal{X}} f(x)$
なお、$x$ がどのような集合の要素であることが文脈から明らかな場合は、下記のように $\operatorname{argmax}$ の添字を単に $x$ のように省略して表記する場合があります。
$\operatorname{argmax}_{x} f(x)$
実際に先程紹介した強化学習を定式化した下記の式では、方策 $Π$ が属する集合の表記を省略していました。
$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$
上記の式で省略されている方策の集合(方策空間)とは、環境のすべての状態 $\forall s \in \mathcal{S}$ に対して下記の 2 つの確率の性質を満たす「あらゆる方策の集まり」のことです。
- $\forall a \in \mathcal{A}(s)、0 \leq π(a | s) \leq 1$
- $\sum_{a \in \mathcal{A}(s)}π(a | s) = 1$
上記の式を言葉で説明すると以下のようになります。
- $π(a | s)$ は状態 $s$ で行動 $a$ をとる確率を表すので、その状態でとることができるすべての行動($\forall a \in \mathcal{A}(s)$)に対する確率は必ず 0 以上 1 以下の値をとる
- 状態 $s$ において「何らかの行動を必ず 1 つ選択する」ため、その状態で取れるすべての行動の確率の合計は必ず 1(100 %)となる
最適化問題の用語
最適化問題では以下の用語と記号を用います。
| 用語 | 記号 | 意味 |
|---|---|---|
| 目的関数 | $f$ | 最大化(または最小化)の対象となる関数 |
| 実行可能領域 | $\mathcal{X}$ | 関数 $f$ の引数がとりうる値を表す集合 |
| 制約 | なし | $f$ の引数が満たすべきルール($\mathcal{X}$ を規定する条件) 例:「整数のみ」、「正の値のみ」など |
| 実行可能解 | $x \in \mathcal{X}$ | 制約を満たし、$f$ に入力できる候補となる要素 |
| 最適解 | $x^*$ | 実行可能解の中で $f(x)$ を最大化(最小化)する最高の要素 |
| 最適値 | $f(x^*)$ | 最適解を入力した時に得られる $f(x)$ の最大値(最小値) |
1 変数の最適化問題
抽象的な説明だけではわかりづらいと思いますので、身近な具体例をあげて説明します。なお、本記事では最適解が 1 つだけとなる具体例を紹介しますが、最適問題には最適解が複数存在する場合があります。
以降の説明では「目的関数を表す $f$」や「販売価格を表す $s$」のように、強化学習で用いられるいくつかの記号を 全く異なる意味 で用います。そのため、以降の解説を読む間は強化学習の記号のことは忘れて読み進めて下さい。
最初に最もシンプルな、目的関数の変数(引数)が 1 つだけの場合の例を紹介します。
最適化問題は、現実のビジネスの課題を解くために良く使われます。例えば、「アイスクリームを販売する際に 1 日の利益を最大化する」という問題を考えてみましょう。ただし、それだけでは問題が漠然としすぎているので以下のようなルール(条件)を設定します。
- アイスクリームの仕入れ値は 1 つ 100 円とする
- アイスクリームの在庫は無限にあるものとする
- アイスクリームの販売価格(sales price)を $s$、一日の販売個数(number)を $n$、利益(profit)を$p$ と表記する。ただし販売価格は 0 以上の値($0 \le s$)であるものとする
従って、この問題は「利益 $p$ を最大にするための条件」を見つけることが目的になります。
上記の設定から 1 日の利益は「(販売価格 - 100)× 販売個数」という式で計算できるので、利益 $p$ は下記の式で表されます。
$p = (s - 100)n$
一般的に商品の販売個数は「価格が低いほど多く売れ、高いほど売れなくなる」という性質があります。そこで、過去のアイスクリームの販売経験から、販売価格 $s$ と販売個数 $n$ の間に下記の式で表される関係が成り立つことがわかったとします。ただし、下記の式を用いると販売価格が 1000 円を超えると販売個数が負になるので $0 \le s \le 1000$ とします。
$n = 1000 - s$
下記はこの「販売価格」と「販売個数」の関係をグラフ化するプログラムです。なお、np.linspace は以前の記事で紹介した、指定した範囲の数値を、指定した個数で等分した 1 次元の ndarray を計算する関数です。実行結果のグラフからわかるように、この式は販売価格が増えると販売個数が直線的に減るという関係を表しています。
import matplotlib.pyplot as plt
import numpy as np
import japanize_matplotlib
S = np.linspace(0, 1000, 1000)
N = 1000 - S
plt.xlabel("販売価格")
plt.ylabel("販売個数")
plt.plot(S, N)
実行結果
ここで、先程の利益 $p$ の式にこの式($n = 1000 - s$)をあてはめると、下記のように利益 $p$ は販売価格 $s$ だけを用いた下記の 2 次関数で表すことができます。
$p = (s - 100) × (1000 - s) = -s^2 + 1100s - 100000$
この利益 $p$ を販売価格 $s$ に対する関数 $f(s)$ と考えると、このビジネスの課題は以下の表の条件のもとで利益を最大化する「最適な販売価格 $s^*$ を求める」という最適化問題に翻訳することができます。なお、以下では $a$ 以上 $b$ 以下の実数の範囲を $[a, b]$ と表記します。
| 用語 | この具体例での値 |
|---|---|
| 目的関数 | $f(s) = p = -s^2 + 1100s - 100000$ |
| 実行可能領域 | $[0, 1000]$ |
| 制約 | 0 以上 1000 以下の実数 |
| 実行可能解 | $s \in [0, 1000]$ |
| 最適解 | $s^* = \operatorname{argmax}_{s \in [0, 1000]} f(s)$ |
| 最適値 | $f(s^*)$ |
具体的な対象や現象 を抽象化、簡略化し、数学的に記述したもの のことを 数理モデル と呼びます。上記の「ビジネスの問題」を翻訳した「最適化問題」は、ビジネスの問題を数学的に記述した数理モデルです。対象を適切に表現した数理モデルを扱うことで、対象について理解したり、それを構成する要素や要因の影響を調べたり、そのふるまいを予測したり制御したりすることができるようになります。
参考までに Wikipedia の数理モデルの項目のリンクを下記に示します。
この問題の解法
上記の $f(s)$ のような、目的関数に影響を与える変数(引数)が 1 つだけである問題を「1 変数の最適化問題」と呼びます。
目的関数が 1 変数の 2 次関数4で表される最適化問題は、高校数学の知識(平方完成)を用いて簡単に解くことができます。
具体的な解法を説明する前に、販売価格 $s$ と利益 $p$ の関係を下記のプログラムでグラフ化する化することで $f(s)$ の最大値がどのあたりにあるかの見当をつけることにします。
P = -S ** 2 + 1100 * S - 100000
plt.xlabel("販売価格")
plt.ylabel("利益")
plt.plot(S, P)
実行結果
2 次関数のグラフは実行結果のような放物線の形状になり、グラフの形状から明らかに販売価格が 400 から 600 の間のどこかで利益が最大化することが視覚的にわかります。
$f(s)$ を最大化する $s^*$ は $f(s)$ を下記のように変形することで求めることができます。なお、このような 2 次関数の式の変形を平方完成と呼びます。
$f(s) = -s^2 + 1100s - 100000$
$= -(s - 550)^2 + 202500$
実数を 2 乗して負の値にした $-(s - 550)^2$ は必ず 0 以下になり、この値が最大値である 0 となるのは $s = 550$ の場合です。従って $f(s)$ は $s = 550$ の場合に最大値である $202500$ となります。550 は $s$ の制約である 0 以上 1000 以下の範囲内なので、この最適化問題の最適解と最適値は下記のようになります。
- 最適解:$s^* = \operatorname{argmax}_{s \in [0, 1000]} f(s) = 550$
- 最適値:$f(s^*) = 202500$
このような数式の変形だけを用いて 厳密に求められた解 のことを「解析解」と呼びます。
もう一つの重要な解法として微分を利用するという方法があります。
具体的には、$f(s)$ を $s$ で微分した $f'(s)$ を求め、$f(s)$ のグラフの傾きが 0 となる $f'(s) = 0$ の解から最適解を求めます。微分を用いた解法は 3 次以上のより複雑な目的関数の最適解を求める際に役立ち、この後で具体例を紹介します。
参考までに Wikipedia の平方完成の項目のリンクを下記に示します。
目的関数の表現力と最適化問題の難しさのトレードオフ
上記の例では販売価格 $s$ と販売個数 $n$ の間に下記の式が成り立つという前提で最適化問題を解きました。
$n = 1000 - s$
先程のグラフが示すように、この式は販売価格が増えると販売個数が 直線的に減少するという単純な関係 を表しますが、実際の関係がこのような単純な直線になるとは限りません。
例えば、販売価格の上昇に伴って、最初は販売個数が急速に落ち込み、その後は緩やかに 0 に近づいていくケースなどが考えられます。このような複雑な関係を表現するためには、$n = 1000 - s$ よりも複雑な数式を用いる必要があります。
複雑な関係を表す式の具体例
具体例として販売価格 $s$ と 販売個数 $n$ が下記の関係を持つ場合を考えることにします。
- $n = 1000 -s$ と同様に、$s = 0$ の時に $n = 1000$、$s = 1000$ の時に $n = 0$ となる
- $s$ が増えると最初は $n$ が急激に減るが、次第に減り方が緩やかになる
下記はそのような条件を満たす式の一例で、$n$ を $s$ の 2 次関数として定義しました。$s = 0$ の場合に $n = 1000$、$s = 1000$ の時に $n = 0$ となることを確認してみて下さい。
$n = \dfrac{(1000 - s)^2}{1000}$
下記は上記をグラフ化するプログラムで、実行結果から上記の条件が満たされていることが確認できます。
N = (1000 - S) ** 2 / 1000
plt.xlabel("販売価格")
plt.ylabel("販売個数")
plt.plot(S, N)
実行結果
$n$ を下記の式で定義することで、$n$ の減らし方を細かく調整することができます。下記の式の $i$ は自然数で、$i$ を増やすことで $n$ の減り方がより急速になります。
$n = \dfrac{(1000-s)^i}{1000^{i-1}}$
下記は $i$ が 1 から 5 までのそれぞれの場合のグラフを描画するプログラムです。実行結果から $i$ を増やすと $n$ の減り方が急激になることが確認できます。また、$i$ が 1 の場合は $n = 1000 - s$ と同じグラフになることが確認できます。
for i in range(1, 6):
N = (1000 - S) ** i / (1000 ** (i - 1))
plt.xlabel("販売価格")
plt.ylabel("販売個数")
plt.plot(S, N, label=f"i = {i}")
plt.legend()
実行結果
先程設定した条件を満たす式は、上記以外にも様々なものが考えられます。
一例として $n = \frac{1}{s}$ のような $s$ に反比例する式が挙げられます。ただし、そのままでは「$s = 0$ の時に $n = 1000$」、「$s = 1000$ の時に $n = 0$」とはならないため、式をうまく変形してつじつまを合わせる必要があります。また、複雑な計算が必要になるため説明は省略しますが、このような反比例の式で $n$ を表した場合は目的関数の最適解を求めることが非常に難しくなります。
上記の $n = \frac{(1000 - s)^2}{1000}$ を利益を表す $p = (s - 100)n$ に代入すると、目的関数である $p=f(s)$ は下記のような $s$ の 3 次関数になります。
$p = f(s) = \dfrac{(s - 100) (1000 - s)^2}{1000}$
$= \dfrac{s^3 -2100s^2 + 1200000s - 100000000 }{1000}$
残念ながら、3 次以上の関数の最大値に対しては 2 次関数の「平方完成」のような簡潔な解法はありません。そのため、一般的には「微分」を用いて最適解を求める必要があります。
微分は高校数学の範囲であり、人によっては学んでいないことがあるため、具体的な解法については参考として今回の記事の最後で説明します。現時点で微分がよくわからないという方も、目的関数の次数が 2 から 3 に増えるだけで、最適解を求めることが一気に難しくなるというポイントだけは押さえておいて下さい。
n 次関数の表現力と最適解の求めやすさのトレードオフ
ここまでの例では販売価格 $s$ と販売個数 $n$ の関係を下記の 2 種類の方法で表現しました。
- 1 次関数:直線的な関係
- 2 次関数:放物線で表される曲線的な関係
2 次関数を用いることで曲線的な関係を表すことができるようになりましたが、2 次関数で表される放物線は「下降→上昇」または「上昇→下降」という、「上昇」と「下降」の移り変わりが 1 箇所しかない曲線 しか表現できません。
「上昇」と「下降」の移り変わりが複数存在するような、より複雑な関係を表したい場合は関数の次数を上げる必要があります。証明は省略しますが、$n$ 次関数は最大で $n - 1$ 個の「上昇」と「下降」の移り変わりを持つ曲線を表現することができます。
下記は 1 次から 4 次までの関数を描画するプログラムで、実行結果のグラフから「上昇」と「下降」の移り変わりが「関数の次数 - 1」個存在することが確認できます。
なお、下記のプログラムは $x = 0, 1, 2, ・・・, n-1$ を解として持つ $y = x(x - 1) ・・・ (x - (n - 1))$ という $n$ 次関数のグラフを描画します。
-
1 行目:4 つのグラフを縦横 2 x 2 の形で並べて描画するための 4 つの Axes を以前の記事で説明した
subplotsメソッドで作成する。axesには 2 次元の list の要素に 4 つの Axes が代入される - 3 ~ 10 行目:繰り返し処理で 1 ~ 4 次関数のグラフを適切な Axes に描画する
-
4 行目:
axesからn次関数のグラフを描画する Axes を参照してaxに代入する -
5 行目:
Xに $y = 0$ となる解の範囲を 100 個に区切った値を持つ ndarray の配列を代入する。なお、1 次関数の場合の解は 0 しかなく「範囲」が存在しないため、Xの範囲を解の場所から 0.1 だけ広げるという工夫を行なった -
6 ~ 8 行目:最初に
YにXを代入し、その後繰り返し処理で必要な数だけYにX - iを掛け合わせることでn次関数に対するYの値を計算する - 9、10 行目:グラフのタイトルを設定してグラフを描画する
-
11 行目:このままグラフを描画するとグラフのタイトルとグラフの目盛りが重なってしまうため、その問題を解決するための
tight_layoutメソッドを呼び出す
1 fig, axes = plt.subplots(2, 2)
2
3 for n in range(1, 5):
4 ax = axes[(n - 1) // 2][(n - 1) % 2]
5 X = np.linspace(-0.1, n - 0.9, 100)
6 Y = X
7 for i in range (1, n):
8 Y = Y * (X - i)
9 ax.set_title(f"{n} 次関数")
10 ax.plot(X, Y)
11 plt.tight_layout()
12 plt.show()
行番号のないプログラム
fig, axes = plt.subplots(2, 2)
for n in range(1, 5):
ax = axes[(n - 1) // 2][(n - 1) % 2]
X = np.linspace(-0.1, n - 0.9, 100)
Y = X
for i in range (1, n):
Y = Y * (X - i)
ax.set_title(f"{n} 次関数")
ax.plot(X, Y)
plt.tight_layout()
plt.show()
実行結果
matplotlib の tight_layout メソッドの詳細については下記のリンク先を参照して下さい。また、tight_layout の効果を確認したい方は、11 行目の plt.tight_layout() を削除してプログラムを実行してみて下さい。
このように、関数の次数を上げることで目的関数の表現力を高めることができますが、一方で目的関数の最適解を求めることが困難になるという問題が生じます。
先程のビジネスの課題の例では利益が $p = (s - 100)n$ という式で表されるので、$n$ を $s$ の $i$ 次関数で表現すると、目的関数である $p = f(s)$ は $s$ の $i + 1$ 次関数になります。
目的関数 $f(s)$ の最適解を微分を用いて求める場合は、目的関数を微分した $f'(s) = 0$ という方程式の解を求める必要があります。$s^i$ を微分すると $is^{i-1}$ となるという性質から $f'(s)$ は $f(s)$ よりも次数が 1 つ少ない $i$ 次関数になります。
$f'(s) = 0$ の解は、$f'(s)$ の次数が高くなればなるほど求めることが困難になります。また、5 次以上の方程式には、四則演算とルート(√)だけで表せる「解の公式」が存在しないことが証明されています5。そのため、目的関数 $f(s)$ の次数が 6 以上の場合は最適解を数式の変形によって解析的に求めることができなくなります。
最適解を解析的に求めることが困難、または不可能な場合は近似解を求めることになりますが、目的関数の次数が高くなると近似解を求めることが困難になる点は変わりません。
以上のことから、最適化問題には以下のようなトレードオフがあることがわかります。
- 目的関数の次数を高くすると、表現力が上がる
- 目的関数の次数を高くすると、最適解を見つけることが困難になる
そのため、最適化問題では現実の現象を一定以上の精度で再現できるという「適度な表現力をもちつつ」、「最適解を見つけるための難易度が上がりすぎない」ような、バランスの良い目的関数を設定することが重要になります。
次回の記事で詳しく説明しますが、「マルコフ性」をという概念を導入することで強化学習の目的関数にこのようなバランスの良い性質を持たせることができるようになります。
目的関数の次数を必要以上に高くする必要はありません。例えば、アイスクリームの販売価格と販売数の関係が「価格を上げると売れ行きが落ち、また上がって、さらに落ちる」といった上下を何度も繰り返すような複雑な動きをすることは考えにくいため、あえて 3 次以上の関数を用いる必要はありません。
関数の次数が高くなると、必ず最適解を求めることが困難になるわけではありません。例えば $f(x) = -x^{100}$ は 100 次関数という非常に高い次数を持ちますが、明らかに $x=0$ で最大値である 0 になります。そのため、「一見すると解くのが難しそうだが、実は綺麗に最適解が求まる」という特殊な構造を持った複雑な目的関数があえて選択される場合もあります。
べき乗以外を目的関数に用いた場合
ここまでの例では、目的関数として変数のべき乗の和で表される「多項式($n$ 次関数)」のみを扱ってきましたが、分数関数、三角関数、無理関数などの多項式以外の関数を目的関数に組み込むこともできます。
参考までに、それらの関数のグラフを下記のプログラムで描画します。なお、特に難しい点はないと思いますのでプログラムの説明は省略します。
- $y = \frac{1}{1 + x^2}$ (x の 2 次関数が分母にある分数関数)
- $y = sin(x)$ (三角関数の正弦関数)
- $y = \sqrt{1 - x^2}$ (円を表す $x^2+y^2 =1$ の $y \gt 0$ の部分を表す無理関数)
fig, axes = plt.subplots(1, 3, figsize=(12, 3))
ax = axes[0]
X = np.linspace(-10, 10, 100)
Y = 1 / (1 + X ** 2)
ax.set_title("y = 1 / (1 + x * x)")
ax.plot(X, Y)
ax = axes[1]
X = np.linspace(-8, 8, 100)
Y = np.sin(X)
ax.set_title("y = sin(x)")
ax.plot(X, Y)
ax = axes[2]
X = np.linspace(-1, 1, 100)
Y = np.sqrt(1 - X ** 2)
ax.set_title("y = √(1 - x * x)")
ax.plot(X, Y)
plt.tight_layout()
plt.show()
実行結果
目的関数にこのような関数を導入することで、多項式(べき乗の和)だけでは表現できない豊かな表現力を得ることができます。一方で、多項式以外の関数を導入すると、多くの場合で目的関数の最適解を求めることが一段と困難になるという問題が発生します。
従って、最適化問題のトレードオフをは、より一般的に下記のように言い換えることができます。
「目的関数の表現力を高くすると、一般的に最適解を見つけることが困難になる」
上記の表現を広げても、最適化問題のトレードオフの本質は変わりません。「適度な表現力と解きやすさを持つ、バランスの良い目的関数を設定することが重要である」という結論は、どのような関数を扱う場合でも共通する重要な視点です。
多変数の最適化問題
これまでは、アイスクリームの利益 $p$ を販売価格 $s$ という 1 変数の関数で表していましたが、現実の利益 $p$ は他のさまざまな要因にも影響されます。例えば「暑い日のほうが冷たいアイスクリームを食べたくなる」ことから、その日の「気温」がアイスクリームの売り上げに大きな影響を与えることが容易に想像できます。また、「アイスクリームは仕事中よりも休日に食べることが多い」ことから、平日よりも祝日のほうが売り上げ高くなるでしょう。このように複数の要因で利益 $p$ が変動する場合は、目的関数の変数を複数にした 多変数の最適化問題 を考える必要があります。
利益 $p$ を表す目的関数 $f$ を「販売価格」を表す $s$ に加え、気温(temperature)を表す $t$、平日(weekday)の度合いを表す $w$ の 3 つの変数を持つ $f(s, t, w)$ のように表記し、「$s$、$t$、$w$ がどのような売り上げの場合に利益 $p$ が最大化するかを求める」という多変数の最適化問題の、最適解 $s^*$、$t^*$、$w^*$ を表す式は下記のようになります。
$s^*, t^*, w^* = \operatorname{argmax}_{s, t, w} f(s, t, w)$
なお、実際に上記の式から最適解を求める際には $s$ だけでなく、変数 $t$ と $w$ の実行可能領域(変数がとりうる値の領域)を設定する必要があります。以下にその一例を示します。
- 気温 $t$:0 度以上 40 度以下を表す $[0, 40]$
- 平日であるかを表す $w$:平日の場合を 0、祝日の場合を 1 とした $\{0, 1\}$6
多変数の最適化問題では、目的関数の変数と実行可能領域の要素を、複数の値から構成される「多次元のデータ(ベクトル)」と捉えて、一つの記号で表すことが良くあります。
今回の記事の最初で示した、下記の最適化問題の定義の $x$ や $\mathcal{X}$ は、実は特定の 1 つの値とは限らず、1 つ以上の値から構成される多次元のデータを表しています。
$\forall x \in \mathcal{X}, f(x^*) \geq f(x) \text{となる} x^* \in \mathcal{X} \text{を求めよ}$
実際に、強化学習の目的である下記の式において、方策を表す $Π$ や $Π^*$ は一つの値ではなく、それぞれの「状態」においてどのような「行動」をどれくらいの確率で取るかという、大規模なデータの集まり(多次元のデータ)を表します。
$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$
このことから強化学習の本質が、大規模な多変数の最適化問題を解くことである ということがわかります。
多変数の最適化問題の解法は、一般的に 1 変数の最適化問題よりもはるかに複雑になるため、これまでに様々な手法が考案されてきました。そのうちのいくつかは強化学習のアルゴリズムにも取り入られているため、今後の記事で詳しく紹介する予定です。
また、多変数の最適化問題の場合でも、先程説明した下記の性質は変わりません。
- 目的関数の表現力を高くすると、一般的に最適解を見つけることが困難になる
- 適度な表現力と解きやすさを持つバランスの良い目的関数を設定することが重要である
微分を用いた解法(参考)
参考までにビジネスの問題において、目的関数が 3 次関数以上の場合の「微分を用いた解法」について説明します。微分がよくわからない方は以下は読み飛ばしても大丈夫です。
目的関数が 3 次関数の場合の解法
最初に、先程紹介した販売個数 $n$ と販売価格 $s$ の関係が $n = \frac{(1000 - s)^2}{1000}$ で表される場合の解法を説明します。
この場合の目的関数である利益 $p$ は下記の式で表されます。
$p = f(s) = \dfrac{(s - 100) (1000 - s)^2}{1000}$
まず、$f(s)$ を下記のプログラムでグラフ化し、その形状から $s^*$ がどのあたりにあるかを確認することにします。
N = (1000 - S) ** 2 / 1000
P = (S - 100) * N
plt.xlabel("販売価格")
plt.ylabel("利益")
plt.plot(S, P)
実行結果
上記の実行結果のグラフから $f(s)$ は $0 \le s \le 1000$ の範囲において 400 の付近で最大値を持つことが視覚的にわかります。
$f(s)$ を最大化する最適解は下記の手順で厳密に求めることができます。ただし、以下では変数 $s$ の取りうる範囲(実行可能領域)の最小値を $s_{min}$、最大値を $s_{max}$ と表記します7。
-
導関数8と導関数の方程式の解を求める:
$f(s)$ を $s$ で微分した $f'(s)$ を求め、$f'(s) = 0$ となる $s$ をすべて求める -
極大値(山の頂上)を求める:
上記で求めた $s$ の前後で $f'(s)$ の値が正から負の値に変化する場合は、その $s$ で $f(s)$ のグラフが山の頂上のような形状になる。これを極大値(その付近での最大値)と呼ぶ -
候補の中から最大値を選択する:
以下の「最大値の候補」をすべて計算し、その中で最も値が大きいものが、本当の最大値(最適解)となる- 手順 2 で求めた $f(s)$ の極大値
- 実行可能領域の左端の $f(s_{min})$。これは、グラフが左端に向かって上昇する $f'(s_{min}) \lt 0$ の場合に最大値の候補となる
- 実行可能領域の右端の $f(s_{max})$。これは、グラフが右端に向かって上昇する $f'(s_{max}) \gt 0$ の場合に最大値の候補となる
手順 3 で最大値の候補を比較する必要がある理由は、現実世界で高さの異なる山の頂上(標高の極大値)が複数存在するように、$f(s)$ にも極大値が複数存在する場合があるからです。さらに、実行可能領域の両端に向かってグラフが単調増加する場合は、極大値以外の両端の値が最大値となる可能性があります。
次に、上記の手順に従って最適解 $s^*$ 求めます。
なお、以下では下記の微分の公式を用いました。なお、$(g(x)h(x))'$ は $g(x)h(x)$ を $x$ で微分するということを意味します。また $\cdot$ は掛け算を表す記号です。
- 積の微分の公式:$(g(x)h(x))' = g'(x)h(x) + g(x)h'(x)$
- 合成関数の微分公式:$g(x)^n = n\cdot g'(x)g(x)^{n-1}$
最初に $f'(s)$ を計算します。なお、$f'(s)$ の計算は $f(s)$ を展開した下記の式に対して行うこともできますが、
$f(s) = \dfrac{s^3 -2100s^2 + 1200000s - 100000000 }{1000}$
展開する前の下記の式のまま計算を行うほうが、この後で示すように共通因数でくくり出せるため $f'(s) = 0$ を簡単に解きやすくなります。
$f(s) = \dfrac{(s - 100) (1000 - s)^2}{1000}$
上記の式から $f'(s)$ を計算すると、以下のような式になります。
$f'(s) = \dfrac{(s-100)'(1000 - s)^2 + (s - 100)((1000 - s)^2)'}{1000}$
$= \dfrac{1\cdot(1000 - s)^2 + (s - 100)\cdot 2(1000 - s)'(1000 - s)^{2-1}}{1000}$
$= \dfrac{(1000 - s)^2 - 2(s - 100)(1000 - s)}{1000}$
$= \dfrac{(1000 - s)(1000 - s - 2(s - 100))}{1000}$
$= \dfrac{(1000 - s)(-3s + 1200)}{1000}$
$-3s + 1200 = 0$ の解は $\frac{1200}{3} = 400$ なので、$f'(s) = 0$ の解は下記のようになります。
$s = 400, 1000$
$f'(s)$ は $s$ に対する 2 次関数で $s^2$ の係数は正なので、このグラフは下記のプログラムの実行結果のように青色の「下に凸の放物線」になります。なお、オレンジ色の線は $y = 0$ を表すグラフで、青色のグラフとの交点である (400, 0) と (1000, 0) が $f'(s) = 0$ となる点です。
DF = (1000 - S) * (-3 * S + 1200) / 1000
plt.xlabel("販売価格")
plt.ylabel("f'(s)")
plt.plot(S, DF)
Z = S * 0
plt.plot(S, Z, label="")
plt.legend()
実行結果
下記は $0 \le s \le 1000$ の範囲での $f'(s)$ の正負の移り変わりを表す増減表です。$f'(s)$ は $f(s)$ のグラフの $s$ での傾きを表し、正の場合は $s$ が増えると $f(s)$ が増加し、負の場合は減少することを表します。
| $s$ | 0 | ・・・ | 400 | ・・・ | 1000 |
|---|---|---|---|---|---|
| $f'(s)$ | $+$ | $+$ | 0 | $-$ | 0 |
上記の表から $0 \le s \le 1000$ の範囲では $s$ が 0 から 400 になるまでは $f(s)$ が単調増加し、400 で極大値(山の頂上)を取った後は 1000 になるまで単調減少することがわかります。従って、$s = 400$ の時に $f(s)$ が最大値をとり、最適解 $s^* = 400$ が求められました。
目的関数が 4 次以上の場合の解法
一般的に目的関数の次数が高くなると最適解を求めることが困難になりますが、先程紹介した販売個数 $n$ と販売価格 $s$ の関係が $n = \frac{(1000 - s)^i}{1000^{i-1}}$ (ただし $i$ は自然数)で表される場合は、例外的に最適解を先程と同様の方法で求めることができます。
この場合の目的関数である利益 $p$ は下記の $i + 1$ 次関数で表されます。
$p = f(s) = \dfrac{(s - 100)(1000 - s)^{i}}{1000^{i-1}}$
この目的関数 $f(s)$ に対する導関数 $f'(s)$ の計算は以下のようになります。
$f'(s) = \dfrac{(s-100)'(1000 - s)^i + (s - 100)((1000 - s)^i)'}{1000^{i-1}}$
$= \dfrac{1\cdot(1000 - s)^i + (s - 100)\cdot i(1000 - s)'(1000 - s)^{i-1}}{1000^{i-1}}$
$= \dfrac{(1000 - s)^i - i(s - 100)(1000 - s)^{i-1}}{1000^{i-1}}$
$= \dfrac{(1000 - s)^{i-1}(1000 - s - i(s - 100))}{1000^{i-1}}$
$= \dfrac{(1000 - s)^{i-1}(-(1+i)s + 1000 + 100i)}{1000^{i-1}}$
従って、$f'(s) = 0$ の解は下記のようになります。
$s = \frac{1000+100i}{i+1}, 1000$
以後はこの 2 つの解を $s_1 = \frac{1000+100i}{i+1}, s_2 = 1000$ として表記することにします。
次に、$0 \le s \le 1000$ の範囲の $f'(s)$ の正負を調べることにします。
$f'(s)$ は分子にある「$(1000 - s)^{i-1}$」と「$-(i + 1)s + 1000 + 100i$」、分母にある「${1000^{i-1}}$」の 3 つの部分から構成されています。
$f'(s)$ が 0 となる $s = s_2 = 1000$ を除く $0 \le s \lt 1000$ の範囲ではこのうちの $(1000 - s)^{i-1}$ と ${1000^{i-1}}$ は明らかに正の値となるため、残りの $-(i + 1)s + 1000 + 100i$ の正負がそのまま $f'(s)$ の正負を決めることになります。
$i + 1 \gt 0$ から $-(i + 1)s + 1000 + 100i$ の値は $s_1 = \frac{1000+100i}{i+1}$ を境に正から負の値に変化するため、$s_1$ がとりうる値の範囲がわかれば $f'(s)$ の正負の推移が求められます。
$i$ は自然数($i \gt 1$ の整数)なので明らかに $0 \lt s_1 = \frac{1000+100i}{i+1}$ となります。
また、$1000 - s_1$ を計算すると下記のように $i$ が自然数の場合は必ず正の値になります。
$1000 - \dfrac{1000+100i}{i+1} = \dfrac{1000(i + 1) - (1000+100i)}{i+1}$
$= \dfrac{900i}{i+1} \gt 0$
従って、下記の大小関係が成り立ちます。
$0 \lt s_1 \lt s_2 = 1000$
上記から $0 \le s \le 1000$ の範囲での $f'(s)$ の正負の移り変わりは、先ほどと同様の下記の増減表のようになります。
| 0 | ・・・ | $s_1$ | ・・・ | $s_2 = 1000$ |
|---|---|---|---|---|
| $+$ | $+$ | 0 | $-$ | 0 |
従って、最適解は $s* = s_1 = \frac{1000+100i}{i+1}$ であることが解析的に求められました。
実際にこの式に $i=1$(直線の関係)を代入すると $s^*=550$、$i=2$(放物線の関係) を代入すると $s^* = 400$ となり、今回の記事で求めた答えと一致することが確認できます。
なお、残念ながら一般的には目的関数が 6 次以上の関数の場合は $f'(s) = 0$ の解を解析的に求めることができないため、このように最適解を解析的に綺麗に求めることはできません。
今回の記事のまとめ
今回の記事では、最初に強化学習の用語と記号のおさらいを行いました。
その後で、最適化問題の定義と性質について説明し、以下の事を示しました。
- 強化学習は、大規模な多変数の最適化問題を解くものである
- 最適化問題には、「目的関数の表現力を高くすると、一般的に最適解を見つけることが困難になる」というトレードオフがある
- そのため、適度な表現力と解きやすさを兼ね備えた、バランスの良い目的関数を設定することが重要である
次回の記事では「マルコフ性」という概念を導入することで、強化学習の目的関数にこのようなバランスの良い性質を持たせることができる仕組みについて解説する予定です。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
次回の記事
-
$Π$ はギリシャ文字の $π$(パイ) の大文字です ↩
-
この式は状態遷移が決定論的な場合です。状態遷移が確率的な場合は若干異なる式になります ↩
-
Wikipedia の項目では最適解を $x_0$ と表記していますが、本記事では最適方策 $Π^*$ の表記に倣って最適であることを表す $*$ を用いて $x^*$ と表記することにします。また、前回の記事までは不等号として $≧$ を用いていましたが、以後は数学の分野で用いられる $\ge$ を用いることにします ↩
-
n 次関数とは、変数 $x$ の最大にべき乗が $n$ である関数の事を表します。例えば、3 次関数は $f(x) = ax^3 + bx^2 + cx + d$ のように表されます。なお、この $f(x)$ の定数項と呼ばれる $d$ は $dx^0$ に等しいので、$n$ 次関数は $x$ のべき乗の和で構成されます ↩
-
正確には「代数的な解の公式(加減乗除とべき根だけで表される公式)」が存在しないことを指します。例えば 2 次方程式 $ax^2 + bx + c = 0$ の解の公式である $\frac{-a±\sqrt{b^2-4ac}}{2a}$ のような万能な公式が、5 次以上の方程式では存在しないことが数学的に証明されています ↩
-
土曜日を祝日と区別したい場合は、土曜日を 2 とした $\{0, 1, 2\}$ とすることも考えられます ↩
-
厳密には $s$ の実行可能領域が $[s_{min}, s_{max}]$ のように最小値と最大値の間で連続している場合いる場合を想定しています。実行可能領域が $[1, 2]、[3, 4]$ のように途中で途切れている場合は、連続した領域のすべての端点(境目の点)に対する $f(s)$ の値を考慮する必要があります ↩
-
$f(x)$ を微分した $f'(x)$ のことを $f(x)$ の導関数と呼びます ↩