固有値分解と白色化 — 知識ノート

共分散行列 $C$ を実際に使うには、固有値分解しておく必要がある。

C = B D^{2} B^{⊤}

使い道 1 — 候補の生成#

標準正規から引いた $z \sim 𝒩 (0, I)$ を変換すれば、目的の分布から引いたことになる。

y = B D z ⟹ y \sim 𝒩 (0, C)

$D$ で各軸方向に伸ばし、 $B$ で回す、という順序。

逆向きの変換が行列の逆平方根。

C^{- 1 / 2} = B D^{- 1} B^{⊤}

これを掛けると、分布が球状に戻る（白色化）。ステップサイズ適応で $p_{σ}$ をこの空間で測るのは、分布が細長いせいで長さの判定が歪むのを避けるため。球に戻してから測れば、「でたらめなら長さはこれくらい」という基準がそのまま使える。

固有値分解は $𝒪 (n^{3})$ かかる。毎世代やると、次元が上がったときにここが支配的になる。

実装では $𝒪 (n^{2})$ 世代に 1 回だけ分解を行い、その間は前回の $B, D$ を使い回す。 $C$ の学習率が小さく、 1 世代での変化がわずかであることを利用した近似で、 Hansen らの 2003 年の論文が計算量をこの形に落とした。

数値的な注意
$C$ は理論上は対称正定値だが、浮動小数点の丸め誤差で対称性が崩れることがある。実装では上三角だけを保持して明示的に対称化するのが定石。

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
Nikolaus Hansen, Sibylle D. Müller, Petros Koumoutsakos. Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation 11(1), 2003. https://doi.org/10.1162/106365603321828970