從NAS到Apollo，最佳化方法如何助力設計空間探索

摘要

不管是AutoML中的自動化調參和神經架構搜尋（Neural Architecture Search, NAS），還是Google在硬體架構設計方面的最新研究工作[1]，最佳化方法都在空間設計探索中扮演著非常重要的角色。最佳化方法種類繁多，適用場景也可能會不同。本文藉助當前熱門研究方向NAS的空間設計問題，開展了對主流最佳化方法的研究，主要內容包括最佳化方法類別（黑盒子最佳化、可微分方法以及其他加速方法）、NAS公開資料集、拓展思考等。

因篇幅較長，此次研究分為兩部分。本篇為第一部分，主要研究和分析了黑盒子最佳化(Black-box optimization, BBO)，以及用於NAS空間設計的三種主流黑盒子最佳化方法，即進化演算法(Evolutionary algorithm)、強化學習（Reinforcement learning）、貝葉斯最佳化(Bayesian optimization)。在後續的第二部分中，將研究基於可微分的非黑盒子方法DARTS（Darts : Differentiable architecture search），以及避免重複從零開始訓練的“weight sharing”等最佳化加速思想，並對現有最佳化方法進行評述。

黑盒子最佳化

黑盒子最佳化方法的一個顯著特徵是“derivative-free”。如圖1所示，該方法只關注盒子兩端的輸入

和輸出

，而從輸入到輸出之間的對映關係

卻不給予明確的形式化表示，因此也無法計算函式

的derivative。在BBO中，函式

又稱為目標函式，求解目標是找到輸入

使得函式

最大化，函式

可能是Apollo硬體架構探索中的加權平均的執行時間或者是NAS中的探索模型在測試資料上的準確率。

黑盒子方法適用於很多複雜、難解的最佳化問題，尤其當計算和獲取函式值

在實際問題中非常困難的時候，這也是NAS和Apollo經常遇到的挑戰。例如，在硬體架構探索的過程中，評估一次硬體配置的效能是一個漫長耗時的過程，導致不可能在實際應用中收集足夠的輸入

和輸出資料

。同樣的問題也出現在NAS中，尤其是訓練超大規模模型，如引數量達數萬億的Switch Transformer。這種表達目標函式所需要的資料不足經常在最佳化過程中遇到，在架構探索中表現地尤為突出。

圖1：黑盒子最佳化

進化演算法(Evolutionary algorithm，EA)

進化演算法的靈感來源於大自然的生物進化，是基於自然選擇和遺傳等生物機制的一種搜尋方法，與傳統的基於微積分的方法相比，該方法不依賴於空間是否具有可導性質，具有自適應、自學習、自組織地進行全域性探索的特點。

圖2：進化方法流程圖

進化演算法的基本思想是，從給定群體中選擇適應性較強的子種群作為進化的樣本，透過基因遺傳等方式產生新個體，然後根據某種評估標準對新舊個體進行篩選，從而得到具有多樣性、適應能力更強的新種群。圖2包含了進化演算法的四個主要步驟：選擇(Selection)、交叉（Crossover）、變異（Mutation）、更新（Update），很多變種方法都是在其中一個或者多個步驟進行調整，如文[2]在update時引入”age”屬性，使新種群中最大程度地保留新個體。在上述步驟中，交叉、變異是兩個比較重要的基因遺傳操作，現做簡單介紹如下：

交叉：針對兩個配體的基因序列，在每個序列上選擇一定數量（可以是1個或者是多個）的交叉點，並進行相應位置的基因互換。在圖3(a)中，分別對雙親基因在第三個基因座的基因值進行了互換。交叉方式有多種方式，根據交叉位置的數量可分為單點交叉、兩點交叉、多點交叉；如果兩個配對個體的每個基因座上都以相同的交叉機率進行交叉，則稱之為均勻交叉；如果兩個配體隨機產生兩個交叉點，然後按照隨機產生的整數進行基因互換，則稱為均勻兩點交叉。
變異：針對單個個體的基因序列的某些基因值做出修改。一般的流程是，對種群內的所有個體以事先設定的變異機率判斷是否進行變異，然後對進行變異的個體隨機選擇基因座進行變異。在圖3(b)中，將第三個基因座的基因值0替換成1。

圖3：兩種基因遺傳操作

在使用進化演算法時，需要先完成相關最佳化問題到基因式編碼的處理。例如，在將進化演算法用於NAS時，首先需要對神經網路結構進行編碼。文[3]採用二進位制編碼（如圖4中的1-00-111）來描述一個神經網路結構，其中節點表示對輸入資料或者前一層輸出資料的操作，如卷積核大小為3×3的卷積操作 conv 3×3。然後，根據操作的先後順序繪製相應的有向圖，其中連線節點的邊表示前後緊鄰的兩個操作。文[3]按照圖中兩個節點之間是否有邊定義二進位制序列，1代表相鄰兩個節點有邊連線；反之，則無。如果將這個二進位制序列中的1變異為0，表示對應的兩個卷積操作失去現有的操作順序。在完成二進位制編碼之後，進化方法中的交叉、變異等基因遺傳操作同樣適用於NAS中的二進位制序列，不同基因值的序列對應於不同的神經網路結構。

