Adaboost 算法的原理與推導(dǎo)

0 引言

    一直想寫Adaboost來著，但遲遲未能動筆。其算法思想雖然簡單“聽取多人意見，最后綜合決策”，但一般書上對其算法的流程描述實在是過于晦澀。昨日11月1日下午，鄒博在我組織的機器學(xué)習(xí)班第8次課上講決策樹與Adaboost，其中，Adaboost講得酣暢淋漓，講完后，我知道，可以寫本篇博客了。

    無心啰嗦，本文結(jié)合鄒博之決策樹與Adaboost 的PPT 跟《統(tǒng)計學(xué)習(xí)方法》等參考資料寫就，可以定義為一篇課程筆記、讀書筆記或?qū)W習(xí)心得，有何問題或意見，歡迎于本文評論下隨時不吝指出，thanks。

1 Adaboost的原理

1.1 Adaboost是什么    

    AdaBoost，是英文"Adaptive Boosting"（自適應(yīng)增強）的縮寫，由Yoav Freund和Robert Schapire在1995年提出。它的自適應(yīng)在于：前一個基本分類器分錯的樣本會得到加強，加權(quán)后的全體樣本再次被用來訓(xùn)練下一個基本分類器。同時，在每一輪中加入一個新的弱分類器，直到達到某個預(yù)定的足夠小的錯誤率或達到預(yù)先指定的最大迭代次數(shù)。

    具體說來，整個Adaboost 迭代算法就3步：

1. 初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。如果有N個樣本，則每一個訓(xùn)練樣本最開始時都被賦予相同的權(quán)重：1/N。
   
2. 訓(xùn)練弱分類器。具體訓(xùn)練過程中，如果某個樣本點已經(jīng)被準(zhǔn)確地分類，那么在構(gòu)造下一個訓(xùn)練集中，它的權(quán)重就被降低；相反，如果某個樣本點沒有被準(zhǔn)確地分類，那么它的權(quán)重就得到提高。然后，權(quán)重更新過的樣本集被用于訓(xùn)練下一個分類器，整個訓(xùn)練過程如此迭代地進行下去。
3. 將各個訓(xùn)練得到的弱分類器組合成強分類器。各個弱分類器的訓(xùn)練過程結(jié)束后，加大分類誤差率小的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較大的決定作用，而降低分類誤差率大的弱分類器的權(quán)重，使其在最終的分類函數(shù)中起著較小的決定作用。換言之，誤差率低的弱分類器在最終分類器中占的權(quán)重較大，否則較小。

1.2 Adaboost算法流程

    給定一個訓(xùn)練數(shù)據(jù)集T={(x1,y1), (x2,y2)…(xN,yN)}，其中實例，而實例空間，yi屬于標(biāo)記集合{-1,+1}，Adaboost的目的就是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)一系列弱分類器或基本分類器，然后將這些弱分類器組合成一個強分類器。

    Adaboost的算法流程如下：

• 步驟1. 首先，初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。每一個訓(xùn)練樣本最開始時都被賦予相同的權(quán)重：1/N。

• 步驟2. 進行多輪迭代，用m = 1,2, ..., M表示迭代的第多少輪

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

由上述式子可知，Gm(x)在訓(xùn)練數(shù)據(jù)集上的誤差率em就是被Gm(x)誤分類樣本的權(quán)值之和。

由上述式子可知，em <= 1/2時，am >= 0，且am隨著em的減小而增大，意味著分類誤差率越小的基本分類器在最終分類器中的作用越大。

使得被基本分類器Gm(x)誤分類樣本的權(quán)值增大，而被正確分類樣本的權(quán)值減小。就這樣，通過這樣的方式，AdaBoost方法能“聚焦于”那些較難分的樣本上。

    其中，Zm是規(guī)范化因子，使得Dm+1成為一個概率分布：

• 步驟3. 組合各個弱分類器

從而得到最終分類器，如下：

