1. はじめに

この記事では、Conpositional Pattern Producing Network (CPPN)について解説していきます。CPPNはニューラルネットワーク (NN)の一種で、NeuroEvolution of Augumented Topologies (NEAT) という、進化計算に基づくアルゴリズムにより最適化され、画像生成やロボットデザインなどを得意としています。また、CPPNを用いてニューラルネットワークを生成するHyperNEATという手法も知られています。
本記事では、CPPN、NEAT、HyperNEATを解説し、その応用についても紹介できたらと思います。

2. NEATアルゴリズム

2.1. 遺伝的アルゴリズム

現在のNNは、誤差逆伝播によって最適化されることがほとんどです。一方のNEATアルゴリズムでは、遺伝的アルゴリズムによってNNを最適化させていきます。遺伝的アルゴリズムは、生物の進化を応用した最適化アルゴリズムです。遺伝的アルゴリズムの日本語の説明は以下を参照してください。

一般に、進化によってNNを最適化させる試みはNeuroEvolutionと呼ばれます。誤差逆伝播はNNの重み調整に対しては確かに有力ですが、NNの構造は経験則や試行錯誤に基づいて人手によって設計することがほとんどです。NeuroEvolutionには、NNの重みのみならず、構造をも最適化することができる点や、そもそも勾配が定義できない最適化問題を解く際に有用となります。

2.2. NNのエンコード

実際の生物は、自らの設計図はゲノムに書き込まれており、集団内の生物が自らのゲノムを変化させたり掛け合わせたりすることで進化をしていきます。NEATでも、NNの構造はゲノムとしてエンコードされ、集団内の複数のNNのゲノムを掛け合わせることでNNを最適化させていきます。ゲノム (genome) とは遺伝子 (gene) の集まりのことであり、NNをエンコードするゲノムも複数の遺伝子からなります。

上の図はその一例です。ゲノムはNNのノード遺伝子 (の集合) であるNode Genesと、コネクション遺伝子 (の集合) であるConnection Genesとからなります。

2.2.1 Node Genes

図の例では、Node Genesは5つの遺伝子からなります。それぞれの遺伝子はノードに対応しており、番号と種類を保持しています。種類にはSensor (入力ノード) 、Hidden (隠れノード) 、Output (出力ノード) があります。進化による最適化を経て遺伝子の数は増減しますが、通常NNでは入出力のノード数が増減することはないので、Sensor属性およびOutput属性を持つ遺伝子の増減はありません。Hidden属性を持つ遺伝子のみが増減を繰り返すこととなります。

2.2.2. Connection Genes

図の例では、Connection Genesは7つの遺伝子からなります。それぞれの遺伝子はノード間をつなぐ有向エッジに対応しており、入力ノード番号と出力ノード番号、エッジの重みといった情報を保持しています。そのほかにも有効ビット (Enabled / Disabled) 、Inovation番号といった情報も遺伝子に含まれます。有効ビットはその遺伝子が発動するかを決めるbool値であり、Enabledならその遺伝子に対応するエッジをNNに追加し、Disabledならしません。有効ビットの必要性とInnovation番号はのちに説明します。

2.3. 突然変異

