Bagging與Adaboos演算法原理及推導（詳細版）

02-03

Bagging裝袋演算法

1.概念

是一種在原始數據集上通過有放回抽樣重新選出S個新數據集來訓練分類器的集成技術。也就是說這些新數據集是允許重複的。

使用訓練出來的分類器集合來對新樣本進行分類，然後用多數投票或者對輸出求均值的方法統計所有分類器的分類結果，結果最高的類別即為最終標籤。為了提高模型的方差(variance, 差異性)，bagging在訓練待組合的各個模型的時候是從訓練集合中隨機的抽取數據。比如隨機森林(random forest)就是多個隨機決策樹平均組合起來以達到較優分類準確率的模型。

2.演算法原理及實現

隨機採樣(bootsrap)就是從我們的訓練集裡面採集固定個數的樣本，但是每採集一個樣本後，都將樣本放回。也就是說，之前採集到的樣本在放回後有可能繼續被採集到。對於我們的Bagging演算法，一般會隨機採集和訓練集樣本數m一樣個數的樣本。這樣得到的採樣集和訓練集樣本的個數相同，但是樣本內容不同。如果我們對有m個樣本訓練集做T次的隨機採樣，，則由於隨機性，T個採樣集各不相同。

注意到這和GBDT(梯度提升決策樹)的子採樣是不同的。GBDT的子採樣是無放回採樣，而Bagging的子採樣是放回採樣。

對於一個樣本，它在某一次含m個樣本的訓練集的隨機採樣中，每次被採集到的概率是1m。不被採集到的概率為1?1m。如果m次採樣都沒有被採集中的概率是(1?1m)m。當m→∞時，(1?1m)m→1e?0.368。也就是說，在bagging的每輪隨機採樣中，訓練集中大約有36.8%的數據沒有被採樣集採集中。

對於這部分大約36.8%的沒有被採樣到的數據，我們常常稱之為袋外數據(Out Of Bag, 簡稱OOB)。這些數據沒有參與訓練集模型的擬合，因此可以用來檢測模型的泛化能力。

3.演算法流程

輸入為樣本集D={(x1,y1),(x2,y2),...(xm,ym)}，弱學習器演算法, 弱分類器迭代次數T。

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

1）對於t=1,2…,T:

a)對訓練集進行第t次隨機採樣，共採集m次，得到包含m個樣本的採樣集Dm

b)用採樣集Dm訓練第m個弱學習器Gm(x)

2) 如果是分類演算法預測，則T個弱學習器投出最多票數的類別或者類別之一為最終類別。如果是回歸演算法，T個弱學習器得到的回歸結果進行算術平均得到的值為最終的模型輸出。

Adaboost 演算法的原理與推導

1 Adaboost的原理

1.1 Adaboost是什麼

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

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

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

1.2 Adaboost演算法流程

給定一個訓練數據集T={(x1,y1), (x2,y2)…(xN,yN)}，其中實例

，而實例空間

，yi屬於標記集合{-1,+1}，Adaboost的目的就是從訓練數據中學習一系列弱分類器或基本分類器，然後將這些弱分類器組合成一個強分類器。

Adaboost的演算法流程如下：

步驟1. 首先，初始化訓練數據的權值分布。每一個訓練樣本最開始時都被賦予相同的權值：1/N。

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

a. 使用具有權值分布Dm的訓練數據集學習，得到基本分類器（選取讓誤差率最低的閾值來設計基本分類器）：

b. 計算Gm(x)在訓練數據集上的分類誤差率

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

c. 計算Gm(x)的係數，am表示Gm(x)在最終分類器中的重要程度（目的：得到基本分類器在最終分類器中所佔的權重）：

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

d. 更新訓練數據集的權值分布（目的：得到樣本的新的權值分布），用於下一輪迭代

使得被基本分類器Gm(x)誤分類樣本的權值增大，而被正確分類樣本的權值減小。就這樣，通過這樣的方式，AdaBoost方法能「重點關注」或「聚焦於」那些較難分的樣本上。

其中，Zm是規範化因子，使得Dm+1成為一個概率分布：

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

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

1.3 Adaboost的一個例子

下面，給定下列訓練樣本，請用AdaBoost演算法學習一個強分類器。

求解過程：初始化訓練數據的權值分布，令每個權值W1i = 1/N = 0.1，其中，N = 10，i = 1,2, ..., 10，然後分別對於m = 1,2,3, ...等值進行迭代。

拿到這10個數據的訓練樣本後，根據 X 和 Y 的對應關係，要把這10個數據分為兩類，一類是「1」，一類是「-1」，根據數據的特點發現：「0 1 2」這3個數據對應的類是「1」，「3 4 5」這3個數據對應的類是「-1」，「6 7 8」這3個數據對應的類是「1」，9是比較孤獨的，對應類「-1」。拋開孤獨的9不講，「0 1 2」、「3 4 5」、「6 7 8」這是3類不同的數據，分別對應的類是1、-1、1，直觀上推測可知，可以找到對應的數據分界點，比如2.5、5.5、8.5 將那幾類數據分成兩類。當然，這只是主觀臆測，下面實際計算下這個具體過程。

迭代過程1

對於m=1，在權值分布為D1（10個數據，每個數據的權值皆初始化為0.1）的訓練數據上，經過計算可得：

閾值v取2.5時誤差率為0.3（x < 2.5時取1，x > 2.5時取-1，則6 7 8分錯，誤差率為0.3），
閾值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），
閾值v取8.5時誤差率為0.3（x < 8.5時取1，x > 8.5時取-1，則3 4 5分錯，誤差率為0.3）。

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

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

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

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

