提煉再提煉濃縮再濃縮：Neural Architecture Search 介紹

[Updates]

• 2021/07/12 — 更新圖片以及文字內容。
• 2021/11/02 — 更新內容

Introduction

在現今電腦視覺的領域當中，CNN 已經可以達到非常高甚至超越人類的精確度，但隨之而來的代價就是追求更深更大的網路所造成的高複雜度（例如:大量的記憶體需求，大量的運算），因此對於在有限資源的硬體設備（例如：手機，嵌入式系統）中應用產生了巨大的挑戰，因為我們總不可能在每一台手機每一台監視器，都放一張 1080Ti 或是 2080Ti，所以現今的網路需求除了對於精確度的要求，也慢慢開始注重效能的優化。

然而，設計出一個能夠兼顧準確度以及效能的網路是很困難的。

要設計一個好的網路，首先會遇到兩個問題，分別是 intractable search space 和 non transferable optimality。

Intractable Search Space

Search space 的意思是在我們搜索出一個網路的時候，我們的搜索的空間，也就是所有可能的選擇所組合成的空間。

以大家熟悉的 VGG16 為例，其中並沒有任何較為複雜的設計（例如：residual connection），單純為 13 層的 convolutional layers，假設在每一層 kernel size 的選擇皆是 {1, 3, 5}，單是這樣可能構成的選擇便有 3¹³ 次方種選擇。且訓練一個 CNN 往往會花費許多時間，更不用說要從這麼多的選擇中要挑出一個最好的架構了，畢竟我們不可能實際的訓練這 3¹³ 種網路吧！

Non transferable optimality

而對於不同的裝置，由於其不同的硬體架構，因此對於同樣的一個運算，也會有不同的速度，所以一個在 A 裝置表現的好的網路架構，並不一定同樣可以在 B 裝置表現的好，也就是 CNN 的 non transferable optimality。

因此便有人開始進行 neural architecture search 的研究，目的是希望可以開法出一個方法，並且可以自動的探尋 search space 以獲得最好的網路。

What is Neural Network Search (NAS)?

簡單來說，NAS 的目的就是希望可以有一套演算法或是一個框架能夠自動的根據我們的需求找到最好的 neural architecture，而我們的搜索目標有可能會是根據 performance，或是根據硬體資源限制 (hardware constraints) 來進行搜索。

而 NAS 可以分成三個大部份，也就是 search space, search strategy 和 performance estimation strategy。

Search Space

中文又稱作為搜索空間，也就是我們在選擇 neural architecture 時，我們所可以調整的所有選擇。舉例來說，kerne size, channel size, convolution type 以及 layer number 等等。

Search Strategy

在給定的 search space 當中，我們要透過什麼方式來搜索出最好的 neural architecture。舉例來說，在搜索 hyperparameter 時最為大家熟悉的 grid search 以及 random search，或是 evolution algorithm (基因演算法) 等等。

Performance Estimation Strategy

當我們從 search space 當中挑選出了一個 neural architecture，我們如何評估這個 neural architecture 是好還是壞的方式。舉例來說，我們可以實際的訓練每個 neural architecture 來獲得實際的 top-1 accuracy，我們也可以訓練少量的 neural architecture，並且將實際訓練好的數據，用來訓練一個額外的 accuracy predictor。

Reinforcement Learning NAS

對於 NAS 這個 task 來說，其實最直覺的方法就是我不斷的從 search space 當中取出不同的 neural architecture ，並且實際的訓練之後來獲得真正的 performance，藉著不斷的重複這個動作，當我窮盡整個 search space 時，我理所當然的就可以得到這個 search space 當中最好的那個 neural architecture。

而也因為這個簡單的概念，所以最早的 NAS 是基於 reinforcement learning 的方式來進行搜索，也就是透過一個 controller (agent) 不斷的挑出 neural architecture，並且透過 trainer (environment) 實際的進行訓練，而所得到的 performance (e.g., top-1 accuracy, FLOPs or latency) 會作為 reward 進而更新 controller，使得 controller 可以學習要如何才可以 sample 出可以讓 reward 最好的 neural architecture。

