MetaQNN : 與Google同場競技，MIT提出基於Q-Learning的神經網路搜索 | ICLR 2017

2020 年 4 月 10 日
筆記

論文提出MetaQNN，基於Q-Learning的神經網路架構搜索，將優化視覺縮小到單層上，相對於Google Brain的NAS方法著眼與整個網路進行優化，雖然準確率差了2～3%，但搜索過程要簡單地多，所以才能僅用100GPU days就可以完成搜索，加速240倍。論文本身是個很初期的想法，可以看到搜索出來的網路結構還是比較簡單的，也需要挺多的人工約束。整體而言，論文的輸出的搜索思想還是很重要的，有很多參考的地方

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

論文: Designing Neural Network Architectures using Reinforcement Learning

論文地址：https://arxiv.org/abs/1611.02167

Introduction

論文提出MetaQNN演算法，使用基於強化學習的meta-modeling procedure來自動化CNN結構搭建過程。該方法首先搭建一個全新的Q-learning代理，學習如何發現性能好的CNN結構，發現過程先按順序選擇網路每層的參數，然後對搜索到的網路進行訓練和測試，並將測試準確率作為reward，在學習過程中使用了經驗回放(experience replay)進行加速

Background

將代理學習最優路徑的任務為有限環境(finite-horizon)內的馬爾可夫決策過程(Markov Decision Process, MDP)，將環境限制為有限的能夠保證代理在一定time step後停止。限制離散的有限狀態空間$mathcal{S}$以及動作空間$mathcal{U}$，對於狀態$s_i in S$，存在可供代理選擇的選擇的動作集$mathcal{U}(s_i)in mathcal{U}$。由於環境的隨機轉移性，狀態$s_i$選擇動作$uin mathcal{U}(s_i)$轉移到$s_j$的概率為$p_{s^{‘}|s,u()}(s_j|s_i,u)$，這可能是代理未知的。在每個time step $t$時，代理的reward $r_t$可能也是隨機的，由狀態$s$轉移到$sprime$以及動作$u$的概率$p_{sprime|s,u}(s_j|s_i,u)$決定

代理的目標是最大化所有可能路徑的期望reward，即${max}_{mathcal{T}i in mathcal{T}}R{mathcal{T}}$，單個路徑的reward計算如公式1

儘管限制了狀態空間和動作空間，代理仍然能組合出大量的路徑，所以用強化學習來進行優化。將最大化問題迭代成多個子問題，優化每個子問題到最優解。對於狀態$s_iin S$以及後續動作$uin mathcal{U}(s_i)$，定義最大化期望reward為$Q^{*(s_i,u)$，$Q}(cdot)$為action-value函數，單個$Q^(s_i,u)$稱為Q-values，Q-values的最優解為公式2，即Bellman』s Equation，為當前動作的回報的期望與下個狀態的Q值最大的動作的加權求和

一般不能直接學習到概率來求解Bellman』s Equation，可以轉化為迭代式優化，如公式3，為Q-learning的一種簡單形式。只要每種轉移取樣足夠多次${lim}_{tto infty}Q_t(s,u)=Q^*(s_i,u)$，就可以很好地逼近公式2，更新公式包含兩個參數:

$alpha$為Q-learning rate，決定新資訊對舊資訊的權重
$gamma$為折扣率(discount factor)，決定短期reward對於長期reward的權重

Q-learning是model-free的，代理的學習過程不用構造環境變數的估計，也是off policy的，意味著可以在非最優的整體行為分布下依然可以學習到最優的策略。論文使用$epsilon$-greedy策略，以概率$epsilon$選取隨機動作，以概率$1-epsilon$選取貪婪動作${max}_{uin mathcal{U}(s_i)}Q_t(s_i, u)$，將$epsilon$逐漸從1降為0，這樣代理能從探索(exploration)階段慢慢變為榨取(exploitation)階段。由於探索階段花費較大，所以使用經驗回放來加速收斂，使用記錄探索的路徑和reward給予代理進行公式3學習