実際の生物は、遺伝子が突然変異することで新たな形質を獲得します。その形質が生存に有利であるか不利であるかは偶然に左右されますが、生存に有利な変異を経た個体は生き残り、その変異は生殖によりまた次の個体へと引き継がれます。
NEATアルゴリズムでも、NNは変異によって変化します。変異は「コネクション付加変異」・「ノード付加変異」・「エッジ重みの変異」に大別することができます。また、一般的なneatの実装 (https://github.com/CodeReclaimers/neat-python) ではノード・コネクションが消失する変異も存在します。基本的に、進化が進むにつれてNNの構造はより長大に、より複雑になっていきます。
下の図の上部はコネクション付加変異に、下部はノード付加変異に対応しています。

2.3.1. コネクション付加変異

コネクション付加変異では、ノード間のコネクションを表す遺伝子がランダムに付加されます。図の例ではノード3からノード5に向かうエッジが追加されていて、その重みはランダムに決定されます。
新たなコネクションには7という番号が付けられています。この番号をinnovation numberといい、この番号を交叉の際に利用します。Innovation numberは集団内で共有されます。つまり、あるNNで付加されたコネクションに7というinnovation numberがつけられたなら、次に付加されるコネクションにつけられるinnovation numberは8となります。たとえそのコネクションが別のNNであっても。つまり、innovation nubmerはNN各々で1,2,3...とカウントしていくのではなく、集団全体で1,2,3,...とカウントしていくのです。

2.3.2. ノード付加変異

ノード付加変異では、ノード3とノード4の間に新たにノード6が付加されています。この時、元々ノード3とノード4の間にあったコネクションはDisabledになり、新たにノード3とノード6間、そしてノード6とノード4間にコネクションが追加されます。このとき、ノード3とノード6間の重みは1.0に、ノード6とノード4間の重みはノード3とノード4の間の重みと同じなります。これにより、NNの働きを変えないままノードを付加することが可能になります。

新たに付加されたノードの番号も、innovation numberと同じように集団全体で共有します。

2.3.3. エッジ重みの変化をもたらす変異

論文では詳しく述べられていませんが、「他のNeuroEvolutionアルゴリズムと同じように変化する」そうです。実装 (https://github.com/CodeReclaimers/neat-python) ではガウス分布に従って生成された値を重みに加えるか、それよりも低い確率で重みが完全に書き換えられるという変異が起きています。

2.4. 交叉

生物は個体同士で遺伝子を掛け合わせることで、多様な遺伝子を持つ新たな個体を複製することができます。NEATでも、異なるNNのゲノムを掛け合わせ、新たなNNを生成します。交叉では、innovation numberが威力を発揮します。

2.4.1. How to 交叉

交叉の例を下の図に示します。

この例では、parent1のconnection genesと、parent2のconnection genesを掛け合わせて、offspringのconnection genesを生成しています。

交叉では、まず両親の遺伝子をマッチングします。このとき、「同じinnovation number」をもつ遺伝子同士がマッチングし、「同じinnovation number」を持つ遺伝子が相方にない遺伝子は余り (図中でdisjointまたはexcessと表記) となります。

マッチングが済んだなら、各遺伝子は、両親から子供に引き継がれます。この継承は、

マッチング相手のいる遺伝子はランダムに選択された親から引き継がれる
マッチング相手のいない遺伝子は、より優秀な親から直接引き継がれる

という操作により行われます。

注：個体の「優秀さ」は、損失で評価されることが多いです。訓練用のデータに対するNNの損失に-1をかけたものを個体の「優秀さ」の指標とします。この値は遺伝的アルゴリズムの文脈では「適合度」と呼ばれます

2.4.2. innovation numberの役割

innovation numberは、個体間の遺伝子のマッチングに使われました。そもそもinnovation numberは、集団内で新たに誕生したコネクションへ順々に割り振られる通し番号でした。つまり、innovation numberは「そのコネクションがいつ誕生したのか」を意味することとなります。このような意味からinnovation numberの割り振りはhistorical markingと呼ばれます。

innovation numberの一致・不一致を確かめるだけで、計算量の多いNNの構造解析を行うことなく、異なるNN間のコネクションの対応関係を確かめることができる点に、innovation numberの強力さがあります。

2.5. 種分化 (Speciation)

2.5.1. アルゴリズムの問題点

以上を踏まえた上で、NEATアルゴリズムのフローチャートを説明できます。

集団において複数のゲノムを初期化する
集団内のゲノムを読み取り、NNを構成する
NNに訓練データを与え、より良い成績を残したものほど高い適合度を付与する
高い適合度を獲得したゲノムは生き残り、そうでないゲノムは死滅する
生き残ったゲノムに突然変異・交叉を施す
2.に戻る

しかしこのアルゴリズムにはある問題点があります。それは、構造の変化したNNは、その世代の他の個体に比べて適合度が下がりやすく死滅しやすいために、ある程度進化が進むと構造のイノベーションが起こらなくなり、局所最適化に陥ってしまうという点です。

2.5.2. 種分化

NEATでは、局所最適解への停滞は、種分化という方法を用いることで回避されています。生物学的な文脈における種分化とは、「ある1つの種が、生殖を障壁とした異なる複数の種に分化していくこと」を指します。分化により生じた複数の種は、それぞれ異なる生活環境への棲み分けなどが起こることがあり、種の間ではなく種の中で自然選択や生殖が行われるようになっていきます。

NEATでは、NNも種分化を起こしていきます。つまり、似たような構造を持つNN同士は同じ種に、かけ離れた構造を持つNNとは別の種に分類して、それぞれの種の中で自然選択や交叉・突然変異を起こすことで、構造のイノベーションが担保される仕組みとなっているのです。

2.6. NEATアルゴリズムまとめ

以上を踏まえて、NEATアルゴリズムの流れは以下のように図示されます。

3. CPPN

CPPNはNNに分類されます。NNでは通常、活性化関数にtanh関数やSigmoind関数などが用いられ、NN構造もノードがいくつかの層に分かれていることがほとんどです。しかしCPPNでは、活性化関数にガウス関数や一次関数、三角関数などの周期関数が用いられており、ノードも層に分かれておらず、その接続にも規則性がありません。
CPPNの一例を下の図に示します。

CPPNは、何らかの適合度を用意してNEATアルゴリズムにより最適化させることで、より複雑で最適なNN構造を獲得することができます。

3.1. CPPNの応用

3.1.1. 画像生成

この画像はCPPNの作り出した画像です。CPPNに、画像上の座標を与えて、CPPNの出力をその座標で指定される位置の画素値とみなすことにより生成しています。
このように、CPPNは「規則性のある幾何学パターンを作り出す」ことが得意なのです。

3.1.2. ソフトロボットの設計への応用

CPPNは、ソフトロボットという、実際の生物を模して柔らかい素材で構成されるロボットの構造デザインの生成で強みを発揮しています。以下の動画を見てください。

この動画では、筋肉や骨などの役割を担う、4種類の柔らかい立方体を組み合わせて構成されるロボットが歩行している様子が描かれています。これらのロボット、なんとCPPNが生成しているのです。CPPNに座標情報を入力し、出力をその座標のパーツの種類としてみなすことによりロボットが設計されています。
ソフトロボットのパーツは対称に配置される必要があるので、対称的な幾何学パターンを生成できるCPPNが役になっているのです。

3.1.3. HyperNEAT

HyperNEATは、「NEATで最適化されるCPPNによって、NNを生成する」アルゴリズムです。HyperNEATでは、NNのノードに座標を割り振ります。CPPNには2ノードの座標が入力され、出力がその2ノード間のコネクション重みとして解釈することでNNが作られるのです。

参考文献

A hypercube-based encoding for evolving large-scale neural networks. (https://direct.mit.edu/artl/article-pdf/15/2/185/1662702/artl.2009.15.2.15202.pdf?casa_token=98BQpS5RUDkAAAAA:Tvy9B5S-bTuwAKn6rtLqCPcPnVHrIiZsKzNiot05sBNifKWOA1ZKd8r_Icc2eESwX2OsB3nz4wA)
Evolving Neural Networks through Augmenting Topologies. (https://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf)
Compositional Pattern Producing Networks: A Novel Abstraction of Development (http://eplex.cs.ucf.edu/papers/stanley_gpem07.pdf)