AccSMBO:一種基于超參梯度和元學習的SMBO加速算法

程大寧 張漢平 夏 粉 李士剛 袁 良 張云泉

1(中國科學院大學 北京 100190)

2(中國科學院計算技術研究所 北京 100190)

3(智鈾科技有限公司 北京 100190)

4(蘇黎世理工大學 瑞士蘇黎世8914)

5(紐約州立大學布法羅分校 紐約 14260)

隨著機器學習技術的發展，自動機器學習技術成為了機器學習的關鍵技術之一[1]，即AutoML技術.當前的機器學習模型的訓練需要大量的超參，超參優化是AutoML的重要部分.

為了解決上述問題，超參優化成為了一個非常熱門的研究方向.近年來研究者提出了不同的超參優化方法，如Hyperband算法SMAC算法、TPE算法等.這些算法將歷史調參信息或者梯度信息作為輸入，使用不同模型對最優超參進行預測，從而迭代求解出最優超參.

基于超參梯度的調優是超參調優的重要手段之一，現有的很多工作已經形式化定義了超參梯度并開發出了相關的調參算法.除了超參梯度，元學習也是現代超參調優的重要研究方向.傳統元學習方法依照任務目標.機器學習模型和數據集的不同對最優調參任務進行分類，并記錄其最優超參值.每次遇到新的機器學習任務時，都從原有的記錄中尋找歷史記錄中這類情況的最優超參.此外，基于經驗的人工調參是現有主流調參手段.相比于調參算法，人工調參可以在機器學習訓練中的不同階段靈活依照經驗調參.

序列模型優化算法(sequential model-based opti-mization algorithms, SMBO)是現在最好的超參優化算法框架[2]之一.然而，作為黑箱優化算法的延伸，傳統的SMBO算法不考慮已有的超參信息.非常顯然的是，合理使用已知的超參信息可以加快黑箱調優算法的收斂速度，提升搜索到的超參的效果.

我們總結出機器學習使用的超參常常滿足2個超參規律，這2個規律往往是在超參調優前可以得到的已知的超參信息：1)超參-效果之間的關系往往是充滿“噪音”的單峰或者單調的函數.這種趨勢上簡單的函數意味著使用傳統SMBO算法求解超參優化問題時，往往使用較少的采樣點即可擬合出總體趨勢.但是超參-效果之間的關系在局部上往往充滿了“噪音”，這意味著過分依賴局部信息，如梯度，過分依賴局部信息會導致擬合函數對總體趨勢的表述變形.2)最優超參的分布情況往往是不均勻的，即有些超參容易取特定的幾個值.

基于上述相關的技術和我們總結的規律，針對SMBO算法，我們考慮2個問題：1)如何使用超參梯度加速調參速度，其中的難點是合理使用超參梯度信息的同時避免局部“噪音”帶來的影響；2)如何使用元學習，替代人工調參中經驗的成分進而加速調參.

本文提出了AccSBMO算法.AccSMBO使用3種方法來優化傳統SMBO算法.

1) 基于第1個超參規律，我們設計了基于梯度的多核高斯過程回歸模型來擬合觀測值和觀測梯度值.基于此，AccSMBO可以更快地建立完整有效的超參-效果模型(也稱作響應面[3]).基于梯度的多核高斯過程回歸模型具有良好的抗噪能力和較少的計算負載.

2) 基于第2個超參規律，AccSMBO使用meta-acquisition函數替代原本的獲取函數.基于元學習數據集，AccSMBO尋找出現最佳超參概率較高的范圍(稱為最佳超參高概率范圍)，并使用EPDF(empirical probability density function)表述這一范圍.在每次AccSMBO迭代中，AccSMBO算法基于EPDF提供的信息，在最佳超參高概率范圍內選擇預測最優值.

3) 同樣基于第2個超參規律，我們在并行方法上設計的策略：在SMBO自然對應的并行算法中，為了充分使用并行資源，將更多并行計算資源用于探索最佳超參高概率范圍，AccSMBO算法使用了基于元學習數據集的并行資源調配方案.這使得在計算超參效果的過程中充分利用計算資源，減少計算過程中同步操作的消耗，同時將計算資源傾斜在最佳超參高概率范圍中.