圖4：神經網路結構表示方法(來源[3])

強化學習(Reinforcement learning)

與進化演算法中以卷積核操作為基本單元來定義神經網路結構類似，文[4]將決定每層卷積相關的引數（如卷積核寬度、高度、卷積核數量等）選擇看成字串序列的生成問題，從而轉化為適用強化學習的序列決策問題。該文的思路是透過基於RNN控制器生成字串序列，字串的長度由RNN決定，如圖5所示。從整體上來看，為了最佳化由該字串描述的神經網路結構，作者將每次新生成的字串作為反饋重新用於訓練RNN，如圖6所示。其中，輸出的一系列字串看成是強化學習中的action，由字串描述的神經網路在測試集上的準確率作為reward。可以看出，強化學習只是用於訓練控制器，而不直接參與字串序列的生成過程。除了NAS，強化學習也用於軟硬體架構協同設計[5]。進化演算法是現在NAS問題的主流設計思想，也可以與遷移學習進行完美結合[1，8]。

圖5：基於RNN的神經網路卷積核生成器(來源[4])

圖6：基於RNN的控制器(來源[4])

貝葉斯最佳化(Bayesian optimization)

貝葉斯最佳化透過基於目標函式

的過去評估結果來搜尋更優的設計點

，包含代理函式（surrogate function）和採集函式(acquisition function)兩個重要函式的設計和選擇。其中，前者用於近似目標函式

，後者用於評估和篩選下一個設計點，並將之與當前所有設計點一起來更新代理函式。貝葉斯方法與其他隨機取樣方法的不同之處在於，在嘗試下一個設計點時，透過貝葉斯公式使得先驗與後驗分佈進行關聯，從而更好地利用現有設計點，來避免之後的無效探索，演算法流程如圖7所示。首先，在觀察到資料

，其中

為已經嘗試過的設計點的數量，透過採集函式尋找下一個可能使目標函式更優的設計點

，形象化表示如圖8(a)所示，其中紅色下三角

是根據採集函式選擇出來的下一個設計點，黑色實圈

是當前已經選擇的設計點。常用的採集函式有Probability of improvement (PI)、Expected improvement(EI)，其中EI能解決PI面對的區域性最優問題。根據最新的觀察資料

，更新目標函式分佈

，也就是目標函式的後驗分佈。

圖7：貝葉斯最佳化流程（來源文[6]）

在貝葉斯最佳化中，高斯程序(Gaussian process, GP)是常用的代理函式。簡單來說，高斯程序是一個描述高斯函式的函式。例如，在圖8(b)中，在給定設計點

，透過代理函式計算得到的是在該點的均值為

、方差為

高斯分佈，而不是單個值。在選擇下一個設計點時，通常會在當前均值的利用(Exploitation)以及由均值和方差確定的範圍內進行的探索（Exploration）之間進行權衡。有關貝葉斯最佳化的更多細節請參考文[6]。

（a）採取函式與近似函式的設計點選取

(b)高斯程序

圖8：基於高斯程序的貝葉斯最佳化示意圖（來源文[6]）

與進化演算法、強化學習方法類似，在使用貝葉斯方法之前也需要對NAS進行編碼，常見做法是採用有向圖的處理方式，如文[7]。貝葉斯最佳化方法中的一個要素是描述高斯程序的核函式，文[7]根據有向圖重新定義了兩個變數，用於描述和更新核函式。

總結

空間設計探索是NAS和Apollo的重要研究內容，本文從最佳化方法在空間設計探索中的助力作用，深入研究了進化演算法、強化學習和貝葉斯最佳化這三種主流的黑盒子最佳化方法，希望能幫助相關研究人員更快速地瞭解這些方法的精髓。

由於水平有限，文中存在不足的地方，請各位讀者批評指正，也歡迎大家參與我們的討論。

參考文獻

[1]Yazdanbakhsh, Amir,et al."Apollo:Transferable Architecture Exploration." arXiv: 2102.01723.

[2]Real,Esteban,et al."Regularized evolution for image classifier architecture search." AAAI, 2019.

[3]Xie,Lingxi,et al."Genetic CNN.", ICCV 2017.

[4]Zoph,Barret,et al."Neural architecture search with reinforcement learning." ICLR, 2017.

[5]Zhou,Yanqi, et al."Rethinking co-design of neural architectures and hardware accelerators." arXiv:2102.08619.

[6]Brochu,Eric, et al."A tutorial on Bayesian optimization of expensive cost functions,with application to active user modeling and hierarchical reinforcement learning." arXiv:1012.2599.

[7]Kandasamy,Kirthevasan,et al."Neural architecture search with Bayesian optimisation and optimal transport.", NeurIPS 2018.

[8]Wong,Catherine,et al."Transfer learning with neural AutoML.", NeurIPS 2018.

往期推薦

1、貝葉斯方法與深度學習的結合及應用（1）

2、貝葉斯方法與深度學習的結合及應用（2）

3、機率圖模型在深度學習的應用