AGenetic Programming Approach to Designing Convolutional  Neural Network Architectures

## Abstract
CNNベースのモデルを自動でアーキテクチャを生成するものを選んだ。これにはGCPのアルゴリズムを採用してよいアーキテクチャを組む。データセットはcifar-10を使用した。
## Introduction
畳み込み層とプーリング、全結合層からなるCNNはとても画像認識タスクにおいてよい性能を出しているが、パラメータの数がとても多くネットワークを作成するのにはコストと時間がかかる。またReSNetやDecentNetやGoogle Netといった素晴らしいCNNも出てきているが、これらのようなよいアーキテクチャは専門的な知識やよい技術がなければ作り出すことができない。そして簡単なモデルであるCNNでは自動的にNN探索を行う手法が注目されている。
アーキテクチャを作るにあたって最初の問題はパラメータ最適化である。いくつものneuronをブラックボックス最適化で最適化することなどが挙げられる。
遺伝的アルゴリズムにより最適化する手法が存在しているが、Direct EncodingとIndirect Encodingである。
（Direct Encoding 
ニューロン数や連鎖などを直接遺伝的に求めるもの）
（　Indirect Encoding
　この節で紹介するIndirect Encodingは結合や結合荷重を直接コード化する代わりに、ネットワークの生成ルールをコード化する手法である。人間の脳のニューロン数は遺伝子の塩基数よりもはるかに多いので、生物学的にも実際により近いモデルであると言える。）
 しかしこれらの過去の手法は小さな規模のネットワークでも畳み込みやプーリング、バッチ正規化といった様々なパラメータが存在する。したがってこれらの手法は最小限のユニット数でなければなりません。
 この論文では遺伝的アルゴリズムに基づいたCGPによる最適化を行ないます。この手法はdirect encodingの一種です。この手法はスキップ接続やネットワークの長さなど柔軟に対応できるだけでなく、畳み込みブロックの個数やテンソルの数など探索空間において様々なものを減らすことができます。評価にはオリジナルのデータセットを使います。他の分野における評価はアーキテクチャが適合するもののデータセットを使います。この適合度を評価することで遺伝的アルゴリズムでCNNを最適化していきます。提案手法の検証方法はcifar-10のデータセットで画像分類タスクをときます。実験は自動で作成したCNNのモデルと最先端のモデルを比べて行います。
 ## 2.Related Work
 ハイパパラメータ探索や遺伝的アルゴリズム、強化学習的なアプローチなどの自動ネットワーク探索について簡単に復習します。
 ## 2.1 Hyperparameter Optimization
 NNのハイパパラメータはグリッドサーチ、ランダムサーチ、ベイズ最適化など様々存在している。当然のことながら遺伝的アルゴリズムも。ベイズ最適化は良い性能でブラックボックス最適化やノイズがある場合などもよい性能。正規分布はノイズを簡単に削除できる。
 Bergtra→tree-stuructedを（TPE)ランダムサーチより良い→meta-modeling approach
 Snoek→Gガウス分布→計算コストの削減

 
 これらはレイヤーの数やニューロンのタイプや活性化関数など様々な問題を解消に成功しているが、より柔軟なアーキテクチャへの探索は困難であるという問題がある。

 ## 2.2 Evolutionary Neural Networks
 進化アルゴリズムはNNを最適化してきた。これまでの手法は少ないニューロンでないと最適化することができない。
 Fernado→DPPNs(differentiable pattern-producing networks)オートエンコーダの重みを最適化する。これはcompositonal pattern-producing networks(CPPNs)といったものの、微分タイプである。この論文では重みの最適化であるindirect codingの効率性に焦点を当てる。
 Verbansics→HyperNEATでCNNとNNを最適化した。(hepercube-based neuroevolution of augmenting topologies)
 
 しかしながら、この手法は最先端のネットワークには勝てておらず、自動探索によって作成したネットワークの方が劣っている。またこれらの手法は専門家によって再定義をしなれけば行けないネットワークである。したがって探索のためのネットワークをデザインすることはできていない（困難）だといえる。

 ## 2.3 Reinforcement Learning Approach
 自動探索において強化学習を用いるのはとても面白いアプローチである。これらの研究はイメージタスクにおいてCNNアーキテクチャを競争的に作成される強化学習の手法である。RNNは強化学習訓練し、期待した性能を実現している。この手法は強化学習を加速させ800ものＧＰＵで非同期的にパラメータを更新している。Bakerはmeta-modelingを行った。これはＣＮＮを作るときに強化学習によって探索を行う手法である。Q-learningはエージェントの探索とεgreddy法による探索領域を行うのを繰り返す。

 これらの手法はネットワークの計画をindirect codingする計画のものであり、それはＲＮＮのようなＮＮの探索の最適化を行なう。これらの手法と同様に私たちはCGP(Cartesian genetic programming)によるdirect codingでＣＮＮのアーキテクチャを探索する。それに加え、より効果的なＣＮＮを見付けるためにtensor concatenationsや畳み込み層の関係を紹介する。

 ## 3.3 CNN architecture design using cartesian genetic programming
 CGPによる探索を行う。検証データによってよりよい性能のアーキテクチャーを採用しそのアーキテクチャの最大の検証誤差を進化アルゴリズムによって最適化する。
 図1にそれを示す。
 ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3656436/464ebfd7-9669-047e-3da6-e0e665df3ef2.png)
