Genetic CNN: 經典NAS演算法，遺傳演算法的標準套用 | ICCV 2017
- 2020 年 4 月 14 日
- 筆記
論文將標準的遺傳演算法應用到神經網路結構搜索中，首先對網路進行編碼表示，然後進行遺傳操作，整體方法十分簡潔，搜索空間設計的十分簡單，基本相當於只搜索節點間的連接方式，但是效果還是挺不錯的，十分值得學習
來源：曉飛的演算法工程筆記 公眾號
論文: Genetic CNN
Introduction
為了進行神經網路架構搜索，論文將網路限制為有限的深度，每層為預設的操作，但仍然存在很多候選網路，為了有效地在巨大的搜索空間中進行搜索，論文提出遺傳演算法進行加速。首先構造初始種群，然後對種群內的個體進行遺傳操作，即選擇、交叉和變異，通過識別的準確率來判斷其適應性，最終獲得強大的種群
Our Approach
Binary Network Representation
目前SOTA的網路大都由多個階段構成，每個階段內的層具有相同的維度，而相鄰的階段則用池化進行連接。借鑒這種思想，定義網路有$S$個階段組成，$s$-th階段($s=1,2,…,S$)包含$K_s$個節點，標記為$v_{s,k}$，$k_s=1,2,…,K_s$，節點按順序排列，僅允許低序號節點連接到高序號節點，對節點的所有輸入進行element-wise sum，每個節點代表卷積操作，卷積後都接BN+ReLU，網路不加入全連接層
每個階段使用$1+2+…+(K_s-1)=\frac{1}{2}K_s(K_s-1)$位來表示內部連接，第一位表示連接$(v_{s,1},v_{s,2})$，第二位和第三位則表示連接$(v_{s,1},v_{s,3})$和$(v_{s,2},v_{s,3})$，以此類推，最後$K_s-1$位則表示$v_{s,K_s}$與其它節點的連接。對於$1\le i\le j\le K_s$，如果$(v_{s_i}, v_{s,j})=1$，則$v_{s_i}$和$v_{s,j}$有邊，$v_{s,j}$將$v_{s,i}$的輸出作為element-wise sum的一部分。編碼如圖1所示，但是Stage 2的編碼好像有點問題，按照圖片應該是0-10-000-0011
-
Technical Details
每個階段默認有兩個節點，分別為輸入節點$v_{s,0}$和輸出節點$v_{s,K_s+1}$，輸入節點使用卷積將前一個階段的特徵進一步提取，然後傳遞給沒有輸入的節點中，輸出節點則element-wise sum所有沒被使用的節點的輸出，然後進行一次卷積再接池化層，這裡有兩種特殊的情況：
-
如果節點$v_{s,i}$被隔離了，沒有非默認輸入和輸出，則直接忽略，如圖1 B2節點
-
如果當前階段沒有連接，全部為0，則只進行一次卷積（原本至少輸入輸出節點都會進行一次）
-
Examples and Limitations
這樣的編碼形式可以編碼目前的主流分類結構，但也有很多局限性：
- 目前的連接方式只有卷積和池化，不能使用其它比較tricky的模組，例如Maxout
- 每個階段的卷積核是固定的，阻礙了multi-scale特徵的融合
Genetic Operations
遺傳演算法過程如圖1所示，共進行$T$代遺傳，每代包含3個操作，選擇、變異和交叉，適應值通過訓練後的模型在驗證集上獲得
-
Initialization
初始化一個隨機模型集合${\mathbb{M}{0,n} }{n=1}N$，每個模型是長度為$L$的二進位串，串上每位服從伯努利分布$b_{0,n}l \sim \mathcal{B}(0.5)$,$l=1,2,…,L$，然後訓練並測試每個模型的準確率，這裡的初始化策略影響不大
-
Selection
在每一代種群生成前都會進行選擇操作，在$t$-th代前，個體$\mathbb{M}{t-1,n}$的適應性為$r{t-1,n}$，直接影響$\mathbb{M}{t-1,n}$在選擇階段存活的概率。具體選擇使用俄羅斯輪盤選擇法(Russian roulette)，每個個體選取的概率與$r{t-1,n}-r_{t-1,0}$成比例，$r_{t-1,0}$為上一代的最低適應性。選擇後的保持種群總數不變，所以一個個體可能會被選擇多次
-
Mutation and Crossover
變異的操作包含對二進位串每個位進行概率為$q_M$的反轉，而交叉的操作則同時改變兩個個體，以概率$q_C$對個體間的stage進行交換。個體變異的概率為$p_M$，每組個體交叉的概率為$p_C$，具體的操作看演算法1，雖然這種方法很簡單，但是十分有效
-
Evaluation
在上述操作後，對每個個體$\mathbb{M}_{t,n}$進行訓練以及測試來獲得適應值，如果該個體之前已經測試過了，則直接再測一遍然後求平均，這樣能移除訓練中的不確定性
Experiments
MNIST Experiments
實驗配置，$S=2$，$(K_1,K_2)=(3,5)$，$L=13$，種群初始$N=20$，共一次$T=50$，$p_M=0.8$,$q_M=0.1$,$p_C=0.2$,$q_C=0.3$，一共只產生$20\times (50+1)=1020\le 8192$個網路，耗時2 GPU-day
CIFAR10 Experiments
實驗配置，$S=3$，$(K_1,K_2,K_3)=(3,4,5)$，$L=19$，種群初始$N=20$，共一次$T=50$，$p_M=0.8$,$q_M=0.05$,$p_C=0.2$,$q_C=0.2$，一共只產生$20\times (50+1)=1020\le 524288$個網路，耗時17 GPU-day
CIFAR and SVHN Experiments
將CIFAR-10中學習到的網路直接在別的數據集上進行測試
ILSVRC2012 Experiments
將圖5中的兩個網路在ILSVRC2012上進行訓練，先用VFFNet的stem進行下取樣，再過圖5的網路，最後接全連接進行分類
CONCLUSION
論文將標準的遺傳演算法應用到神經網路結構搜索中，首先對網路進行編碼表示，然後進行遺傳操作，整體方法十分簡潔，搜索空間設計的十分簡單，基本相當於只搜索節點間的連接方式，但是效果還是挺不錯的，十分值得學習
如果本文對你有幫助，麻煩點個贊或在看唄～
更多內容請關注 微信公眾號【曉飛的演算法工程筆記】