但由於每次 controller 所挑出的 neural architecture，都需要經過 trainer 實際的進行訓練，因此可想而知的是這會是一個非常耗費時間成本的一件事情，因此為了使得 trainer 不會花費過大量的時間，過去的 work 會利用叫小型的 dataset (e.g., CIFAR10 or CIFAR100) 或是訓練較少的 epoch 數。

然而，儘管這個方法在過去皆達到了很好的結果，但是這個方法依舊是需要一般人所無法負荷的龐大成本 (例如， CVPR 2019 Google 所提出的 MnasNet，在同時使用 64 個 TPU 的情況下，依舊是需要搜索 4.5 天！)，因此現今越來越少 NAS 使用 RL 的方式來進行搜索。

Progressive NAS

Progressive NAS 最主要的概念便是一層一層漸進式的方式決定在每一層要用什麼樣的選擇。

而由於要決定每一層要用什麼樣的架構，我們首先需要知道所有選擇的好壞，而實際的將所有種可能的架構 training，並根據結果來決定好壞會花費許多時間，因此會額外的訓練一個 controller，而 controller 的目的就是預測當前這樣的組合的準確率會是多少。

因此 Progressive NAS 主要可以分成幾個大步驟：

1. 從 l-layers 的 N 個可能的網路架構中，透過 controller 預測結果，並挑選出最好的 K 個網路架構。
2. 將 K 個網路架構實際的訓練並得到他們間的好壞，並利用這 K 個結果更新 controller，使其可以預測的更加準確，將最好的網路架構接上下一層的所有可能選擇，建構出 l+1 layers的 N 個架構，並回到步驟 1。

One-shot NAS

為了減少過去 NAS 所耗費的大量時間 (e.g., 實際訓練每個 neural architecture 的時間)，One-shot NAS 透過將 search space 當中的所有 neural architectures 結合成為一個 over-parameterized 的 neural network，而這個巨大且錯綜複雜的網路又被稱作為 supernet。下圖為建構 Supernet 的範例，假如在每層當中，我們總共有三種 candidate blocks 可以選擇，則在 supernet 當中每層裡面便會同時有三個不同 candidate blocks。

而這樣建構的好處在於當 supernet 訓練完畢之後，透過 activate supernet 當中不同的 candidate blocks，我們可以進而 approximate 在 search space 當中的任何一個 neural architecture (如下圖最右邊的部分)。因此 one-shot NAS 之所以稱為 “one-shot” 的原因在於，我們只需要訓練一個 neural network (supernet) ，便可以藉此評估整個 search space 當中的任一個 neural architecture。

而在 One-shot NAS 當中，根據訓練 supernet 以及搜索的不同，又可以分為兩種，分別為 Differentiable NAS 以及 Single-path NAS。

想要實際實作看看 one-shot NAS 的讀者們，歡迎參考這篇文章！

Differentiable NAS

Differentiable NAS (DNAS) 希望可以透過 gradient descent 的方式來進行搜索。然而，由於 neural architectures 本身是離散的，因此我們沒有辦法直接對 neural architectures 微分並且計算梯度。因此 DNAS 使用了一個額外的可微分參數，我們稱作為 architecture parameters，目的是希望透過這個可以微分的參數來學習在 search space 當中好的 neural architecture 的分佈。

下圖為 supernet 當中的某一層 layer，而 DNAS 首先對於每個 candidate block 皆會給予一個 architecture parameter，而這個值通常會是隨機初始的 (如圖中的 0.2, 0.7, 和 0.1)，因此對於這層 layer output 的計算方式，便會是每個 candidate block 本身的 output 和 architecture parameters 進行 weighted sum (如左圖中的數學式)，透過這樣的方式，我們便計算出 architecture parameters 的梯度，並且更新，而當 architecture parameters 更新完畢之後，便可以將之作為 “candidate blocks 之間重要程度的依據” ，進而直接對其做 argmax 並 sample 出搜索到的 architecture (如下圖的右邊)。