1.3 Adaboost的一個例子

    下面，給定下列訓(xùn)練樣本，請用AdaBoost算法學(xué)習(xí)一個強分類器。

    求解過程：初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布，令每個權(quán)值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然后分別對于m = 1,2,3, ...等值進行迭代。

    拿到這10個數(shù)據(jù)的訓(xùn)練樣本后，根據(jù) X 和 Y 的對應(yīng)關(guān)系，要把這10個數(shù)據(jù)分為兩類，一類是“1”，一類是“-1”，根據(jù)數(shù)據(jù)的特點發(fā)現(xiàn)：“0 1 2”這3個數(shù)據(jù)對應(yīng)的類是“1”，“3 4 5”這3個數(shù)據(jù)對應(yīng)的類是“-1”，“6 7 8”這3個數(shù)據(jù)對應(yīng)的類是“1”，9是比較孤獨的，對應(yīng)類“-1”。拋開孤獨的9不講，“0 1 2”、“3 4 5”、“6 7 8”這是3類不同的數(shù)據(jù)，分別對應(yīng)的類是1、-1、1，直觀上推測可知，可以找到對應(yīng)的數(shù)據(jù)分界點，比如2.5、5.5、8.5 將那幾類數(shù)據(jù)分成兩類。當(dāng)然，這只是主觀臆測，下面實際計算下這個過程。

迭代過程1

對于m=1，在權(quán)值分布為D1（10個數(shù)據(jù)，每個數(shù)據(jù)的權(quán)值皆初始化為0.1）的訓(xùn)練數(shù)據(jù)上，經(jīng)過計算可得：

1. 閾值v取2.5時誤差率為0.3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.3），
2. 閾值v取5.5時誤差率最低為0.4（x < 5.5時取1，x > 5.5時取-1，則3 4 5 6 7 8皆分錯，誤差率0.6大于0.5，不可取。故令x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.4），
3. 閾值v取8.5時誤差率為0.3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.3）。

所以無論閾值v取2.5，還是8.5，總得分錯3個樣本，故可任取其中任意一個如2.5，弄成第一個基本分類器為：

上面說閾值v取2.5時則6 7 8分錯，所以誤差率為0.3，更加詳細的解釋是：因為樣本集中

1. 0 1 2對應(yīng)的類（Y）是1，因它們本身都小于2.5，所以被G1(x)分在了相應(yīng)的類“1”中，分對了。
2. 3 4 5本身對應(yīng)的類（Y）是-1，因它們本身都大于2.5，所以被G1(x)分在了相應(yīng)的類“-1”中，分對了。
3. 但6 7 8本身對應(yīng)類（Y）是1，卻因它們本身大于2.5而被G1(x)分在了類"-1"中，所以這3個樣本被分錯了。
4. 9本身對應(yīng)的類（Y）是-1，因它本身大于2.5，所以被G1(x)分在了相應(yīng)的類“-1”中，分對了。
   

從而得到G1(x)在訓(xùn)練數(shù)據(jù)集上的誤差率（被G1(x)誤分類樣本“6 7 8”的權(quán)值之和）e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。

然后根據(jù)誤差率e1計算G1的系數(shù)：

值得一提的是，由權(quán)值更新的公式可知，每個樣本的新權(quán)值是變大還是變小，取決于它是被分錯還是被分正確。

即如果某個樣本被分錯了，則yi * Gm(xi)為負，負負等正，結(jié)果使得整個式子變大（樣本權(quán)值變大），否則變小。

第一輪迭代后，最后得到各個數(shù)據(jù)新的權(quán)值分布D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出，因為樣本中是數(shù)據(jù)“6 7 8”被G1(x)分錯了，所以它們的權(quán)值由之前的0.1增大到0.1666，反之，其它數(shù)據(jù)皆被分正確，所以它們的權(quán)值皆由之前的0.1減小到0.0715。

分類函數(shù)f1(x)= a1*G1(x) = 0.4236G1(x)。

此時，得到的第一個基本分類器sign(f1(x))在訓(xùn)練數(shù)據(jù)集上有3個誤分類點（即6 7 8）。

    從上述第一輪的整個迭代過程可以看出：被誤分類樣本的權(quán)值之和影響誤差率，誤差率影響基本分類器在最終分類器中所占的權(quán)重。

  迭代過程2

對于m=2，在權(quán)值分布為D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715,  0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計算可得：

