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

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

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

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

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

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

隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，自動機(jī)器學(xué)習(xí)技術(shù)成為了機(jī)器學(xué)習(xí)的關(guān)鍵技術(shù)之一[1]，即AutoML技術(shù).當(dāng)前的機(jī)器學(xué)習(xí)模型的訓(xùn)練需要大量的超參，超參優(yōu)化是AutoML的重要部分.

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

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

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

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

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

本文提出了AccSBMO算法.AccSMBO使用3種方法來優(yōu)化傳統(tǒng)SMBO算法.

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

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

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

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

1 相關(guān)工作

近年來，自動機(jī)器學(xué)習(xí)工具相繼被開發(fā)出來，如谷歌的AutoML,Auto-Weka，AutoSklearn等[4].這些工具使用了不同的超參優(yōu)化算法.

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

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

隨機(jī)優(yōu)化方法是現(xiàn)在最常用的超參調(diào)優(yōu)方法，例如網(wǎng)格搜索、隨機(jī)搜索、啟發(fā)式算法和神經(jīng)網(wǎng)絡(luò)算法[6]，但是這類算法效率低下.

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

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

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

隨著計算平臺的發(fā)展，并行計算環(huán)境逐漸成為了機(jī)器學(xué)習(xí)計算環(huán)境的主流.并行貝葉斯調(diào)優(yōu)算法也逐漸成為了研究熱點(diǎn)[16-19].

如何使用元學(xué)習(xí)(metalearning)[20]和超參梯度[21-23]加速自動調(diào)參優(yōu)化過程是AutoML領(lǐng)域中討論最多的話題之一.

2 研究背景

2.1 問題定義

本文使用形式化定義超參優(yōu)化[4]問題：

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

(1)

2.2 算法背景

2.2.1 SMBO算法及其最優(yōu)實現(xiàn)

SMBO算法是用于超參調(diào)優(yōu)的黑盒優(yōu)化算法框架.

算法1.SMBO算法.

Repeat

④λ←從③中的超參集中選出最優(yōu)超參；

⑤ 計算f(λ)；

Until消耗完給定計算資源;

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

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

元學(xué)習(xí)是提升SMBO算法效果的重要手段.基于元學(xué)習(xí)方法，SMBO可以在第1輪迭代到第2輪迭代中取到最優(yōu)或者次最優(yōu)的超參值.但是，為了通過元學(xué)習(xí)取得較好的超參初始值，經(jīng)常需要花費(fèi)較多成本構(gòu)建足夠大的元學(xué)習(xí)數(shù)據(jù)庫.

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

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

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

2.2.2 代

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

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

1) 因為算法在代碼實現(xiàn)和運(yùn)行平臺上的不同，每代所花費(fèi)的時間在不同情況下也不盡相同，而當(dāng)初始值和參數(shù)設(shè)置幾乎一致時，調(diào)優(yōu)過程幾乎是穩(wěn)定的，所以在讀者復(fù)現(xiàn)本實驗時，橫坐標(biāo)為代的實驗結(jié)果可以用較少代價得到復(fù)現(xiàn).

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

高斯過程是現(xiàn)有最好的響應(yīng)面的選擇之一[27].基于高斯過程的SMBO算法是最常用的SMBO算法實現(xiàn)之一[15].

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

本文中定義向量

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

其中，f維度為n.

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

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

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

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

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

協(xié)方差函數(shù)形式為

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

2.2.4 超參梯度

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

現(xiàn)有很多基于超參梯度的優(yōu)化方法都是基于梯度下降.

2.2.5 元學(xué)習(xí)數(shù)據(jù)庫

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

盡管元學(xué)習(xí)在AutoML中取得了巨大的成功，對于大多數(shù)情況，元學(xué)習(xí)只有在元學(xué)習(xí)數(shù)據(jù)集龐大的基礎(chǔ)上才能取得足夠好的效果.當(dāng)元學(xué)習(xí)數(shù)據(jù)集較小時，元學(xué)習(xí)對AutoML的提升有限.

2.2.6 并行SMBO算法

