轉(zhuǎn)自：http://www.cnblogs.com/pinard/p/6133937.html

在集成學(xué)習(xí)原理小結(jié)中，我們講到了集成學(xué)習(xí)按照個(gè)體學(xué)習(xí)器之間是否存在依賴關(guān)系可以分為兩類，第一個(gè)是個(gè)體學(xué)習(xí)器之間存在強(qiáng)依賴關(guān)系，另一類是個(gè)體學(xué)習(xí)器之間不存在強(qiáng)依賴關(guān)系。前者的代表算法就是是boosting系列算法。在boosting系列算法中， Adaboost是最著名的算法之一。Adaboost既可以用作分類，也可以用作回歸。本文就對(duì)Adaboost算法做一個(gè)總結(jié)。

1. 回顧boosting算法的基本原理

在集成學(xué)習(xí)原理小結(jié)中，我們已經(jīng)講到了boosting算法系列的基本思想，如下圖：

從圖中可以看出，Boosting算法的工作機(jī)制是首先從訓(xùn)練集用初始權(quán)重訓(xùn)練出一個(gè)弱學(xué)習(xí)器1，根據(jù)弱學(xué)習(xí)的學(xué)習(xí)誤差率表現(xiàn)來更新訓(xùn)練樣本的權(quán)重，使得之前弱學(xué)習(xí)器1學(xué)習(xí)誤差率高的訓(xùn)練樣本點(diǎn)的權(quán)重變高，使得這些誤差率高的點(diǎn)在后面的弱學(xué)習(xí)器2中得到更多的重視。然后基于調(diào)整權(quán)重后的訓(xùn)練集來訓(xùn)練弱學(xué)習(xí)器2.，如此重復(fù)進(jìn)行，直到弱學(xué)習(xí)器數(shù)達(dá)到事先指定的數(shù)目T，最終將這T個(gè)弱學(xué)習(xí)器通過集合策略進(jìn)行整合，得到最終的強(qiáng)學(xué)習(xí)器。

不過有幾個(gè)具體的問題Boosting算法沒有詳細(xì)說明。

1）如何計(jì)算學(xué)習(xí)誤差率e?

2) 如何得到弱學(xué)習(xí)器權(quán)重系數(shù)αα?

3）如何更新樣本權(quán)重D?

4) 使用何種結(jié)合策略？

只要是boosting大家族的算法，都要解決這4個(gè)問題。那么Adaboost是怎么解決的呢？

2. Adaboost算法的基本思路

我們這里講解Adaboost是如何解決上一節(jié)這4個(gè)問題的。

假設(shè)我們的訓(xùn)練集樣本是

T={(x,y1),(x2,y2),...(xm,ym)}T={(x,y1),(x2,y2),...(xm,ym)}

訓(xùn)練集的在第k個(gè)弱學(xué)習(xí)器的輸出權(quán)重為

D(k)=(wk1,wk2,...wkm);w1i=1m;i=1,2...mD(k)=(wk1,wk2,...wkm);w1i=1m;i=1,2...m

首先我們看看Adaboost的分類問題。

分類問題的誤差率很好理解和計(jì)算。由于多元分類是二元分類的推廣，這里假設(shè)我們是二元分類問題，輸出為{-1，1}，則第k個(gè)弱分類器Gk(x)Gk(x)在訓(xùn)練集上的加權(quán)誤差率為

ek=P(Gk(xi)≠yi)=∑i=1mwkiI(Gk(xi)≠yi)ek=P(Gk(xi)≠yi)=∑i=1mwkiI(Gk(xi)≠yi)

接著我們看弱學(xué)習(xí)器權(quán)重系數(shù),對(duì)于二元分類問題，第k個(gè)弱分類器Gk(x)Gk(x)的權(quán)重系數(shù)為

αk=12log1?ekekαk=12log1?ekek

為什么這樣計(jì)算弱學(xué)習(xí)器權(quán)重系數(shù)？從上式可以看出，如果分類誤差率ekek越大，則對(duì)應(yīng)的弱分類器權(quán)重系數(shù)αkαk越小。也就是說，誤差率小的弱分類器權(quán)重系數(shù)越大。具體為什么采用這個(gè)權(quán)重系數(shù)公式，我們?cè)谥vAdaboost的損失函數(shù)優(yōu)化時(shí)再講。

第三個(gè)問題，更新更新樣本權(quán)重D。假設(shè)第k個(gè)弱分類器的樣本集權(quán)重系數(shù)為D(k)=(wk1,wk2,...wkm)D(k)=(wk1,wk2,...wkm)，則對(duì)應(yīng)的第k+1個(gè)弱分類器的樣本集權(quán)重系數(shù)為

