自然進化戦略

自然進化戦略（NES ）は、ブラックボックス問題に対する数値最適化アルゴリズムの一種です。進化戦略と原理的には類似しており、自然勾配に従って 探索分布の（連続的な）パラメータを、より高い期待適応度へと反復的に更新します。

方法

一般的な手順は次のとおりです。パラメータ化された検索分布を使用して一連の検索ポイントが生成され、各ポイントで適合度関数が評価されます。分布のパラメータ（戦略パラメータを含む）により、アルゴリズムは適合度関数の（ローカル）構造を適応的に捉えることができます。たとえば、ガウス分布の場合、これは平均と共分散行列で構成されます。サンプルから、NES はパラメータに対する検索勾配を、より高い期待適合度に向かうものとして推定します。次に NES は自然勾配に沿って勾配上昇ステップを実行します。これは、単純な勾配とは異なり、不確実性に関して更新を再正規化する 2 次手法です。このステップは、振動、早期収束、および特定のパラメータ化から生じる望ましくない影響を防ぐため、非常に重要です。停止基準が満たされるまで、プロセス全体が繰り返されます。

NESファミリーのすべてのメンバーは、同じ原理に基づいて動作します。ただし、確率分布の種類と勾配近似法が異なります。探索空間が異なると、必要な探索分布も異なります。例えば、低次元では、共分散行列全体をモデル化することが非常に効果的です。一方、高次元では、共分散を対角線のみに制限する方がスケーラブルです。さらに、高度に多峰性の探索空間では、ガウス分布ではなくコーシー分布などの裾野の厚い分布が効果的です。最後に、自然勾配を解析的に計算できる分布と、標本から勾配を推定する必要があるより一般的な分布との間に区別があります。

検索勾配

探索分布のパラメータと、で評価された適応度関数を表すものとする。NESは、探索分布の下で期待される適応度を最大化するという目的を追求します。θ{\displaystyle \theta}π（×|θ）{\displaystyle \pi (x\,|\,\theta )}f（×）{\displaystyle f(x)}×{\displaystyle x}

J（θ）＝Eθ⁡[f（×）]＝∫f（×）π（×|θ）d×{\displaystyle J(\theta )=\operatorname {E} _{\theta }[f(x)]=\int f(x)\;\pi (x\,|\,\theta )\;dx}

勾配上昇法によって、勾配は次のように書き直すことができる。

∇θJ（θ）＝∇θ∫f（×）π（×|θ）d×{\displaystyle \nabla_{\theta}J(\theta)=\nabla_{\theta}\int f(x)\;\pi (x\,|\,\theta)\;dx}
＝∫f（×）∇θπ（×|θ）d×{\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;dx}
＝∫f（×）∇θπ（×|θ）π（×|θ）π（×|θ）d×{\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;{\frac {\pi (x\,|\,\theta )}{\pi (x\,|\,\theta )}}\;dx}
＝∫[f（×）∇θログ⁡π（×|θ）]π（×|θ）d×{\displaystyle =\int {\Big [}f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta ){\Big ]}\;\pi (x\,|\,\theta )\;dx}
=Eθ⁡[f(x)∇θlog⁡π(x|θ)]{\displaystyle =\operatorname {E} _{\theta }\left[f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta )\right]}

つまり、の期待値に における対数微分を掛けたものである。実際には、有限個のサンプル に基づくモンテカルロ近似を使用することができる。f(x){\displaystyle f(x)}x{\displaystyle x}λ{\displaystyle \lambda }

∇θJ(θ)≈1λ∑k=1λf(xk)∇θlog⁡π(xk|θ){\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }f(x_{k})\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )}。

最後に、探索分布のパラメータは反復的に更新することができる。

θ←θ+η∇θJ(θ){\displaystyle \theta \leftarrow \theta +\eta \nabla _{\theta }J(\theta )}

自然勾配上昇

NES は更新に単純な確率的勾配を使用する代わりに、単純な (バニラ) 勾配に比べて多くの利点があることがわかっている自然勾配に従います。たとえば、

  • 勾配方向は探索分布のパラメータ化とは無関係である
  • 更新の規模は不確実性に基づいて自動的に調整され、高原と尾根での収束が加速されます。

NESのアップデートは

θ←θ+ηF−1∇θJ(θ){\displaystyle \theta \leftarrow \theta +\eta \mathbf {F} ^{-1}\nabla _{\theta }J(\theta )}、

ここではフィッシャー情報行列です。フィッシャー行列は正確に計算できる場合もありますが、そうでない場合は対数微分を再利用してサンプルから推定されます。 F{\displaystyle \mathbf {F} }∇θlog⁡π(x|θ){\displaystyle \nabla _{\theta }\log \pi (x|\theta )}

フィットネスシェイプ

NESは、アルゴリズムをより堅牢にし、適応度関数の単調増加変換に対して不変にするために、ランクベースの適応度シェーピングを利用しています。この目的のために、集団の適応度は効用値 の集合に変換されます。i番目に優れた個体を とします。適応度を効用で置き換えると、勾配推定値は次のようになります。 u1≥⋯≥uλ{\displaystyle u_{1}\geq \dots \geq u_{\lambda }}xi{\displaystyle x_{i}}

∇θJ(θ)=∑k=1λuk∇θlog⁡π(xk|θ){\displaystyle \nabla _{\theta }J(\theta )=\sum _{k=1}^{\lambda }u_{k}\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )}。

効用関数の選択はアルゴリズムの自由なパラメータです。

擬似コード

入力:f,θinit{\displaystyle f,\;\;\theta _{init}} 1 回繰り返し 2 for dok=1…λ{\displaystyle k=1\ldots \lambda } // λは母集団の大きさ 3つの サンプルxk∼π(⋅|θ){\displaystyle x_{k}\sim \pi (\cdot |\theta )} 4 適応度を評価するf(xk){\displaystyle f(x_{k})} 5 対数微分を計算する∇θlog⁡π(xk|θ){\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )} 6 終わり 7 ユーティリティをuk{\displaystyle u_{k}}ランクに基づいて割り当てる 8 勾配を推定する∇θJ←1λ∑k=1λuk⋅∇θlog⁡π(xk|θ){\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )} 9 推定するF←1λ∑k=1λ∇θlog⁡π(xk|θ)∇θlog⁡π(xk|θ)⊤{\displaystyle \mathbf {F} \leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k}|\theta )\nabla _{\theta }\log \pi (x_{k}|\theta )^{\top }}// または正確に計算する 10 更新パラメータθ←θ+η⋅F−1∇θJ{\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}// ηは学習率 停止基準が満たされる まで 11

参照

参考文献

「 https://en.wikipedia.org/w/index.php?title=Natural_evolution_strategy&oldid=1326470091」より取得