PNAS
2018-ECCV-Progressive Neural Architecture Search
來源：ChenBong 博客園
- Johns Hopkins University(霍普金斯大學) && Google AI && Stanford
- GitHub：300+ stars
- Citation：504
Motivation
current techniques usually fall into one of two categories: evolutionary algorithms(EA) or reinforcement learning(RL).
Although both EA and RL methods have been able to learn network structures that outperform manually designed architectures, they require significant computational resources.
目前的兩種nas方法，EA和RL，存在計算代價高昂的問題
Contribution
we describe a method that requiring 5 times fewer model evaluations during the architecture search.
只需要評估1/5的模型，
We propose to use heuristic search to search the space of cell structures, starting with simple (shallow) models and progressing to complex ones, pruning out unpromising structures as we go.
漸進式的搜索，從淺層網路開始，逐步搜索復雜網路，
Since this process is expensive, we also learn a model or surrogate function(替代函式) which can predict the performance of a structure without needing to training it.
提出一種近似評估模型好壞的評估函式（預測器），直接預測模型性能，而不是從頭訓練候選網路，
Several advantages：
First, the simple structures train faster, so we get some initial results to train the surrogate quickly.
代理網路比較小，訓練速度快（代價可以忽略不計），
Second, we only ask the surrogate to predict the quality of structures that are slightly different (larger) from the ones it has seen
預測器只需要預測稍微不同的網路，
Third, we factorize(分解) the search space into a product(乘積) of smaller search spaces, allowing us to potentially search models with many more blocks.
將大的搜索空間分解為小的搜索空間的乘積，
we show that our approach is 5 times more efficient than the RL method of [41] in terms of number of models evaluated, and 8 times faster in terms of total compute.
效率相比RL方法提高5倍，總計算量快了8倍，
Method
Search Space
we first learn a cell structure, and then stack this cell a desired number of times, in order to create the final CNN.
先學習cell結構，再堆疊cell到目標層數，
一個cell接收HxWxF的tensor，如果cell的stride=1，輸出HxWxF的tensor，如果stride=2，輸出H/2 x W/2 x 2F的tensor，
一個cell由B個block組成，每個block有2個input和1個output，每個block可以用一個五元組表示\(\left(I_{1}, I_{2}, O_{1}, O_{2}, C\right)\)，第c個cell的輸出表示為\(H^c\)，第c個cell的第b個block的輸出表示為\(H^c_b\)，
每個block的輸入為當前cell中，在 {此block之前所有block的輸出} 和 {上一個cell的輸出，上上個cell的輸出} 的集合，
Operator的選擇空間有8種操作，
we stack a predefined number of copies of the basic cell (with the same structure, but untied weights 不繼承權重 ), using either stride 1 or stride 2, as shown in Figure 1 (right).
找到最佳cell結構后，堆疊預定義的層數，構成右邊的完整網路，不繼承權重（重新訓練），
The number of stride-1 cells between stride-2 cells is then adjusted accordingly with up to N number of repeats.
Normal cell（stride=1）的數量，取決于N（超參），
we only use one cell type (we do not distinguish between Normal and Reduction cells, but instead emulate a Reduction cell by using a Normal cell with stride 2),
我們沒有區分normal cell 和Reduction cell，僅將Normal cell的stride設定為2作為Reduction cell，
Progressive Neural Architecture Search
Many previous approaches directly search in the space of full cells, or worse, full CNNs.
之前的方法直接搜索完整的cell結構，更糟糕的是整個cnn，
While this is a more direct approach, we argue that it is difficult to directly navigate in an exponentially large search space, especially at the beginning where there is no knowledge of what makes a good model.
盡管這種方式很直接，但搜索空間太大，而且一開始我們沒有任何先驗知識指導我們在巨大的搜索空間往哪個方向搜索，
從每個cell含有1個block開始搜索，訓練所有可能的\(B_1\)，用\(B_1\)訓練預測器，然后將\(B_1\)展開為\(B_2\)，
訓練所有可能的\(B_2\)代價太大，我們使用預測器來評估所有\(B_2\)-cell的性能并選出最佳的K個\(B_2\)-cell，重復此程序（用選出來K個\(B_2\)-cell訓練預測器，將選出的K個\(B_2\)-cell展開為\(B_3\)，再用預測器選出最佳的K個...），
Performance Prediction with Surrogate Model
Requirement of Predictor：
- Handle variable-sized inputs（接受可變輸入）
- Correlated with true performance（預測值與真實值得相關性）
- Sample efficiency（簡單高效）
- The requirement that the predictor be able to handle variable-sized strings immediately suggests the use of an RNN.
Two Predictor method
RNN and MLP（多層感知機）
However, since the sample size is very small, we fit an ensemble of 5 predictors, We observed empirically that this reduced the variance of the predictions.
由于樣本很簡單，因此集成5個預測器（RNN-ensemble，MLP-ensemble），可以減少方差，
Experiments
Performance of the Surrogate Predictors
we train the predictor on the observed performance of cells with up to b blocks, but we apply it to cells with b+1 blocks.
在{B=b}上訓練，在{B=b+1}的集合上預測，
We therefore consider predictive accuracy both for cells with sizes that have been seen before (but which have not been trained on), and for cells which are one block larger than the training data.
同時考慮在{B=b}的未訓練的cell集合上的預測準確率，和{B=b+1}的cell集合上的預測準確率，
在所有{B=b}的cell集合中隨機選擇10k個作為資料集\(U_{b,1 :R}\)，訓練20個epochs，
randomly select K = 256 models (each of size b) from \(U_{b,1 :R}\)to generate a training set \(S_{b,t,1:K}\);
從資料集U中隨機選擇256個作為每輪的訓練集S，
一共會訓練20*256=5120個資料點，
We now use this random dataset to evaluate the performance of the predictors using the pseudocode(偽代碼) in Algorithm 2, where A(H) returns the true validation set accuracies of the models in some set H.
A(H) 回傳cell的集合H訓練后真實的準確率，
當B=b時，訓練集為所有{B=b}的cell的一個子集，第一行為在所有{B=b}的cell的訓練集(256*20=5120)上的預測結果和真實結果的相關性，
第二行為在所有{B=b+1}的cell的資料集(10k)上的預測結果和真實結果的相關性，
We see that the predictor performs well on models from the training set, but not so well when predicting larger models. However, performance does increase as the predictor is trained on more (and larger) cells.
預測器在訓練集{B=b}上表現良好，但在較大的資料集{B=b+1}上表現不夠好，但隨著b的增加，越來越好，
We see that for predicting the training set, the RNN does better than the MLP, but for predicting the performance on unseen larger models (which is the setting we care about in practice), the MLP seems to do slightly better.
RNN方法的預測器在訓練集{B=b}上表現更好，MLP在較大的資料集{B=b+1}上表現更好(我們關心的)
Conclusion
The main contribution of this work is to show how we can accelerate the search for good CNN structures by using progressive search through the space of increasingly complex graphs
使用漸進式（cell的深度逐漸增加）的搜索加速NAS
combined with a learned prediction function to efficiently identify the most promising models to explore.
使用可學習的預測器來識別潛在的最優網路，（引入P網路來搜索目標網路的最佳結構，eg. 用C網路來搜索B網路的最佳結構，而B網路又是來搜索A網路的最佳結構，套娃）
The resulting models achieve the same level of performance as previous work but with a fraction of the computational cost.
用小代價達到了了SOTA
Appendix
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/24852.html
標籤：其他
上一篇：Axure使用中繼器報錯