wk+1,i=wkiZKexp(?αkyiGk(xi))wk+1,i=wkiZKexp(?αkyiGk(xi))

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

Zk=∑i=1mwkiexp(?αkyiGk(xi))Zk=∑i=1mwkiexp(?αkyiGk(xi))

從wk+1,iwk+1,i計(jì)算公式可以看出，如果第i個(gè)樣本分類錯(cuò)誤，則yiGk(xi)<0yiGk(xi)<0，導(dǎo)致樣本的權(quán)重在第k+1個(gè)弱分類器中增大，如果分類正確，則權(quán)重在第k+1個(gè)弱分類器中減少.具體為什么采用樣本權(quán)重更新公式，我們?cè)谥vAdaboost的損失函數(shù)優(yōu)化時(shí)再講。

最后一個(gè)問題是集合策略。Adaboost分類采用的是加權(quán)平均法，最終的強(qiáng)分類器為

f(x)=sign(∑k=1KαkGk(x))f(x)=sign(∑k=1KαkGk(x))

接著我們看看Adaboost的回歸問題。由于Adaboost的回歸問題有很多變種，這里我們以Adaboost R2算法為準(zhǔn)。

我們先看看回歸問題的誤差率的問題，對(duì)于第k個(gè)弱學(xué)習(xí)器，計(jì)算他在訓(xùn)練集上的最大誤差

Ek=max|yi?Gk(xi)|i=1,2...mEk=max|yi?Gk(xi)|i=1,2...m

然后計(jì)算每個(gè)樣本的相對(duì)誤差

eki=|yi?Gk(xi)|Ekeki=|yi?Gk(xi)|Ek

這里是誤差損失為線性時(shí)的情況，如果我們用平方誤差，則eki=(yi?Gk(xi))2E2keki=(yi?Gk(xi))2Ek2,如果我們用的是指數(shù)誤差，則eki=1?exp（?yi+Gk(xi))Ek）eki=1?exp（?yi+Gk(xi))Ek）

最終得到第k個(gè)弱學(xué)習(xí)器的 誤差率

ek=∑i=1mwkiekiek=∑i=1mwkieki

我們?cè)賮砜纯慈绾蔚玫饺鯇W(xué)習(xí)器權(quán)重系數(shù)αα。這里有：

αk=ek1?ekαk=ek1?ek

對(duì)于更新更新樣本權(quán)重D，第k+1個(gè)弱學(xué)習(xí)器的樣本集權(quán)重系數(shù)為

wk+1,i=wkiZkα1?ekikwk+1,i=wkiZkαk1?eki

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

Zk=∑i=1mwkiα1?ekikZk=∑i=1mwkiαk1?eki

最后是結(jié)合策略，和分類問題一樣，采用的也是加權(quán)平均法，最終的強(qiáng)回歸器為

f(x)=∑k=1K(ln1αk)Gk(x)f(x)=∑k=1K(ln1αk)Gk(x)

3. AdaBoost分類問題的損失函數(shù)優(yōu)化

剛才上一節(jié)我們講到了分類Adaboost的弱學(xué)習(xí)器權(quán)重系數(shù)公式和樣本權(quán)重更新公式。但是沒有解釋選擇這個(gè)公式的原因，讓人覺得是魔法公式一樣。其實(shí)它可以從Adaboost的損失函數(shù)推導(dǎo)出來。

從另一個(gè)角度講，　Adaboost是模型為加法模型，學(xué)習(xí)算法為前向分步學(xué)習(xí)算法，損失函數(shù)為指數(shù)函數(shù)的分類問題。

模型為加法模型好理解，我們的最終的強(qiáng)分類器是若干個(gè)弱分類器加權(quán)平均而得到的。

前向分步學(xué)習(xí)算法也好理解，我們的算法是通過一輪輪的弱學(xué)習(xí)器學(xué)習(xí)，利用前一個(gè)弱學(xué)習(xí)器的結(jié)果來更新后一個(gè)弱學(xué)習(xí)器的訓(xùn)練集權(quán)重。也就是說，第k-1輪的強(qiáng)學(xué)習(xí)器為

fk?1(x)=∑i=1k?1αiGi(x)fk?1(x)=∑i=1k?1αiGi(x)

而第k輪的強(qiáng)學(xué)習(xí)器為

fk(x)=∑i=1kαiGi(x)fk(x)=∑i=1kαiGi(x)

上兩式一比較可以得到

fk(x)=fk?1(x)+αkGk(x)fk(x)=fk?1(x)+αkGk(x)

