ニュートン法とCMA-ES

Posted at 2025-01-14

ニュートン法

目的関数 $f: \mathbb{R}^n \to \mathbb{R}$ の最小化問題において：

f(x + \Delta x) \approx f(x) + \nabla f(x)^T \Delta x + \frac{1}{2} \Delta x^T \nabla^2 f(x) \Delta x

ニュートン法の更新式：

dx = -[\nabla^2 f(x)]^{-1} \nabla f(x)

ニュートン法の二次近似は、ガウス分布の負の対数尤度関数として解釈できます。目的関数を以下のように変換することで、確率分布との対応関係が明らかになります：

p(x) \propto \exp\left(-f(x)\right) \approx \exp\left(-f(x^*) - \frac{1}{2}(x - x^*)^T \nabla^2 f(x^*) (x - x^*)\right)

これは多変量ガウス分布の形式と一致します：

p(x) \propto \exp\left(-\frac{1}{2}(x - \mu)^T \Sigma^{-1} (x - \mu)\right)

CMA-ES (Covariance Matrix Adaptation Evolution Strategy) は、多変量正規分布を用いたブラックボックス最適化アルゴリズムです：

x_{k+1} \sim \mathcal{N}(\mu_k, \sigma_k^2 C_k)

ここで：

CMA-ESは以下の主要なステップで構成されています：

x_i \sim \mathcal{N}(\mu_k, \sigma_k^2 C_k), \quad i = 1,\ldots,\lambda

選択と重み付け: サンプルを評価値で順位付けし、上位 μ 個を選択
- 各選択個体に重み $w_i$ を割り当て（通常 $\sum w_i = 1$）
- より良い解に大きな重みを付与
平均の更新: 選択された個体の重み付き平均を計算

\mu_{k+1} = \sum_{i=1}^{\mu} w_i x_{i:\lambda}

p_{c,k+1} = (1-c_c)p_{c,k} + \sqrt{c_c(2-c_c)} \sqrt{\mu_w} \frac{\mu_{k+1}-\mu_k}{\sigma_k}

C_{k+1} = (1-c_1-c_μ)C_k + c_1p_{c,k+1}p_{c,k+1}^T + c_μ\sum_{i=1}^{\mu} w_i y_i y_i^T

\sigma_{k+1} = \sigma_k \exp\left(\frac{c_σ}{d_σ}\left(\frac{\|p_σ\|}{E\|\mathcal{N}(0,I)\|} - 1\right)\right)

CMA-ESの共分散行列 $C_k$ は、目的関数の局所的な形状（ヘッセ行列の逆行列に相当）を学習します：

C_k \approx [\nabla^2 f(x)]^{-1}

この関係は以下の特徴を持ちます：

両手法とも、最適化の方向は二次情報によって決定されます：

両手法は、情報幾何学の観点から深い関連性を持っています。

目的関数の確率的解釈において、エントロピーは重要な役割を果たします：

H[p] = -\int p(x) \log p(x) dx

ガウス分布の場合、エントロピーは以下のように表されます：

H[\mathcal{N}(\mu, \Sigma)] = \frac{n}{2}(1 + \log(2\pi)) + \frac{1}{2}\log|\Sigma|

この関係は、最適化における探索空間の不確実性を定量化します。

フィッシャー情報行列は、確率分布の曲率を表現し、以下のように定義されます：

\mathcal{I}(\theta) = \mathbb{E}_{p(x|\theta)}\left[\nabla_\theta \log p(x|\theta) \nabla_\theta \log p(x|\theta)^T\right]

ガウス分布の場合、フィッシャー情報行列は以下の形式になります：

\mathcal{I}(\mu, \Sigma) = \begin{bmatrix}
\Sigma^{-1} & 0 \\
0 & \frac{1}{2}D^TD
\end{bmatrix}

ここで、$D$ は共分散行列の要素に関する微分を表す行列です。

自然勾配法は、パラメータ空間のリーマン計量としてフィッシャー情報行列を用います：

\theta_{t+1} = \theta_t - \eta \mathcal{I}(\theta_t)^{-1} \nabla_\theta L(\theta_t)

これは以下の点でニュートン法とCMA-ESに関連します：

ニュートン法との関係:

dx = -[\nabla^2 f(x)]^{-1} \nabla f(x) \approx -\mathcal{I}(x)^{-1} \nabla f(x)

CMA-ESとの関係:

\Delta \mu \propto -C^{-1} \nabla_\mu \mathbb{E}[f(x)]