上述3種方法加快了SMBO的收斂速度：在實驗中，在不同數據集上，從迭代次數上，串行AccSMBO算法的收斂速度是SMAC算法速度的175%～330%，是HOAG算法的100%～150%；從絕對時間上，串行AccSMBO算法的收斂速度是SMAC算法的167%～329%，是HOAG算法的109%～150%.從絕對時間上，使用4個worker的并行AccSMBO算法的收斂速度是SMAC算法的322%～350%，是HOAG算法的145%～316%.從調優結果上，AccSMBO算法和SMAC算法在所有數據集上都找到了最優效果超參，HOAG算法在小規模數據集上未能收斂.

1 相關工作

近年來，自動機器學習工具相繼被開發出來，如谷歌的AutoML,Auto-Weka，AutoSklearn等[4].這些工具使用了不同的超參優化算法.

在上述的應用中，研究人員通常在所有參數空間使用網格搜索，但隨著超參數量的增加，這種搜索很快變得令人望而卻步.

貝葉斯優化算法[2-5]是最常用的用于超參數調優的黑箱優化算法.貝葉斯優化算法通過假設損失函數的先驗分布，然后根據新的觀測值不斷更新該先驗分布.每一個新的觀測值都是根據一個獲取函數計算得來，這個函數負責維持整個探索過程的開發和探索平衡(exploitation and exploration trade off)，使得新的觀測值能帶來更好的結果，或者有助于獲得更多關于超參-效果函數的信息.

隨機優化方法是現在最常用的超參調優方法，例如網格搜索、隨機搜索、啟發式算法和神經網絡算法[6]，但是這類算法效率低下.

傅里葉分析法是近幾年發力的超參調優算法，如Harmonica[7]算法.傅里葉分析法也叫作低階布爾函數多項式擬合法，這類方法首先隨機選取抽樣點，再使用正交函數組擬合這些采樣點[8-10]，進而使用擬合函數預測最優超參值.

決策理論方法考慮的是在現有超參候選集中使用最少的資源選出最佳超參，這類算法在機器學習模型的訓練中逐步尋找該模型可能的效果下限，早停效果不好的機器學習模型的訓練[11].這種算法最常見的是Hyperband算法[12].

在用于超參調優的貝葉斯優化算法[2,4,13]中，SMBO算法[2]框架使用最為廣泛.SMAC[2](sequential model-based algorithm configuration)，TPE[14](tree-structured parzen estimator)和基于高斯過程的SMBO算法[15]是當前效果最好、求解速度最快的SMBO算法實現.

隨著計算平臺的發展，并行計算環境逐漸成為了機器學習計算環境的主流.并行貝葉斯調優算法也逐漸成為了研究熱點[16-19].

如何使用元學習(metalearning)[20]和超參梯度[21-23]加速自動調參優化過程是AutoML領域中討論最多的話題之一.

2 研究背景

2.1 問題定義

本文使用形式化定義超參優化[4]問題：

給定一個由參數λ所影響的學習算法A(λ)，和數量有限的數據集D={(x1,y1),(x2,y2),…,(xm,ym)}，超參優化是尋找最優超參λ使超參-效果函數f取到最小值的任務.f需要由算法A(λ)和由數據集D產生的訓練集Dtrain、驗證集Dvail來計算得出.對超參優化問題的表述可表達為

(1)

2.2 算法背景

2.2.1 SMBO算法及其最優實現

SMBO算法是用于超參調優的黑盒優化算法框架.

算法1.SMBO算法.

Repeat

④λ←從③中的超參集中選出最優超參；

⑤ 計算f(λ)；

Until消耗完給定計算資源;

許多研究者提出了不同的算法來填充SMBO算法框架.表1總結了現有效果較好的算法實現.

Table 1 State of the Art Algorithm for SMBO Algorithm Frame表1 SMBO算法中不同步驟可選擇的算法

元學習是提升SMBO算法效果的重要手段.基于元學習方法，SMBO可以在第1輪迭代到第2輪迭代中取到最優或者次最優的超參值.但是，為了通過元學習取得較好的超參初始值，經常需要花費較多成本構建足夠大的元學習數據庫.

為了較好地反映出原函數f(λ)的趨勢，不同研究提出了不同的響應面模型，但是這些模型并沒有考慮如何合理使用梯度信息.在這些模型中，最常使用且效果最好的響應面模型是隨機森林和高斯過程[13].使用隨機森林和高斯過程的SMBO算法實現的是SMAC算法.因此本文實驗的主要benchmark是SMAC算法.

