李金香，王福勝

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，從海量高維數(shù)據(jù)中建立精確預(yù)測模型的迫切需求使得人們對提升算法越來越感興趣.提升算法的思想是通過改變訓(xùn)練數(shù)據(jù)的概率分布(權(quán)重分布)來學(xué)習(xí)多個(gè)弱學(xué)習(xí)器，并將它們線性組合成強(qiáng)學(xué)習(xí)器.提升算法起源于Freund和Schapire的組合分類器工作[1-3].進(jìn)一步，Breiman和Friedman等人在論文和技術(shù)報(bào)告中闡述了提升和優(yōu)化之間的突破性聯(lián)系[4,5].Friedman于2001年受數(shù)值優(yōu)化文獻(xiàn)的啟發(fā)提出了梯度提升算法(GBM)并討論了弱學(xué)習(xí)器是決策樹的情況[6,7].GBM在處理異構(gòu)數(shù)據(jù)集(分類數(shù)據(jù)、數(shù)據(jù)缺失、高度相關(guān)數(shù)據(jù)等)方面具有優(yōu)勢，并有多個(gè)開源實(shí)現(xiàn)，例如scikitlearn[8]，XGBoost[9]，LightGBM[10]，TF提升樹[11]等.

盡管GBM在實(shí)踐中表現(xiàn)出了優(yōu)異的性能，但目前人們對這種算法的理論理解卻相當(dāng)有限.1999年，Mason和Collins等人首先建立了梯度提升算法的收斂性保證，但沒有給出收斂速度[12,13].Bickel[14]于2006年證明了當(dāng)損失函數(shù)光滑強(qiáng)凸時(shí)，GBM具有O(exp(1/ε2))次迭代復(fù)雜度.之后Telgarsky[15]在2012年根據(jù)GBM的原始對偶關(guān)系證明了該算法實(shí)際上只需要O(ln(1/ε))次迭代.最近，Lu和Mazumder[16]給出了更好的結(jié)果，即當(dāng)損失函數(shù)是光滑且凸的，只要O(1/ε)迭代就足夠了.

近年來，有關(guān)學(xué)者進(jìn)一步改進(jìn)了梯度提升算法.例如，Wang等人[17]在他們提出的FWboost算法中用Frank-Wolfe算法代替梯度下降，Chen和Guestrin[9]通過計(jì)算Hessian矩陣執(zhí)行牛頓步而不是梯度步，Biau等人[18]結(jié)合梯度提升和Nesterov加速下降設(shè)計(jì)了AGBM.在AGBM的基礎(chǔ)上，Lu等人[19]進(jìn)一步使用修正偽殘差建立了AGBM的一個(gè)變體，它的收斂速度為O(1/t2)，F(xiàn)ouillen等人[20]基于鄰近點(diǎn)算法提出了PBM，且結(jié)合Nesterov加速下降設(shè)計(jì)了APBM.

眾所周知，梯度提升算法中時(shí)間成本最高的步驟是尋找最佳的弱學(xué)習(xí)器.例如，當(dāng)弱學(xué)習(xí)器是深度為d的決策樹時(shí)，訓(xùn)練樣本數(shù)為n，特征數(shù)為p，要找到最佳的弱學(xué)習(xí)器則需要遍歷n2d-1p2d-1次可能的樹拆分，這說明對于中等規(guī)模的問題，即使d=1時(shí)也是難以解決的.因此，文獻(xiàn)[16]通過使用隨機(jī)化方案提出了RGBM算法，能夠減少弱學(xué)習(xí)器空間中的搜索進(jìn)而降低計(jì)算成本.然而RGBM只適用于損失函數(shù)可微的情況下.例如，當(dāng)損失函數(shù)l(x,y)=|x-y|時(shí)，由于絕對值函數(shù)不可微則無法訓(xùn)練數(shù)據(jù).因此，RGBM算法具有局限性.本文用鄰近算子代替負(fù)梯度來計(jì)算偽殘差，提出了新算法隨機(jī)鄰近提升機(jī)(RPBM)，該算法不僅可以捕獲數(shù)據(jù)用以準(zhǔn)確預(yù)測，而且對可微損失函數(shù)和不可微損失函數(shù)均適用.本文還將新算法用于機(jī)器學(xué)習(xí)常用數(shù)據(jù)分類上且通過數(shù)值實(shí)驗(yàn)說明了RPBM的有效性.

