文章目錄

概述

提升方法Adaboost算法

Adaboost算法流程

Adaboost算法的說(shuō)明

Adaboost算法的解釋

Adaboost算法的訓(xùn)練誤差分析

提升樹

提升樹模型

提升樹算法

一個(gè)例子

梯度提升決策樹(Gradient boosting decision tree,GBDT)

回歸

分類

概述

提升(boosting)方法是一種常用的統(tǒng)計(jì)學(xué)習(xí)方法,應(yīng)用廣泛且有效.在分類問(wèn)題中,它通過(guò)改變訓(xùn)練樣本的權(quán)重,學(xué)習(xí)多個(gè)分類器,并將這些分類器進(jìn)行線性組合,提高分類性能.

對(duì)于分類問(wèn)題而言,給定一個(gè)訓(xùn)練樣本集,求比較粗糙的分類規(guī)則(弱分類器)要比求精確的分類規(guī)則(強(qiáng)分類器)容易得多.提升方法就是從弱學(xué)習(xí)算法出發(fā),反復(fù)學(xué)習(xí),得到一系列弱分類器(又稱為基本分類器),然后組合這些弱分類器,構(gòu)成一個(gè)強(qiáng)分類器.大多數(shù)的提升方法都是改變訓(xùn)練數(shù)據(jù)的概率分布(訓(xùn)練數(shù)據(jù)的權(quán)值分布),針對(duì)不同的訓(xùn)練數(shù)據(jù)分布調(diào)用弱學(xué)習(xí)算法學(xué)習(xí)一系列弱分類器.

這樣,對(duì)提升方法來(lái)說(shuō),有兩個(gè)問(wèn)題需要回答:

一,在每一輪如何改變訓(xùn)練數(shù)據(jù)的權(quán)值或概率分布.

二,如何將弱分類器組合成一個(gè)強(qiáng)分類器.

關(guān)于第1個(gè)問(wèn)題,Adaboost的做法是,提高那些被前一輪弱分類器錯(cuò)誤分類樣本的權(quán)值,而降低那些被正確分類樣本的權(quán)值.這樣一來(lái),那些沒(méi)有得到正確分類的數(shù)據(jù),由于其權(quán)重的加大而受到后一輪的更大關(guān)注.于是,分類問(wèn)題被一系列的弱分類器"分而治之".至于第2個(gè)問(wèn)題,即弱分類器的組合,Adaboost采取加權(quán)多數(shù)表決的方法.具體地,加大分類誤差率小的弱分類器的權(quán)值,使其在表決中起較大作用,減小分類誤差大的弱分類器的權(quán)重,使其在表決中起較小的作用.

提升方法Adaboost算法

假定給定一個(gè)二類分類的訓(xùn)練數(shù)據(jù)集

T={(x1,y1),(x2,y2),...,(xN,yN)}

其中,每個(gè)樣本點(diǎn)由實(shí)例與標(biāo)記組成.實(shí)例 xi∈χRn,類標(biāo)記 yi∈Y={1,+1},X是實(shí)例空間,Y是標(biāo)記集合.Adaboost利用如下算法,從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)一系列弱分類器或基本分類器,并將這些弱分類器線性組合成為一個(gè)強(qiáng)分類器.

Adaboost算法流程

輸入:訓(xùn)練數(shù)據(jù)集 T={(x1,y1),(x2,y2),...,(xN,yN)},其中, xi∈χRn; yi∈Y={1,+1};弱學(xué)習(xí)算法;

輸出:最終分類器G(x).

(1)初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布

D1=(w11,...,w1i,...,w1N),w1i=1N,i=1,2,..,N

(2)對(duì)m=1,2,...,M

(a)使用具有權(quán)值分布 Dm的訓(xùn)練數(shù)據(jù)集學(xué)習(xí),得到基本分類器

Gm(x)→{1,+1}

(b)計(jì)算 Gm(x)在訓(xùn)練數(shù)據(jù)集上的分類誤差率

