ICLR2020のNAS調査(1): PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search

弊部署で，1月だけどアドベントカレンダーやろうぜ!![^1]となったので，自分も書くかということで、
ICLR2020のNAS(Neural Architecture Search)の論文調査をはじめました．
ICLR2020ではNAS関連の論文が少なくとも以下の11件[^2]出ていました

- Poster(8件)
    - [Evaluating The Search Phase of Neural Architecture Search](https://openreview.net/forum?id=H1loF2NFwr&noteId=H1loF2NFwr)
    - [Understanding Architectures Learnt by Cell-based Neural Architecture Search](https://openreview.net/forum?id=BJxH22EKPS)
    - [Fast Neural Network Adaptation via Parameter Remapping and Architecture Search](https://openreview.net/forum?id=rklTmyBKPH)
    - [AtomNAS: Fine-Grained End-to-End Neural Architecture Search](https://openreview.net/forum?id=BylQSxHFwr)
    - [NAS-BENCH-1SHOT1: BENCHMARKING AND DISSECTING ONE-SHOT NEURAL ARCHITECTURE SEARCH](https://openreview.net/forum?id=SJx9ngStPH)
    - [NAS evaluation is frustratingly hard](https://openreview.net/forum?id=HygrdpVKvr)
    - [How to 0wn the NAS in Your Spare Time](https://openreview.net/forum?id=S1erpeBFPB)
    - [Once for All: Train One Network and Specialize it for Efficient Deployment](https://openreview.net/forum?id=HylxE1HKwS)[^3]

- Spotlight(2件)
    - **[PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://openreview.net/forum?id=BJlS634tPr)**
    - [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://openreview.net/forum?id=HJxyZkBKDr)

- Oral(1件)
    - [Understanding and Robustifying Differentiable Architecture Search](https://openreview.net/forum?id=H1gDNyrKDS)


本稿では(次があるとは(ry)最初に読んだ，
**PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search**
についてざっくりとまとめたいと思います
ちなみに，[ICLR2020論文読み会](https://connpass.com/event/162218/)にて本内容を発表予定です
NASまだまだ全然わかってないので，参加者の方は色々教えて頂けると嬉しいです

# TL;DR
探索時にチャンネルを一部だけ使う"Partial Channel Connection"を行うことで，NAS(DARTS)を正則化しつつ高速化．CIFAR10ではわずか0.1 GPU-daysの探索でエラー率2.57%(DARTS:2.76%,4 GPU-days)，ImageNetでも3.8 GPU-daysの探索でエラー率24.2%(DARTS:26.7%)を実現．
(著者の書いたTL;DRは↓)
> Allowing partial channel connection in super-networks to regularize and accelerate differentiable architecture search  



# 手法
提案手法は①**Partial Channel Connection**(図上部)と，②**Edge Normalization**(図下部)の2つの要素で構成されています．
![Figure 1](https://cugtyt.github.io/blog/papers/2019/R/pc-darts-fig1.png)
### Partial Channel Connection
[DARTS](https://arxiv.org/abs/1806.09055)において，全候補オペレーションの計算はメモリを大量に使うし重いのが難点です，そこで，下式の通り，**1/Kのサンプリングされたチャンネルだけを計算**して，残りはインプットをそのまま渡すようにしています．
<math id="S3.E1.m1" class="ltx_Math" alttext="{f_{i,j}^{\mathrm{PC}}\!\left(\mathbf{x}_{i};\mathbf{S}_{i,j}\right)}={{\sum_{%
o\in\mathcal{O}}}\frac{\exp\left\{\alpha_{i,j}^{o}\right\}}{{\sum_{o^{\prime}%
\in\mathcal{O}}}\exp\left\{\alpha_{i,j}^{o^{\prime}}\right\}}\cdot o\!\left(%
\mathbf{S}_{i,j}\ast\mathbf{x}_{i}\right)+\left(1-\mathbf{S}_{i,j}\right)\ast%
\mathbf{x}_{i}}." display="block"><mrow><mrow><mrow><mpadded width="-1.7pt"><msubsup><mi>f</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>PC</mi></msubsup></mpadded><mo>⁢</mo><mrow><mo>(</mo><msub><mi>𝐱</mi><mi>i</mi></msub><mo>;</mo><msub><mi>𝐒</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><munder><mo largeop="true" movablelimits="false" symmetric="true">∑</mo><mrow><mi>o</mi><mo>∈</mo><mi class="ltx_font_mathcaligraphic">𝒪</mi></mrow></munder><mrow><mrow><mfrac><mrow><mi>exp</mi><mo>⁡</mo><mrow><mo>{</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><mi>o</mi></msubsup><mo>}</mo></mrow></mrow><mrow><msub><mo largeop="true" symmetric="true">∑</mo><mrow><msup><mi>o</mi><mo>′</mo></msup><mo>∈</mo><mi class="ltx_font_mathcaligraphic">𝒪</mi></mrow></msub><mrow><mi>exp</mi><mo>⁡</mo><mrow><mo>{</mo><msubsup><mi>α</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow><msup><mi>o</mi><mo>′</mo></msup></msubsup><mo>}</mo></mrow></mrow></mrow></mfrac><mo>⋅</mo><mpadded width="-1.7pt"><mi>o</mi></mpadded></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><msub><mi>𝐒</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>∗</mo><msub><mi>𝐱</mi><mi>i</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>-</mo><msub><mi>𝐒</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mrow><mo>)</mo></mrow><mo>∗</mo><msub><mi>𝐱</mi><mi>i</mi></msub></mrow></mrow></mrow><mo>.</mo></mrow></math>
これで，**メモリ量と計算量はだいたい1/K**にできます．メモリが減ったことで**バッチサイズを大きくとれる**ようになり，**学習を安定**させることができます．また，正則化による性能改善効果も得られるようです．
### Edge Normalization(図下部)
チャンネル1/Kとかやって大丈夫?と思いますよね．著者も，反復ごとで違うチャンネルがサンプリングされ一貫性がなくなることは学習を不安定にする可能性があり望ましくないとしています．
そこで，セルのアウトプットを計算するときに，**各ノードの出力を下式を用いて重みづけして足し合わせることで，この欠点の影響の緩和**を図っています．
<math id="S3.E2.m1" class="ltx_Math" alttext="\mathbf{x}_{j}^{\mathrm{PC}}={\sum_{i&lt;j}\frac{\exp\left\{\beta_{i,j}\right\}}{%
{\sum_{i^{\prime}&lt;j}}\exp\left\{\beta_{i^{\prime},j}\right\}}\cdot f_{i,j}\!%
\left(\mathbf{x}_{i}\right)}." display="block"><mrow><mrow><msubsup><mi>𝐱</mi><mi>j</mi><mi>PC</mi></msubsup><mo>=</mo><mrow><munder><mo largeop="true" movablelimits="false" symmetric="true">∑</mo><mrow><mi>i</mi><mo>&lt;</mo><mi>j</mi></mrow></munder><mrow><mrow><mfrac><mrow><mi>exp</mi><mo>⁡</mo><mrow><mo>{</mo><msub><mi>β</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>}</mo></mrow></mrow><mrow><msub><mo largeop="true" symmetric="true">∑</mo><mrow><msup><mi>i</mi><mo>′</mo></msup><mo>&lt;</mo><mi>j</mi></mrow></msub><mrow><mi>exp</mi><mo>⁡</mo><mrow><mo>{</mo><msub><mi>β</mi><mrow><msup><mi>i</mi><mo>′</mo></msup><mo>,</mo><mi>j</mi></mrow></msub><mo>}</mo></mrow></mrow></mrow></mfrac><mo>⋅</mo><mpadded width="-1.7pt"><msub><mi>f</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub></mpadded></mrow><mo>⁢</mo><mrow><mo>(</mo><msub><mi>𝐱</mi><mi>i</mi></msub><mo>)</mo></mrow></mrow></mrow></mrow><mo>.</mo></mrow></math>
Edge Normalizationでチャンネルをサンプリングする影響が緩和される理由について，
↓のように，ノードの重みパラメタβが学習プロセス全体でシェアされているから，とされていますが，
> Since βi,j are shared through the training process, the learned network architecture
is insensitive to the sampled channels across iterations, making the architecture search more stable.

このお気持ちが分からない…


# 実験
### CIFAR10
わずか0.1 GPU-days(DARTS 2nd orderの1/10!!)の探索時間でエラー率2.57%を実現，
著者曰く，3%以下のエラー率の手法では探索時間最速とのこと．
![CIFAR10](https://cugtyt.github.io/blog/papers/2019/R/pc-darts-tab1.png)
### ImageNet
3.8 GPU-daysの探索でtop-1エラー率24.2%を実現．
(公開されている中では)最高性能とのこと．
![ImageNet](https://cugtyt.github.io/blog/papers/2019/R/pc-darts-tab2.png)
### Ablation Study
![PC-DARTS.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/543346/7d048c8c-528a-7833-3618-bffd8cab9e0e.png)
- **サンプリングパラメタKの影響**(図左部):
ハイパラKの影響について，CIFAR10の場合，**K=4までは性能改善**がみられています．
このことから，Partial Channel Connectionには，メモリ削減&高速化効果だけでなく，
**正則化による過学習の抑制効果**もあると思われます
- **Partial Channel Connection(PC)，Edge Normalization(EN)それぞれの効果**(図右部):
CIFAR10, ImageNetどちらの場合でも，**PC・ENともに単独で改善効果**がみられています．また，**組合せた場合がベスト**です．(PCについて，Batch Sizeを変えて実験したかどうかが少し気になるところ…)
図には含まれていませんが，ENなしの場合，CIFAR10で5回試行を行ったときに，
エラー率は2.54%~3.01%と変動していたの対し，**ENありの場合，探索5試行の最小と最大の差は0.15%以下だったということで，学習安定化**効果が狙い通り得られていたようです．


# 所感
やってることのシンプルさのわりに良好な結果が得られていて面白かったです．
DARTSは試行ごとで性能の変動がそれなりにあるので，PC-DARTSは1発でもそれなりに見れる結果が出そうなのも良いですね．(バッチサイズ大きくできることが効いてそうだな～と個人的には感じています)
あと，実装でマルチGPU対応してくれてることが地味にありがたいです．(DARTSのオリジナル実装はシングルGPU前提)
実験設定や他手法との比較について書ききれなかったので出来れば追記したいです…

# 論文情報
- 著者: Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, Hongkai Xiong
- 機関: Shanghai Jiao Tong University, Huawei Noah’s Ark Lab, Tongji University, Futurewei Technologie
- コード: [Github](https://github.com/yuhuixu1993/PC-DARTS), [Dropbox](https://www.dropbox.com/sh/on9lg3rpx1r6dkf/AABG5mt0sMHjnEJyoRnLEYW4a?dl=0)
- 論文: [OpenReview](https://openreview.net/forum?id=BJlS634tPr), [arXiv](https://arxiv.org/abs/1907.05737)


# 参考
- DARTSのおさらい
    - [Neural Architecture Searchの新潮流 〜DARTSとFBNetの衝撃〜](https://qiita.com/cvusk/items/e7c9bb30c801996cd973)
    - [論文紹介 "DARTS: Differentiable Architecture Search"](https://www.slideshare.net/YutaKoreeda/darts-differentiable-architecture-search)
    - [Investigating Differentiable Neural Architecture Search for Scientific Datasets ← DARTSの解説+色んなデータで検証](https://towardsdatascience.com/investigating-differentiable-neural-architecture-search-for-scientific-datasets-62899be8714e)
- その他NAS関連
    - [NAS(Neural architecture search)の歴史と現在の動向(Elsken et al. 2019)](https://qiita.com/norihitoishida/items/9f73865a0c8f99c203cd)
    - [Architecture Design for Deep Neural Networks III ← PC-DARTSも掲載](https://www.slideshare.net/ssuser2ff343/architecture-design-for-deep-neural-networks-iii)
    - [ProxylessNASをざっくりざっくり理解する ← 自分の書いたざっくりな解説](https://qiita.com/kuz44ma69/items/2184dd6a1ad5bb0fa2ce)

[^1]: アドベントの意味的には1月は変な気もしますがそこは流してもらえると…
[^2]: [こちら](https://openreview.net/group?id=ICLR.cc/2020/Conference)で"architecture search" or "NAS"をタイトルに含む論文をカウント．1件例外は注釈3に記載．keywordsに含むとかで検索すれば恐らく他にも見つかると思う．
[^3]: "architecture search"タイトルに入ってないけど何かの経緯で見つけたので一応