1.背景

函數(shù)估計(jì)(Function Estimation/Approximation)是對(duì)函數(shù)空間(Function Space)進(jìn)行數(shù)值優(yōu)化，而不是對(duì)參數(shù)空間(Paramter Space)進(jìn)行優(yōu)化。這篇論文^[1]提出的Gradient Boosting Machine算法將stagewise additive expansions(分步加和擴(kuò)展)和steepest-descent minimization(最速下降極小化，也就是梯度下降法)結(jié)合起來(lái)實(shí)現(xiàn)對(duì)函數(shù)空間的數(shù)值優(yōu)化，可以適用于回歸和分類(lèi)問(wèn)題，具有完整性好，魯棒性強(qiáng)，解釋性好等優(yōu)點(diǎn)。

2.動(dòng)因

為了理解作者的動(dòng)因，我們首先從我們熟悉的函數(shù)最小值優(yōu)化問(wèn)題談起：

對(duì)于該優(yōu)化問(wèn)題，可以使用Steepest Gradient Descent，梯度下降法進(jìn)行求解。這個(gè)算法大致過(guò)程如下：

• 給定一個(gè)起始點(diǎn)
• 對(duì)分別作如下迭代：
• , 其中表示在上的梯度值，是步長(zhǎng)，是通過(guò)在方向線(xiàn)性搜索來(lái)動(dòng)態(tài)調(diào)整的。
• 一直到足夠小，或者足夠小，即函數(shù)收斂。

以上過(guò)程就是梯度下降法，可以理解為整個(gè)過(guò)程就是小步走，每小步都往函數(shù)值下降最快的方向走。這樣的尋優(yōu)過(guò)程得到的結(jié)果可以表示為加和形式，即：

我們可以從上面得到啟發(fā)，這樣的過(guò)程是否可以推廣至函數(shù)空間求函數(shù)估計(jì)問(wèn)題？求解函數(shù)估計(jì)問(wèn)題本身也是一個(gè)尋優(yōu)的過(guò)程，只不過(guò)我們尋找的結(jié)果是最優(yōu)函數(shù)估計(jì)，而不是最優(yōu)點(diǎn)估計(jì)。優(yōu)化的目標(biāo)通常通過(guò)最小化損失函數(shù)來(lái)定義：

類(lèi)似上面的梯度下降法，我們可以依次迭代得到,可以類(lèi)比成上述的,則最優(yōu)的 , 每次迭代求梯度：

其中，是負(fù)梯度，是每次迭代需要學(xué)習(xí)的弱學(xué)習(xí)器(基函數(shù))，用于擬合負(fù)梯度，即。此處前的權(quán)重為1，通常會(huì)給每次學(xué)習(xí)的弱學(xué)習(xí)器分配一個(gè)權(quán)重，即，，從最終的組成來(lái)看，衡量了該弱學(xué)習(xí)器在所有弱學(xué)習(xí)器中的重要性。

我們發(fā)現(xiàn)上述求解是函數(shù)對(duì)函數(shù)求梯度，由于損失函數(shù)對(duì)函數(shù)的梯度是關(guān)于的函數(shù)，而只能觀測(cè)到在離散的訓(xùn)練樣本上的取值，因此對(duì)的梯度也只能觀測(cè)到在訓(xùn)練樣本上的取值。為了泛化到測(cè)試樣本，我們需要對(duì)訓(xùn)練集上的離散梯度值進(jìn)行曲線(xiàn)擬合，得到梯度的近似。

我們首先將函數(shù)表示成由所有樣本點(diǎn)在該函數(shù)上的離散值構(gòu)成。即：

這是一個(gè)N維向量，可以計(jì)算：

上式是函數(shù)對(duì)向量的求導(dǎo)，得到的也是一個(gè)梯度向量。這里求導(dǎo)過(guò)程，首先是求,即每個(gè)樣本點(diǎn)的F函數(shù)值，然后再根據(jù)具體的損失函數(shù)，來(lái)計(jì)算損失函數(shù)對(duì)函數(shù)值的導(dǎo)數(shù)，而不是對(duì)的導(dǎo)數(shù)。