em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)

(c)計(jì)算 Gm(x)的系數(shù)

am=12log1emem

這里的對(duì)數(shù)是自然對(duì)數(shù)

(d)更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布

wm+1,i=wmiZmexp(amyiGm(xi)),i=1,2,....,N

Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)

這里, Zm是規(guī)范化因子

Zm=∑i=1Nwmiexp(amyiGm(xi))

它使 Dm成為一個(gè)概率分布.

(3)構(gòu)建基本分類器的線性組合

f(x)=∑m=1MamGm(x)

得到最終分類器

G(x)=sign(f(x))=sign(∑m=1MamGm(x))

Adaboost算法的說(shuō)明

步驟(1)  假設(shè)訓(xùn)練數(shù)據(jù)集具有均勻的權(quán)值分布,即每個(gè)訓(xùn)練樣本在基本分類器的學(xué)習(xí)中作用相同,這一假設(shè)保證第1步能夠在原始數(shù)據(jù)上學(xué)習(xí)基本分類器 G1(x)

步驟(2)  Adaboost反復(fù)學(xué)習(xí)基本分類器,在每一輪m=1,2,...,M順次地執(zhí)行下列操作:

(a)使用當(dāng)前分布 Dm加權(quán)的訓(xùn)練數(shù)據(jù)集,學(xué)習(xí)基本分類器 Gm(x).

(b)計(jì)算基本分類器 Gm(x)在加權(quán)訓(xùn)練數(shù)據(jù)集上的分類誤差率:

em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)

這里, wmi表示第m輪中第i個(gè)實(shí)例的權(quán)值, ∑i=1Nwmi=1.這表明, Gm(x)在加權(quán)的訓(xùn)練數(shù)據(jù)集上的分類誤差率是被 Gm(x)誤分類樣本的權(quán)值之和,由此可以看出數(shù)據(jù)權(quán)值分布 Dm與基本分類器 Gm(x)的分類誤差率的關(guān)系.

(c)計(jì)算基本分類器 Gm(x)的系數(shù) am. am表示 Gm(x)在最終分類器中的重要性.當(dāng) em≤12時(shí), am≥0,并且 am隨著

em的減小而增大,所以分類誤差率越小的基本分類器在最終分類器中的作用越大.

(d)更新訓(xùn)練數(shù)據(jù)的權(quán)值分布為下一輪作準(zhǔn)備.

wm+1,i={wmiZmeam,Gm(xi)=yiwmiZmeam,Gm(xi)≠yi

由此可知,被基本分類器 Gm(x)誤分類樣本的權(quán)值得以擴(kuò)大,而被正確分類樣本的權(quán)值卻得以縮小.兩相比較,誤分類樣本的權(quán)值被放大 e2am=1emem倍.因此,誤分類樣本在下一輪學(xué)習(xí)中起更大的作用.不改變所給的訓(xùn)練數(shù)據(jù),而不斷改變訓(xùn)練數(shù)據(jù)權(quán)值的分布,使得訓(xùn)練數(shù)據(jù)在基本分類器的學(xué)習(xí)中起不同的作用,這是Adaboost的一個(gè)特點(diǎn).

步驟(3)  線性組合f(x)實(shí)現(xiàn)M個(gè)基本分類器的加權(quán)表決.系數(shù) am表示了基本分類器 Gm(x)的重要性,這里,所有 am之和并不為1.f(x)的符號(hào)決定實(shí)例的x的類,f(x)的絕對(duì)值表示分類的確信度.利用基本分類器的線性組合構(gòu)建最終分類器是Adaboost的另一個(gè)特點(diǎn).

Adaboost算法的解釋

Adaboost算法還有另一個(gè)解釋,即可以認(rèn)為Adaboost算法是模型為加法模型、損失函數(shù)為指數(shù)函數(shù)、學(xué)習(xí)算法為前向分布算法的二類分類學(xué)習(xí)方法。

Adaboost算法的訓(xùn)練誤差分析

Adaboost最基本的性質(zhì)是它能在學(xué)習(xí)過(guò)程中不斷減少訓(xùn)練誤差,即在訓(xùn)練數(shù)據(jù)集上的分類誤差率.關(guān)于這個(gè)問(wèn)題有下面的定理:

定理1 (Adaboost的訓(xùn)練誤差界) Adaboost算法最終分類器的訓(xùn)練誤差界為

1N∑i=1NI(G(xi)≠yi)≤1N∑i=1Nexp(yif(xi))=∏mZm

證明 當(dāng) G(xi)≠yi時(shí), yif(xi)<0,因而 exp(yif(xi))≥1.由此直接推導(dǎo)出前半部分

后半部分的證明要用到 Zm的定義,具體推導(dǎo)如下:

這一定理說(shuō)明,可以在每一輪選取適當(dāng)?shù)?Gm使得 Zm最小,從而使訓(xùn)練誤差下降最快.

