MLエンジニアへの道 #72 - NEAT

MLNE

Last Edited: 12/11/2025

このブログ記事では、ニューロエボリューションにおけるNEATについて紹介します。

ML

前回の記事では、Schaffer関数やRastrigin関数のグローバル最大値の探索の文脈で、 GA、ES、CMA-ES、OpenAI-ES、およびその他の関連する進化的アルゴリズムについて取り上げました。 これらの議論を踏まえ、本記事では、ニューラルネットワークの進化におけるこれらのアルゴリズムの応用について論じます。

トポロジー固定ニューロエボリューション

ニューラルネットワークにEAを適用する最もシンプルなアプローチは、ネットワークのトポロジー(接続形態)を固定し、重みの最適化に焦点を当てることです。 ネットワークの重みを実数値ベクトルとして直接符号化することで、Schaffer関数やRastrigin関数に対して行ったように、 これまで議論してきたCMA-ESやOpenAI-ESなどの任意のEAを利用することができます。適応度は結果として得られるネットワークを実行し、 目的関数や報酬を測定することで計算できます。実際に、我々が活用する予定のJAXベースのニューロエボリューションツールキットであるEvoJAXは、 様々な教師あり学習、制御、その他の新規タスクに対するトポロジー固定ニューロエボリューションにおいて、 CMA-ESやOpenAI-ESなどのEAを含む様々な最適化アルゴリズムの実装を提供しています。 (EvoJAXを用いてさまざまな実験を行なってみることを強くお勧めします。)

トポロジー固定ニューロエボリューションは一部のタスクにおいて堅牢な性能を達成したと報告されていますが (後のセクションでいくつかの結果について議論します)、理想的には、ネットワークトポロジーを含む他のハイパーパラメータも最適化し、 トポロジーと重みが進化するANN(Topology and weight evolving ANN, TWEANN)を得たいです。 これらは革新的でコンパクトなアーキテクチャを生成し、必要な計算量を削減し、さらに堅牢な性能を達成する可能性があります。 しかし、トポロジーを実数値ベクトルで表現してTWEANNにESを適用することは直感的ではなく、 TWEANNには他にも進化的アルゴリズムを単純に適用することを妨げる独特な課題があります。

TWEANNの課題

TWEANNの最初の独特な課題は、ニューラルネットワークの順列不変性です。これは、機能的に同一の2つのネットワークが、 (隠れノード(A、B、C)を持つネットワークが(C、B、A)でも表現できるように)異なる順序で表現できることです。 これは同じネットワークの重複評価につながるだけでなく、多様な探索にとって重要な変分演算子であるネットワークの交叉を潜在的に破綻させます ((A、B、C)と(C、B、A)の間の交叉は、機能を保持するために理想的には(A、B、C)または(C、B、A)に限定されるべきですが、 (A、B、A)や(C、B、C)になる可能性があります)。

TWEANNの2つ目の独特な課題は、ニューラルネットワークに新しい構造を追加することが初期段階では性能を悪化させることが多く、 複雑性が追加された新しいネットワークが、これまでを生き抜いてきたより単純なネットワークに支配されることです。 これにより新しい構造的革新が失われ、探索空間が大幅に制限されます。最後に、初期集団でランダムに生成された大きなネットワークを使用すると、 初期探索次元が爆発的に増加し、タスクによっては不必要に大きなネットワークを生み出す可能性があります。 したがって、TWEANNの実現を成功させるためには、競合する符号化を処理し、新しい構造的突然変異を保護し、 最小解から段階的に複雑性を増加させることができるメカニズムが必要です。

NEAT

Neuroevolution of Augmenting Topologies (NEAT)は、ニューラルネットワークの重みとトポロジーの両方を適切に進化させることのできる遺伝的アルゴリズムとして注目を集めました。 NEATは、履歴マーキングを用いた遺伝子表現、類似トポロジーの種分化、および段階的複雑化のアプローチにより、上述の課題に対処しています。 NEATは、ノード遺伝子オブジェクトのリスト(ノードIDと、オプションでバイアスと活性化関数により属性付けされる)と、 接続遺伝子オブジェクトのリスト(イノベーション番号、ソースとターゲットのノードID、重み、および接続が有効かどうかにより属性付けされる) を用いてニューラルネットワークを符号化し、これは隣接リストに対応します。ここで、遺伝子の歴史的起源を追跡するために、 新しく変異した各接続遺伝子に一意のイノベーション番号を割り当てます。これにより、高価なマッチングアルゴリズムを使用することなく、 接続遺伝子をマッチングする適切な交叉が可能になります。

NEAT representations

イノベーション番号を使用して同じ歴史的起源を共有する接続遺伝子の適切なマッチングは、ゲノム間の構造的差異の簡単な計算も可能にし、 これを用いてゲノムを種にグループ化し、新しい構造的革新を保護することができます。NEATは具体的に、 非連結および余剰接続遺伝子の数DDとEE(ゲノムペアの一方にのみ現れる接続遺伝子)と、 マッチングする接続遺伝子の平均重み距離Wˉ\bar{W}を使用して、ゲノム距離δ=(c1/N)E+(c2/N)D+c3Wˉ\delta=(c_1/N) E + (c_2/N) D + c_3\bar{W} (ここでcic_iはハイパーパラメータ)を計算し、指定された閾値δt\delta_t内のゲノムを同じ種にグループ化します。 またNEATは、種内で適応度を正規化する明示的適応度共有を使用し、ある種が集団全体を支配することを防ぐことで、新しい種をさらに保護します。