1. 閾值v取2.5時誤差率為0.1666*3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1666*3），
2. 閾值v取5.5時誤差率最低為0.0715*4（x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0715*3 + 0.0715），
3. 閾值v取8.5時誤差率為0.0715*3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.0715*3）。

所以，閾值v取8.5時誤差率最低，故第二個基本分類器為：

面對的還是下述樣本：

很明顯，G2(x)把樣本“3 4 5”分錯了，根據(jù)D2可知它們的權(quán)值為0.0715, 0.0715,  0.0715，所以G2(x)在訓(xùn)練數(shù)據(jù)集上的誤差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。

計算G2的系數(shù)：

此時，得到的第二個基本分類器sign(f2(x))在訓(xùn)練數(shù)據(jù)集上有3個誤分類點（即3 4 5）。

  迭代過程3

對于m=3，在權(quán)值分布為D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667,  0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的訓(xùn)練數(shù)據(jù)上，經(jīng)過計算可得：

1. 閾值v取2.5時誤差率為0.1060*3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.1060*3），
2. 閾值v取5.5時誤差率最低為0.0455*4（x > 5.5時取1，x < 5.5時取-1，則0 1 2 9分錯，誤差率為0.0455*3 + 0.0715），
3. 閾值v取8.5時誤差率為0.1667*3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.1667*3）。

所以閾值v取5.5時誤差率最低，故第三個基本分類器為（下圖畫反了，待后續(xù)修正）：

依然還是原樣本：

此時，被誤分類的樣本是：0 1 2 9，這4個樣本所對應(yīng)的權(quán)值皆為0.0455，

所以G3(x)在訓(xùn)練數(shù)據(jù)集上的誤差率e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

計算G3的系數(shù)：

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

D4 = (0.125, 0.125, 0.125, 0.102, 0.102,  0.102, 0.065, 0.065, 0.065, 0.125)。被分錯的樣本“0 1 2 9”的權(quán)值變大，其它被分對的樣本的權(quán)值變小。

f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

此時，得到的第三個基本分類器sign(f3(x))在訓(xùn)練數(shù)據(jù)集上有0個誤分類點。至此，整個訓(xùn)練過程結(jié)束。

    G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]，將上面計算得到的a1、a2、a3各值代入G(x)中，得到最終的分類器為：G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

2 Adaboost的誤差界

  通過上面的例子可知，Adaboost在學(xué)習(xí)的過程中不斷減少訓(xùn)練誤差e，直到各個弱分類器組合成最終分類器，那這個最終分類器的誤差界到底是多少呢？

事實上，Adaboost 最終分類器的訓(xùn)練誤差的上界為：

下面，咱們來通過推導(dǎo)來證明下上述式子。

當(dāng)G(xi)≠yi時，yi*f(xi)<0，因而exp(-yi*f(xi))≥1，因此前半部分得證。

關(guān)于后半部分，別忘了：

整個的推導(dǎo)過程如下：

    這個結(jié)果說明，可以在每一輪選取適當(dāng)?shù)腉m使得Zm最小，從而使訓(xùn)練誤差下降最快。接著，咱們來繼續(xù)求上述結(jié)果的上界。

    對于二分類而言，有如下結(jié)果：

    其中，。

    繼續(xù)證明下這個結(jié)論。

    由之前Zm的定義式跟本節(jié)最開始得到的結(jié)論可知：

    而這個不等式可先由e^x和1-x的開根號，在點x的泰勒展開式推出。

    值得一提的是，如果取γ1, γ2… 的最小值，記做γ（顯然，γ≥γi>0，i=1,2,...m），則對于所有m，有：

    這個結(jié)論表明，AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的。另外，AdaBoost算法不需要事先知道下界γ，AdaBoost具有自適應(yīng)性，它能適應(yīng)弱分類器各自的訓(xùn)練誤差率 。

    最后，Adaboost 還有另外一種理解，即可以認為其模型是加法模型、損失函數(shù)為指數(shù)函數(shù)、學(xué)習(xí)算法為前向分步算法的二類分類學(xué)習(xí)方法，有機會再推導(dǎo)下，然后更新此文。而在此之前，有興趣的可以參看《統(tǒng)計學(xué)習(xí)方法》第8.3節(jié)或其它相關(guān)資料。

3 參考文獻與推薦閱讀