對(duì)于二分類問(wèn)題,有如下結(jié)果:

定理2 (二分類問(wèn)題AdaBoost的訓(xùn)練誤差界)

∏mZm=∏m=1M[2em(1em)√]=∏m=1M(14γ2m)√≤exp(2∑m=1Mγ2m)

這里, γm=12em.

證明 由 Zm的定義式以及 em=∑Gm(xi)≠yiwmi可得:

至于不等式

∏m=1M(14γ2m)√≤exp(2∑m=1Mγ2m)

則可先由 ex和 1x√在x=0的泰勒展開(kāi)式推出不等式 (14γ2m)√≤exp(2γ2m).

推論 如果存在 γ>0,對(duì)所有的m有 γm>γ,則

1N∑i=1NI(G(xi)≠yi)≤exp(2Mγ2)

這表明在此條件下Adaboost的訓(xùn)練誤差是以指數(shù)速率下降的.Adaboost算法不需要知道下界 γ.這正是Freund與Schapire設(shè)計(jì)Adaboost時(shí)所考慮的.與一些早期的算法不同,Adaboost具有適應(yīng)性,即它能適應(yīng)弱分類器各自的訓(xùn)練誤差率.這也是它的名稱(適應(yīng)的提升)的由來(lái),Ada是Adaptive的簡(jiǎn)寫.

提升樹

提升樹是以分類樹或回歸樹為基本分類器的提升方法。提升樹被認(rèn)為是統(tǒng)計(jì)學(xué)習(xí)中性能最好的方法之一。

提升樹模型

提升方法實(shí)際采用加法模型（即基函數(shù)的線性組合）與前向分步算法。以決策樹為基函數(shù)的提升方法稱為提升樹（boosting tree）。對(duì)分類問(wèn)題決策樹是二叉分類樹，對(duì)回歸問(wèn)題決策樹是二叉回歸樹(一般就是CART樹)。提升樹模型可以表示為決策樹的加法模型：

fM(x)=∑m=1MT(x;Θm)

其中， T(x;Θm)表示決策樹; Θm表示決策樹的參數(shù);M為樹的個(gè)數(shù).

提升樹算法

提升樹采用前向分布算法,首先確定初始提升樹 f0(x)=0,第m步的模型是

fm(x)=fm1(x)+T(x;Θm)

其中, fm1(x)為當(dāng)前模型,通過(guò)經(jīng)驗(yàn)風(fēng)險(xiǎn)極小化確定下一棵決策樹的參數(shù) Θm.

Θ^m=argminΘm∑i=1NL(yi,fm1(x)+T(x;Θm))

由于樹的線性組合可以很好地?cái)M合訓(xùn)練數(shù)據(jù),即使數(shù)據(jù)中的輸入與輸出之間的關(guān)系很復(fù)雜也是如此,所以提升樹是一個(gè)高功能的學(xué)習(xí)算法.

