ニュートン法とCMA-ES

# ニュートン法
目的関数 $f: \mathbb{R}^n \to \mathbb{R}$ の最小化問題において：

```math
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
```

ニュートン法の更新式：
```math
dx = -[\nabla^2 f(x)]^{-1} \nabla f(x)
```

## 1. 確率的解釈とガウス分布

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

```math
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)
```

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

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


## 2. CMA-ESの基本概念

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

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

ここで：
- $\mu_k$ は分布の平均
- $\sigma_k^2$ はステップサイズ
- $C_k$ は共分散行列

### 2.1 アルゴリズムの基本ステップ

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

1. **サンプリング**: 現在の分布から λ 個の個体をサンプリング
```math
x_i \sim \mathcal{N}(\mu_k, \sigma_k^2 C_k), \quad i = 1,\ldots,\lambda
```

2. **選択と重み付け**: サンプルを評価値で順位付けし、上位 μ 個を選択
   - 各選択個体に重み $w_i$ を割り当て（通常 $\sum w_i = 1$）
   - より良い解に大きな重みを付与

3. **平均の更新**: 選択された個体の重み付き平均を計算
```math
\mu_{k+1} = \sum_{i=1}^{\mu} w_i x_{i:\lambda}
```

4. **進化経路の更新**: 累積的な移動方向を追跡
```math
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}
```

5. **共分散行列の更新**: 
```math
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
```

6. **ステップサイズの更新**: σ-進化経路を用いて適応
```math
\sigma_{k+1} = \sigma_k \exp\left(\frac{c_σ}{d_σ}\left(\frac{\|p_σ\|}{E\|\mathcal{N}(0,I)\|} - 1\right)\right)
```

### 2.2 主要なパラメータ

- λ: 各世代での個体数（通常 4+⌊3ln(n)⌋）
- μ: 選択される親の数（通常 λ/2）
- $c_c$: 進化経路の更新率
- $c_1$: ランク1更新の学習率
- $c_μ$: ランクμ更新の学習率
- $c_σ$: ステップサイズの更新率

### 2.3 アルゴリズムの特徴

1. **適応的な探索**: 問題の構造に応じて探索分布を自動調整
2. **スケール不変性**: パラメータのスケールに対して頑健
3. **回転不変性**: 座標系の選択に依存しない
4. **並列化可能**: λ個の評価は並列実行可能

## 3. ニュートン法とCMA-ESの関係性

### 3.1 共分散行列の適応

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

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

この関係は以下の特徴を持ちます：
- ニュートン法：ヘッセ行列を直接計算
- CMA-ES：共分散行列を進化的に学習

### 3.2 更新方向の決定

両手法とも、最適化の方向は二次情報によって決定されます：
- ニュートン法：$dx = -[\nabla^2 f(x)]^{-1} \nabla f(x)$
- CMA-ES：$dx \sim \mathcal{N}(0, C_k)$


## 4. 情報幾何学的な解釈

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

### 4.1 エントロピーと最適化

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

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

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

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

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

### 4.2 フィッシャー情報行列との関係

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

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

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

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

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

### 4.3 自然勾配法との関連

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

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

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

1. **ニュートン法との関係**:
   ```math
   dx = -[\nabla^2 f(x)]^{-1} \nabla f(x) \approx -\mathcal{I}(x)^{-1} \nabla f(x)
   ```
   
2. **CMA-ESとの関係**:
   ```math
   \Delta \mu \propto -C^{-1} \nabla_\mu \mathbb{E}[f(x)]
   ```