理解GBDT算法（三）——基于梯度的版本 標(biāo)簽： GBDT梯度殘差代價(jià)函數(shù)回歸樹(shù) 2015-03-31 16:13 1395人閱讀 評(píng)論(3) 收藏 舉報(bào) 本文章已收錄于： 分類(lèi)： Machine Learning&&Data Mining（44） 作者同類(lèi)文章X

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

目錄(?)[+]

算法的基本步驟

公式推導(dǎo)

兩個(gè)版本之間的聯(lián)系

上一篇中我們講到了GBDT算法的第一個(gè)版本，是基于殘差的學(xué)習(xí)思路。今天來(lái)說(shuō)第二個(gè)版本，可以說(shuō)這個(gè)版本的比較復(fù)雜，涉及到一些推導(dǎo)和矩陣論知識(shí)。但是，我們今天可以看到，兩個(gè)版本之間的聯(lián)系，這個(gè)是學(xué)習(xí)算法的一個(gè)重要步驟。

這篇博文主要從下面這幾個(gè)方面來(lái)說(shuō)基于梯度的GBDT算法：
（1）算法的基本步驟；
（2）其中的學(xué)數(shù)學(xué)推導(dǎo)；
（3）基于梯度的版本和基于殘差的版本之間的聯(lián)系；

在講解算法的詳細(xì)步驟之前，我們可以先明確一個(gè)思路，就是梯度版本的GBDT是用多類(lèi)分類(lèi)Multi-class classification 的思想來(lái)實(shí)現(xiàn)的，或者可以說(shuō)GBDT的這個(gè)版本融入到多類(lèi)分類(lèi)中可以更好的掌握。

1. 算法的基本步驟

首先網(wǎng)上很多講解博客都會(huì)出現(xiàn)下面這個(gè)圖：

那么也就是說(shuō)梯度版的GBDT的算法主要有8個(gè)步驟。
（0）初始化所有樣本在K個(gè)類(lèi)別上的估計(jì)值。
F_k(x)是一個(gè)矩陣，我們可以初始化為全0，也可以隨機(jī)設(shè)定。如下：

上面的矩陣中，我們假設(shè)有N=8個(gè)樣本，每個(gè)樣本可能會(huì)屬于K=5個(gè)類(lèi)別中的一個(gè)，其中估計(jì)值矩陣F初始化為0.
除此之外，這8個(gè)訓(xùn)練樣本都是帶著類(lèi)別標(biāo)簽的，例如：

說(shuō)明第i=1個(gè)樣本是屬于第3類(lèi)的。

（1）循環(huán)下面的學(xué)習(xí)更新過(guò)程M次；

（2）對(duì)沒(méi)有樣本的函數(shù)估計(jì)值做logistic變換。
我們?cè)谇懊娼榻BLogistic回歸的時(shí)候提到，Logistic函數(shù)一個(gè)重要的特性就是可以轉(zhuǎn)換為0~1之間的概率值，我們通過(guò)下面的變換公式就可以把樣本的估計(jì)值轉(zhuǎn)換為該樣本屬于某一類(lèi)的概率是多少：

可以看到樣本初始的時(shí)候每個(gè)類(lèi)別的估計(jì)值都是0，屬于類(lèi)別的概率也是相等的，不過(guò)，隨著后面的不斷更新，其估計(jì)值不一樣了，概率自然也就差別開(kāi)來(lái)。
比如下面：

（3）遍歷所有樣本的每個(gè)類(lèi)別的概率
這一步需要注意，遍歷的是每個(gè)類(lèi)別，而不是所有樣本。如下：

為什么這里是按照類(lèi)別逐個(gè)學(xué)習(xí)呢？因?yàn)楹竺嫘枰o每個(gè)類(lèi)別k學(xué)習(xí)出一個(gè)回歸樹(shù)。

（4）求每個(gè)樣本在第k類(lèi)上概率梯度
上面一步中，我們有了許多個(gè)樣本屬于某個(gè)類(lèi)別k的概率，以及它們是否真正屬于類(lèi)別k的概率（這些樣本都是訓(xùn)練樣本，所以它們是否屬于某個(gè)類(lèi)別都是已知的，概率為0/1）。那么這個(gè)就是一個(gè)典型的回歸問(wèn)題。我們當(dāng)然可以用回歸樹(shù)的算法來(lái)求解（注，這里就是多類(lèi)分類(lèi)問(wèn)題和GBDT聯(lián)系的關(guān)鍵）。
我們通過(guò)常見(jiàn)的建立代價(jià)函數(shù)，并求導(dǎo)的梯度下降法來(lái)學(xué)習(xí)。代價(jià)函數(shù)是對(duì)數(shù)似然函數(shù)的形式為：

對(duì)這個(gè)代價(jià)函數(shù)的求導(dǎo)，我們可以得到：

（詳細(xì)的推導(dǎo)過(guò)程下一節(jié)給出）
有沒(méi)有發(fā)現(xiàn)這里的求導(dǎo)得到的梯度形式居然是殘差的形式：第i個(gè)樣本屬于第k個(gè)類(lèi)別的殘差 = 真實(shí)的概率 - 估計(jì)的概率。
這一步也是殘差版本和梯度版本的聯(lián)系。
這些的梯度也是下面我們構(gòu)建回歸樹(shù)的學(xué)習(xí)方向。

（5）沿著梯度方法學(xué)習(xí)到J個(gè)葉子結(jié)點(diǎn)的回歸樹(shù)
學(xué)習(xí)的偽代碼：