針對(duì)不同問(wèn)題的提升樹學(xué)習(xí)算法,其主要區(qū)別在于使用的損失函數(shù)不同.包括用平方誤差損失函數(shù)的回歸問(wèn)題,用指數(shù)損失函數(shù)的分類問(wèn)題,以及用一般損失函數(shù)的一般決策問(wèn)題.

對(duì)于二類分類問(wèn)題,提升樹算法只需要將Adaboost算法的基本分類器限制為二類分類樹即可,可以說(shuō)這時(shí)的提升樹算法是Adaboost算法的特殊情況,這里不再細(xì)述.下面敘述回歸問(wèn)題的提升樹.

當(dāng)采用平方誤差損失函數(shù)時(shí):

L(y,f(x))=(yf(x))2

其損失變?yōu)?/p>

∑i=1NL(yi,fm1(x)+T(x;Θm))=[yfm1(x)T(x;Θm)]2=[rT(x;Θm)]2

這里,

r=yfm1(x)

是當(dāng)前模型擬合數(shù)據(jù)的殘差(residual).所以,對(duì)回歸問(wèn)題的提升樹算法來(lái)說(shuō),只需簡(jiǎn)單地?cái)M合當(dāng)前模型的殘差.

這樣,算法是相當(dāng)簡(jiǎn)單的,現(xiàn)將回歸問(wèn)題的提升樹算法描述如下.

一個(gè)例子

對(duì)于年齡預(yù)測(cè)，簡(jiǎn)單起見(jiàn)訓(xùn)練集只有4個(gè)人，A,B,C,D，他們的年齡分別是14,16,24,26。其中A、B分別是高一和高三學(xué)生；C,D分別是應(yīng)屆畢業(yè)生和工作兩年的員工。如果是用一棵傳統(tǒng)的回歸決策樹來(lái)訓(xùn)練，會(huì)得到如下圖1所示結(jié)果：

現(xiàn)在我們使用GBDT來(lái)做這件事，由于數(shù)據(jù)太少，我們限定葉子節(jié)點(diǎn)做多有兩個(gè)，即每棵樹都只有一個(gè)分枝，并且限定只學(xué)兩棵樹。我們會(huì)得到如下圖2所示結(jié)果：

在第一棵樹分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測(cè)值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測(cè)值 + A的殘差 = A的實(shí)際值）， 所以A的殘差就是16-15=1（注意，A的預(yù)測(cè)值是指前面所有樹累加的和，這里前面只有一棵樹所以直接是15，如果還有樹則需要都累加起來(lái)作為A的預(yù)測(cè) 值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹去學(xué)習(xí)，如果我們的預(yù)測(cè)值和它們的殘 差相等，則只需把第二棵樹的結(jié)論累加到第一棵樹上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí) 所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。

換句話說(shuō)，現(xiàn)在A,B,C,D的預(yù)測(cè)值都和真實(shí)年齡一致了.：

A: 14歲高一學(xué)生，購(gòu)物較少，經(jīng)常問(wèn)學(xué)長(zhǎng)問(wèn)題；預(yù)測(cè)年齡A = 15 – 1 = 14

B: 16歲高三學(xué)生；購(gòu)物較少，經(jīng)常被學(xué)弟問(wèn)問(wèn)題；預(yù)測(cè)年齡B = 15 + 1 = 16

C: 24歲應(yīng)屆畢業(yè)生；購(gòu)物較多，經(jīng)常問(wèn)師兄問(wèn)題；預(yù)測(cè)年齡C = 25 – 1 = 24

D: 26歲工作兩年員工；購(gòu)物較多，經(jīng)常被師弟問(wèn)問(wèn)題；預(yù)測(cè)年齡D = 25 + 1 = 26