作為貝葉斯優(yōu)化算法的一種，SMBO算法也可以先天在并行環(huán)境中得到加速.現(xiàn)在最優(yōu)的貝葉斯優(yōu)化算法是2018年提出的異步并行貝葉斯優(yōu)化算法[16].這種優(yōu)化算法使用異步并行的方法避免了集群間同步的開銷，在工程上受益.這種異步并行的SMBO算法是可以實現(xiàn)在當(dāng)前主流機(jī)器學(xué)習(xí)框架-參數(shù)服務(wù)器上的.異步并行的SMBO算法在算法2中給出.

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

Worker端:

Repeat

① 計算從server接收預(yù)測最佳超參λ；

② 計算λ對應(yīng)的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←從⑤中的超參集中選最優(yōu)超參；

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

Until計算資源耗盡;

3 出發(fā)點(diǎn)和主要思想

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

Fig. 1 Some of those performance functions are close to unimodal functions or monotonic functions圖1 f(λ)曲線在全局上經(jīng)常呈現(xiàn)為單峰函數(shù)或者單調(diào)函數(shù)

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

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

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

算法3.串行AccSMBO算法.

Repeat

③ 使用元學(xué)習(xí)數(shù)據(jù)集和AC函數(shù)計算metaAC函數(shù)；

⑤λ←從④中的超參集中選出最優(yōu)超參；

⑥ 計算f(λ)；

Until消耗完給定計算資源；

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

Worker端:

Repeat

① 計算從對應(yīng)的棧中接收彈出的預(yù)測最佳超參λ；

② 計算λ對應(yīng)的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))組；

⑤ 使用元學(xué)習(xí)數(shù)據(jù)集和AC函數(shù)計算metaAC函數(shù)；

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

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

Until計算資源耗盡；

4 AccSMBO算法

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

4.1.1 數(shù)學(xué)符號

本節(jié)主要介紹后文中使用的額外的數(shù)學(xué)符號.

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

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

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

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

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

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

(2)

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

4.1.3 均值函數(shù)

在傳統(tǒng)的高斯過程回歸中，均值函數(shù)m(λ)是使用內(nèi)核函數(shù)作為基底對觀測點(diǎn)的擬合函數(shù).

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 方差函數(shù)

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

4.1.5 抗噪、約近和計算負(fù)載的減少

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

Fig. 3 Regression function with different accurate gradient and original function圖3 使用不同精準(zhǔn)度的梯度的擬合函數(shù)與原函數(shù)

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

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

4.2 metaAC函數(shù)

現(xiàn)有SMBO算法都是在使用者對目標(biāo)函數(shù)毫無所知的情況下設(shè)計的.但是在真實情況下，算法使用者對超參都有一些了解.元學(xué)習(xí)數(shù)據(jù)集可以反映出這些信息.合理使用這些信息可以提升超參調(diào)優(yōu)的速度.基于這些信息，本文提出了metaAC函數(shù)對SMBO算法進(jìn)行加速.

4.2.1 metaAC函數(shù)及其收斂性

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

最佳超參的概率密度分布函數(shù)是最佳超參高概率范圍的表達(dá)方式之一.AccSMBO算法使用最佳超參的概率密度分布函數(shù)對AC函數(shù)進(jìn)行調(diào)整.AccSMBO根據(jù)元學(xué)習(xí)數(shù)據(jù)集中的信息構(gòu)建一個經(jīng)驗概率密度分布函數(shù)：首先，根據(jù)元學(xué)習(xí)數(shù)據(jù)集中的信息統(tǒng)計出不同超參的頻率；然后，使用函數(shù)依照頻率分布的信息擬合得到概率密度分布函數(shù)p(λ)(簡寫為EPDF).

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

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

基于上述的性質(zhì)，本文設(shè)計了metaAC函數(shù)：

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

其中,rate∈[0,1].rate主要用于描述元學(xué)習(xí)數(shù)據(jù)集是否足夠完整和算法使用者想多大程度依賴于元學(xué)習(xí)數(shù)據(jù)集進(jìn)行加速.元學(xué)習(xí)數(shù)據(jù)集越大越完整時，rate應(yīng)越大.

