最近最適化問題に触れることが多くなり、基礎的な部分と気になった点で調べ、自分の理解をまとめました。
最適化とは
「何らかの目的（目標）を最もよい状態にするために、変数やパラメータの値を調整すること」を指す。
もう少し噛み砕くと「できるだけ良い答えを探す」
より詳しく数理最適化寄りに書くと「目的関数を最小化または最大化する変数やパラメータの探索」
となるかと思う。
今回は数理最適化に着目してまとめていく。
数理最適化と機械学習の違い
数理最適化
目的や制約を数式でモデル化してできるだけ良い答えを計算で求める。
- しっかりとしたルール（目的関数・制約条件）が与えられる
- 与えられたルール内で計算から最適解を探索する
機械学習
データからパターンや法則を学習し予測をする。
- 過去データからルールやパターンを導き出す
- 導いたルール、パターンから解を予測する
と一般的にはまとめることができる。が。実は綺麗に分けられるものではない。なぜならば利用する機械学習モデルの学習プロセスには数理最適化が含まれているものが存在するから。
機械学習だけど数理最適化
線形回帰
与えられた$(x_i, y_i)$に対して単回帰を想定した場合、解くべき問題は2乗誤差を最小化する問題として定義が既にできている。
$$
\min_{w, b} \frac{1}{N} \sum_{i=1}^{n} \left( y_i - (w x_i + b) \right)^2
$$
この目的関数の最適化を探索するタスクであり、これは数理最適化問題とも言える。
ニューラルネット
NNのモデルを組むときにoptimizerを設定するが、これはニューラルネットのパラメータを最適化するアルゴリズムであり数理最適化を使用している。
SDGもAdam系も過去の勾配を活用した数理最適化アルゴリズムである。
GBDT
GBDT系のモデルも損失関数としてloglossやRMSEなどを設定するがこれが目的関数にあたる。
ざっくりいうとここから出力される値が最小となるように決定木を順次構築していくアルゴリズムである。
この損失関数の勾配に沿ってモデルを修正していくため、こちらも勾配を活用した数理最適化アルゴリズムともいえる。
そのため、機械学習と数理最適化は綺麗には分割することはできないと理解。
機械学習だと言い切るものをどうにか探すなら、単純な教師なしのk近傍法みたいなものは数理最適化は使われてないと理解したけど、応用や拡張をしていくと結果最適化手法が登場していくイメージ。
機械学習の中で数理最適化が使われているんだよーと理解した方がモヤっと感がなくなる。
獲得関数
数理最適化の基礎の話の戻って獲得関数を理解したい。
評価関数とは
「ガウス過程法によって推定される期待値μと標準偏差σを用いて表現される関数」
参考：ガウス過程法によって推定される期待値μと標準偏差σを用いて表現される関数
である。
以下は代表的な目的関数。今回はEIに興味があったのでそこだけ深ぼって説明。
EI (Expected Improvement)
最大の改善値の期待値から次の候補点を選択する関数。
調べていくと最適化では「活用（既知の良い領域の深堀）」と「探索（未知の領域への開拓）」の２つの言葉を定義して語られることが多いっぽいのですが、EIはこの２つをバランスよくみているのが特徴とのこと。
$$
\begin{align*}
EI(x) =
\begin{cases}
\left( \mu(x) - f^* \right) \cdot \Phi(z) + \sigma(x) \cdot \phi(z), & \text{if } \sigma(x) > 0 \\
0, & \text{if } \sigma(x) = 0
\end{cases}
\end{align*}
$$
$$
z = \frac{\mu(x) - f^*}{\sigma(x)}
$$
$\Phi(z)$：標準正規分布の累積分布関数
$\phi(z)$：標準正規分布の確率密度関数
$f^*$: 現在の最良値
$\left( \mu(x) - f^* \right) \cdot \Phi(z)$ 項が「活用」
$\sigma(x) \cdot \phi(z)$ 項が「探索」であり、両項を加算して評価することでバランスをとっている。
$\mu(x)$と$\sigma(x)$はガウス過程法によって推定する。
ガウス過程法
ガウス課程は正規分布を定義したベイズ的なモデルで、入力を与えるとその点における「予測値（平均）」と「予測の不確かさ（標準偏差）」を返す。
具体的には
$$\mu(x) = \mathbf{k}_v^T (\mathbf{K} + \sigma_n^2 \mathbf{I})^{-1} \mathbf{y}$$
$$\sigma^2(x) = k(x, x) - k(x, X)\left[ K + \sigma_n^2 \mathbf{I} \right]^{-1} k(X, x)$$
$k$: カーネル関数（入力の類似度を測る関数）
$k_v$ :カーネル値のベクトル
$K$：既存点間の共分散行列（カーネル行列）
$k(x,x)$：自己共分散
$k(x, X)$：新規点と既存点の共分散ベクトル
$\sigma_n^2 \mathbf{I}$：ノイズ分散項
$k(X, x)$：既存点と新規点の共分散ベクトル
簡略化のため、観測ノイズを０と仮定すると以下になる。
$$\mu(x) = \mathbf{k}_v^T \mathbf{K}^{-1} \mathbf{y}$$
$$\sigma^2(x) = k(x, x) - k(x, X),\mathbf{K}^{-1} k(X, x)$$
なおカーネルは RBFと設定して以下の式で表される。
$$k(x, x') = \exp\left(-\frac{(x - x')^2}{2l^2}\right)$$
以下は具体的な計算をする例をまとめたもの。
細かい計算は実装内容をご確認ください。
【前提データ】
-
既知点（観測点）：
$x_1 = 1.0,\ y_1 = 2.3$
$x_2 = 3.0,\ y_2 = 3.1$
$x_3 = 5.0,\ y_3 = 2.7$ -
予測したい点：$x = 4.0$
-
カーネル：RBFカーネル（カーネル幅 $l = 1.0$とする）
【カーネル行列とベクトル】
-
既知点同士のカーネル行列 $\mathbf{K}$
$$
\mathbf{K} = \begin{pmatrix}
k(1,1) & k(1,3) & k(1,5) \\
k(3,1) & k(3,3) & k(3,5) \\
k(5,1) & k(5,3) & k(5,5)
\end{pmatrix}
$$ -
予測点と既知点のカーネルベクトル $\mathbf{k}_v$
$$
\mathbf{k}_v = \begin{pmatrix} k(4,1) \\ k(4,3) \\ k(4,5) \end{pmatrix}
$$
【計算手順】
- 既知点どうしと予測点とのカーネル値を計算して $\mathbf{K}$ と $\mathbf{k}_*$ を作成
- $\mathbf{K}$ の逆行列 $\mathbf{K}^{-1}$ を求める
- $\mu(x)$ の式で $\mathbf{k}_*^T \mathbf{K}^{-1} \mathbf{y}$ を計算
- $\sigma^2(x)$ の式で $k(x, x) - \mathbf{k}_v^T \mathbf{K}^{-1} \mathbf{k}_v$ を計算
- 標準偏差は $\sigma(x) = \sqrt{\sigma^2(x)}$
【コード例】
import numpy as np
# 既知のデータ
X = np.array([1.0, 3.0, 5.0])
y = np.array([2.3, 3.1, 2.7])
x_star = 4.0
l = 1.0 # RBFカーネル幅
# RBFカーネル関数
def rbf(x, x_prime, l=1.0):
return np.exp(-0.5 * ((x - x_prime) / l) ** 2)
# カーネル行列（既知点どうし）
K = np.array([[rbf(xi, xj, l) for xj in X] for xi in X])
# カーネルベクトル（予測点と既知点）
k_star = np.array([rbf(x_star, xi, l) for xi in X])
# μ(x*) の計算
mu_star = k_star.T @ np.linalg.inv(K) @ y
# σ²(x*) の計算
sigma2_star = rbf(x_star, x_star, l) - k_star.T @ np.linalg.inv(K) @ k_star
# 標準偏差 σ(x*) の計算
sigma_star = np.sqrt(sigma2_star)
print("mu(4.0) =", mu_star)
print("sigma(4.0) =", sigma_star)
# mu(4.0) = 2.9783271811659473
# sigma(4.0) = 0.5900066419765272
UCB/LCB (Upper/Lower Confidence Bound)
信頼区間の上限/下限を基準に次の候補点を選択する関数。
UCBは最大化問題、LCBは最小化問題で使用される。
式は以下のようになる：
$UCB(x) = \mu(x) + \beta \sigma(x)$
$LCB(x) = \mu(x) - \beta \sigma(x)$
EIと同様に$\mu(x)$と$\sigma(x)$はガウス過程法によって推定する。
$\beta$は探索と活用のバランスを調整するハイパーパラメータ。
$\beta$を大きくすると探索が強くなり、小さくすると活用が強くなる。
PI (Probability in Target Range)
現在の最良値より改善する確率を基準に次の候補点を選択する関数。
式は以下のようになる：
$$PI(x) = \Phi\left(\frac{\mu(x) - f^*}{\sigma(x)}\right)$$
$\Phi$は標準正規分布の累積分布関数。
現在の最良値$f^*$より改善する確率を計算し、その確率が高い点を選択する。
より保守的な探索が可能だが、局所解に陥りやすい可能性がある。
PTR (Probability in Target Range)
目標値の範囲内に入る確率を基準に次の候補点を選択する関数。
式は以下のようになる：
$$PTR(x) = \Phi\left(\frac{u - \mu(x)}{\sigma(x)}\right) - \Phi\left(\frac{l - \mu(x)}{\sigma(x)}\right)$$
$l$と$u$は目標値の下限と上限。
$\Phi$は標準正規分布の累積分布関数。
目標値の範囲内に入る確率が高い点を選択する。
特定の目標値の範囲内に収める必要がある場合に有用。
まとめ
最適化問題について資料読んで学んだことをまとめました。もう少し重みを工夫したいとかがあればどこを触れば良いか手触り感が出てきたのでまとめてよかった。
他の目的関数も興味が出てきたらもう少し具体的にまとめてみたいと思います。