但是， 只是描述了 在每個(gè)訓(xùn)練樣本點(diǎn)上的值，并不足以表達(dá) ，也就是說(shuō)只是表達(dá)了訓(xùn)練集，不能泛化到其它數(shù)據(jù)上。重點(diǎn)在于，我們可以通過(guò)「函數(shù)擬合」的方法從 中構(gòu)造出, 這是一個(gè)我們非常熟悉的問(wèn)題，例如回歸曲線(xiàn)擬合問(wèn)題。這個(gè)問(wèn)題可以當(dāng)作一個(gè)子問(wèn)題求解，只要損失函數(shù)可導(dǎo)即可。這樣我們就近似得到了函數(shù)對(duì)函數(shù)的求導(dǎo)結(jié)果。

上述過(guò)程歸納起來(lái)，也就是加和擴(kuò)展(additive expansion)和梯度下降(steepest-descent minimization)的結(jié)合。表示成如下形式：

其中是初始估計(jì)，是用于擬合負(fù)梯度的弱學(xué)習(xí)器，是最優(yōu)步長(zhǎng)，。

3.主要思想

了解了動(dòng)因之后，我們從一般化函數(shù)估計(jì)問(wèn)題談起。首先仍然從介紹函數(shù)估計(jì)開(kāi)始，函數(shù)估計(jì)的目標(biāo)是得到對(duì)映射函數(shù)(從x映射到y(tǒng))的估計(jì),使得在所有訓(xùn)練樣本的聯(lián)合分布上，最小化期望損失函數(shù) ：

上式是求聯(lián)合分布，等于對(duì)在x上求邊緣分布。

我們需要在函數(shù)空間進(jìn)行數(shù)值優(yōu)化。在函數(shù)空間，為了表示一個(gè)函數(shù),理想狀況下有無(wú)數(shù)個(gè)點(diǎn)，我們可以使用“非參數(shù)方法”來(lái)求解上述問(wèn)題，非參數(shù)方法可以理解為，我們并沒(méi)有指定的形式，任意的都有可能。

根據(jù)前文（參見(jiàn)動(dòng)因一節(jié)），我們需要解：

是初始估計(jì)，是負(fù)梯度的擬合函數(shù)，是對(duì)梯度。是最優(yōu)步長(zhǎng)。

其中：

假設(shè)可以交換微分和積分的順序，則：

乘子沿著步長(zhǎng)方向進(jìn)行線(xiàn)性搜索，代表步長(zhǎng)：

然而我們面對(duì)的情況是只能用有限的數(shù)據(jù)集表示x，y的聯(lián)合分布的時(shí)候，上述方法就有點(diǎn)行不通了，因?yàn)?不能被數(shù)據(jù)集上的每個(gè)點(diǎn)正確估計(jì)，即使可以，也只是針對(duì)訓(xùn)練集，不能泛化到其它任意點(diǎn)。

因此我們需要修改解的形式?？梢酝ㄟ^(guò)限制為一系列帶參數(shù)的函數(shù)集合 是一個(gè)有限的參數(shù)集合，即首先確定了的形式，然后再在參數(shù)空間中搜索的參數(shù)值，實(shí)際上這是將函數(shù)估計(jì)問(wèn)題轉(zhuǎn)化成了參數(shù)估計(jì)問(wèn)題。

本文也采用類(lèi)似的思想，使用“分步加和擴(kuò)展(Stagewise Additive Expansion)”求解上述函數(shù)估計(jì)目標(biāo)。即，我們定義的形式為：

其中，可以理解為基函數(shù),是基函數(shù)的參數(shù)。對(duì)于GBDT而言，為CART樹(shù),而對(duì)應(yīng)著這棵小的CART樹(shù)的結(jié)構(gòu)，可以認(rèn)為是基函數(shù)的權(quán)重。即，我們使用的是基函數(shù)乘上某個(gè)權(quán)重來(lái)擬合負(fù)梯度。該權(quán)重通常為1。

則可將上述優(yōu)化問(wèn)題轉(zhuǎn)化為：

上述問(wèn)題仍然是難以求解的。難以求解的原因是，我們要一次性同時(shí)找出所有的（注意看min下標(biāo)），也就是找出所有基函數(shù)和的一個(gè)最優(yōu)序列，每次有新的分類(lèi)器加入，還需要調(diào)整之前的分類(lèi)器。

一種貪心算法的思想是采用「Greedy Stagewise」方法，對(duì),

然后更新：