1 算法

在本節(jié)中，我們首先給出了問題的描述和背景并回顧了RGBM算法，之后用鄰近算子計(jì)算偽殘差，構(gòu)造了我們提出的新算法RPBM.

1.1 問題描述和背景

在本文中，假設(shè)我們給定一個(gè)參數(shù)為τ∈的基學(xué)習(xí)器類={bτ(x)∈}，這些基學(xué)習(xí)器的線性組合的集合為span其中為非負(fù)整數(shù)的集合，bτt∈為其中一個(gè)基學(xué)習(xí)器且βt為其對應(yīng)的加性系數(shù).

我們的目標(biāo)是獲得一個(gè)對函數(shù)f的良好估計(jì)，使經(jīng)驗(yàn)損失近似最小化:

(1)

其中l(wèi)(yi,f(xi))是損失函數(shù)的數(shù)據(jù)保真度的度量.

1.2 RGBM

為了構(gòu)造新算法，首先回顧一下RGBM算法[16](如算法1所示)，該算法通過隨機(jī)化方案減少弱學(xué)習(xí)器空間的搜索.

算法1 RGBM 輸入:f0(x)=0,步長η.For t=0,…,T-1 do a)計(jì)算偽殘差rit=-?l(yi,ft(xi))?ft(xi),i=1,…,n,rt=(r1t,r2t,…,rnt). b)通過規(guī)則1)-4)選擇弱學(xué)習(xí)器的隨機(jī)子集. c)在中尋找最佳弱學(xué)習(xí)器τt=argminτ∈∑ni=1(rit-bτ(xi))2. d)更新模型ft+1(x)=ft(x)+ηbτt(x).End for輸出:fT(x).

2)(隨機(jī)選擇)我們從所有可能的弱學(xué)習(xí)器中不替換地隨機(jī)選擇t個(gè)弱學(xué)習(xí)器，集合用表示.

3)(隨機(jī)單組選擇)給定弱學(xué)習(xí)器的不重疊劃分，我們隨機(jī)地選擇一個(gè)組，并用表示該組中弱學(xué)習(xí)器的集合.

4)(隨機(jī)多組選擇)給定弱學(xué)習(xí)器的不重疊劃分，我們隨機(jī)選擇t組，并令這t組中的弱學(xué)習(xí)器的集合為.

RGBM從一個(gè)空模型f0(x)開始，在每次迭代t中計(jì)算偽殘差rt∈n.由于提升的關(guān)鍵是學(xué)習(xí)器為弱學(xué)習(xí)器且預(yù)測空間不密集，因此，APBM在最小二乘意義上通過擬合偽殘差rt尋找最佳弱學(xué)習(xí)者：最后f序列由一個(gè)最逼近rt的弱學(xué)習(xí)器更新.

RGBM使用隨機(jī)化方案降低了搜索最佳弱學(xué)習(xí)器的時(shí)間成本.然而，該算法只適用于可微損失函數(shù)，對于不可微損失函數(shù)無法計(jì)算偽殘差.

1.3 RPBM

在本小節(jié)中，我們提出可以同時(shí)適用于可微損失函數(shù)與不可微損失函數(shù)的新算法RPBM.RPBM與RGBM的主要區(qū)別是偽殘差的不同，偽殘差由鄰近算子給出，其定義如下：

(2)

算法2 RPBM 輸入:f0(x)=0,步長η,鄰近步λ.Fort=0,…,T-1 do a)計(jì)算偽殘差rit=1λproxλL(ft(xi))-ft(xi) ,i=1,…,n,rt=(r1t,r2t,…,rnt). b)通過規(guī)則1)-4)選擇弱學(xué)習(xí)器的隨機(jī)子集T. c)在T中尋找最佳弱學(xué)習(xí)器τt=argminτ∈∑ni=1(rit-bτ(xi))2. d)更新模型ft+1(x)=ft(x)+ηbτt(x).End for輸出:fT(x).

2 數(shù)值實(shí)驗(yàn)

本節(jié)通過數(shù)值實(shí)驗(yàn)驗(yàn)證了所提出的RPBM(算法2)的有效性.所有的測試均在Python計(jì)算環(huán)境下的具有4GB內(nèi)存的IntelCorei5處理器上進(jìn)行.我們在數(shù)值實(shí)驗(yàn)中使用的數(shù)據(jù)集是從LIBSVM庫[21]中收集到的.表1顯示了這些數(shù)據(jù)集的詳細(xì)信息.