現有效果最好的AC函數是EI(expected improvement)函數[3]，EI函數使用期望下降值作為輸出，EI函數是最為常用的AC函數的選擇.因為我們的加速方法并沒有涉及AC函數的選擇，所以在實驗中使用EI函數作為AC函數.

算法1的第④步的主要目的是從有限個超參中使用最少的資源選擇出效果最好的超參.這一步中最好的算法是Hyperband算法和intensify process.因為加速算法不涉及如何在這一步選擇最優超參，因此在實驗中，AccSMBO算法在這一步使用intensify process算法.

2.2.2 代

在SMBO算法中，本文稱一輪循環為一代(epoch).在每一代中，SMBO算法都需要做相同的工作：構建模型—選擇超參—計算超參效果—寫入歷史，從而SMBO算法在每一代花費的時間基本相同，因此SMBO算法中的一代是測量SMBO算法性能的最小單位.

在本文的實驗中，除了以時間作為衡量指標的實驗外，還會增加以代作為實驗衡量指標的實驗，基于2點原因：

1) 因為算法在代碼實現和運行平臺上的不同，每代所花費的時間在不同情況下也不盡相同，而當初始值和參數設置幾乎一致時，調優過程幾乎是穩定的，所以在讀者復現本實驗時，橫坐標為代的實驗結果可以用較少代價得到復現.

2) 更重要的是，絕大多數算法，如d_KG算法[23]和Hyperband算法[12]的理論結果、理論分析所用的指標均為迭代次數，即代數.所以使用代作為橫坐標可以更好地對應理論結果.

高斯過程是現有最好的響應面的選擇之一[27].基于高斯過程的SMBO算法是最常用的SMBO算法實現之一[15].

本文中，設置λ包含了d個不同的超參.k(·,·)是內核函數(協方差函數).

本文中定義向量

f=(f(λ1),f(λ2),…,f(λn))T,

其中，f維度為n.

定義矩陣Mλ=(λ1,λ2,…,λn)T，其維度是d×n.

定義維度為n×n的內核矩陣K(Mλ,Mλ)：

定義K(λ*，Mλ)形式為

K(λ*,Mλ)=(k(λ*,λ1),k(λ*,λ2),…,k(λ*,λn)).

m(λ*)=γK(λ*,Mλ),
γ=K(Mλ,Mλ)-1f.

協方差函數形式為

var(λ*)=k(λ*,λ*)-
K(Mλ,λ*)K(Mλ,Mλ)-1K(Mλ,λ*).

2.2.4 超參梯度

很多工作都提供了基于超參梯度的優化方法[21,22].超參的梯度可以定義和計算[22]：

現有很多基于超參梯度的優化方法都是基于梯度下降.

2.2.5 元學習數據庫

元學習(metalearning)是加速SMBO算法的重要手段.依照分類或者回歸任務的不同，數據集特征的不同和目標函數的不同，元學習可以提供針對不同情況的最優或者次優的參考超參.元學習數據集記錄了在不同情況下的這些最優超參.SMBO算法可以將元學習提供的參考超參作為初始值，進一步搜索得到更好的超參，從而加快超參搜索速度.

盡管元學習在AutoML中取得了巨大的成功，對于大多數情況，元學習只有在元學習數據集龐大的基礎上才能取得足夠好的效果.當元學習數據集較小時，元學習對AutoML的提升有限.

2.2.6 并行SMBO算法

作為貝葉斯優化算法的一種，SMBO算法也可以先天在并行環境中得到加速.現在最優的貝葉斯優化算法是2018年提出的異步并行貝葉斯優化算法[16].這種優化算法使用異步并行的方法避免了集群間同步的開銷，在工程上受益.這種異步并行的SMBO算法是可以實現在當前主流機器學習框架-參數服務器上的.異步并行的SMBO算法在算法2中給出.

算法2.異步并行SMBO算法.

Worker端:

Repeat

① 計算從server接收預測最佳超參λ；

② 計算λ對應的f(λ)；

③ 將(λ,f(λ))推回server；

Until計算資源耗盡.

Server端:

① 將λ1,λ2,…,λk給worker1,worker2,…,workerk，使得worker1,worker2,…,workerk開始計算f(λ1),f(λ2),…,f(λk)；

Repeat

② 從workeri中接受一個(λpre,f(λpre))組；

⑥λnext←從⑤中的超參集中選最優超參；

⑦ 將λnext發給workeri計算f(λnext)；

Until計算資源耗盡;

3 出發點和主要思想