可見強(qiáng)學(xué)習(xí)器的確是通過前向分步學(xué)習(xí)算法一步步而得到的。

Adaboost損失函數(shù)為指數(shù)函數(shù)，即定義損失函數(shù)為

argminα,G∑i=1mexp(?yifk(x))argmin?α,G∑i=1mexp(?yifk(x))

利用前向分步學(xué)習(xí)算法的關(guān)系可以得到損失函數(shù)為

(αk,Gk(x))=argminα,G∑i=1mexp[(?yi)(fk?1(x)+αG(x))](αk,Gk(x))=argmin?α,G∑i=1mexp[(?yi)(fk?1(x)+αG(x))]

令w′ki=exp(?yifk?1(x))wki′=exp(?yifk?1(x)), 它的值不依賴于α,Gα,G,因此與最小化無關(guān)，僅僅依賴于fk?1(x)fk?1(x),隨著每一輪迭代而改變。

將這個(gè)式子帶入損失函數(shù),損失函數(shù)轉(zhuǎn)化為

(αk,Gk(x))=argminα,G∑i=1mw′kiexp[?yiαG(x)](αk,Gk(x))=argmin?α,G∑i=1mwki′exp[?yiαG(x)]

首先，我們求Gk(x)Gk(x).，可以得到

Gk(x)=argminG∑i=1mw′kiI(yi≠G(xi))Gk(x)=argmin?G∑i=1mwki′I(yi≠G(xi))

將Gk(x)Gk(x)帶入損失函數(shù)，并對(duì)αα求導(dǎo)，使其等于0，則就得到了

αk=12log1?ekekαk=12log1?ekek

其中，ekek即為我們前面的分類誤差率。

ek=∑i=1mw′kiI(yi≠G(xi))∑i=1mw′ki=∑i=1mwkiI(yi≠G(xi))ek=∑i=1mwki′I(yi≠G(xi))∑i=1mwki′=∑i=1mwkiI(yi≠G(xi))

最后看樣本權(quán)重的更新。利用fk(x)=fk?1(x)+αkGk(x)fk(x)=fk?1(x)+αkGk(x)和w′ki=exp(?yifk?1(x))wki′=exp(?yifk?1(x))，即可得：

w′k+1,i=w′kiexp[?yiαkGk(x)]wk+1,i′=wki′exp[?yiαkGk(x)]

這樣就得到了我們第二節(jié)的樣本權(quán)重更新公式。

4. AdaBoost二元分類問題算法流程

這里我們對(duì)AdaBoost二元分類問題算法流程做一個(gè)總結(jié)。

輸入為樣本集T={(x,y1),(x2,y2),...(xm,ym)}T={(x,y1),(x2,y2),...(xm,ym)}，輸出為{-1, +1}，弱分類器算法, 弱分類器迭代次數(shù)K。

輸出為最終的強(qiáng)分類器f(x)f(x)

1) 初始化樣本集權(quán)重為

D(1)=(w11,w12,...w1m);w1i=1m;i=1,2...mD(1)=(w11,w12,...w1m);w1i=1m;i=1,2...m

2) 對(duì)于k=1,2，...K:

a) 使用具有權(quán)重DkDk的樣本集來訓(xùn)練數(shù)據(jù)，得到弱分類器Gk(x)Gk(x)

b)計(jì)算Gk(x)Gk(x)的分類誤差率

ek=P(Gk(xi)≠yi)=∑i=1mwkiI(Gk(xi)≠yi)ek=P(Gk(xi)≠yi)=∑i=1mwkiI(Gk(xi)≠yi)

c) 計(jì)算弱分類器的系數(shù)

αk=12log1?ekekαk=12log1?ekek

d) 更新樣本集的權(quán)重分布

wk+1,i=wkiZKexp(?αkyiGk(xi))i=1,2,...mwk+1,i=wkiZKexp(?αkyiGk(xi))i=1,2,...m

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

Zk=∑i=1mwkiexp(?αkyiGk(xi))Zk=∑i=1mwkiexp(?αkyiGk(xi))

3) 構(gòu)建最終分類器為：

f(x)=sign(∑k=1KαkGk(x))f(x)=sign(∑k=1KαkGk(x))

對(duì)于Adaboost多元分類算法，其實(shí)原理和二元分類類似，最主要區(qū)別在弱分類器的系數(shù)上。比如Adaboost SAMME算法，它的弱分類器的系數(shù)

αk=12log1?ekek+log(R?1)αk=12log1?ekek+log(R?1)