我們輸入所有樣本xi, i = 1~N， 以及每個(gè)樣本在第k個(gè)類(lèi)別上概率的殘差作為更新方向，我們學(xué)習(xí)到有J個(gè)葉子的回歸樹(shù)。學(xué)習(xí)的基本過(guò)程和回歸樹(shù)類(lèi)似：遍歷樣本的特征維數(shù)，選擇一個(gè)特征作為分割點(diǎn)，需要滿(mǎn)足最小均方差的原則，或者滿(mǎn)足【左子樹(shù)樣本目標(biāo)值（殘差）和的平方均值+右子樹(shù)樣本目標(biāo)值（殘差）和的平方均值-父結(jié)點(diǎn)所有樣本目標(biāo)值（殘差）和的平方均值】最大的準(zhǔn)則，一旦學(xué)習(xí)到J個(gè)葉子結(jié)點(diǎn)，我們就停止學(xué)習(xí)。結(jié)果是該回歸樹(shù)中每個(gè)葉子上都會(huì)有許多個(gè)樣本分布在上面。
記住：每個(gè)葉子上的樣本，既有自己屬于類(lèi)別k的估計(jì)概率，也有真實(shí)概率，因?yàn)楹竺媲笤鲆嫘枰玫剿鼈儭?/p>

（6）求每個(gè)葉子結(jié)點(diǎn)的增益
每個(gè)結(jié)點(diǎn)的增益計(jì)算公式為：

注意后標(biāo)，每個(gè)葉子結(jié)點(diǎn)j都有一個(gè)增益值（不是向量，是值）。計(jì)算的時(shí)候需要用到該葉子結(jié)點(diǎn)上的所有樣本的梯度。
換句話說(shuō)，每個(gè)葉子結(jié)點(diǎn)都可以計(jì)算出一個(gè)增益值，記住是值啊！

（7）更新所有樣本在第k類(lèi)下的估計(jì)值
上一步中求得的增益是基于梯度計(jì)算得到的，而且前面說(shuō)到的梯度和殘差有一定的關(guān)聯(lián)，我們可以利用這個(gè)增益更新樣本的估計(jì)值。

第m次迭代中的第k類(lèi)下，所有樣本的估計(jì)值F可以通過(guò)上次迭代m-1中，這些樣本的估計(jì)值+增益向量求得。注意，這個(gè)增益向量需要把所有的J個(gè)葉子結(jié)點(diǎn)的增益值求和，然后和向量1相乘，而得。
也就是我們上面講的，第k類(lèi)的所有樣本的估計(jì)值是一列：

也就是按列更新，前面有對(duì)類(lèi)別數(shù)k的循環(huán)，所以每一類(lèi)（每一列）的估計(jì)值都可以更新。一定記住是按列更新，每一類(lèi)（每一列）都建立一個(gè)回歸樹(shù)來(lái)更新下去，最后原始的K類(lèi)的N個(gè)樣本的估計(jì)值矩陣都更新了一遍，帶著這個(gè)新的估計(jì)值矩陣，我們進(jìn)入下次m+1次的迭代學(xué)習(xí)。

如此，迭代學(xué)習(xí)M次之后，我們可以得到最終的所有樣本在所有類(lèi)別下的估計(jì)值矩陣，基于這個(gè)估計(jì)值矩陣，我們可以實(shí)現(xiàn)多類(lèi)分類(lèi)。

這樣，基于梯度版本的GBDT算法的所有詳細(xì)步驟我們都說(shuō)完了。

2. 公式推導(dǎo)

上面建立的代價(jià)函數(shù)是對(duì)數(shù)似然函數(shù)的形式：

對(duì)這個(gè)代價(jià)函數(shù)的求導(dǎo)，我們可以得到：

那么其中的詳細(xì)推導(dǎo)過(guò)程是什么呢？

其中涉及到對(duì)數(shù)函數(shù)的求導(dǎo)，主要是最后一步，yi是樣本屬于第k類(lèi)的真實(shí)概率，故yi就是0/1數(shù)，而且K個(gè)類(lèi)別中只可能屬于一個(gè)類(lèi)別，也就是說(shuō)只有一個(gè)yi是1，其余全是0，所以有最后一步推導(dǎo)結(jié)果。

3. 兩個(gè)版本之間的聯(lián)系

前面我們提到的一些聯(lián)系，這兒再總結(jié)一下：

• 基于殘差的版本四把殘差作為全局方向，偏向于回歸的應(yīng)用。而基于梯度的版本是把代價(jià)函數(shù)的梯度方向作為更新的方向，適用范圍更廣。
• 如果使用Logistic函數(shù)作為代價(jià)函數(shù)，那么其梯度形式和殘差的形式類(lèi)似，這個(gè)就說(shuō)明兩個(gè)版本之間是緊密聯(lián)系的，雖然實(shí)現(xiàn)的思路不同，但是總體的目的是一樣的。或者說(shuō)殘差版本是梯度版本的一個(gè)特例，當(dāng)代價(jià)函數(shù)換成其余的函數(shù)，梯度的版本仍是適用的。

參考：
http://blog.csdn.net/w28971023/article/details/43704775
http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/1976562.html
http://blog.csdn.net/kunlong0909/article/details/17587101
http://blog.csdn.net/puqutogether/article/details/44752611

總結(jié)

以上是生活随笔為你收集整理的理解GBDT算法（三）——基于梯度的版本的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。