1.背景

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

2.動因

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

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

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

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

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

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

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

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

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

這是一個N維向量，可以計算：

上式是函數(shù)對向量的求導，得到的也是一個梯度向量。這里求導過程，首先是求,即每個樣本點的F函數(shù)值，然后再根據(jù)具體的損失函數(shù)，來計算損失函數(shù)對函數(shù)值的導數(shù)，而不是對的導數(shù)。

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

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

其中是初始估計，是用于擬合負梯度的弱學習器，是最優(yōu)步長，。

3.主要思想

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

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

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

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

是初始估計，是負梯度的擬合函數(shù)，是對梯度。是最優(yōu)步長。

其中：

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

乘子沿著步長方向進行線性搜索，代表步長：

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

因此我們需要修改解的形式。可以通過限制為一系列帶參數(shù)的函數(shù)集合 是一個有限的參數(shù)集合，即首先確定了的形式，然后再在參數(shù)空間中搜索的參數(shù)值，實際上這是將函數(shù)估計問題轉(zhuǎn)化成了參數(shù)估計問題。

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

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

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

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

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

然后更新：

可以看出這是一種分步加和擴展的方式(注意min的下標)，即每次只訓練一個弱分類器，當新分類器被加入模型的時候，不調(diào)整原來得到的分類器, 實際上是一種貪心策略。

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

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

因此N維空間上的函數(shù)負梯度可以表示為.然而這只是對訓練集樣本而言，不能泛化到其它樣本上。也就是說，我們原本的目標是需要損失函數(shù)對函數(shù)進行求梯度(參考動因一節(jié))，函數(shù)對函數(shù)的梯度難以求解，現(xiàn)在通過所有樣本在處的「取值的梯度」集合來近似替代對函數(shù)的梯度。然而這里只是對訓練集進行求值替代，為了能夠泛化到其他數(shù)據(jù)集，我們需要「根據(jù)訓練集在取值的梯度集合擬合出對的梯度」,使得其能夠泛化到其它樣本上。

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

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

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

乍看和非常像，但是二者是有略微區(qū)別的。我們一開始設想的是，是我們在用基函數(shù)擬合負梯度時，在負梯度方向上的最優(yōu)步長；然而我們實際操作的時候為了能夠泛化到測試集，用平方誤差損失來擬合，導致得到的并不一定能保證對訓練集數(shù)據(jù)而言是最優(yōu)步長。因此，重新使用線性搜索方法，在訓練集上求最優(yōu)步長。當然，這一步似乎也沒什么必要，影響應該不算太大。

然后更新模型：

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

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

解釋：

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

上述第四步中實際上還可以使用其他擬合標準進行求解，最小二乘法是其中一種簡單又自然的選擇。

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

4.主要工作

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

4.1 算法

Least-squares Regression

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

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

Least absolute Deviation Regression

此時損失函數(shù)為

在第四步中，使用擬合。在第五步中線性搜索為：

Regression trees

考慮基學習器為的回歸樹。

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

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

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

的線性搜索采用公式第五步進行求解。

則更新策略簡寫為：

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

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

4.2 正則化

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

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

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

參考

Greedy Function Approximation: A Gradient Boosting Machine