對于大多數超參，超參—性能函數f(λ)經常呈現2種模式：1)f(λ)的全局變化趨勢簡單，f(λ)在全局上經常呈現為單調函數或單峰函數.但是，超參的效果局部變化趨勢是不穩定的，即充滿了噪音，如圖1所示.圖1中展示了在決策樹和GBDT模型中不同超參對模型效果(log loss)的f(λ).圖1具體呈現了模式1).2)最佳超參的分布不是均勻分布.實際調參時，調參人員經常會提前知道一些先驗的、合理的范圍，即最佳超參高概率存在的范圍.很明顯，元學習數據集可以反映這些信息.通過總結Auto-Sklearn中元學習模塊使用的數據集，圖2展示了在F1范式多分類任務中一些參數的頻度統計情況與其擬合的概率密度分布函數.圖2展示了最佳超參分布不均的特點，同時展示了如何通過函數擬合統計值得到EPDF函數.

Fig. 1 Some of those performance functions are close to unimodal functions or monotonic functions圖1 f(λ)曲線在全局上經常呈現為單峰函數或者單調函數

Fig. 2 The frequency and its EPDF of hyperparameter value for F1 norm multi-class task on sparse dataset圖2 稀疏數據集下F1范式多分類任務中超參分布情況及其EPDF

為了在SMBO算法中充分利用模式1)、模式2)，我們提出了AccSMBO算法，串行AccSMBO在算法3中給出.異步并行AccSMBO算法在算法4中給出.

AccSMBO使用了2種方法提升了傳統串行SMBO算法的效果和一種資源調度方法提升并行SMBO算法的效果.1)AccSMBO使用了基于梯度的多核高斯過程，AccSMBO使用的高斯過程可以最大程度上利用梯度信息，同時可以避免精細擬合梯度信息而導致噪音對擬合過程的負面作用；2)在迭代過程中，AccSMBO使用元學習數據集調整AC函數,即metaAC函數(meta-acquisition functions).metaAC函數可以在最佳超參高概率范圍中有較高輸出，使得AccSMBO算法將更多的搜索資源放在最佳超參高概率范圍中，加快搜索到最佳超參的效率；3)根據元學習數據集，我們優化了并行AccSMBO算法.使在最佳超參高概率范圍中的超參使用更多的計算資源，加快搜索到最佳超參的效率.

算法3.串行AccSMBO算法.

Repeat

③ 使用元學習數據集和AC函數計算metaAC函數；

⑤λ←從④中的超參集中選出最優超參；

⑥ 計算f(λ)；

Until消耗完給定計算資源；

算法4.異步并行AccSMBO算法.

Worker端:

Repeat

① 計算從對應的棧中接收彈出的預測最佳超參λ；

② 計算λ對應的f(λ)；

③ 將(λ,f(λ))推回server；

Until計算資源耗盡.

Server端:

① 將λ1,λ2,…,λk+m給workerk+1,workerk+2,…,workerk+m，使得worker1,worker2,…,workerk+m開始計算f(λ1),f(λ2),…,f(λk+m)；

Repeat

② 從workeri中接受一個(λpre,f(λpre))組；

⑤ 使用元學習數據集和AC函數計算metaAC函數；

⑦λnext1,λnext2,…,λnextq←從⑤中的超參集中選q(q>2)個最優超參；

⑧ 分別判斷λnexti的優先級并壓入stackfast或者stackslow中；

Until計算資源耗盡；

4 AccSMBO算法

4.1 基于梯度的多核高斯過程

4.1.1 數學符號

本節主要介紹后文中使用的額外的數學符號.

本文中，將矩陣的組合簡寫為

Km:n=(Km;Km+1;…;Kn).

4.1.2 基于梯度的多核高斯過程回歸

本文設計了一種新的基于梯度的高斯過程回歸方法，這種算法在算法5中給出.

算法5.基于多核高斯過程回歸算法.

① 使用最小二乘法求解式(5)中的α和β：

(2)

②m(λ*)=K2:n(λ*,Mλ)α+K1(λ*,Mλ)β；

4.1.3 均值函數

在傳統的高斯過程回歸中，均值函數m(λ)是使用內核函數作為基底對觀測點的擬合函數.

f=K1(Mλ,Mλ)α1+K2(Mλ,Mλ)α2+…+
Kd+1(Mλ,Mλ)αd+1,

(3)

(4)

通過式(3)、(4)可解得α1,α2,…,αd+1，則

4.1.4 方差函數

