作者來自將門計算機視覺社群：李國豪
論文作者來自阿卜杜拉國王科技大學的在讀博士生李國豪，本次分享的是KAUST與Intel ISL在CVPR 2020的工作：SGAS，一種基于貪心思想的CNN/GCN網絡結構搜索算法。
本工作通過貪心()的搜索方式減輕了NAS中模型排名在搜索和最后評估不一致的問題。是一種更優更快的網絡結構搜索算法，并同時支持CNN和GCN的搜索。代碼已開源，想在圖像，點云，生物圖數據上做網絡結構搜索的同學都可以試一試。
Arxiv:
:
Code:
相關工作
網絡結構搜索（ ， 簡稱NAS) 是一種神經網絡結構自動化設計的技術。NAS基于相應算法在特定的樣本集內自動設計出高性能的網絡結構。這些自動搜索出的網絡結構在某些任務上已經媲美或超過了人類專家手工設計的網絡結構。
早期NAS的算法是基于強化學習（Zoph et al.[1]）或進化算法（Real et al.[2]）。這些算法計算成本高昂，阻礙了其廣泛應用。近來，Liu et al.[3]提出了一種高效的可微分的網絡結構搜索算法：可微分網絡結構搜索（ , 簡稱DARTS）。DARTS的提出使得網絡結構搜索在單卡一天內完成搜索。后續許多工作都基于DARTS基礎上進行改進，比如SNAS/FBNet//P-DARTS/GDAS//PC-DARTS/等等。
背景知識：DARTS
DARTS采用基于單元(Cell)的搜索方法進行網絡結構搜索。Cell是一個網絡子模塊，可以自由堆疊多次形成卷積網絡。DARTS通過學習cell的結構，完成對網絡的結構搜索。Cell是由N個節點的有序序列組成的有向無環圖(如圖1)。Cell中每個節點x^(i)是卷積網絡中的特征圖，每個有向邊（i，j）代表一種對x的運算o(i, j) （如3x3的卷積）。一個cell具有兩個輸入節點，一個輸出節點和多個中間結點。Cell的輸入節點被定義為前兩層的輸出。Cell的輸出是對所有中間節點進行歸約運算（例如）后的結果。每個中間節點由它之前結點經過算子op變換后相加得到：
DARTS為了實現可微搜索，提出了搜索空間的機制，利用函數來學習所有可能候選運算op的權重：
其中，$\(O)$ 表示搜索空間中的候選運算（例如卷積，最大池化，零）等，零表示沒有運算（邊）。其中一對節點（i，j）之間的運算由向量\{i, j}參數化。運算的結果是每種可能運算結果的加權求和。向量\{i, j}的維度為搜索空間長度|O|。因而，DARTS將網絡結構搜索的任務簡化為了學習一組連續變量\alpha= {\alpha(i, j)}，如圖1所示。DARTS在搜索結束階段，通過得到權重最大的候選運算op當作該邊的搜索結果：
圖1 DARTS的單元結構以及網絡結構搜索示意圖[3]
DARTS存在的部分問題
一般NAS的流程是分為搜索階段和評估階段，在訓練集與驗證集上進行結構的搜索（搜索階段），然后在測試集上進行模型的評估（評估階段）。DARTS在搜索結束的階段直接得到網絡結構，如圖1和公式3所示。這種策略導致在搜索和評估階段派生的網絡結構的性能相關性非常低。網絡在搜索階段的效果，并不能反映其在評估階段的真實效果。我們將這種現象稱之為：退化的搜索評估相關性（- ）。我們認為造成這種想象的主要原因是：（1）搜索階段和評估階段設置的不一致性；（2）權重共享（ ）造成的副作用。
舉個例子：假設我們只搜索3種候選運算，skip-，3x3卷積，5x5卷積。如果搜索時分配的權重分別是skip- （0.34），3x3卷積（0.33），5x5卷積（0.33），最后所選的操作會是沒有可學習參數的skip-，如果所有的邊都是這種情況，那么最后的網絡在評價階段性能就會很差，然而在搜索階段這個網絡和權重分配為skip- （0.33），3x3卷積（0.34），5x5卷積（0.33），最后會得到3x3卷積的網絡性能幾乎不會有區別。這一現象并不僅僅發生在DARTS上，也發生其他大部分NAS算法上，這嚴重影響了NAS的性能。
肯德爾系數\tau[4]可用于量化搜索評估相關性（ - ）?？系聽栂禂到橛?1到1，-1表示完全負相關，1表示完全正相關。如果肯德爾系數為0，則分布完全獨立。理想的NAS方法應具有較高的搜索評估相關性\tau。我們以DARTS 為例， 在CIFAR-10數據集上運行10次，分別根據搜索準確性和最終評估準確性排名，計算其肯德爾系數。一階和二階的DARTS的肯德爾系數分別僅為0.16和-0.29。因此，DARTS算法的搜索評估相關性極低，無法根據DARTS在搜索階段的效果預測模型測試階段的準確性。
圖2 搜索-測試相關性可以用肯德爾系數衡量。常見的NAS算法，如DARTS，肯德爾系數低，無法根據其搜索階段對最終測試的準確性做出可靠的預測。
SGAS詳細方案
針對退化的搜索評估相關性這一重要的問題，我們提出了SGAS（ ），一種順序貪心決策的搜索算法。
圖2 SGAS的網絡結構搜索示意圖
我們基于貪心算法的思想將網絡結構的搜索問題，轉化為逐步地選擇一條邊并確定其運算的子問題。實驗證明，依次解決這些簡單的子問題，可以讓最終結構具有更高的搜索-測試相關性。算法的迭代過程如算法1所示。
在每個決策時期，我們根據預先確定的選擇標準選擇一條邊(i^{+}, j^{+})。通過用公式(3)得到這條邊的運算，并替換相應的混合運算o^{\bar}。所選擇的運算，即是所選的邊基于貪心的最優選擇。每當確定好一條邊的運算，我們就不再需要這條邊的結構參數\alpha(i^{+}, j^{+}))以及混合操作中其余路徑的權重，我們可以將這條邊從后續的優化中去除。這樣可以帶給我們一個額外的好處是：優化問題得到了剪枝，進而可以提高搜索的效率。一條邊被剪枝后用到貪心策略的算法，剩下的超網絡以及參數形成一個新的子問題，該子問題將被以相同的算法迭代求解。在搜索階段的最后，便得到一個沒有權重共享的離散子網絡，如圖2所示。SGAS算法基于順序貪心算法，減少了在搜索階段和評價階段的模型不一致性和權重共享的副作用，使得模型的搜索-測試相關性最大化。
在SGAS中，選擇標準的設計至關重要。我們考慮影響邊的選擇的三個重要因素：邊的重要性，選擇確定性和選擇穩定性。
邊的重要性：如果這條邊的非零運算選擇的可能性越高，表明這條邊越重要。
選擇確定性：熵（）是分布用度量不確定性的常。非零運算的歸一化權重可以看作是一種分布：
我們將選擇確定性定義為一減去操作分布的歸一化熵：
選擇穩定性：為了讓選擇更穩定，我們需要考慮選擇確定性的歷史分布。直方圖相交[48]是檢測分布變化的常用方法，我們利用直方圖相交來計算第T步中的前K時間的邊的平均選擇穩定性：
根據這三個影響邊選擇的三個因素，我們提出了兩個選擇指標：
指標1 ：具有高的邊重要性和高的邊確定性的邊將被選擇，公式為：
指標2：在指標1的基礎上，被選擇的邊也應該具有較高的穩定性：
這里用到貪心策略的算法，(·)指 Min-Max標準化。
實驗結果
我們搜索了CNN和GCN網絡結構，并在CIFAR，圖像分類，點云分類，PPI生物圖數據節點分類上達到了SOTA效果。
我們將SGAS用到CNN的網絡結構搜索中， CNN網絡結構由普通單元() 和 歸約單元( cell)組成。普通單元保持特征圖大小不變，歸約單元縮小特征圖至?. CNN任務中，搜索空間由8個運算組成：skip-,max-pool-3×3, avg-pool-3×3, sep-conv-3×3, sep-conv5×5, dil-conv-3×3,dil-conv-5×5, zero。
SGAS在CIFAR-10的訓練集與驗證集搜索結構，并在測試集上進行測試，結果如表1所示：
SGAS在CIFAR-10的訓練集與驗證集搜索結構，并在測試集上進行測試，結果如表2所示：
我們的SGAS在性能超越了手工設計的網絡結構以及其他NAS算法。
我們是同時將SGAS用到GCN的網絡結構搜索中的。GCN網絡結構由普通單元( cell) 組成。其搜索空間由10個運算組成：conv-1×1, , , GAT, , GIN, SAGE, ,skip-, and zero 。
SGAS在的訓練集與測試集搜索結構，并在訓練集和測試集上進行訓練與測試，結果如表3所示：
我們也將SGAS應用到生物信息圖的結點預測上。我們在PPI ( ) 數據集的訓練集與驗證集搜索結構，并在PPI的訓練集和測試集上進行訓練與測試，結果如表4所示：
我們SGAS在GCN上的實驗，超越了之前最好的模型。我們在以及PPI數據集上成為了新的state-of-the-art.
更多的結果與分析可以
閱讀我們的論文
（包含附錄）
訪問我們的項目網頁
或參考我們的開源代碼
參考資料[1] Zoph and Quoc V Le. with . arXiv :1611.01578, 2016.[2] Real, Alok , , and Quoc V Le. for image . In of the AAAI on , 33, pages 4780–4789, 2019.[3] Liu, Karen , and . Darts: . arXiv :1806.09055, 2018.[4] G . A new of rank . ,30(1/2):81–93, 1938.
點擊“?在看”，讓更多朋友們看到吧~