"AIを作るAI"の中身に迫る[NNアーキテクチャ最適化フレームワークNASBOT&NNアーキテクチャ間の距離OTMANN]

最近はやりの[AutoML](<https://cloud.google.com/automl/?hl=ja>)の内部ではNeural Networkのハイパーパラメータだけでなく、レイヤーの種類、数、つなぎ方などの**アーキテクチャ自体を自動で決定する**手法が使われています。まさに、**AIを作るAI**というやつですね。AutoMLでは強化学習をベースにした手法を用いているようです。([こちらを参照](<https://qiita.com/cvusk/items/536862d57107b9c190e2>)) 今回はそんなAIをつくるAIの手法の一つを紹介します。

この記事ではNeuralIPS2018で発表された、

- **ベイズ最適化**を基にNeural Network の**アーキテクチャを自動決定する**ためのフレームワークである***NASBOT***
- その内部で使われている最適輸送を基に**２つのNeural Network 間の距離**(類似度)を表現する***OTMANN*距離**

を紹介します。
次の図は、NASBOTによって作られたNeural Networkのアーキテクチャです。なんとなくスキップ構造が多くあります。
![Neural_architecture_found.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/b2578754-0c8d-46c5-55bf-e08baa419ca5.png)

著者の主張によると、毎回提案したNeural Networkについて高コストである学習・評価しなければいけない強化学習や進化的アルゴリズムを基にした手法と比べ、**ベイズ最適化はより効率がいい探索手法である**とのことです。

元論文は[こちら](<https://papers.nips.cc/paper/7472-neural-architecture-search-with-bayesian-optimisation-and-optimal-transport.pdf>)、ソースコードは(<https://github.com/kirthevasank/nasbot>)で公開されています。

この記事は中身の説明に重きを置いたものになります。ただし、**"わかった気"にさせる**ことを目標に、ある程度適当な書き方をするので、もっと深いところが知りたい方はリンクも極力貼っていきますので、別途調べていただけると幸いです。（フレームワークの使い方など後々加筆するかも）

実際に使う場合もgithubのREADMEの方にかなり詳しく書いてあるため、そちらを参照してみてください。
# ガウス過程回帰とベイズ最適化

最初に*NASBOT*のベースになるガウス過程回帰と、それを用いたベイズ最適化について簡単に説明します。詳しい話は[ガウス過程と機械学習](<https://www.amazon.co.jp/%E3%82%AC%E3%82%A6%E3%82%B9%E9%81%8E%E7%A8%8B%E3%81%A8%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%8C%81%E6%A9%8B-%E5%A4%A7%E5%9C%B0/dp/4061529269/ref=sr_1_1?adgrpid=69939430007&gclid=Cj0KCQiA4NTxBRDxARIsAHyp6gBOLdsjECo0TjRGRW1xcTw0vLpXrQ22WwkGs8rePiAx5kqAWe3v7uMaAnkvEALw_wcB&hvadid=338534031558&hvdev=c&hvlocphy=1009565&hvnetw=g&hvpos=1t1&hvqmt=e&hvrand=14902591016785552650&hvtargid=aud-758806828536%3Akwd-642407283523&hydadcr=4072_10899412&jp-ad-ap=0&keywords=%E3%82%AC%E3%82%A6%E3%82%B9%E9%81%8E%E7%A8%8B%E3%81%A8%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92&qid=1580618599&sr=8-1>)や[こちらのページ](<https://www.smartbowwow.com/2019/06/blog-post.html>)なんかがわかりやすかったです。ベイズ最適化については、[こちらのページ](<https://qiita.com/masasora/items/cc2f10cb79f8c0a6bbaa>)なんかを参考にさせていただいています。ガウス過程もベイズ最適化も十分理解できている方は**この章はまるまる飛ばしていただいて構いません**。

ここで理解していただきたいのは、

- ガウス過程回帰を用いるためには（それを用いたベイズ最適化でも同様に）**データ間の距離**（のようなもの）を何かしらの方法で表す必要があること。
- データ間の距離が定義できれば、**データ自体を数値的に表せる必要はない**こと。

の２点です。ここで言うデータは具体的にはNeural Networkのアーキテクチャになります。

## ガウス過程回帰(Gaussian Process)

ガウス過程の細かい数理については前述の本やページを参考にしていただくださると助かります。ポイントとしては

- 新たな（未知の）データ点に対して、それまでで得られているカーネル行列とデータを使うことで、関数の**予測分布**を得ることができる。

- カーネル関数（**データ間の距離**のようなものを表す）が定義できれば予測分布を計算できる。

という点になります。具体的に数式を見ると、

データ$D={(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)}$($N$はデータ数)について、

$$y\sim\mathcal{N}(\bf{0},\bf{K})$$

とすると、新たな（未知の）データ$(x\^\*,y\^\*)$に対して、

```math

\left(\begin{array}{new_posterior}
\bf{y} \\
y^* 
\end{array}
\right)=\mathcal{N}\left(\bf{0},\left(
\begin{array}{new_posterior}
\bf{K}&k\_*\\
k_* ^{T}&k\_{**}
\end{array}\right)\right)
\tag{1}

```

```math

\left
\{
\begin{array}{abc}
&k_{**}=(k(x^*,x_1),k(x^*,x_2),\dots ,k(x^*,x_N))^T \\
&k_{**}=k(x^*,x^*)
\end{array}
\right.

```

が成り立ちます。ここで、$k(\cdot,\cdot)$はカーネル行列を表します。

(1)式はいわゆる同時分布になり、導出は省きますが、これを変形することで次の事後分布を得ます。

$p(y\^\*|x\^\*,D)=\mathcal {N}(\bf{k}\_\*\^T\bf{K}\^\{-1}\bf{y},k\_\{**}-\bf{k}\_\*\^T\bf{K}\^\{-1}\bf{k}\_\*)\tag{2}$

この式は新たなデータが複数の場合にも同様に成り立ち、未知の点に対してこの式に従い平均と分散（のようなもの）を得ることで画像のように関数の予測分布の形で回帰を行うことができます。
![gp_regression_16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/e3a32d28-1b10-092d-bbc5-f7364e1f288f.png)

図では、赤点線が真のモデル（つまり予測したいのも）、青線が推定した分布のの平均、薄く青いエリアは信頼区間(2$\sigma$区間)です。
つまり、各点の値が**どのくらいの値になるかの予測**と、その予測が**どのくらい信頼できるか**（できないか）を考えることができる部分が通常の回帰と違う部分になります。

カーネル関数については代表的なものとしてガウシアンカーネルを上げると次の式で表されます。

$k(x,x')=\theta_1\exp({-|x-x'|^2}/\theta_2)\tag{3}$

注目してほしいのは２つの入力の**距離**に応じて値が決まる形になっていることです。

これらの性質から、ベイズ最適化を用いたアーキテクチャサーチのためには、**Neural Network間の距離（類似度]）をしめす尺度が必要**になります。もう一つ重要な性質として、データ間の距離が示せればその**データ自体は数値的に表せる必要は無い**という点があります。つまり、１つのNeural Netwokを数値的に表す必要はありません。

##ベイズ最適化(Bayesian Optimisation)

つづいてベイズ最適化ですが、[こちら](<https://qiita.com/masasora/items/cc2f10cb79f8c0a6bbaa>)や[こちら](<https://qiita.com/watakandai/items/c8abe4f80dab1cdace54>)なんかを読んでいただけるとイメージはすごくわかると思います。ベイズ最適化はブラックボックス最適化の手法の一つで、実験計画などに使われるようです。たとえば、ボーリング調査でつぎに調査を行う地点を決めたり、機械学習でのハイパーパラメータサーチを効率よく行うために用いられます。

ざっくり言うと、ベイズ最適化では次の探索点を、獲得関数(acquisition functrion)$\varphi(x)$を基準に決定します。次の探索点を決定する際によく言われるものとして、**活用と探索のトレードオフ**があります。これは、すでに得られたデータを基準に考えて次の点を決める活用と、より多くの未知の部分を失くすように次の点を決める探索、どちらを重要視するかを考えることになります。
![bayesian_opt_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/e1628033-0717-acfa-2db0-eb379a64bd71.png)

図では、上がガウス過程回帰を用いた$f(x)$の推定、下が獲得関数$\varphi(x)$になります。$\varphi(x)$が高い点が次の探索点になります。

獲得関数にはいろいろなものがありますが、NASBOTではExpected Improvement(EI)を用いています。式は次のようになります。

$\varphi(x)=E[\max\{0,f(x)-\tau_{t-1}\}|\{(x_i,y_i)\}^{t-1}_{i-1}]\tag{4}$

ここで$\tau_t$は時刻$t$までの目的関数$f$の最大値です。EIは一言でいうと、探索点$x$が新たに$f$の最大値になる期待値をとっていることになります。

$f$のモデルにガウス過程(GP)を適用すると次のようになります。

```math
\varphi(x)=\left\{
\begin{matrix}(\mu(x)-\tau_{t-1}-\xi)\Phi(Z)+\sigma(x)\phi(x)     \quad&\mbox{if}\quad\sigma(x)>0\\
0\quad &\mbox{if}\quad\sigma(x)<0
\end{matrix}
\right.
\tag{5}

```

```math
Z=\left\{
\begin{array}{iii}
\frac{\mu(x)-\tau_{t-1}-\xi}{\sigma (x)}\quad&\mbox{if}\quad\sigma(x)>0\\
0\quad&\mbox{if}\quad\sigma(x)=0
\end{array}
\right.

```

ここで、$\mu(x),\sigma(x)$は平均と分散、$\xi$は活用と探索のトレードオフを決めるハイパーパラメータになります。また、$\Phi(Z),\phi(Z)$はそれぞれ累積密度関数と確率分布関数を表しています。この四季を眺めると、平均$\mu(x)$が大きい点は$\varphi(x)$が大きくなり、分散$\sigma(x)$が大きいときにも$\varphi(x)$が大きくなるようになっていることがわかります。ここで、$\mu(x)$を重要視する場合は活用、$\sigma(x)$を重要視する場合は探索にそれぞれ重点を置く形になると言えます。

上記のような獲得関数をつかい、次のような流れで次の探索点を決定します。

ステップ1. 得られたデータからガウス過程回帰により事後分布(2)式を計算る  

```math
p(y^*|x^*,D)=\mathcal{N}(\bf{k}_*^T \bf{K}^{-1}\bf{y},k_{**}- \bf{k}_*^T\bf{K}^{-1}\bf{k}_*)
```
ステップ2. 得られた事後分布を用いて、獲得関数$\varphi(x)$を最大にする点を次の探索点とする  

```math
x_t=\mbox{arg}\min_{x}\varphi(x)
```

# *OTMANN* distance

上記のように、ガウス過程ベースのベイズ最適化では、**データ間の距離**（類似度）を計算する必要があります。そのため、この論文で提案された、２つのNeural Networkの**アーキテクチャ間の擬距離を示す**OTMANNが登場します。このOTMANNは、最適輸送（Optimal Transport)をもとに分布間の距離を表す*Earth Mover's Distance*や*Wasserstein metric*に着想を得ていると思われます。そこでまずは、最適輸送について説明します。ここについても**最適輸送に関しては十分理解している方は**、つぎの"OTMANNで使う表記について"に飛んでいただいて大丈夫です。

##最適輸送(Optimal Transport)

ここでは、かなり簡単な説明にとどめておきますが最適輸送の話はかなり奥が深く興味深い話であると思います。（正直、勉強不足で深い話ができるような知識はありません...今後頑張りたい...)

