導讀：在CVPR 2020上，商湯移動智能事業群-3DAR-身份認證與視頻感知組提出了基於貪心超網絡的One-Shot NAS方法，顯著提升了超網絡直接在大規模數據集上的搜索訓練效率，並在標準ImageNet數據集上取得了300M FLOPs量級的SOTA。GreedyNAS論文通過提出一種貪心的超網絡結構採樣訓練方法，改善了訓練得到的超網絡對結構的評估能力，進而幫助搜索算法得到精度更高的結構。
動機與背景
在目前的神經結構搜索領域中，One-Shot NAS方法由於其搜索開銷小被廣泛應用，這些方法使用一個權重共享的超網絡（supernet）作為不同網絡結構的性能評估器，因此，supernet的訓練對搜索結果的好壞至關重要。然而，目前的方法一般採用了一個基本的假設，即supernet中每一個結構是同等重要的，supernet應該對每個結構進行準確評估或相對排序。然而，supernet中所包含的結構量級（搜索空間的size）是非常巨大的（如 7^{21} ），因此準確的評估對於supernet來說是非常困難的，導致supernet中結構的表現與其真實表現相關性很差 [1]。
在本篇論文中，我們提出一種貪心超網絡來減輕supernet的評估壓力，使得supernet更加貪心地注重於有潛力的好結構，而不是全體。具體而言，在supernet訓練過程中，我們提出了一種多路徑拒絕式採樣方法(multi-path sampling with rejection)來進行路徑濾波 (path filtering)，使得有潛力的好結構得到訓練。通過這種方法，supernet的訓練從整個搜索空間貪心地縮小到了有潛力的結構組成的空間中，因此訓練的效率得到了提升。同時，為了進一步增大有潛力結構的採樣概率與提高訓練效率，我們基於exploration and exploitation準則，使用一個經驗池存儲評估過的「好」結構，用來加強貪心度並為後續的搜索提供好的初始點。本論文搜索出的結構在ImageNet (mobile setting) 下取得了 SOTA(state-of-the-art) 的結果。
主要思路
巨大的搜索空間帶來的評估壓力使supernet難以準確地區分結構的好壞，由於所有結構的權重都是在supernet中高度共享的，如果一個差的結構被訓練到了，好的結構的權重也會受到幹擾。這樣的幹擾會削弱好網絡的最終評估精度，影響網絡的搜索結果。同時，對差的結構進行訓練相當於對權重進行了沒有必要的更新，降低supernet的訓練效率。
多路徑拒絕式採樣
針對上述問題，一個直接的想法就是基於貪心策略，在訓練過程中只訓練好的結構。但很顯然，我們並不知道一個隨機初始化的搜索空間中哪些結構是好的。假設對於一個supernet，我們考慮其搜索空間A的一個完備劃分，即：
搜索空間可以如上劃分為好的空間與差的空間，且好空間中每一個結構的ACC均大於差空間，即
於是，一個理想的採樣策略是直接在好空間中進行採樣即可。然而根據上面的不等式，確定所有結構中哪些是來自好空間需要遍歷整個搜索空間，計算開銷是無法接受的。為了解決這個問題，我們首先考慮從全空間中進行的一個均勻採樣，那麼每個path來自好空間的概率為：
為了得到需要的來自於好空間的結構，我們進一步考慮一個多維的Bernoulli實驗，那麼有如下的結論：
我們取m = 10和m = 20，對定理1的概率進行繪製，如Figure 2所示，可見這種採樣下得到來自好空間中的path的概率是很高的。
於是，我們可以對採樣到的多個結構進行評估篩選的方法提升採樣到「好」結構的概率，即每次採樣m個結構，從中選取評估指標最高的k個結構進行訓練。但是，對結構進行評估需要在驗證集上計算其ACC，這樣會增加非常多計算量（我們的ImageNet驗證集大小為50k）。為了減少評估網絡的消耗，我們從驗證集中隨機選取了一小部分（如1000張圖）組成小驗證集，並使用在小驗證集上的loss作為結構的排序指標。使用小驗證集進行評估，在保證評估準確性的前提下，相較uniform sampling方法只增加了很少的計算代價，詳見論文實驗部分。
基於exploration and exploitation策略的路徑候選池
在前面提到的路徑濾波中，我們通過評估可以區分出較好的結構，為了進一步提升訓練效率，受蒙特卡洛樹搜索(Monte Carlo tree search)[4] 和 deep Q-learning[5] 中常用的exploration and exploitation策略啟發，我們提出使用一個路徑候選池用於存放訓練過程中評估過的「好」結構，並進行重複利用。具體而言，候選池可以看作是一個固定大小的有序隊列，其只會存儲所有評估過結構中得分前n(候選池大小) 的結構。
有了候選池的幫助，我們可以選擇從搜索空間中或候選池中採樣結構。從候選池中採樣的結構是好結構的概率更高，但可能會犧牲結構的多樣性。為了平衡exploration與exploitation，我們採用-採樣策略，即以一定的概率從整個搜索空間A或候選池P中採樣結構α：
在網絡剛開始訓練時評估過的結構較少，候選池中存儲的結構是好結構的可信度不高，因此從候選池中採樣的概率 在開始時設為0，併線性增加至一個較高的值（在實驗中，我們發現0.8是一個較優的值）。若候選池中的結構都來自好空間，通過使用候選池，定理1中好網絡的採樣概率q提升為：
因此，採樣10個結構，至少有5個好結構的概率由88.38%提升至99.36% 。
基於候選池的early stopping策略
候選池的更新為supernet的訓練情況提供了一個很好的參考。若候選池發生的更新（順序變換、進出）較少，可以認為超網絡中較好的網絡維持著一個相對穩定的排序，這也說明此時的supernet已經是一個較好的性能評估器，因此訓練進程可以提前結束，而不需要訓練至網絡完全收斂。
在實際使用中，我們會比較當前候選池P與t輪迭代前的候選池P_t的差異度，若差異度低於某個數值（我們的實驗使用0.08），訓練停止。差異度的定義如下：
基於候選池的搜索策略
Supernet訓練結束後，我們可以使用驗證集的ACC評估結構的好壞。本文使用 NSGA-II 進化算法[3] 進行結構搜索。我們在進化算法中使用候選池中的結構進行population的初始化，相較於隨機初始化，藉助於候選池能夠使進化算法有一個更好的初始，提升搜索效率及最終的精度。
如 Figure 3 所示，我們在同一個訓練好的supernet上使用了隨機初始化與候選池初始化兩種方式進行搜索，使用候選池初始化搜索到的結構的準確率平均會比隨機初始化要高。
實驗結果
為了與目前的one-shot方法進行對比，我們首先在與 ProxylessNAS[6] 一樣的 MobileNetV2 搜索空間上進行結構搜索，結果見 Table 1 。
同時為了進一步提升網絡性能，我們在加入了SE的更大搜索空間上進行搜索，結果見 Table 2 。
Ablation Study
多路徑拒絕式採樣中的路徑評估相關性
我們對隨機初始化、uniform sampling、greedy方法訓練得到的supernet下的小驗證集指標與完整驗證集ACC相關性進行了評估，如 Table 3 所示。可見在小驗證集上使用loss相比ACC會得到更高的相關性，我們的貪心方法訓練出的supernet有著更好的相關性。
我們對不同大小小驗證集與完整驗證集的相關性進行了評估（Figure 4 左圖），同時對uniform-sampling算法在不同迭代輪數下的相關性作了評估（Figure 4 右圖）。可以看出我們的算法在較小的驗證集大小上仍能保持較高的相關性，在精度與效率的權衡下，我們最終選取 1000 作為小驗證集大小。
對多路徑貪心採樣及候選池效果的評估
我們在MobileNetV2的search space下評估了多路徑貪心採樣及候選池的效果，如 Table 4 所示。
總結
超網絡訓練是單分支One-Shot NAS 方法的關鍵。與目前方法的對所有分支一視同仁不同，我們的方法貪心地注重於有潛力的好分支的訓練。這種貪心地分支濾波可以通過我們提出的多分支採樣策略被高效地實現。我們提出的 GreedyNAS 在準確率和訓練效率上均展現出了顯著的優勢。
論地址：
https://arxiv.org/abs/2003.11236
Reference
[1] Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint arXiv:1902.08142, 2019.
[2] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path oneshot neural architecture search with uniform sampling. arXiv preprint arXiv:1904.00420, 2019.
[3] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182–197, 2002.
[4] Levente Kocsis and Csaba Szepesvari. Bandit based montecarlo planning. In European conference on machine learning, pages 282–293. Springer, 2006.
[5] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
[6] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXiv:1812.00332, 2018.
如何通過深度學習，完成計算機視覺中的所有工作？看似毫不相干，哲學與機器學習竟有如此大的交集黑客用上機器學習你慌不慌？這 7 種竊取數據的新手段快來認識一下「谷歌殺手」發明者，科學天才 Wolfram清晰架構的 Go 微服務: 程序容器5分鐘！就能學會以太坊 JSON API 基礎知識