英語論文まとめvol.1~"Neural Architecture Search: A Survey"

#はじめに
今回の論文情報をまとめておきます. 
題名: Neural Architecture Search: A Survey
著者名: Thomas Elsken, Jan Hendrik Metzen, Frank Hutter
出典: Journal of Machine Learning Research 20 (2019) 1-21

#目次
-Introduction
-探索空間(Search Space)
-探索戦略(Search Strategy)
-パフォ-マンス推定戦略(Performance Estimation Strategy)
-Conclusion and Future Work

#Introduction
既にNASメソッドは画像分類, 物体検知, セマンティックセグメンテーションなどのタスクにおいて, 人間が開発したアーキテクチャを上回っているようです. 
ちなみに画像分類→物体検知→セマンティックセグメンテーションの順でタスクの難易度が上がっていくようです. 
<img width="400" alt="スクリーンショット 2019-11-27 10.58.17.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/5371b80a-0896-bf65-3a84-85fe43dd2820.png">
<img width="400" alt="スクリーンショット 2019-11-27 10.55.04.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/dab3e6a9-6d41-00b8-6266-2a8d5c350eac.png">

そしてNASメソッドは３つの次元に分けられるそうです. 
**1. 探索空間(Search Space)**
**2. 探索戦略(Search Strategy)**
**3. パフォーマンス推定戦略(Performance Estimation Strategy)**

それぞれの特徴を簡単に説明すると...
<img width="400" alt="スクリーンショット 2019-11-27 14.42.59.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/dbaa5f32-7452-86f8-f12b-c48c4b199a1b.png">
<img width="400" alt="スクリーンショット 2019-11-27 14.43.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/c84fbf39-56ca-d307-5800-e3516fca7aae.png">
<img width="400" alt="スクリーンショット 2019-11-27 14.43.40.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/b1bf01db-1d7e-0e04-b352-2be013032653.png">

以下, 簡単なNASの流れです. 
<img width="400" alt="スクリーンショット 2019-11-27 14.46.26.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/f1eb6930-df3e-7441-54be-016030b0e57d.png">

#探索空間(Search Space)
どういった構造を表現できるのかを定義します. 
構造にもいくつか種類があり, 代表的なものにチェーン構造, マルチブランチ構造, セル構造があるようです. 
順番にまとめていきます. 
##チェーン構造
<img width="400" alt="スクリーンショット 2019-11-29 10.18.47.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/04d320db-8550-a2fa-beb0-b33178f5fc90.png">

##マルチブランチ構造
<img width="400" alt="スクリーンショット 2019-11-29 10.26.26.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/d8fc6b4d-ea08-3a7a-d4c8-6e457f19bfb9.png">
<img width="400" alt="スクリーンショット 2019-11-29 10.35.46.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/bc50eb97-fb72-0b51-ca54-0df7f2fc44cd.png">


##cell構造
<img width="400" alt="スクリーンショット 2019-11-29 10.30.42.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/a6d396a0-820b-a095-b98a-8bb0b9927607.png">
<img width="400" alt="スクリーンショット 2019-11-29 10.30.54.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/8e3b6995-125b-d1a3-ebf0-afe39f86b41a.png">
<img width="400" alt="スクリーンショット 2019-11-29 10.31.04.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/b6021a94-5329-a834-2d2e-e943e0e30070.png">


#探索戦略
探索戦略には, 
- ランダム探索
- ベイズ最適化
- 進化アプローチ
- 強化学習
- 勾配ベースアプローチ
などが使用されるようです. 

強化学習と進化アプローチについてまとめていきます. 

##強化学習(RL)
NASは様々な強化学習の枠組みで考えることができます. 
例えば, 行動=ネットワークの生成, 行動空間=探索空間, 報酬=未知データへのパフォーマンスといった場合や状態=現在のNNの構造, 行動=NNの構造の変化, 報酬=現在のNNのパフォーマンスとする場合などがあります. 

強化学習を用いたモデルは高いパフォーマンスを発揮するが, 膨大な計算コストがかかるため, 計算コストを削減するための研究が進められている. 

##進化アルゴリズム(EA)
進化アルゴリズムには以下の手法があります. 
-　遺伝的アルゴリズム
-　遺伝的プログラミング
-　進化戦略
-　進化アプローチ

EA手法の潮流としては, 
1. EAにより構造を最適化, BPにより重みを最適化
2. EAにより構造と重みを最適化
3. EAにより構造を最適化, 勾配ベース手法により重みを最適化
という流れになっています. 
2から3の間でまた1と同様の使い方に戻ったのは, 「現代のNNでは重みが何百万とあり勾配ベースの方が適しているから」といった理由のためです. 

またEAでは, 
- 両親のサンプリング方法
- 母集団の更新方法
- 子孫の生成方法
といった部分で違いがあるようです. 

###両親のサンプリング
- トーナメント選択を用いる方法
- Inverse densityを用いる方法

###母集団の更新
- 最悪個体を除去する方法
- 最古個体を除去する方法
- 個体の除去を行わない方法

###子孫の生成
- ランダムに初期化する方法
- Lamarckian inheritanceを用いる方法
- 親個体のパラメータをすべて継承する方法

#パフォーマンス推定(Performance Estimation Strategy)
パフォーマンス推定の最も簡単な方法は, trainデータで学習し, validデータで評価することです. しかし, アーキテクチャをフルスクラッチで生成して評価するのは非常に計算コストが大きいため, 様々な高速化手法が開発されています. 
<img width="400" alt="スクリーンショット 2020-01-19 0.44.07.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/21abccb7-c586-e151-ac5e-18afc4282ce4.png">

##Lower fidelity estimates
パフォーマンスを低い忠実度で推定する方法です. 
具体的には...
- 短い学習時間で学習する
- データのサブセットを使用する
- 低解像度の画像を使用する
- レイヤごとのフィルタ数やセル数を削減する

低忠実度による近似は計算コストを削減するがパフォーマンスを過小評価するため, バイアスが導入されます. しかし, 探索戦略がアーキテクチャの順位のみに依存していて, 相対的な順位が安定している限りは問題になりません. 
最近の研究では, 安易な近似で実際の評価値の差が大きすぎると, 相対順位が変化する可能性があることを示しています. 

##Learning Curve Extrapolation
学習曲線の外挿に基づいた方法です.  
具体的には...
- 初期の学習曲線を推定し, パフォーマンスが低下すると予測される曲線を終了し, 探索プロセスを高速化させる方法
- どの部分学習曲線が将来的に有望であるかを予測する方法
- 新しいアーキテクチャのパフォーマンスを予測するため, 代理モデルを学習する方法

##Weight Inheritance/Network Morphism
Weight Inheritanceはトレーニング済みのアーキテクチャの重みに基づいて, 新しいアーキテクチャの重みを初期化する方法です. 
Network MorphismはNNの構造が変異して子個体を生成する方法です. 

##One-Shot NAS
スーパーグラフのエッジが共通するアーキテクチャ間で重みを共有する方法です. 
One-Shot NASの流れは
1. ワンショットモデル(スーパーグラフ)を1回トレーニングする
2. ワンショットモデルのトレーニング済みの重みをサブグラフに継承する
3. サブグラフの評価をする
4. 2と3を繰り返す

<img width="400" alt="スクリーンショット 2020-01-19 1.03.06.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/8abeada0-18f3-efc9-962a-43b05b48442a.png">

#今後の展望
<img width="600" alt="IMG_0031.jpg" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/2f362c29-ab52-e70b-4b00-98e11db87670.jpeg">