基於層級表達的高效網路搜索方法 | ICLR 2018

論文基於層級表達提出高效的進化演算法來進行神經網路結構搜索，通過層層堆疊來構建強大的卷積結構。論文的搜索方法簡單，從實驗結果看來，達到很不錯的準確率，值得學習

來源：【曉飛的演算法工程筆記】公眾號

論文: Hierarchical Representations for Efficient Architecture Search

論文地址：//arxiv.org/abs/1711.00436

Introduction

由於網路的驗證需要耗費很長的時間，神經網路結構搜索計算量非常巨大，很多研究通過降低搜索空間的複雜度來提高搜索的效率。論文通過加入分層網路結構來約束搜索空間，在最初幾層僅使用卷積和池化等簡單操作，逐步到高層將底層的block進行組合搭建，最後將最高層的block堆疊成最終的網路。由於搜索空間設計夠好，網路的搜索方法僅用進化演算法或隨機搜索足以。
論文總結如下：

提出對神經網路結構的層級表達
通過實驗證明搜索空間的設計十分重要，可以降低搜索方法的投入，甚至隨機搜索也可以
提出可擴展的進化搜索方法，對比其它進化搜索方法有更好的結果

Architecture Representations

Flat Architecture Representation

將神經網路結構定義為單輸入、單輸出的計算圖，圖中每個節點代表特徵圖，每條有向邊為基本操作(卷積、池化等)，所以網路的表達(G,o)包含兩部分:

一個有效的操作集合o=\{o_1,o_2,…\}
一個鄰接矩陣G，用以指定操作的神經網路圖，G_{ij}=k為節點i和節點j間的操作為o_k

將操作集o和鄰接矩陣G組合起來就得到網路的結構

每個節點i的特徵圖x_i由其前面的節點j通過公式2計算而得，|G|是圖中節點數量，merge將多個特徵圖合併成一個的操作，這裡直接使用depthwise concatentation，由於element-wise addition要求維度一致，比較不靈活，而且如果融合特徵後接的是$1\times 1$卷積，這就其實類似於做concatienation

Hierarchical Architecture Representation

層級結構表達的關鍵是找到不同的層級的模版，在構建高層模版時使用低層的模版作為積木(operation)進行構建

對於L層的層級關係，\ell層包含M_{\ell}個模版，最高層\ell=L僅包含一個模版，對應完整的網路，最低層\ell=1是元操作集，定義o_m^{(\ell)}為\ell層的第m個模版，為低層模版o^{(\ell)}=\{o_1^{(\ell -1)},o_2^{(\ell -1)},…,o_1^{(\ell – 1)}\}根據公式3的組合。最終的層級結構表達為(\{\{G_m^{(\ell)}\}_{m=1}^M\}_{\ell=2}^L,o^{(1)})，由每層的模版的網路結構關係和最底層操作定義，如圖1

Primitive Operations

低層的原操作共六種(\ell=1,M_t=6)：

1 × 1 convolution of C channels
3 × 3 depthwise convolution
3 × 3 separable convolution of C channels
3 × 3 max-pooling
3 × 3 average-pooling
identity

使用時，所有元操作為stride=1，以及進行padded來保留解析度，卷積後都接BN+ReLU，維度固定為C。另外每層都有none操作，代表節點i和節點j之間沒有連接

Evolutionary Architecture Search

Mutation

分層基因的變異包含以下步驟：

取樣一個非原始層\ell\ge2作為目標層
在目標層取樣一個模版m作為目標模版
在目標模版中取樣一個後繼節點i
在目標模版中取樣一個前置節點j
隨機替換當前操作o_k^{(\ell -1)}為其它操作o_{k^{‘}}^{(\ell -1)}

對於當前層級只有兩層的，第一步直接將\ell設為2，變異可總結為公式4，\ell,m,i,j,k^{‘}從各自區域的均勻分布中隨機抽樣得到，上面的突變足夠對模版產生3種修改：

添加邊：o_k^{(\ell -1)}=none，o_{k^{‘}}^{(\ell -1)}\ne none
修改存在的邊：o_k^{(\ell -1)}\ne none，o_{k^{‘}}^{(\ell -1)}\ne none，o_k^{(\ell -1)}\ne o_{k^{‘}}^{(\ell -1)}
刪除存在的邊：o_k^{(\ell -1)}\ne none，o_{k^{‘}}^{(\ell -1)}= none

Initialization

基因指代完整的網路，基因的種群初始化包含兩個步驟:

建立一個不重要的基因，每個模版都使用identity進行連接
對基因進行大批量的隨機變異來多樣化

對比以前的研究使用常見的網路進行基因初始化，這樣的初始化不僅能很好地覆蓋不常見的網路的搜索空間，還能去除人工初始化帶來的傳統偏向

Search Algorithms

論文的進化演算法基於錦標賽選擇(tournament selection)，首先對初始化的種群網路進行訓練和測試得到分數，然後從種群中隨機獲取5%的基因，表現最好的基因進行突變得到新網路，在訓練和測試後放入種群中，重複進行上述選取與放回，種群數量不斷增大，最終取種群表現最好的基因
論文也使用隨機搜索進行實驗，基因種群隨機生成，然後進行訓練和驗證，選取最好的模型，這種方法的主要好處在於能整個種群並行化計算，減少搜索時間

Implementation

論文使用非同步分散式進行實現，包含一個controller和多個worker，分別負責基因的進化和測試，兩者共享一個記憶體表格\mathcal{M}，記錄基因及其準確率(fitness)，還有一個數據隊列\mathcal{Q}，包含待測試的基因

當有worker空餘時，controller使用錦標賽選擇從\mathcal{M}中選擇一個基因進行突變，然後放到隊列\mathcal{Q}中等待測試

worker從\mathcal{Q}中拿到待測試的基因，測試後放到\mathcal{M}中，訓練是從頭開始訓練的，沒有使用權值共享加速

Experiments and Results

Experimental Setup

在實驗中，沒有對整體網路進行搜索，而是使用提出的方法進行卷積單元(cell)的搜索，這樣能夠在小網路上快速進行網路測試然後遷移到較大的網路。具體的各結構如圖2，每個cell後面接$2c維度和stride=2的$3\times 3分離卷積，用於升維和降低解析度，最後一個cell後面接c維度和stride=1的$3\times 3$分離卷積

Architecture Search on CIFAR-10

200卡，初始種群為200，層級L=3，每層模版的操作分別為M_1=6，M_2=6和M_3=1，每層(\ell \ge2)的節點圖分別為|G^{(2)}|=4和|G^{(3)}|=5，層2的模版跟一個跟模版輸入維度一樣$1\times 1$的卷積來降維。對於用於對比的不分層的搜索方法，則使用11個節點的計算圖。從圖3來看，論文提出的方法在收斂速度、準確率和參數量上都不錯