共分散行列適応

CMA-ES の名前の由来であり、中心的な仕掛け。 うまくいった動きの方向へ、分布を広げる。

2 種類の更新を足す#

$C$ の更新は性質の異なる 2 つの項からなる。

$$C\leftarrow (1-c_1-c_{\mu })C+c_1\underset{\text{rank-one}}{\underbrace{p_c{p}_c^{\top }}}+c_{\mu }\underset{\text{rank-}\mu }{\underbrace{\sum _{i=1}^{\mu }{w}_i{y}_{i:\lambda }{y}_{i:\lambda }^{\top }}}$$

rank-one 更新 は進化パス $p_c$ の外積を足す。 $p_c$ は世代をまたいだ移動方向の蓄積なので、 「何世代も同じ向きに進んでいる」という情報が反映される。 1 世代分の情報だけでは見えない長期的な傾向を捉える役割。

rank-$\mu$ 更新 は今世代の上位個体の方向を足す。 $\lambda$ が大きいときに情報を無駄なく使える。1 世代の情報だけなので反応は速い。

なぜ外積なのか#

$y{y}^{\top }$ は $y$ 方向に伸びた半正定値行列。 これを足すと、その方向の分散が大きくなる。 つまり「この向きは当たりだったから、次はこの向きを広めに探そう」を そのまま行列演算にしている。

学習率 $c_1,c_{\mu }$ は次元 $n$ から自動的に決まり、 $c_1+c_{\mu }<1$ を満たすので $C$ は正定値のまま保たれる。

何を学んでいるのか#

十分に世代を重ねると、$C$ は目的関数の ヘッセ行列の逆行列に比例する形へ近づくことが 知られている。つまり CMA-ES は二階の情報を、微分せずに標本から推定している。 準 Newton 法が勾配の履歴から ヘッセ行列を近似するのと、目的が対応している。

参考文献#

• Nikolaus Hansen. The CMA Evolution Strategy: A Tutorial. 2016.（実装まで踏み込んだ標準的な解説） https://arxiv.org/abs/1604.00772
• Nikolaus Hansen, Andreas Ostermeier. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9(2), 2001.（CMA-ES の原論文） https://doi.org/10.1162/106365601750190398
• CMA-ES 公式サイトと参照実装 pycma https://github.com/CMA-ES/pycma