Designing Neural Network Architectures with Q-learning

代理的學習任務即按順序地選取神經網路層，圖2(a)展示了靈活的狀態空間和動作空間，圖2(b)則為代理可能選擇的潛在路徑並用該路徑構造網路
將層選擇過程建模為馬爾可夫決策過程，假設一個網路中表現好的層也能在別的網路中有很好的表現。代理按順序通過$epsilon$-greedy策略進行選擇直到達到停止狀態，從代理的路徑中構建CNN網路，然後進行訓練並將準確率回饋給代理，將準確率和網路存到回放存儲(replay memory)中，定期從回放存儲中取樣進行公式3的Q-values更新
MetaQNN主要包含三個設計理念：

減少CNN層定義來簡化狀態參數
定義代理可選擇的動作集，用以狀態轉移
平衡state-action空間大小和模型容量的關係，代理需要大量探索進行收斂

The State Space

每個狀態為一組層相關參數，如表1所示，共有6種層類型，網路每層都預有一個layer depth來表示當前層的位置，從而進行action的約束，保證網路為有向無環圖(DAG)

為了避免感受域大於特徵圖大小，每層有一個representation size(R-size)，為特徵圖大小，根據R-size進行兩個action的約束，限制R-size為n的狀態的action的感受域必須小於或等於n來保證輸出不會太小，而為了更好的約束，將R-size值分為3個離散區間，但這有可能導致生成的狀態在另一個不同的區間，如圖A1所示

The Action Space

對代理的動作進行了限制，從而約束state-action空間大小和簡化學習過程：

允許代理在任何節點終止，可以從非終止狀態直接轉移到終止狀態。另外，只允許層$i$轉移到層$i+1$，保證無環，最大層僅能轉移為終止層
限制全連接層的數量最多為兩層，防止參數過多，另外全連接層轉移到全連接層必須滿足consecutive FC的限制，而且全連接層只能轉移為neurons不大於轉移前的全連接層或終止狀態
卷積狀態能轉移到其它任何狀態，而池化狀態只能轉移到非池化狀態，只有Representation size為$[8,4)$和(4,1]的層能轉移到全連接層

Q-Learning Training Procedure

設置公式3的Q-Learning rate($alpha$)為0.001，discount factor($gamma$)為1，$epsilon$的下降如表2，在$epsilon=1$的探索階段訓練大量的網路，其它值則保證代理在壓榨前有充足的時間來繼續探索，在$epsilon=0.1$時停止

在整個訓練過程使用回放字典(replay dictionary)存放網路結構及其測試的準確率，如果取樣的網路有已經測試過的，則直接拿之前的準確率，不再重新訓練，在當前批次網路取樣和訓練完後，從回放字典中隨機選取100個網路對所有轉移的進行公式3的Q-value更新，更新順序以時間倒序先對後面的Q-value進行更新

Result

共使用10GPU訓練8-10天，從所有模型中選取10個進行更長時間的訓練

Model Selection Analysis

Prediction Performance

CONCLUSION

論文提出MetaQNN，基於Q-Learning的神經網路架構搜索，將優化視覺縮小到單層上，相對於Google Brain的NAS方法著眼與整個網路進行優化，雖然準確率差了2～3%，但搜索過程要簡單地多，所以才能僅用100GPU days就可以完成搜索，加速240倍。但論文本身是個很初期的想法，可以看到搜索出來的網路結構還是比較簡單的，沒有殘差連接和並行層，也需要挺多的人工約束。整體而言論文的輸出的搜索思想還是很重要的，有很多參考的地方

APPENDIX E — Top Topologies Selected by Algorithm

如果本文對你有幫助，麻煩點個贊或在看唄～
更多內容請關注微信公眾號【曉飛的演算法工程筆記】

MetaQNN : 與Google同場競技，MIT提出基於Q-Learning的神經網路搜索 | ICLR 2017

Introduction

Background