其中R為類別數(shù)。從上式可以看出，如果是二元分類，R=2，則上式和我們的二元分類算法中的弱分類器的系數(shù)一致。

5. Adaboost回歸問題的算法流程

這里我們對(duì)AdaBoost回歸問題算法流程做一個(gè)總結(jié)。AdaBoost回歸算法變種很多，下面的算法為Adaboost R2回歸算法過程。

輸入為樣本集T={(x,y1),(x2,y2),...(xm,ym)}T={(x,y1),(x2,y2),...(xm,ym)}，，弱學(xué)習(xí)器算法, 弱學(xué)習(xí)器迭代次數(shù)K。

輸出為最終的強(qiáng)學(xué)習(xí)器f(x)f(x)

1) 初始化樣本集權(quán)重為

D(1)=(w11,w12,...w1m);w1i=1m;i=1,2...mD(1)=(w11,w12,...w1m);w1i=1m;i=1,2...m

2) 對(duì)于k=1,2，...K:

a) 使用具有權(quán)重DkDk的樣本集來訓(xùn)練數(shù)據(jù)，得到弱學(xué)習(xí)器Gk(x)Gk(x)

b) 計(jì)算訓(xùn)練集上的最大誤差

Ek=max|yi?Gk(xi)|i=1,2...mEk=max|yi?Gk(xi)|i=1,2...m

c) 計(jì)算每個(gè)樣本的相對(duì)誤差:

如果是線性誤差，則eki=|yi?Gk(xi)|Ekeki=|yi?Gk(xi)|Ek；

如果是平方誤差，則eki=(yi?Gk(xi))2E2keki=(yi?Gk(xi))2Ek2

如果是指數(shù)誤差，則eki=1?exp（?yi+Gk(xi))Ek）eki=1?exp（?yi+Gk(xi))Ek）

d) 計(jì)算回歸誤差率

ek=∑i=1mwkiekiek=∑i=1mwkieki

c) 計(jì)算弱學(xué)習(xí)器的系數(shù)

αk=ek1?ekαk=ek1?ek

d) 更新樣本集的權(quán)重分布為

wk+1,i=wkiZkα1?ekikwk+1,i=wkiZkαk1?eki

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

Zk=∑i=1mwkiα1?ekikZk=∑i=1mwkiαk1?eki

3) 構(gòu)建最終強(qiáng)學(xué)習(xí)器為：

f(x)=∑k=1K(ln1αk)Gk(x)f(x)=∑k=1K(ln1αk)Gk(x)

6. Adaboost算法的正則化

為了防止Adaboost過擬合，我們通常也會(huì)加入正則化項(xiàng)，這個(gè)正則化項(xiàng)我們通常稱為步長(zhǎng)(learning rate)。定義為νν,對(duì)于前面的弱學(xué)習(xí)器的迭代

fk(x)=fk?1(x)+αkGk(x)fk(x)=fk?1(x)+αkGk(x)

如果我們加上了正則化項(xiàng)，則有

fk(x)=fk?1(x)+ναkGk(x)fk(x)=fk?1(x)+ναkGk(x)

νν的取值范圍為0<ν≤10<ν≤1。對(duì)于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的νν意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用步長(zhǎng)和迭代最大次數(shù)一起來決定算法的擬合效果。

7. Adaboost小結(jié)

到這里Adaboost就寫完了，前面有一個(gè)沒有提到，就是弱學(xué)習(xí)器的類型。理論上任何學(xué)習(xí)器都可以用于Adaboost.但一般來說，使用最廣泛的Adaboost弱學(xué)習(xí)器是決策樹和神經(jīng)網(wǎng)絡(luò)。對(duì)于決策樹，Adaboost分類用了CART分類樹，而Adaboost回歸用了CART回歸樹。

這里對(duì)Adaboost算法的優(yōu)缺點(diǎn)做一個(gè)總結(jié)。

Adaboost的主要優(yōu)點(diǎn)有：

1）Adaboost作為分類器時(shí)，分類精度很高

2）在Adaboost的框架下，可以使用各種回歸分類模型來構(gòu)建弱學(xué)習(xí)器，非常靈活。

3）作為簡(jiǎn)單的二元分類器時(shí)，構(gòu)造簡(jiǎn)單，結(jié)果可理解。

4）不容易發(fā)生過擬合

Adaboost的主要缺點(diǎn)有：

1）對(duì)異常樣本敏感，異常樣本在迭代中可能會(huì)獲得較高的權(quán)重，影響最終的強(qiáng)學(xué)習(xí)器的預(yù)測(cè)準(zhǔn)確性。

（歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處。歡迎溝通交流： pinard.liu@ericsson.com）