表1 數(shù)據(jù)信息

對于每個(gè)數(shù)據(jù)集，我們隨機(jī)選擇80%作為訓(xùn)練數(shù)據(jù)集，其余部分作為測試數(shù)據(jù)集.提升算法在實(shí)踐中常用的弱學(xué)習(xí)器有小波函數(shù)，支持向量機(jī)，樹樁(即深度為1的決策樹)和分類和回歸樹(CART)等[22].本節(jié)實(shí)驗(yàn)中所有的算法都使用樹樁作為弱學(xué)習(xí)器，我們考慮可微的logistic損失函數(shù)l(x,y)=log2(1+e-xy)和不可微的hinge損失函數(shù)l(x,y)=max(0,1-xy).實(shí)驗(yàn)中我們選擇2.2節(jié)介紹的規(guī)則4)，其中每一組代表在單個(gè)特征上分裂的所有樹樁.

實(shí)驗(yàn)包括兩個(gè)部分.首先第一個(gè)實(shí)驗(yàn)說明我們提出的RPBM算法能夠同時(shí)適用于可微損失函數(shù)與不可微損失函數(shù)，結(jié)果如圖1所示.不同的線對應(yīng)于不同的t值，即每次迭代中隨機(jī)集J出現(xiàn)多少組.因?yàn)閍9a數(shù)據(jù)集的特征為123，故藍(lán)線t=123對應(yīng)于無隨機(jī)的鄰近提升機(jī)PBM[20].此外，我們設(shè)置步長η=0.3.圖1的左列和右列分別顯示了可微logistic損失函數(shù)與不可微hinge損失函數(shù)的訓(xùn)練損失/測試損失與運(yùn)行時(shí)間的關(guān)系.從圖1中可以觀察到，當(dāng)t的組數(shù)變小時(shí)，每次迭代的成本顯著降低，也就是說，與較大的t值相比，一個(gè)小的t值(不一定是最小的)需要更少的計(jì)算就可以實(shí)現(xiàn)類似甚至更小的訓(xùn)練/測試損失.這意味著本文所提出的RPBM對兩種損失函數(shù)都具有良好的性能.

圖1 Logistic損失函數(shù)(左列)與hinge損失函數(shù)(右列)的RPBM訓(xùn)練損失/測試損失與運(yùn)行時(shí)間的關(guān)系

第二個(gè)實(shí)驗(yàn)展示了RPBM在不可微的hinge損失函數(shù)的泛化性能.實(shí)驗(yàn)中選取機(jī)器學(xué)習(xí)中五個(gè)常用分類數(shù)據(jù)集，分別是w7a，cifar10，mnist，splice，german，每個(gè)數(shù)據(jù)集的t取最大均代表無隨機(jī)狀態(tài)的鄰近提升機(jī)(PBM).此外，算法中的步長η=0.1，鄰近步λ=1，運(yùn)行時(shí)間以秒為單位，具體數(shù)值實(shí)驗(yàn)結(jié)果見表2.

表2 RPBM在不同t值(最大的t值對應(yīng)于PBM)的性能

通過表2可以看出通過使用較小的t值，RPBM可以顯著地節(jié)省計(jì)算量，且訓(xùn)練損失與測試損失都較小.因此，隨機(jī)鄰近提升算法不僅可以在可微損失函數(shù)上訓(xùn)練數(shù)據(jù)，還可應(yīng)用在不可微損失函數(shù)上，且在不同的數(shù)據(jù)集上均具有良好的性能，這說明本文提出的RPBM有效，且與已有算法比較具有優(yōu)勢.

3 小結(jié)

本文基于鄰近點(diǎn)算法，用鄰近算子計(jì)算偽殘差，提出一種新算法RPBM，新算法克服了RGBM的局限性，可以同時(shí)應(yīng)用于可微損失函數(shù)與不可微損失函數(shù).數(shù)值實(shí)驗(yàn)表明，與已有的無隨機(jī)的PBM相比，本文提出的RPBM可以顯著降低計(jì)算成本，提高了運(yùn)算效率，因而具有優(yōu)良的數(shù)值表現(xiàn).