多核高斯過程的方差反映了預測點λ*與觀測點λi之間的距離.對于使用ki(·,·)作為內核的高斯過程，其方差函數的計算方法為vari(λ*)=ki(λ*,λ*)-Ki(Mλ,λ*)Ki(Mλ,Mλ)-1Ki(Mλ,λ*).因為高斯過程的和依舊為高斯過程，和的高斯過程的方差是不同高斯過程方差的和，所以多核高斯過程回歸的數學形式為

4.1.5 抗噪、約近和計算負載的減少

雖然徑向基核函數(radial basis function, RBF)滿足了擬合梯度的要求：提供了足夠多線性無關的內核函數，但計算負載的減少和抗噪能力的增加也是考量的重點之一.正如第3節中提到的，從整體上，f(λ)相對簡單，但曲線的局部充滿了噪音.梯度反映的是曲線的局部信息，而不是f(λ)曲線的總體趨勢.對梯度信息的精確擬合會對高斯過程回歸產生負面影響，并且增加計算量：如當歷史超參的梯度因為噪音與總趨勢相反時，梯度信息的精確引入會對高斯過程回歸產生非常顯著的負面影響，如圖3所示.

Fig. 3 Regression function with different accurate gradient and original function圖3 使用不同精準度的梯度的擬合函數與原函數

AccSMBO算法可以通過減少核函數的數量來減少梯度噪音帶來的影響.在實踐中，噪音越多，使用的內核數量就越少.在求解方程時，式(3)(4)的地位是不同的.在大多數情況下，噪音對梯度方程的影響會更大，如圖3所示.因此，我們期望α和β可以滿足式(3)，然后使用最小二乘法來求解式(4)除此之外，減少內核可以減少計算的負載.

因此，考慮到f(λ)曲線的性質和計算負載，上述基于梯度的多核高斯過程回歸更適合于解決超參優化的問題.

4.2 metaAC函數

現有SMBO算法都是在使用者對目標函數毫無所知的情況下設計的.但是在真實情況下，算法使用者對超參都有一些了解.元學習數據集可以反映出這些信息.合理使用這些信息可以提升超參調優的速度.基于這些信息，本文提出了metaAC函數對SMBO算法進行加速.

4.2.1 metaAC函數及其收斂性

使用metaAC函數需要2個步驟：1)為了使得metaAC函數在最佳超參高概率范圍的輸出較高，需要根據元學習數據集總結出最佳超參高概率范圍.2)依照最佳超參高概率范圍，在保證收斂性的前提下調整AC函數.

最佳超參的概率密度分布函數是最佳超參高概率范圍的表達方式之一.AccSMBO算法使用最佳超參的概率密度分布函數對AC函數進行調整.AccSMBO根據元學習數據集中的信息構建一個經驗概率密度分布函數：首先，根據元學習數據集中的信息統計出不同超參的頻率；然后，使用函數依照頻率分布的信息擬合得到概率密度分布函數p(λ)(簡寫為EPDF).

構建最佳超參的概率密度分布函數并不要求元學習數據集包含不同情況下所有的最優超參值，只需要元學習數據集能夠反映出最優超參分布的趨勢即可.此時p(λ)就可以表達出最佳超參高概率范圍信息.p(λ)的輸出區域越高，則這一超參越有可能成為最優超參.

在設計metaAC函數時，metaAC應具有2個性質：1)在迭代優化的過程中，p(λ)輸出高的區域應具有更高的優先權，這樣有更大概率更快地找到最優超參.2)隨著算法的進行，p(λ)的影響應該遞減.過度依賴p(λ)會嚴重破壞AC函數的開發和探索平衡(exploitation and exploration trade off)，從而導致隨著迭代地進行AccSMBO算法無法描繪出目標函數的全局形式.

基于上述的性質，本文設計了metaAC函數：

metaAC(λ,epoch,p(λ),AC(λ))=
AC(λ)×(rate×p(λ)×e-epoch+1-rate×e-epoch),

其中,rate∈[0,1].rate主要用于描述元學習數據集是否足夠完整和算法使用者想多大程度依賴于元學習數據集進行加速.元學習數據集越大越完整時，rate應越大.

metaAC函數實際上是傳統AC函數的調整，而且可以看到隨著迭代地進行，metaAC函數將會收斂于傳統的AC函數.換句話說當在資源充足的情況下，metaAC函數的收斂性證明等同于未被調整過的AC函數的證明，即metaAC是可以保證算法收斂的.