正直[こちらのページ](<http://aidiary.hatenablog.com/entry/20120804/1344058475>)や[こちらのリンク集](<http://tam5917.hatenablog.com/entry/2018/01/19/213040>)のほうがよっぽど参考になると思いますので、是非皆さん勉強してみてください。（そして最適輸送の解説記事を書いてくださるととても嬉しいです。）
![スクリーンショット 2020-01-21 21.15.23.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/db052813-7609-9e06-9943-f1a570df7ed9.png)

最適輸送では名前の通り、最適な輸送の仕方を考える問題になります。図のように、$n_1$個の工場の集合$\mathcal{L}\_1$にある荷物を$n_2$個の倉庫の集合$\mathcal{L}\_2$へ運ぶことを考えます。それぞれの工場からそれぞれの倉庫へ運ぶ際の輸送コストが$C_{ij}$で示されています。そして、それぞれの工場からそれぞれの倉庫への輸送量$Z_{ij}$を、**総コストが最小になるように決定する**問題になります。総コスト$W$は次のように表すことができます。

$W=\sum\_{i\in\mathcal{L}1,j\in\mathcal{L}\_2}Z\_{ij}C\_{ij}$

さらに次の制約が課されます。

1. 輸送は一方向のみで、倉庫から工場へ運ばれる荷物はない。  
$Z_{ij}\geq0$
2. 工場にある荷物の量は決まっていて、それ以上輸送できない  
$\sum_jZ_{ij}\leqq lm(i)$
3. 倉庫の容量は決まっていて、それ以上は入れることができない  
 $\sum_iZ_{ij}\leqq lm(j)$
4. 輸送量の総和は工場の荷物の量か倉庫の容量の小さい方  
$\sum_i\sum_jZ_{ij}=\mbox{min}(\sum_ilm(i),\sum_jlm(j))$

ここで、$lm(i),lm(j)$はそれぞれの限界の量を示しています。

1,2,3の制約については、このあとに説明するOTMANNにも同様の考えが同様の形で登場します。しかし、４つ目に関してのみ、OTMANN特有の形になることを先に言及しておきます。

これらをまとめると次のようになります。

$\bf Z\in\mathbb{R}^{n_1\times n_2}$について

$\min_{\bf Z} W=\min_{\bf Z}\langle\bf Z\bf C\rangle=\min{\bf Z}{\sum}\_{i\in\mathcal{L}\_1,j\in\mathcal{L}\_2}Z_{ij}C_{ij}\tag{6}$

$\mbox{subject to}\quad Z_{ij}\geq0,\quad\sum_jZ_{ij}\leqq lm(i),\quad\sum_iZ_{ij}\leqq lm(j),\quad\sum_i\sum_jZ_{ij}=\mbox{min}(\sum_ilm(i),\sum_jlm(j))$

$\langle\rangle$はフロベニウス積を表しています。この最小化問題を$\bf Z$について解いたときの,$W$の最小値が工場の集合$\mathcal{L}_1$と倉庫の集合$\mathcal{L}_2$の距離になるというのが*Earth Mover's Distance*の考え方の走りとなります。

具体的な解き方は言及しませんが、OTMANNに使われている最適輸送のsolverは[こちら](<https://arxiv.org/abs/1803.00567>)の論文の手法をもちいているようです。この手法は[こちらのページ](<https://pot.readthedocs.io/en/stable/>)にpythonのライブラリとして提供されています。



##OTMANNで使う表記について

やっと主題の一つであるOTMANNの説明になります。しかしまずは、この論文で用いられているNeural Netの細部の表記について説明しなくていはいけません。
![nn_example.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/9c99d019-222a-e104-ab47-56519d8eac6d.png)

- Neural Networkは$\mathcal{G}=(\mathcal{L,E})$という形で、レイヤー$\mathcal{L}$とエッジ$\mathcal{E}$の集合ノカタチで表されます。またあるエッジの両端のレイヤーのペアを$(u,v)$という形で表します。

- $ll()$でレイヤーの種類を表します。図の(a)のNeural Networkを例にすると、$ll(1)=conv3$となります。

- $lu()$でレイヤーの計算ユニット数を表します。ここで言う計算ユニットとはレイヤーの種類によって異なり、畳み込み層ではフィルタ数、全結合層ではノード数というようなものになります。図の(a)のNeural Networkを例にすると、$lu(4)=32, lu(6)=16$となります。

- $lm()$でレイヤーの重み(layer masses)を表します。この値は、レイヤーの種類によって定義が変わります。

  - processing層(全結合、畳込み、などinput,output,decision layer以外のすべてを指す)：  
            入力ユニット数$\times$出力ユニット数  
    ex)図の(b)で、$lm(5)=(16+16)\times32$  

  - input,output：  
            (全てのprocessing層の$lm$の総和)$\times\xi$

  - decision層(sigmoid,softmaxなど)：  
    $\frac{\mbox{(全てのprocessing層の$lm$の総和)}\times\xi}{\mbox{decision層の数}}$
![explain.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/7be4c22c-bd99-ca86-891f-388c7782a269.png)

    ここで、dicision層の数で割っているのは、dicision層が複数ある場合に均等にその重みを分割する形にするためです。

![matrix_m.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/ac6c71bf-37bb-fd21-9e66-6a6e1f39c84c.png)

- mismatch cost matrix $M$は上の表のように、レイヤーの種類の間の差異を表現して並べたものになります。行列と言っていますが、$\bf{M}$を参照して実際のアーキテクチャ間を見比べてレイヤーの種類の違いからコスト行列を作る際に使われます。この$\bf{M}$は著者によって作られたようなのですが、具体的にどのように決められたなどは不明です。ただ、データによって値を変えてるわけでは無いようなのである程度汎用性のある値になっているようです。

##OTMANNの中身

ついにOTMANNの中身の話に移れます。

OTMANNは次の式を**最小化したときの値**を２つのNeural Networkの**アーキテクチャ間の距離**とするものになります。レイヤーの数がそれぞれ$n1,n2$の２つのNeural Network $\mathcal{G_1=(L_1,E_1)}$と$\mathcal{G_2=(L_2,E_2)}$について、

```math
\min\_{\bf Z}{(\phi\_{lmm}(\bf Z)+\phi_{nas}(\bf Z)+\nu_{str}\phi_{str}(\bf Z))}\tag{7}
```

```math
\mbox{subject to}\quad\sum_{j\in\mathcal{L_2}}Z_{ij}\leqq lm(i),\quad\sum_{i\in\mathcal{L_1}}Z_{ij}\leqq lm(j),\quad\forall i,j
```

ここで、$\bf Z$は最適輸送における輸送量にあたり、$\nu_{str}>0$は$\phi_{lmm},\phi_{nas}$の２つと$\phi_{str}$との間のトレードオフを決めるハイパーパラメータになります。各項間のパラメータが１つしか無いことに関しては後ほど説明します。まずは、それぞれの$\phi$について説明します。

一方のNNのアーキテクチャを変化させて、もう一方のアーキテクチャと同じものにすることを考えた際の変化のさせ方が$\bf Z$にあたります。そして、３つの項はそれぞれNNのレイヤーの種類の違い、変化させきれないものの余り、経路の違いをコストとした物に当たると思われます。(2つ目に関しては、正確に理解できているわけではありません...申し訳ない...)



それではそれぞれの項について説明していきます。

**第１項. $\phi_{lmm}$ (*Label mismatch penalty*)**
この項は２つのNNのアーキテクチャ間の**レイヤーの違いをコストとした項**になります。上記のように一方のアーキテクチャをもう一方と同じものに変化させる際に、レイヤーを交換したときのコストに当たります。中身は次のようになります。

```math
\phi_{lmm}(\bf Z)=\langle \bf{Z,C_{lmm}}\rangle=\underset{i\in\mathcal{L_1},j\in\mathcal{L_2}}{\sum}Z_{ij}C_{lmm}\tag{8}
```

$\bf C_{lmm}\in\mathbb{R^{n_1\times n_2}}$は２つのNNのレイヤーを見比べ上記のmismatch matrix $\bf M$を参照してつくられます。
![スクリーンショット 2020-01-21 16.34.02のコピー.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/ed6d3b83-b8e1-0f90-f810-45fd6cb49baa.png)




```math
C_{lmm}(i,j)=M(i,j)
```

というようにつくられます。

ただし、$\bf M$を眺めると$\infty$があり、これは交換できない場合を示しています。このように、レイヤー間に交換できないものを想定しているため、２つ目の項$\phi_{nas}$につながります。

**第2項. $\phi\_\{nas}$(* Non-assignment penalty *)**
まず$\phi_{nas}$の中身は次のようになります。

![nas_penalty.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/831053a6-bc1e-17d2-c862-366444012be2.png)

$\phi\_{nas}$については解釈が難しいのですが、端的に言うと、**交換しきれないレイヤーの重み(layer masses)$lm$を基準としてコストとしたもの**になります。ひとまず、最適輸送の説明の際に使った例を用いて説明します。

１項目は工場に余った量、２項目は倉庫の空き容量にあたります。ただし荷物の例の場合、どちらにも余りがある時には荷物を運べばいいだけです。このような状況を考えなければいけないのは、今回考えているのは荷物ではなくNNのアーキテクチャの話であるからです。レイヤー同士を交換する際にはmismatch matrix $\bf M$を基準にしてそのコストとしています。しかし、コストが$\infty$、つまり交換を認めないものが存在するため上記のような状況がありえてしまいます。上記の最適輸送の章での、４つ目の制約に関連していると考えられます。

２つのアーキテクチャ間において交換しきれない量をコストとしている項だと思われます。ただ、この項については、私なりの解釈が多分に含まれていおり、論文内の表現を完全に理解しているわけではないことを記しておきます。（もし違う解釈ができるようでしたら、コメントしていただけるとありがたいです！）

**第3項. $\phi\_{str}$(*Structual penalty*)**
この項は、**分岐などの経路の違いをコストとして扱った項**になります。

```math
\phi_{str}(\bf Z)=\langle \bf{Z,C_{str}}\rangle=\underset{i\in\mathcal{L_1},j\in\mathcal{L_2}}{\sum}Z(i,j)C_{str}(i,j)\tag{9}
```

ここで、$\bf C_{str}\in\mathbb{R^{n_1\times n_2}}$は$\mathcal{L}_1$と$\mathcal{L}_2$に含まれるそれぞれのレイヤー間について、６種類の距離の差を考え、次のように定義されます。

```math
C_{str}(i,j)=\frac1 6 \underset {s\in\{sp,lp,rw\}}{\sum}\underset {t\in\{ip,op\}}{\sum}|\delta_t^s(i)-\sigma_t^s(j)
```

$sp,lp,rw$と$ip,op$はそれぞれ、shortest path, longest path, random walk, input, output になります。

このコストでは、あるレイヤーについてinputから最短の距離(shortest path）、最長の距離(longest path)、分岐で等確率で経路を選択するときの平均距離(random walk)の３つを考えます。また、同様にoutputからの距離もそれぞれ３つ考えます。
![nn_example.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/de192190-5348-9892-de73-3e331c476940.png)

図の（ｂ）を例に取ると、５番のconv5のレイヤーについて考えると、inputからのshortest pathは３、longest pathは４、random walk は$(3+4)/2=3.5$となります。outputからの距離は１通りしか経路がないためすべて４になります。

こうして、あるレイヤーについて６つの距離が得られました。

そして、$\mathcal{L}\_1$と$\mathcal{L}\_2$に含まれるそれぞれのレイヤー間での６種類の距離の差を求め、６で割って平均します。これを並べて行列にしたものが$C_{str}$となります。

###OTMANNのまとめ

長くなりましたが、OTMANNについてまとめます。

$\min\_{\bf{Z}}{(\phi\_{lmm}(\bf{Z})+\phi\_{nas}(\bf Z)+\nu\_{str}\phi\_{str}(\bf{Z)})}\tag{10}$

```math
\mbox{subject to}\quad\sum_{j\in\mathcal{L_2}}Z_{ij}\leqq lm(i),\quad\sum_{i\in\mathcal{L_1}}Z_{ij}\leqq lm(j),\quad\forall i,j
```

この式は２つのNNの一方のアーキテクチャをもう一方と同じものにするための最小コストの変換の仕方を求めると考えられます。

この式の３つの項$\phi_{lmm},\phi_{nas},\phi_{str}$は上記の通りでそれぞれ、レイヤーの違い、レイヤーを交換できない部分、経路の違いをコストとして考えたものになります。

そしてこの３つの要素について、最小のコストになるような変換の仕方$\bf{Z}$をみつけ、**その時の最小コストを２つのNN間の距離とする**のが**OTMANN distance**になります。

また、$\phi_{lmm},\phi_{nas}$と$\phi_{str}$の間に一つしかハイパーパラメータ$\nu_{str}$が無いことについてですが、これは$\phi_{lmm}$のコスト行列$\bf C_{str}$をきめる基準になる$mismatch\quad matrix\quad\bf M$の値が$\phi_{nas}$の値を基準にしているからというような説明がされていました。つまり、$\phi_{lmm},\phi_{nas}$については２つセットで考えるものであるようです。既に述べた通り具体的にどのように$\bf M$が導出されているかは書かれていませんでしたので詳しい話はできませんが、固定した$\bf M$でテストを行ったようですので、何かしら有効性はあるようです。

また、この**OTMANNは擬距離である**ことが本論文のAppendixで証明されています。

# *NASBOT*

NASBOTでは上述の**OTMANNを用いた独自のカーネル関数をつかってベイズ最適化**を行います。

###NASBOTの流れ

![nasbot_fig.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/a281b1d1-0b89-a50a-1007-07d8b92c3432.png)

NASBOTの具体的な流れは次のようになります。

時刻$t$において、

1. 学習、評価済みのアーキテクチャの異なるNeural Netのpoolを用意する。
2. これらからガウス過程回帰により性能を示す関数$f(x)$の推定分布、またそれを用いて獲得関数$\varphi_t$を計算する。
3. 得られた**獲得関数$\varphi_t$の値を重みとして**、確率的に$N_{mut}$個の候補を選ぶ。
4. 選んだ候補に変更を加えてmutations(変異体)を得る。
5. 得られたmutationsを学習、評価しpoolに加える。

これを繰り返すことで、性能の良いNeural Networkアーキテクチャを効率的に探索します。

こうのように、通常のベイズ最適化をそのまま使っているわけではなく、進化的アルゴリズムのアイディアを踏襲しています。3で**獲得関数の値が大きものほど選ばれる確率が高くなるようにいくつかの候補を選び**、それらの候補についてのみ変化をくわえてmutationsをつくるという部分が、通常の進化的アルゴリズムとは違う部分になります。
![change_table.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/c3e0adad-000f-c909-c01c-b1fc326b178f.png)

この時に加える変化ですが表のようにあらかじめ用意された変化項目をランダムに選んで適用するようです。また、いくつの変化を加えるかなども乱数で決定します。

### NASBOTで用いられるカーネル関数について

ここで、NASBOTの中のガウス過程回帰で用いられているカーネル関数について説明します。式は次のようになります。

```math
\kappa(\cdot,\cdot)=\alpha \exp (-\underset{i}{\sum}\beta_id_i(\cdot,\cdot))+\overline\alpha \exp (-\underset{i}{\sum}\overline\beta_i\overline d_i(\cdot,\cdot))\tag{11}
```

$d_i(\cdot,\cdot)$は式(10)を最小化した値であるOTMANN距離です。$\overline{d_i}(\cdot,\cdot)$は$d_i(\cdot,\cdot)$を正規化したもので、次の式で表されます。

```math
\overline{d\_i}(\cdot,\cdot)=\frac{d\_i(\cdot,\cdot)}{tm(\mathcal{G}\_1)+tm(\mathcal{G\_2})} \mbox{where}\quad tm(\mathcal{G_i})=\sum_{u\in\mathcal{L}\_i} lm(\mathcal{u})
```

$lm(u)$はOTMANNの説明の際に述べましたが、レイヤーの重みになります。

このカーネル関数がどのように導出されたかは説明が無いためわからないのですが、形はガウシアンカーネルやラプラシアンカーネルを参考にしているように見えます。ただし、このカーネル関数は正定値性などの確認がすんでいないようです。そのため**厳密には、カーネル関数とはいえません**。この点については多くの議論があると思いますが、この関数がカーネル関数であると証明されればOTMANNとカーネル関数を用いていろいろな応用が可能になると考えられます。個人としてはそういった展開が今後あることに期待しています。

# 実験結果

実験としては、提案手法を含めて４種類の手法で比較実験を行っています。データセットも７種類ほどもちいています。（詳しくは本論文を参照してくだされば幸いです。）比較手法は

- NASBOT（提案手法）
- RAND(random serch)
- EA(Evolutional Algorithm)
- Tree BO

Tree BO(元論文は[ここ](<http://proceedings.mlr.press/v70/jenatton17a.html))はスキップ構造を含まないNNのアーキテクチャ探索のための手法です。

![result_table.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/dc4fd842-25a2-83c0-5cbe-7a58639150cb.png)
![result_fig.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/10aebc4d-9f1c-4511-48cd-cad5d1a02dc9.png)


図や表から、提案手法の有効性が示されています。ただ、個人的には冒頭で触れたAutoMLで用いられているような**強化学習ベースの手法との比較がない**のはどうにもいただけない用に感じてしまいます。

また、次の図はOTMANNをベースにtSNEをもちいてNNのアーキテクチャの距離を視覚化したものです。

![Neural_Architec_slide_tsne.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/304217/0278d285-44bc-1e41-5c11-f4baff089517.png)
なんとなく形の似ているものが近くに来ている事がわかります。t-sneの通常ユークリッド距離で計算する部分をOTMANNに変えていると思われますが、それが数理的にただしいのかは個人的に気になっているところではあります。
実装としては、OTMANN基準で距離行列をつくってライブラリのt-sneに放り込んでいるようです。
# さいごに
個人的にはこの論文で提案された

- OTMANN(NNのアーキテクチャ間の距離を表す)
- NASBOT(ベイズ最適化ベースのNNアーキテクチャ探索手法)

はとてもおもしろい試みだと思いました。まだ、数学的な視点から見ると荒い点があるかもしれないですが、ここから整理されてくるとおもしろい発展があるんじゃないかととても楽しみにしています。

冒頭には「AIを作るAI」なんていう煽り文句を書いてしまいましたが、AutoML界隈はさらなる発展が期待できてとてもわくわくしています。
近年、このNeural Architecture Search(NAS)の分野は世界的に盛り上がっています。他の手法についても、ご存じの方は是非コメントや記事を書いていただけると嬉しいと思います。

# 参考文献

- 元論文:https://papers.nips.cc/paper/7472-neural-architecture-search-with-bayesian-optimisation-and-optimal-transport.pdf

- ソースコード:https://github.com/kirthevasank/nasbot

- "AutoMLの理論、Neural Architecture Searchを説明する。":https://qiita.com/cvusk/items/536862d57107b9c190e2

- いわゆる鹿本、これ読んでたらガウス過程の基本的なとこは押さえられると思います。"ガウス過程と機械学習":https://www.amazon.co.jp/%E3%82%AC%E3%82%A6%E3%82%B9%E9%81%8E%E7%A8%8B%E3%81%A8%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92-%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%83%97%E3%83%AD%E3%83%95%E3%82%A7%E3%83%83%E3%82%B7%E3%83%A7%E3%83%8A%E3%83%AB%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%8C%81%E6%A9%8B-%E5%A4%A7%E5%9C%B0/dp/4061529269/ref=sr_1_1?adgrpid=69939430007&gclid=Cj0KCQiA4NTxBRDxARIsAHyp6gBOLdsjECo0TjRGRW1xcTw0vLpXrQ22WwkGs8rePiAx5kqAWe3v7uMaAnkvEALw_wcB&hvadid=338534031558&hvdev=c&hvlocphy=1009565&hvnetw=g&hvpos=1t1&hvqmt=e&hvrand=14902591016785552650&hvtargid=aud-758806828536%3Akwd-642407283523&hydadcr=4072_10899412&jp-ad-ap=0&keywords=%E3%82%AC%E3%82%A6%E3%82%B9%E9%81%8E%E7%A8%8B%E3%81%A8%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92&qid=1580618599&sr=8-1

- いろんな記事がありますが個人的に一番イメージがつかみやすかったガウス過程解説ページ:https://www.smartbowwow.com/2019/06/blog-post.html

- "ベイズ最適化入門:"https://qiita.com/masasora/items/cc2f10cb79f8c0a6bbaa

- "ベイズ最適化の数学":https://qiita.com/watakandai/items/c8abe4f80dab1cdace54

- 最適輸送を解く手法の一つになっています。

  Gabriel Peyré and Marco Cuturi. *Computational Optimal Transport*. Available online, 2017, https://arxiv.org/abs/1803.00567

- 上の論文の手法をpythonライブラリとして提供していただいているようです。

  Python Optimal Transport:https://pot.readthedocs.io/en/stable/

- Earth Mover's Distanceについての解説記事です。:http://aidiary.hatenablog.com/entry/20120804/1344058475

- 最適輸送に関するリンク集です。

  http://tam5917.hatenablog.com/entry/2018/01/19/213040