NEAT Cartpole

種分化が新しい構造的革新を保護するため、NEATは最小限の構造を持つネットワークからネットワークのトポロジーの進化を問題なく開始することができます。 NEATは、リンクを追加する(新しい接続遺伝子を追加する)か、ランダムに選択された接続の間にニューロンを追加する(選択された接続を無効化し、 新しいノード遺伝子を追加し、以前のソースとターゲットノードを新しいノードに接続する新しい接続遺伝子を追加する) 構造的変異を使用して、最小限の構造を持つネットワークを段階的に複雑化します。最小限の構造を持つネットワークから始まる進化は、 効果的な活用とより高速な最適化、そしてコンパクトで高性能なネットワークの発見につながる可能性があります。

他のニューロエボリューションアルゴリズムと同様に、NEATも、ニューラルネットワークの幅と深度を固定化することで、 個体の適応度計算が並列化可能になるように実装することができます(ただし、これは進化するネットワークのサイズを制限します)。 スキップ接続は、恒等重みとゼロバイアスを用いて、すべての前の層の活性化を保持することで実現可能です。 簡単な実験として、この方法でNEATを実装し、EvoJAXで簡単なCart Poleタスクで1000個のネットワークを進化させました。 ここで、個体の適応度は10回のランダムに初期化されたゲーム(1000タイムステップ)の報酬の平均により計算されます。 (すべてのゲームはベクトル化により並列化されました。今回の実装をここで開示することはできませんので、 ご自身で実装を試してみることを強くお勧めします。)

ここで、NEATはハイパーパラメータの微調整なしに、ポールを中央で常にバランスさせることができるコンパクトなネットワークを見つけることに成功しました (100回のランダムに初期化されたテストゲームにおいて、3000タイムステップで最小2834.66、平均2882.02、標準偏差15.79のスコアを記録しました)。 Stanley, O. K. & Miikkulainen, R. (2002)による原論文も、簡単なXOR分類(教師ありタスク)と段階的により困難なダブルポールバランシングタスク(制御タスク)において、 NEATの他のアルゴリズムよりも比較的高い探索効率性とコンパクトなネットワークの性能を確認しています。 また、NEATにおける交叉、種分化、および最小限のネットワークからの進化の重要性は、これらの各コンポーネントを除去した後の性能低下が観察された、 原論文のアブレーション研究によって確認されています。さらに、NEATは構造的変異の影響を解釈できる進化の履歴を残すため、 様々な潜在的応用において魅力的です。

深層ニューロエボリューション

NEATを含むニューロエボリューションの多くの焦点は浅いニューラルネットワークの進化にありましたが、 深層ニューラルネットワークにもニューロエボリューションを適用することができ、現代の計算資源を使用することで良好かつ高速な結果を得ることができます。 例えば、Ho, S. & Chen, X. et al.(2017)の研究では、OpenAI-ESを数千のワーカーに並列化することで、 3D人型歩行のような複雑な連続制御タスクで10分で良い性能を達成し、Atariゲームでは1時間以内で競争力のある結果を得ました。 また、Such, P. & Madhavan, C. et al.(2017)の研究では、切り捨て選択とエリート主義を用いた単純なGAが、 400万以上のパラメータを持つニューラルネットワークをピクセルのみからAtariゲームをプレイするように訓練する際に、 ESやRL手法(DQN、A3C等)と同等な結果を達成し、より長いゲームでは他のアプローチを上回る性能を示しました。

後者の例では、GAに完敗したランダム検索の変種が、テストされたいくつかのゲームでDQNやA3Cを上回ることも発見されました。 これは、ノイズが多く、遅延があり、疎な報酬構造を伴うタスクにおいて勾配に従うことの欠点と、 そのようなタスクにおける(深層)ニューロエボリューションの堅牢性をさらに示唆しています。このような堅牢性に加えて、 ニューロエボリューションは潜在的に解釈可能な進化履歴を提供し、(高度に分散した埋め込みで動作しデータセットに過適合するネットワークではなく) 説明可能で正則化されたネットワークを生成する傾向があります。さらに、前述のEvoJAXやNEATで実証されたように、 ニューロエボリューションにおける集団内の個体の適応度計算は、ベクトル化により容易に並列化でき、一部の従来のRL算法とは異なり、 TPU/GPUを自然に活用することができます。したがって、ニューロエボリューションとその他の技術や計算資源との相乗効果に関する研究は強く推奨され、 様々な領域で継続的に行われています。

結論

本記事では、トポロジー固定ニューロエボリューションとTWEANNsの固有の課題について簡潔に議論し、主にその遺伝子表現によって固有の課題に対処するNEATを紹介しました。 また、いくつかのタスクにおける深層ニューロエボリューションの結果と、ニューロエボリューションのさらなる研究を動機づける利点についても議論しました。 繰り返し述べたように、より詳細な情報については以下に引用されたリソースを確認し、ニューロアルゴリズムを自分で実装してみることを強くお勧めします。

リソース

TOPに戻る↑