前言

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

目錄

1. Boosting算法基本原理

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

3. AdaBoost的算法流程

4. AdaBoost算法的訓練誤差分析

5. AdaBoost算法的解釋

6. AdaBoost算法的正則化

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

8. 總結(jié)

Boosting的算法流程

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

如上圖，Boosting算法的思路：

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

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

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

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

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

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

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

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

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

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

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

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

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

AdaBoost的算法流程

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

（1）如何計算弱學習器的學習誤差；

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

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

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

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

1. AdaBoost的分類算法流程

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

1) 計算弱分類器的分類誤差

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

2) 弱學習權(quán)重系數(shù)α的計算

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

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

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

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

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

2. AdaBoost的回歸算法流程

1) 計算弱學習器的回歸誤差率：

a) 計算訓練集上的最大誤差：

b) 計算每個樣本的相對誤差：

如果是線性誤差，則

如果是平方誤差，則

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

c) 計算回歸誤差率

（2） 弱學習權(quán)重系數(shù)α的計算

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

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

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

AdaBoost算法的訓練誤差分析

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

AdaBoost的訓練誤差界：

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

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