然而，以上的方式對於 DNAS 來說有一個缺點，便是搜索時間不彈性，透過上面的圖，我們可以發現，當今天我們更新完整個 architecture parameters 之後，我們僅僅只能從 architecture parameters 中 sample 出一組在特定硬體資源限制之下的 neural architecture，因此當今天我們需要搜索在 N 個不同硬體資源限制之下的 neural architectures 時，便需要重新訓練 N 次的 architecture parameters 同時重新訓練 N 次的 supernet。

Single-path NAS

而相對於 DNAS 的另外一個種類 single-path NAS，便是直接將整個 NAS 的程序拆成兩個獨立的步驟，分別為 : Supernet training 以及 Architecture searching。

1. Supernet training：在這個階段，每次只會從 supernet 當中 sample 出 single path 並且更新其對應到的參數，透過這樣的方式，除了可以模擬實際在 search space 當中離散的 neural architecture，同時也可以大幅度的減少 GPU memory 需求。而如何訓練 supernet 在現今的 NAS 研究當中也是一個很重要的研究方向 [8][10][11]，原因在於我們會希望 Supernet 是一個可以正確評估 neural architectures 好壞的 performance estimator，因此假如 supernet 並沒有被穩定且公平的訓練，會使得 supernet 本身產生一定的 bias 進而使得我們沒有辦法良好的評估 neural architectures 之間的好壞。
2. Architecture searching：當 supernet 訓練完畢之後，supernet 本身便可以作為一個 performance estimator，並且結合不同的 search strategy(e.g., random search 以及 evolution algorithm) 來進行搜索。

Reference

[1] B. Zoph and Q. V. Le. Neural architecture search with reinforcement learning. In ICLR, 2017

[2] M. Tan, B. Chen, R. Pang, V. Vasudevan, and Q. V. Le. Mnasnet: Platform-aware neural architecture search for mobile. CVPR, 2019

[3] B. Wu, X. Dai, P. Zhang, Y. Wang, F. Sun, Y. Wu, Y. Tian, P. Vajda, Y. Jia, and K. Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. CVPR, 2019

[4] Liu, C., Zoph, B., Shlens, J., Hua, W., Li, L.J., Fei-Fei, L., Yuille, A., Huang, J. Murphy, K.: Progressive neural architecture search. ECCV 2018

[5] Jin-Dong Dong, An-Chieh Cheng, Da-Cheng Juan, Wei Wei, and Min Sun. Dpp-net: Device-aware progressive search for pareto-optimal neural architectures. In ECCV, 2018.

[6] H. Liu, K. Simonyan, and Y. Yang. DARTS: Differentiablearchitecture search. ICLR, 2019

[7] G. Bender, P.-J. Kindermans, B. Zoph, V. Vasudevan, and Q. Le. Understanding and simplifying one-shot architecture search. In International Conference on Machine Learning. ICML 2018

[8] Z. Guo, X. Zhang, H. Mu, W. Heng, Z. Liu, Y. Wei, and J. Sun. Single path one-shot neural architecture search with uniform sampling. arXiv preprint arXiv:1904.00420, 2019.

[9] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv preprint arXiv:1808.05377, 2018b.

[10] Xiangxiang Chu, Bo Zhang, Ruijun Xu, Jixiang Li. FairNAS: Rethinking Evaluation Fairness of Weight Sharing Neural Architecture Search. arxiv:1907.01845.

[11] Shan You, Tao Huang, Mingmin Yang, Fei Wang, Chen Qian, Changshui Zhang. GreedyNAS: Towards Fast One-Shot NAS with Greedy Supernet. CVPR 2020