t然後根據誤差率e1計算G1的係數：

這個a1代表G1(x)在最終的分類函數中所佔的權重，為0.4236。

t接著更新訓練數據的權值分布，用於下一輪迭代：

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

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

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

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

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

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

迭代過程2

對於m=2，在權值分布為D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的訓練數據上，經過計算可得：

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

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

t面對的還是下述樣本：

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

計算G2的係數：

更新訓練數據的權值分布：

D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)。被分錯的樣本「3 4 5」的權值變大，其它被分對的樣本的權值變小。

f2(x)=0.4236G1(x) + 0.6496G2(x)

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

迭代過程3

對於m=3，在權值分布為D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)的訓練數據上，經過計算可得：

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

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

t依然還是原樣本：

此時，被誤分類的樣本是：0 1 2 9，這4個樣本所對應的權值皆為0.0455，

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

t計算G3的係數：

更新訓練數據的權值分布：

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」的權值變大，其它被分對的樣本的權值變小。

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

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

現在，咱們來總結下3輪迭代下來，各個樣本權值和誤差率的變化，如下所示（其中，樣本權值D中加了下劃線的表示在上一輪中被分錯的樣本的新權值）：

訓練之前，各個樣本的權值被初始化為D1 = (0.1, 0.1,0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1)；
第一輪迭代中，樣本「6 7 8」被分錯，對應的誤差率為e1=P(G1(xi)≠yi) = 3*0.1 = 0.3，此第一個基本分類器在最終的分類器中所佔的權重為a1 = 0.4236。第一輪迭代過後，樣本新的權值為D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)；
第二輪迭代中，樣本「3 4 5」被分錯，對應的誤差率為e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143，此第二個基本分類器在最終的分類器中所佔的權重為a2 = 0.6496。第二輪迭代過後，樣本新的權值為D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.01667, 0.1060, 0.1060, 0.1060, 0.0455)；
第三輪迭代中，樣本「0 1 2 9」被分錯，對應的誤差率為e3 = P(G3(xi)≠yi) = 0.0455*4 = 0.1820，此第三個基本分類器在最終的分類器中所佔的權重為a3 = 0.7514。第三輪迭代過後，樣本新的權值為D4 = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)。

從上述過程中可以發現，如果某些個樣本被分錯，它們在下一輪迭代中的權值將被增大，同時，其它被分對的樣本在下一輪迭代中的權值將被減小。就這樣，分錯樣本權值增大，分對樣本權值變小，而在下一輪迭代中，總是選取讓誤差率最低的閾值來設計基本分類器，所以誤差率e（所有被Gm(x)誤分類樣本的權值之和）不斷降低。

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

G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]。

2 Adaboost的誤差界

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

事實上，Adaboost 最終分類器的訓練誤差的上界為：

下面，咱們來通過推導來證明下上述式子。

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

關於後半部分，別忘了：

整個的推導過程如下：

這個結果說明，可以在每一輪選取適當的Gm使得Zm最小，從而使訓練誤差下降最快。接著，咱們來繼續求上述結果的上界。

對於二分類而言，有如下結果：

其中，

。

繼續證明下這個結論。

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

而這個不等式

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

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

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

最後，Adaboost 還有另外一種理解，即可以認為其模型是加法模型、損失函數為指數函數、學習演算法為前向分步演算法的二類分類學習方法，下個月即12月份會再推導下，然後更新此文。而在此之前，有興趣的可以參看《統計學習方法》第8.3節或其它相關資料。

3 Adaboost 指數損失函數推導

事實上，在上文1.2節Adaboost的演算法流程的步驟3中，我們構造的各個基本分類器的線性組合

是一個加法模型，而Adaboost演算法其實是前向分步演算法的特例。那麼問題來了，什麼是加法模型，什麼又是前向分步演算法呢？

3.1 加法模型和前向分步演算法

如下圖所示的便是一個加法模型

其中，

稱為基函數，

稱為基函數的參數，

稱為基函數的係數。

在給定訓練數據及損失函數的條件下，學習加法模型成為經驗風險極小化問題，即損失函數極小化問題：

隨後，該問題可以作如此簡化：從前向後，每一步只學習一個基函數及其係數，逐步逼近上式，即：每步只優化如下損失函數：

這個優化方法便就是所謂的前向分步演算法。

下面，咱們來具體看下前向分步演算法的演算法流程：

輸入：訓練數據集

損失函數：
$L(y,f(x))$
基函數集：

輸出：加法模型
$f(x)$
演算法步驟：

1. 初始化
$f_{0}(x)=0$
2. 對於m=1,2,..M

a)極小化損失函數

得到參數

和

。

b)更新

3. 最終得到加法模型

就這樣，前向分步演算法將同時求解從m=1到M的所有參數 $(β_{m},γ_{m})$ 的優化問題簡化為逐次求解各個 $β_{m}$ , $γ_{m}$ (1≤m≤M）的優化問題。

總結：

以上內容均是引用，非原創！自己略有刪減和修改。引用鏈接下面已列舉出來。這兩篇文章講的都比較詳細，對於學習集成學習的兩個最重要的演算法是很好的參考資料。如果看完這兩篇文章還是沒法理解透徹。請參考這一篇文章，可以幫助你更好的理解Adaboost演算法——Adaboost演算法原理分析和實例+代碼（簡明易懂） - guyuealian的博客 - CSDN博客

集成學習還有另外一個重要的演算法——隨機森林。由於文章太長，將單獨成一篇。

引用：

Adaboost 演算法的原理與推導
集成學習之Bootstrap aggregating(Bagging)裝袋演算法