この３章は提案手法と遺伝的アルゴリズムについての具体的な内容です。
## 3.1 Representation of CNN Architectures
計算ノードに基づいた２次元グリッドの周期的でないグラフをプログラムすることでCGPencodingを表現する。Nrを列、Ncを行に設定してグリッドを仮定してみましょう。入力の数と出力の数はタスクによって決められる。遺伝のタイプは長さからなり、それぞれの遺伝委は情報を持っています。そしてノードを接続します。c番目のノードはc-lからc-1までのノードが接続されておりIをlevel-backparameterと呼ぶ。図２は遺伝タイプの例を示している。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3656436/9b30eee7-b3d3-d701-2d80-86c8197b2f2e.png)
この図の場合はCNNは３行２列で構成されている。CGPの遺伝タイプのfixed-length（固定長）を表す一方で、ネットワークのノードの数は変動します。出力層にすべてノードが接続されていないため。例えば図２の5番目のノードはinactiveです。
CNNについてよく見るとConv Block ResBlock Macpooling average polling concatenation summationといいた３－Dのテンソルを列と行とチャンネル方向に定義する特徴マップを作製する。
Conv Bolockは最後にバッチ正規化とRELUを施す。入力のチャンネル数Cと出力のチャンネル数C'は異なるため、CGPでは対応するカーネルサイズを用意する。また、ResBlockでは図３に示す。これもConvBlockと同じようにカーネルのサイズを合わせる。
 ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3656436/2288a8e5-0e6b-3e17-122b-9f130a3b8b3d.png)
この文は、2つの特徴マップをチャネル次元で連結する「concatenation」関数と、要素ごとの足し算を行う「summation」関数について説明しています。

まず、「concatenation」関数では、2つの入力特徴マップの行または列の数が異なる場合、大きな特徴マップをMaxプーリングによってダウンサンプリングして、入力のサイズを同じにします。連結操作では、出力特徴マップのサイズはmin(M1, M2) × min(N1, N2) × (C1 + C2)になります。ここで、M1、M2は入力の行数、N1、N2は列数、C1、C2はチャネル数です。

次に、「summation」関数では、2つの入力特徴マップの行または列の数が異なる場合、大きな特徴マップをMaxプーリングによってダウンサンプリングします。さらに、入力のチャネル数が異なる場合は、小さい特徴マップをゼロでパディングしてチャネル数を増やします。足し算操作では、出力特徴マップのサイズはmin(M1, M2) × min(N1, N2) × max(C1, C2)になります。

最後に、図2において、「summation」ノードは最初の入力にMaxプーリングを適用して入力テンソルサイズを同じにします。これらの足し算と連結操作を組み合わせることで、GoogleNetやResidual Netなどのショートカット接続やブランチング層を表現することができます。
具体的には、出力ノードはクラスの数を持つソフトマックス関数を表し、その出力は入力のすべての要素に完全に接続されます。実験で使用されるノード関数は、表1に表示されています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3656436/74575019-4a8f-ea0f-cb21-6d917cd8407e.png)
## 3.2 Evolutinary Algorithm

突然変異を行う。突然変異はinactiveのネットワークにしか適応できない。
適当なCNNの評価をするのには訓練されたCNNがなければいけないため、とてもコストがかかります。それぞれの遺伝の関係において並列に候補解を評価する。したがって突然変異は候補解が最後のactiveノードまでをapplyします。これをa forced mutationと呼び、ニューラルdriftを保持することはCGPの進化においてとても効率的です。突然変異によって親を修正するもし、適当な子孫がつくれなかったら。phenotypeの修正なしではinactiveのノードの遺伝子だけを変えることができない。
進化戦略を(1+λ)で（実験ではλ=2)そしてアルゴリズムを以下に示す。
1.親Pからランダムに個々を初期化する。そして適当な汎化性能を仮定し、CNNを訓練させる。
2.Pのforced mutationをapplyすることで子孫Cのλを生成する。
3.子孫Cによって訓練したλと適度な汎化誤差を検証する。
4.親Pの自然突然変異をapplyする。
5.PとCのセットからエリートなPに置き換える。
6.より解に収束するまでstep2から繰り返す。