(此例子摘自http://blog.csdn.net/w28971023/article/details/8240756)

梯度提升決策樹(Gradient boosting decision tree,GBDT)

回歸

對(duì)于損失函數(shù)

L(y,f(x))=(yf(x))2

我們把f(x)換作z,那么損失函數(shù)L(z)就是一個(gè)關(guān)于z的函數(shù),取什么樣的z使損失函數(shù)最小,這是一個(gè)最簡(jiǎn)單的優(yōu)化問(wèn)題,通常我們通過(guò)梯度下降的方式來(lái)求解,也就是:

znew=zold+aL(z)z

這個(gè)式子是不是跟提升樹的前向分布算法的式子很像:

fm(x)=fm1(x)+T(x;Θm)

所以,我們讓 T(x;Θm)去擬合梯度的話,算法也是在逐漸優(yōu)化的.求極小值就是負(fù)梯度方向:

[L(yi,f(xi))f(xi)]f(xi)=fm1(xi)

不同的損失函數(shù)會(huì)有不同的梯度式子:

(從上面的講解來(lái)看這個(gè)跟上面的提升樹擬合殘差很想,這不過(guò)這里換成梯度,擬合梯度,有的地方叫這里的梯度為偽殘差)

分類

在分類問(wèn)題中，有一個(gè)很重要的內(nèi)容叫做Multi-Class Logistic，也就是多分類的Logistic問(wèn)題，它適用于那些類別數(shù)>2的問(wèn)題，并且在分類結(jié)果中，樣本x不是一定只屬于某一個(gè)類可以得到樣本x分別屬于多個(gè)類的概率（也可以說(shuō)樣本x的估計(jì)y符合某一個(gè)幾何分布），這實(shí)際上是屬于Generalized Linear Model中討論的內(nèi)容，這里就先不談了，以后有機(jī)會(huì)再用一個(gè)專門的章節(jié)去做吧。這里就用一個(gè)結(jié)論：如果一個(gè)分類問(wèn)題符合幾何分布，那么就可以用Logistic變換來(lái)進(jìn)行之后的運(yùn)算。

假設(shè)對(duì)于一個(gè)樣本x，它可能屬于K個(gè)分類，其估計(jì)值分別為F1(x)…FK(x)，Logistic變換如下，logistic變換是一個(gè)平滑且將數(shù)據(jù)規(guī)范化（使得向量的長(zhǎng)度為1）的過(guò)程，結(jié)果為屬于類別k的概率pk(x)，

對(duì)于Logistic變換后的結(jié)果，損失函數(shù)為：

其中，yk為輸入的樣本數(shù)據(jù)的估計(jì)值，當(dāng)一個(gè)樣本x屬于類別k時(shí)，yk = 1，否則yk = 0。

將Logistic變換的式子帶入損失函數(shù)，并且對(duì)其求導(dǎo)，可以得到損失函數(shù)的梯度：

上面說(shuō)的比較抽象，下面舉個(gè)例子：

假設(shè)輸入數(shù)據(jù)x可能屬于5個(gè)分類（分別為1,2,3,4,5），訓(xùn)練數(shù)據(jù)中，x屬于類別3，則y = (0, 0, 1, 0, 0)，假設(shè)模型估計(jì)得到的F(x) = (0, 0.3, 0.6, 0, 0)，則經(jīng)過(guò)Logistic變換后的數(shù)據(jù)p(x) = (0.16,0.21,0.29,0.16,0.16)，y - p得到梯度g：(-0.16, -0.21, 0.71, -0.16, -0.16)。觀察這里可以得到一個(gè)比較有意思的結(jié)論：

假設(shè)gk為樣本當(dāng)某一維（某一個(gè)分類）上的梯度:

gk>0時(shí)，越大表示其在這一維上的概率p(x)越應(yīng)該提高，比如說(shuō)上面的第三維的概率為0.29，就應(yīng)該提高，屬于應(yīng)該往“正確的方向”前進(jìn)

越小表示這個(gè)估計(jì)越“準(zhǔn)確”

gk<0時(shí)，越小，負(fù)得越多表示在這一維上的概率應(yīng)該降低，比如說(shuō)第二維0.21就應(yīng)該得到降低。屬于應(yīng)該朝著“錯(cuò)誤的反方向”前進(jìn)

越大，負(fù)得越少表示這個(gè)估計(jì)越“不錯(cuò)誤 ”

總的來(lái)說(shuō)，對(duì)于一個(gè)樣本，最理想的梯度是越接近0的梯度。所以，我們要能夠讓函數(shù)的估計(jì)值能夠使得梯度往反方向移動(dòng)（>0的維度上，往負(fù)方向移動(dòng)，<0的維度上，往正方向移動(dòng)）最終使得梯度盡量=0），并且該算法在會(huì)嚴(yán)重關(guān)注那些梯度比較大的樣本，跟Boost的意思類似。

得到梯度之后，就是如何讓梯度減少了。這里是用的一個(gè)迭代+決策樹的方法，當(dāng)初始化的時(shí)候，隨便給出一個(gè)估計(jì)函數(shù)F(x)（可以讓F(x)是一個(gè)隨機(jī)的值，也可以讓F(x)=0），然后之后每迭代一步就根據(jù)當(dāng)前每一個(gè)樣本的梯度的情況，建立一棵決策樹。就讓函數(shù)往梯度的反方向前進(jìn)，最終使得迭代N步后，梯度越小。

這里建立的決策樹和普通的決策樹不太一樣，首先，這個(gè)決策樹是一個(gè)葉子節(jié)點(diǎn)數(shù)J固定的，當(dāng)生成了J個(gè)節(jié)點(diǎn)后，就不再生成新的節(jié)點(diǎn)了。

算法的流程如下:（參考自treeBoost論文）

0. 表示給定一個(gè)初始值

1. 表示建立M棵決策樹（迭代M次）

2. 表示對(duì)函數(shù)估計(jì)值F(x)進(jìn)行Logistic變換

3. 表示對(duì)于K個(gè)分類進(jìn)行下面的操作（其實(shí)這個(gè)for循環(huán)也可以理解為向量的操作，每一個(gè)樣本點(diǎn)xi都對(duì)應(yīng)了K種可能的分類yi，所以yi, F(xi), p(xi)都是一個(gè)K維的向量，這樣或許容易理解一點(diǎn)）

4. 表示求得殘差減少的梯度方向

5. 表示根據(jù)每一個(gè)樣本點(diǎn)x，與其殘差減少的梯度方向，得到一棵由J個(gè)葉子節(jié)點(diǎn)組成的決策樹

6. 為當(dāng)決策樹建立完成后，通過(guò)這個(gè)公式，可以得到每一個(gè)葉子節(jié)點(diǎn)的增益（這個(gè)增益在預(yù)測(cè)的時(shí)候用的）

每個(gè)增益的組成其實(shí)也是一個(gè)K維的向量，表示如果在決策樹預(yù)測(cè)的過(guò)程中，如果某一個(gè)樣本點(diǎn)掉入了這個(gè)葉子節(jié)點(diǎn)，則其對(duì)應(yīng)的K個(gè)分類的值是多少。比如說(shuō)，GBDT得到了三棵決策樹，一個(gè)樣本點(diǎn)在預(yù)測(cè)的時(shí)候，也會(huì)掉入3個(gè)葉子節(jié)點(diǎn)上，其增益分別為（假設(shè)為3分類的問(wèn)題）：

(0.5, 0.8, 0.1),  (0.2, 0.6, 0.3),  (0.4, 0.3, 0.3)，那么這樣最終得到的分類為第二個(gè)，因?yàn)檫x擇分類2的決策樹是最多的。

7. 的意思為，將當(dāng)前得到的決策樹與之前的那些決策樹合并起來(lái)，作為新的一個(gè)模型(跟6中所舉的例子差不多)

(此小節(jié)摘自http://www.cnblogs.com/LeftNotEasy/archive/2011/03/07/1976562.html)