可以看出這是一種分步加和擴(kuò)展的方式(注意min的下標(biāo))，即每次只訓(xùn)練一個(gè)弱分類(lèi)器，當(dāng)新分類(lèi)器被加入模型的時(shí)候，不調(diào)整原來(lái)得到的分類(lèi)器, 實(shí)際上是一種貪心策略。

對(duì)于給定的損失函數(shù)和基分類(lèi)器。上式求解比較困難。假設(shè)，在確定了的前提下，并且是的某個(gè)成員，同時(shí)也作為步長(zhǎng)的方向，那么可以看作是對(duì)(1)的最優(yōu)貪心步長(zhǎng)(greedy step),也可以認(rèn)為是(3)中的最深梯度下降步長(zhǎng)。

我們構(gòu)建樣本函數(shù)值的負(fù)梯度如下：

因此N維空間上的函數(shù)負(fù)梯度可以表示為.然而這只是對(duì)訓(xùn)練集樣本而言，不能泛化到其它樣本上。也就是說(shuō)，我們?cè)镜哪繕?biāo)是需要損失函數(shù)對(duì)函數(shù)進(jìn)行求梯度(參考動(dòng)因一節(jié))，函數(shù)對(duì)函數(shù)的梯度難以求解，現(xiàn)在通過(guò)所有樣本在處的「取值的梯度」集合來(lái)近似替代對(duì)函數(shù)的梯度。然而這里只是對(duì)訓(xùn)練集進(jìn)行求值替代，為了能夠泛化到其他數(shù)據(jù)集，我們需要「根據(jù)訓(xùn)練集在取值的梯度集合擬合出對(duì)的梯度」,使得其能夠泛化到其它樣本上。

具體而言，我們需要從中選擇某一個(gè)，使得和最接近。這是一個(gè)典型的函數(shù)擬合問(wèn)題，可以使用平方誤差損失在樣本上進(jìn)行擬合：

注意上述平方誤差損失只是用來(lái)擬合負(fù)梯度用的，和前面的是完全不一樣的兩個(gè)東西。對(duì)于GBDT而言，也就是「使用一棵新的回歸樹(shù)CART」，「擬合」損失函數(shù)對(duì)的「負(fù)梯度」。

找到負(fù)梯度擬合函數(shù)后，就可以使用線(xiàn)性搜索方法在負(fù)梯度方向上進(jìn)行搜索乘子。

乍看和非常像，但是二者是有略微區(qū)別的。我們一開(kāi)始設(shè)想的是，是我們?cè)谟没瘮?shù)擬合負(fù)梯度時(shí)，在負(fù)梯度方向上的最優(yōu)步長(zhǎng)；然而我們實(shí)際操作的時(shí)候?yàn)榱四軌蚍夯綔y(cè)試集，用平方誤差損失來(lái)擬合，導(dǎo)致得到的并不一定能保證對(duì)訓(xùn)練集數(shù)據(jù)而言是最優(yōu)步長(zhǎng)。因此，重新使用線(xiàn)性搜索方法，在訓(xùn)練集上求最優(yōu)步長(zhǎng)。當(dāng)然，這一步似乎也沒(méi)什么必要，影響應(yīng)該不算太大。

然后更新模型：

上述實(shí)際上是在公式(5)中加入了擬合約束，即,使用擬合負(fù)梯度. 這可以將（5）中的函數(shù)最小化問(wèn)題轉(zhuǎn)變?yōu)?6)中的最小二乘估計(jì)問(wèn)題，且該二乘估計(jì)只有一個(gè)參數(shù)，很容易求解。因此只要存在能夠使用最小二乘估計(jì)求解（6）中的負(fù)梯度擬合問(wèn)題的基函數(shù),那么就可以使用前向加和模型(forward stagewise additive model) 來(lái)求解復(fù)雜的損失函數(shù)優(yōu)化問(wèn)題。得到如下的算法：

• 1.
• 2.
• 3.
• 4.
• 5.
• 6.

解釋?zhuān)?/p>