在實際的生產中，遇到的最優超參在最優超參高概率范圍內的情況更多一些.從圖4(a)和圖4(b)中可以看到，metaAC函數比起AC函數更側重于搜索最優超參高概率范圍，從而起到加速算法的效果.

Fig. 4 The change of AC function to metaAC function圖4 從AC函數調整到metaAC函數

4.2.2 元學習的缺陷和metaAC的優勢

元學習是當前提升超參調優的重要手段.但是元學習技術存在2個問題：1)當前元學習技術只能給超參調優提供最優/次優的初始值.元學習技術不能在調參過程中對調優算法產生影響.2)元學習數據集一定要非常大.如果元學習數據集較小，對于元學習數據集中沒有被記錄的任務，元學習就難以提供較好的參考超參.同時，因為AC函數會進行開發探索平衡，在提供較好的初始值之后，AC函數會選擇在未探索區域中進行探索，而往往未探索的區域存在最優超參的可能性比較低，如圖4(a)所示，對于沒有被采樣過的區域[3,6]，因為沒有被探索過，AC函數的輸出更高.

metaAC函數可以克服上述的2個缺點：1)metaAC函數參與到了自動調優的過程中；2)metaAC函數的構造并不需要非常完整的元學習數據集.metaAC函數只需要元學習數據集反映出整體的趨勢即可.

4.3 異步并行AccSMBO算法

并行算法的高效優化一直是并行計算領域關注的重要問題.傳統對貝葉斯優化算法的并行加速是一個成熟的領域.但是基于第3節中固有模式和元學習數據集，可以進一步加速異步并行AccSMBO算法.

因為最佳超參在最佳超參高概率范圍中出現的概率較高，因此，將更多資源投入到最佳超參高概率范圍中，基于EPDF提供的最佳超參高概率范圍，異步并行AccSMBO算法可以將更多資源用于探索最佳超參高概率范圍中的參數，將f(λ)在最佳超參高概率性范圍中的情況盡快描繪出來.

AccSMBO使用了圖5所示的算法.在設計并行資源調度算法時，AccSMBO設置2個棧stackfast和stackslow.新產生的預測點包含了更多關于f(λ)的信息.因此總是優先計算最新更新的預測點，即使用棧數據結構.每次worker計算λ時，都從對應的棧中彈出的最新的λ用于計算效果.不同的worker使用異步并行的方法進行并行計算.異步并行極大地減少了同步操作帶來的巨大計算開銷，是現在最好的并行模式之一.

Fig. 5 The parallel workflow of AccSMBO圖5 AccSMBO的并行工作模式

為了并行加速SMBO，AccSMBO將更多的計算資源放在最佳超參高概率范圍中的預測超參，即將最佳超參高概率范圍中的預測超參放在高優先級隊列中.但是考慮到算法收斂性，即保證開發和探索平衡(exploitation and exploration trade off)，這種資源分配的不平衡應該隨著迭代的進行而逐漸減弱.基于此，使用和metaAC函數同樣的設計思路，AccSMBO使用Value函數完成上述目的.

首先AccSMBO需要依照傳統挑選參數的算法對候選參數集中超參的挑選順序付給初始優先級，如intensify process或者Hyperband算法.其中優先級越高，輸出越大.

例如，λ1,λ2,…,λk按照1，2，…，k的順序被Hyperband選出，則pri(λi)=i，pri(λ)越高，優先級越高.即：

pri(λ)=選擇算法選出λ的順序.

基于pri(λ)，這里使用metaAC函數的設計思路設計Value函數：

Value(λ,epoch,p(λ),pri(λ))=
pri(λ)×(rate×p(λ)×e-epoch+1-rate×e-epoch).

基于Value函數進行降序排序之后得到的序列作為候選超參的優先級.選取10%的低優先級超參進入stackslow棧，其余超參放入stackfast棧中.

異步并行AccSMBO算法的優化本質是對傳統異步并行SMBO算法的調整.隨著算法的逐步進行，算法5中的算法會退化為傳統異步并行貝葉斯優化算法，即能保證算法收斂.

與metaAC函數的加速原理一樣，實際問題中，調參人員遇到的最優超參在最優超參高概率范圍內的情況更多一些.AccSMBO側重于搜索最優超參高概率范圍，從而起到加速算法的效果.

5 實 驗

在本文中，實驗使用HOAG算法的實驗框架[22]進行實驗.