metaAC函數(shù)實際上是傳統(tǒng)AC函數(shù)的調(diào)整，而且可以看到隨著迭代地進(jìn)行，metaAC函數(shù)將會收斂于傳統(tǒng)的AC函數(shù).換句話說當(dāng)在資源充足的情況下，metaAC函數(shù)的收斂性證明等同于未被調(diào)整過的AC函數(shù)的證明，即metaAC是可以保證算法收斂的.

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

Fig. 4 The change of AC function to metaAC function圖4 從AC函數(shù)調(diào)整到metaAC函數(shù)

4.2.2 元學(xué)習(xí)的缺陷和metaAC的優(yōu)勢

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

metaAC函數(shù)可以克服上述的2個缺點(diǎn)：1)metaAC函數(shù)參與到了自動調(diào)優(yōu)的過程中；2)metaAC函數(shù)的構(gòu)造并不需要非常完整的元學(xué)習(xí)數(shù)據(jù)集.metaAC函數(shù)只需要元學(xué)習(xí)數(shù)據(jù)集反映出整體的趨勢即可.

4.3 異步并行AccSMBO算法

并行算法的高效優(yōu)化一直是并行計算領(lǐng)域關(guān)注的重要問題.傳統(tǒng)對貝葉斯優(yōu)化算法的并行加速是一個成熟的領(lǐng)域.但是基于第3節(jié)中固有模式和元學(xué)習(xí)數(shù)據(jù)集，可以進(jìn)一步加速異步并行AccSMBO算法.

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

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

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

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

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

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

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

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

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

基于Value函數(shù)進(jìn)行降序排序之后得到的序列作為候選超參的優(yōu)先級.選取10%的低優(yōu)先級超參進(jìn)入stackslow棧，其余超參放入stackfast棧中.

異步并行AccSMBO算法的優(yōu)化本質(zhì)是對傳統(tǒng)異步并行SMBO算法的調(diào)整.隨著算法的逐步進(jìn)行，算法5中的算法會退化為傳統(tǒng)異步并行貝葉斯優(yōu)化算法，即能保證算法收斂.

與metaAC函數(shù)的加速原理一樣，實際問題中，調(diào)參人員遇到的最優(yōu)超參在最優(yōu)超參高概率范圍內(nèi)的情況更多一些.AccSMBO側(cè)重于搜索最優(yōu)超參高概率范圍，從而起到加速算法的效果.

5 實 驗

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

5.1 問題設(shè)置

5.1.1 數(shù)據(jù)集

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

Table 2 Dataset Information表2 數(shù)據(jù)集信息

在實驗中，本實驗抽取30%的數(shù)據(jù)作為驗證集，剩下的數(shù)據(jù)作為訓(xùn)練集.

5.1.2 目標(biāo)問題

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

(5)

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

5.1.3 內(nèi)核函數(shù)

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

和

在本實驗中，需要對矩陣K2求逆矩陣，基于對精準(zhǔn)度的考慮，本實驗選擇高斯徑向基函數(shù)對應(yīng)的矩陣進(jìn)行求逆矩陣操作.

5.1.4 元學(xué)習(xí)數(shù)據(jù)集

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

5.1.5 算 法

本實驗比較了5種現(xiàn)有的超參優(yōu)化方法.為了使收斂過程更清晰，所有算法在選擇初始值時關(guān)閉了元學(xué)習(xí)功能，并將初始值都置為1.

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

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

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

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

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

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

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

5.2 實驗環(huán)境和實驗信息

本實驗的實驗服務(wù)器硬件環(huán)為：

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

服務(wù)器使用網(wǎng)卡為Intel Corporation I350 Gigabit Network Connection.

本實驗的實驗服務(wù)器軟件環(huán)境為：

操作系統(tǒng)為CentOS 7.5.1804系統(tǒng)，C/C++編譯器版本為gcc 7.3.

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

5.3 實驗結(jié)果和分析

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

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

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

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

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

6 結(jié) 論