Adaboost算法總結(jié)

前言

集成學(xué)習(xí)的Boosting算法串行生成多個(gè)弱學(xué)習(xí)器并按一定的結(jié)合策略生成強(qiáng)學(xué)習(xí)器，AdaBoost算法是Boosting系列算法中的一種，本文詳細(xì)總結(jié)了AdaBoost算法的相關(guān)理論。

目錄

1. Boosting算法基本原理

2. Boosting算法的權(quán)重理解

3. AdaBoost的算法流程

4. AdaBoost算法的訓(xùn)練誤差分析

5. AdaBoost算法的解釋

6. AdaBoost算法的正則化

7. AdaBoost算法的過擬合問題討論

8. 總結(jié)

Boosting的算法流程

Boosting算法是一種由原始數(shù)據(jù)集生成不同弱學(xué)習(xí)器的迭代算法，然后把這些弱學(xué)習(xí)器結(jié)合起來，根據(jù)結(jié)合策略生成強(qiáng)學(xué)習(xí)器。

如上圖，Boosting算法的思路：

（1）樣本權(quán)重表示樣本分布，對特定的樣本分布生成一個(gè)弱學(xué)習(xí)器。

（2）根據(jù)該弱學(xué)習(xí)器模型的誤差率e更新學(xué)習(xí)器權(quán)重α。

（3）根據(jù)上一輪的學(xué)習(xí)器權(quán)重α來更新下一輪的樣本權(quán)重。

（4）重復(fù)步驟(1)(2)(3)，結(jié)合所有弱學(xué)習(xí)器模型，根據(jù)結(jié)合策略生成強(qiáng)學(xué)習(xí)器。

Boosting算法的權(quán)重理解

Boosting算法意為可提升算法，可提升方法具體表現(xiàn)在（一）改變訓(xùn)練數(shù)據(jù)的概率分布（訓(xùn)練數(shù)據(jù)的權(quán)值分布），（二）弱分類器權(quán)重的生成。理解這兩個(gè)原理是理解AdaBoost算法的基礎(chǔ)。

1. 訓(xùn)練數(shù)據(jù)的權(quán)重理解

我們對癌癥病人和健康人作一個(gè)定性的分析，目的是理解Boosingt算法訓(xùn)練數(shù)據(jù)權(quán)重更新的思想。

如下圖為分類器G(1)的分類情況，假設(shè)樣本數(shù)據(jù)的權(quán)重相等。

癌癥誤分類成健康人的結(jié)果很可能是喪失生命，因此這種誤分類情況肯定不能出現(xiàn)的，若我們對該誤分類點(diǎn)的權(quán)重增加一個(gè)極大值，以突出該樣本的重要性，分類結(jié)果如下圖：

因此，增加誤分類樣本的權(quán)重，使分類器往該誤分類樣本的正確決策邊界方向移動(dòng)，當(dāng)權(quán)重增加到一定值時(shí)，誤分類樣本實(shí)現(xiàn)了正確分類，因?yàn)橛?xùn)練樣本的權(quán)重和是不變的，增加誤分類樣本權(quán)重的同時(shí)，也降低了正確分類樣本的權(quán)重。這是Boosting算法的樣本權(quán)重更新思想。

2. 弱學(xué)習(xí)器的權(quán)重理解

Boosting算法通過迭代生成了一系列的學(xué)習(xí)器，我們給予誤差率低的學(xué)習(xí)器一個(gè)高的權(quán)重，給予誤差率高的學(xué)習(xí)器一個(gè)低的權(quán)重，結(jié)合弱學(xué)習(xí)器和對應(yīng)的權(quán)重，生成強(qiáng)學(xué)習(xí)器。弱學(xué)習(xí)器的權(quán)重更新是符合常識(shí)的，弱學(xué)習(xí)器性能越好，我們越重視它，權(quán)重表示我們對弱學(xué)習(xí)器的重視程度，即權(quán)重越大，這是Boosting算法弱學(xué)習(xí)器權(quán)重的更新思想。

AdaBoost的算法流程

第一節(jié)描述了Boosting算法的流程，但是沒有給出具體的算法詳細(xì)說明：

（1）如何計(jì)算弱學(xué)習(xí)器的學(xué)習(xí)誤差；

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

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

（4）使用何種結(jié)合策略；

我們從這四種問題的角度去分析AdaBoost的分類算法流程和回歸算法流程。第k輪的弱分類器為

1. AdaBoost的分類算法流程

我們假設(shè)是二分類問題，輸出為{-1,1}。第K輪的弱分類器為

1) 計(jì)算弱分類器的分類誤差

在訓(xùn)練集上的加權(quán)誤差率為：

2) 弱學(xué)習(xí)權(quán)重系數(shù)α的計(jì)算

由上式可知，學(xué)習(xí)器誤差率越小，則權(quán)重系數(shù)越大。

3) 下一輪樣本的權(quán)重更新

其中Zk是規(guī)范化因子，使每輪訓(xùn)練數(shù)據(jù)集的樣本權(quán)重和等于1。

當(dāng)樣本處于誤分類的情況，則該誤分類樣本的權(quán)重增加；當(dāng)樣本是處于正確分類的情況，，則，該正確分類樣本的權(quán)值減小。

4） 結(jié)合策略，構(gòu)建最終分類器為：

2. AdaBoost的回歸算法流程

1) 計(jì)算弱學(xué)習(xí)器的回歸誤差率：

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

b) 計(jì)算每個(gè)樣本的相對誤差：

如果是線性誤差，則

如果是平方誤差，則

如果是指數(shù)誤差，則

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

（2） 弱學(xué)習(xí)權(quán)重系數(shù)α的計(jì)算

（3）下一輪樣本的權(quán)重更新

Zk是規(guī)范化因子，使樣本權(quán)重的和為1,

（4）結(jié)合策略，構(gòu)建最終學(xué)習(xí)器為：

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

過程就不推倒了，可參考李航《統(tǒng)計(jì)學(xué)習(xí)方法》P142~P143，這里就只給出結(jié)論。

AdaBoost的訓(xùn)練誤差界：

由上式可知，AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的，即AdaBoost算法隨著迭代次數(shù)的增加，訓(xùn)練誤差不斷減小，即模型偏差顯著降低 。

本文傾向于入門AdaBoost算法，下一篇文章會(huì)發(fā)散思維，介紹AdaBoost算法的相關(guān)性質(zhì)，