5.1 問題設置

5.1.1 數據集

首先，本實驗選擇不同規模的數據集進行訓練，包含了小規模數據集(OpenML數據庫中的Pc4數據集[29])、中型規模數據集(LibSVM數據庫中的Rcv1數據集[30])、大規模數據(LivSVM數據庫中的Real-sim數據集[22])進行實驗.這些數據集的具體情況在表2中給出.

Table 2 Dataset Information表2 數據集信息

在實驗中，本實驗抽取30%的數據作為驗證集，剩下的數據作為訓練集.

5.1.2 目標問題

在實驗中使用超參調優算法搜索邏輯回歸模型中2階正則參數.本實驗選擇這個參數作為實驗參數是因為這個參數較容易求其超參梯度[21].在這個實驗中，外層優化的目標為log loss，這里選擇log loss是因為log loss克服了傳統0-1損失帶來的非凸問題和不連續問題[21].內層優化目標h(λ)是2階正則化的logistic損失函數.目標函數的形式化表達為

(5)

其中,Φ(t)=ln(1+e-t).在求解內層優化問題時，本實驗使用了一種擬牛頓法：L-BFGS(limited-memory BFGS)算法，作為優化算法[31].其中L-BFGS算法代碼經過了工業級代碼優化，使用在相關廣告CTR預測產品中.

5.1.3 內核函數

在實驗中，超參的維度是1;因此本實驗選擇2個內核：高斯徑向基函數和3階徑向基函數，即:

和

在本實驗中，需要對矩陣K2求逆矩陣，基于對精準度的考慮，本實驗選擇高斯徑向基函數對應的矩陣進行求逆矩陣操作.

5.1.4 元學習數據集

現有唯一開源的元學習數據集是AutoSklearn中的元學習數據集.此元學習數據集由OpenML數據集庫構建.為了使實驗更有說服力，實驗中隨機刪除了這個數據集中20%的內容，并將這份數據集命名為半元學習數據集.半元學習數據集不能用于提供最佳參考超參.但是，因為半元學習數據集保留了整體超參分布的趨勢，所以，半元數據集仍然可以用于構建metaAC函數.

5.1.5 算 法

本實驗比較了5種現有的超參優化方法.為了使收斂過程更清晰，所有算法在選擇初始值時關閉了元學習功能，并將初始值都置為1.

1) SMAC算法.SMAC算法是現有最好的SMBO算法實現之一.SMAC算法被使用在了AutoSklearn和Auto-Weka等自動調優工具中.在每一步中，AC函數選出4個超參作為備選超參.再使用intensify process從4個超參中選擇效果最好的超參.本實驗選擇EI函數作為AC函數.

2) AccSMBO算法.AccSMBO算法代碼是使用AutoSklearn代碼修改而來.在實驗中，設置rate=1.為了使得p(λ)更準確，本實驗中，AccSMBO算法先將任務按照目標函數(log loss)、任務(二分類)和數據集特性(稀疏稠密)分類，統計分類后超參的分布情況.與SMAC算法一樣，每代AC函數選擇4個超參作為備選超參.在使用intensify process從4個超參中選擇效果最好的超參.本實驗選擇EI函數作為AC函數.

3) 網格搜索.網格搜索是現在最常用的超參搜索方法之一.在實驗中，網格搜索算法從區間[0,1]中均勻取出20個超參，每一輪從1開始，逐個計算一個超參的效果.

4) 隨機搜索.隨機搜索是現在最常用的超參搜索方法之一.在實驗中，隨機搜索算法從區間[0,1]中隨機取出20個超參，每一輪計算一個超參的效果.

5) HOAG(hyperparameter optimization with approximate gradient)算法.HOAG算法是現在最優的使用梯度求解最優超參的算法.每一代，超參都會朝著梯度下降的方向進行調整.本實驗直接使用開源的HOAG算法代碼作為實驗代碼.在實驗過程中為了保證算法收斂，實驗設置εk=10-12.為了保證算法的收斂速度并且保證算法能夠收斂到最小值，本實驗預先采樣了f(λ)曲線中的點，基于采樣點的梯度估測在實驗中步長最大為10-3.

6) 并行AccSMBO算法PaccSMBO.多線程AccSMBO算法.在實驗中，并行AccSMBO算法使用4個worker組成的系統.在算法設置上，多線程AccSMBO算法與串行AccSMBO算法一致.在并行設置上，3個worker分配給stackfast,1個worker分配給stackslow.為了使不同worker具有不同的初始值，不同worker從[0,1]間網格地抽取使用初始值，即初始值為0.25，0.5，0.75，1.實驗中，這種算法被稱為PaccSMBO.