• 1.初始化，對(duì)樣本點(diǎn)標(biāo)簽在損失函數(shù)上進(jìn)行線(xiàn)性搜索得到初始分類(lèi)器。
• 2.M個(gè)分類(lèi)器，迭代M次：
• 3.每次求得損失函數(shù)在所有訓(xùn)練樣本上對(duì)分類(lèi)器F的梯度。
• 4.使用定制的h函數(shù)對(duì)梯度進(jìn)行平方誤差擬合。
• 5.在擬合得到的梯度上進(jìn)行線(xiàn)性搜索，得到步長(zhǎng)。
• 6.使用分步加和模型來(lái)更新分類(lèi)器

上述第四步中實(shí)際上還可以使用其他擬合標(biāo)準(zhǔn)進(jìn)行求解，最小二乘法是其中一種簡(jiǎn)單又自然的選擇。

我們要注意上述中的和（4）中的是不一樣的，只不過(guò)在某些特定的損失函數(shù)中，的某種形式可以等價(jià)于（例如當(dāng)L也是最小平方誤差時(shí)，)。不過(guò)，個(gè)人認(rèn)為這里的有點(diǎn)多余，直接讓新的分類(lèi)器來(lái)擬合負(fù)梯度，即可。

4.主要工作

本部分介紹作者使用不同的損失函數(shù)和基函數(shù)來(lái)運(yùn)用加和模型和梯度下降策略得到的算法。

4.1 算法

Least-squares Regression

此時(shí)損失函數(shù)為:, 上述算法的第三步此時(shí)為：。則第四步直接使用擬合當(dāng)前數(shù)據(jù)的殘差即可，第五步線(xiàn)性搜索直接令即可，其中就是第四步擬合的結(jié)果。的原因如下：

第一個(gè)式子是當(dāng)前的優(yōu)化求解目標(biāo)，第二個(gè)式子是算法第四步中擬合負(fù)梯度的目標(biāo)，可以看出兩個(gè)優(yōu)化目標(biāo)完全一致，對(duì)負(fù)梯度的擬合結(jié)果得到的，p直接就是了，不需要第五步中的線(xiàn)性搜索。

Least absolute Deviation Regression

此時(shí)損失函數(shù)為

在第四步中，使用擬合。在第五步中線(xiàn)性搜索為：

Regression trees

考慮基學(xué)習(xí)器為的回歸樹(shù)。

公式第6步更新策略如下：

是第m次迭代時(shí)，回歸樹(shù)葉節(jié)點(diǎn)劃分出來(lái)的區(qū)域。這棵回歸樹(shù)被用來(lái)在第四步中擬合負(fù)梯度，即每次迭代使用回歸樹(shù)來(lái)擬合負(fù)梯度。

是相應(yīng)的最小二乘估計(jì)擬合負(fù)梯度得到的系數(shù)：

的線(xiàn)性搜索采用公式第五步進(jìn)行求解。

則更新策略簡(jiǎn)寫(xiě)為：

則優(yōu)化問(wèn)題轉(zhuǎn)化成：

由于回歸樹(shù)劃分的區(qū)域是不相交的，即如果

4.2 正則化

在訓(xùn)練集上訓(xùn)練模型來(lái)減少期望損失，通常會(huì)產(chǎn)生過(guò)擬合的現(xiàn)象。正則化通過(guò)約束訓(xùn)練過(guò)程來(lái)減輕過(guò)擬合。對(duì)于加和擴(kuò)展模型，一種正則化思想是控制模型的數(shù)量, 可以使用交叉驗(yàn)證來(lái)選擇。另一種正則化思想是使用收縮因子來(lái)控制擬合過(guò)程，即學(xué)習(xí)速率。如下：

這兩者存在一定的關(guān)系，減少學(xué)習(xí)速率意味著收斂速度降低，需要更多次迭代，則會(huì)增加模型的數(shù)量M。實(shí)際上是一種權(quán)衡，作者通過(guò)模擬學(xué)習(xí)simulation study的過(guò)程來(lái)解釋。

第一幅圖使用不同的算法，每張圖中不同曲線(xiàn)代表該算法在不同的學(xué)習(xí)速率下，預(yù)測(cè)錯(cuò)誤率隨迭代次數(shù)（M）的增加的變化情況。第二幅圖同樣給出了v和M的關(guān)系，可以看出，當(dāng)學(xué)習(xí)速率較小時(shí)，意味著更多次迭代M，則相應(yīng)的錯(cuò)誤率也越低。

參考

Greedy Function Approximation: A Gradient Boosting Machine