上面的5個算法分別代表了常用的搜索算法(隨機搜索、網格搜索)，基于梯度的算法(HOAG算法)和其他SMBO算法實現(SMAC算法).

5.2 實驗環境和實驗信息

本實驗的實驗服務器硬件環為：

服務器使用2核Intel?Xeon?CPU E5-2680 2.88 GHz，共有24個內核.同時服務器使用最大內存為60 GB.

服務器使用網卡為Intel Corporation I350 Gigabit Network Connection.

本實驗的實驗服務器軟件環境為：

操作系統為CentOS 7.5.1804系統，C/C++編譯器版本為gcc 7.3.

Python版本為Python 3.7.5，SMAC的版本為SMAC-0.8.0，參數服務器使用MXNet(版本為1.1.0)中的參數服務器模塊.

5.3 實驗結果和分析

在串行算法的比較中，從代數上看，串行Acc-SMBO算法的收斂速度最快，同時搜索到了最好的超參，而SMAC找到了次優的超參.串行AccSMBO算法的收斂速度是SMAC的330%.由于當數據集規模較小時，f(λ)曲線不穩定，f(λ)曲線的梯度信息充滿了噪音，不能夠指示曲線的走向.因此會導致HOAG算法的收斂速度減慢.在本實驗中，HOAG并沒有達到收斂.對于并行的AccSMBO算法(PaccSMBO算法)，盡管從代數上PaccSMBO算法沒有占有優勢，但因為是4個worker同時運行，所以絕對時間上少于串行AccSMBO算法：串行AccSMBO算法使用3代達到收斂，PaccSMBO算法使用9代達到收斂，平均每個worker運行時間為2代.從絕對時間上看，串行AccSMBO的收斂速度是SMAC的329%，由于通信的損耗，并行Acc-SMBO算法(PaccSMBO算法)幾乎同時與串行AccSMBO算法收斂.

Fig. 6 Algorithm iteration performances on thedifferent datasets圖6 不同算法在不同數據集上的迭代性能

在Pc4實驗中，由于HOAG算法使用精確的梯度作為優化方向，在這種情況下無法找到最佳的超參.黑箱優化算法在這里顯示了它的優勢，因為它減少了曲線中的“噪聲”的影響，更快地逼近梯度.圖6(b)和圖7(b)顯示了Rcv1數據集的實驗結果.同樣地，在串行算法的比較中，從代數上看，串行AccSMBO算法的收斂速度最快，并找到了最佳的超參.在Rcv1數據集中，f(λ)曲線特性相對穩定，接近單峰函數，所以HOAG算法找到的超參和收斂速度是次優的.AccSMBO算法的收斂速度是HOAG算法的150%，是SMAC算法的收斂速度的175%.SMAC算法得到的結果和收斂速度幾乎與隨機搜索相同，因為SMAC需要更多的采樣點來構建整個f(λ)的信息.并行AccSMBO算法(PaccSMBO算法)的收斂過程雖然在絕對的代數上比串行AccSMBO算法多，但是平均到每個worker，其消耗的代數會比串行AccSMBO更少，絕對時間會更快.從絕對時間上看，串行AccSMBO算法是HOAG收斂速度的150%，是SMAC算法的167%.PaccSMBO算法的收斂速度是HOAG算法的316%，是SMAC算法的350%.

Fig. 7 Algorithm time performances on thedifferent dataset圖7 不同算法在不同數據集上的時間性能

圖6(c)和圖7(c)展示了不同算法在Real-sim數據集上的實驗結果.在串行算法的比較中，從代數上看，HOAG算法和串行AccSMBO算法都得到了最快的收斂速度并找到最佳超參.串行AccSMBO算法的收斂速度是SMAC算法的240%.并行AccSMBO算法(PaccSMBO算法)在收斂的代數上雖然在絕對的代數上比串行AccSMBO算法多，但是平均到每個worker，其消耗的代數會比串行AccSMBO更少，絕對時間會更快.從絕對時間上看，串行AccSMBO算法的收斂速度是HOAG算法收斂速度的109%，是SMAC算法收斂速度的260%.PaccSMBO算法的收斂速度是HOAG算法的145%，是SMAC算法的347%.

6 結 論