> 本篇文章先介紹了提升放法和AdaBoost算法。已經了解的可以直接跳過。后面給出了AdaBoost算法的兩個例子，附有詳細計算過程。
## 1、提升方法（來源于統計學習方法）
??提升方法是一種常用的統計學習方法，應用十分廣泛且有效。在分類問題中，它通過改變訓練樣本的權重，學習多個分類器，并將這些分類器進行線性組合，提高分類的性能。提升算法基于這樣一種思路：對于一個復雜任務來說，將多個專家的判斷進行適當的綜合所得出的判斷，要比其中任何一個專家單獨的判斷好。實際上，就是“三個臭皮匠頂個諸葛亮”的道理。?
??歷史上，Kearns和Valiant首先提出了“強可學習（strongly learnable）”和“弱可學習（weakly learnable）”的概念。指出：在概率近似正確（probably approximately correct，PAC）學習框架中，一個概念（一個分類），如果存在一個多項式的學習算法能夠學習它，并且正確率很高，那么就稱這個概念是強可學習的；一個概念，如果存在一個多項式的學習算法能夠學習它，學習的正確率僅比隨機猜測略好，那么就稱這個概念是弱可學習的。非常有趣的是Schapire后來證明強可學習與弱可學習是等價的，也就是說，在PAC學習的框架下，一個概念是強可學習的充分必要條件是這個概念是弱可學習的。?
??這樣一來，問題便成為，在學習中，如果已經發現了“弱學習算法”，那么能否將它提升（boost）為“強學習算法”。大家知道，發現弱學習算法通常要比發現強學習算法容易得多。那么如何具體實施提升，便成為開發提升方法時所要解決的問題。關于提升方法的研究很多，有很多算法被提出。最具代表性的是AdaBoost算法（AdaBoost algorithm）。?
??對于分類問題而言，給定一個訓練樣本集，求比較粗糙的分類規則（弱分類器）要比求精確的分類規則（強分類器）容易得多。提升方法就是從弱學習算法出發，反復學習，得到一系列弱分類器，然后組合這些分類器，構成一個強分類器。?
??這樣。對于提升算法來說，有兩個問題需要回答：一是在每一輪如何改變訓練數據的權值分布；二是如何將弱分類器組合成為一個強分類器。
## 2、AdaBoost算法
??對于上一小節末尾提出的提升方法的兩個問題，AdaBoost算法的做法是：1、提高那些被前一輪弱分類器錯誤分類樣本的權值，而降低那些被正確分類樣本的權值。2、采用加權多數表決的方法。具體的，加大分類誤差率小的弱分類器的權值，使其在表決中起較大的作用，減小分類誤差大的弱分類器的權值，使其在表決中起較小的作用。?
??下面給出AdaBoost算法的公式：
> 輸入：訓練數據集T={（x1,y1）,（x2,y2）,...（xN,yN）},其中xi∈X?Rn,yi∈Y={?1,+1};弱學習算法。?
> 輸出：最終分類器G(x)。?
> （1）初始化訓練數據的權值分布?
> ???
>
> D1=(w11,...,w1i,...,w1N),w1i=1N,i=1,2,...,N
>
> ???注：第一次訓練弱分類器時各個樣本的權值是相等的。?
> （2）對m=1,2，…,M ????注：這里是個循環?
> （a）使用具有權值分布Dm的訓練數據集學習，得到基本分類器
>
> Gm:X→{?1,+1}
>
> （b）計算Gm(x)在訓練集上的分類誤差率
>
> em=P(Gm(xi)≠yi)=∑i=1nwmiI(Gm(xi)≠yi)
>
> 注：I(Gm(xi)≠yi)：不等函數I值為1.相等函數值為0。?
> （c）計算Gm(x)的系數
>
> αm=12log1?emem
>
> 這里的對數是自然對數。注：顯然αm是em的調單減函數，這里就解釋了為什么對于沒有正確分類的數據要加大權值。?
> （d）更新訓練數據集的權值分布?
>
>
> Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N)
>
>
>
> wm+1,i=wmiZmexp(?αmyiGm(xi))i=1,2,...,N
>
> 這里，Zm是規范化因子?
>
>
> Zm=∑i=1Nwmiexp(?αmyiGm(xi))
>
> 它使Dm+1成為一個概率分布。?
> 注：自已比較Zm與wm+1,i的表達式，會發現這里的Zm就是在對wm+1,i進行歸一化工作。?
> （3）構建基本分類器的線性組合
>
> f(x)=∑m=1MαmGm(x)
>
> 得到最終分類器
>
> G(x)=sign(f(x))=sign(∑m=1MαmGm(x))
注：對于增大分類錯誤數據的權值和分類誤差計算的說明：
> 1、Gm(x)的系數
>
> αm=12log1?emem
>
> αm表示Gm(x)在最終分類器中的重要性。由αm的表達式可知，當em?12時，αm?0?,并且αm隨著em的減小而增大，所以分類誤差越小的基本分類器在最終分類器中的作用越大。?
> 2、計算基本分類器Gm(x)在加權訓練數據集上的分類誤差率：
>
> em=P(Gm(xi)≠yi)=∑Gm(xi)≠yiwmi
>
> ,這里，wmi表示第m輪中第i個實例的權值，∑Ni=1=1（因為權值利用Zm進行了歸一化）。這表明，Gm(x)在加權的訓練數據集上的分類誤差是被Gm(x)誤分類楊蓓的權值之和，由此可以看出數據權值分布Dm與基本分類器Gm(x)的分類誤差率的關系。
## 3、AdaBoost算法實例
下面提供一個例子幫助大家理解上面的概念。?
給定如下表所示的訓練數據。假設弱分類器由xv或x>v產生，其閾值使該分類器在 訓練數據集上分類誤差率最低。試用AdaBoost算法學習一個強分類器
| 序號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| --- | :-: | --: | --- | --- | --- | --- | --- | --- | --- | --- |
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| y | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1 |
解：初始化數據權值分布
D1=(w11,w12,...,w110)
w1i=0.1,i=1,2,...,10
對m=1，?
（a）在權值分布為D1的訓練數據上，閾值v取2.5時分類誤差率最低，故基本分類器為
G1(x)={1,x2.5?1,x>2.5
（b）顯然序號為7、8、9數據產生了錯誤。G1(x)在訓練數據集上的誤差率等于將這3個數據的權值相加，即
e1=P(G1(xi)≠yi)=∑i=1nw1iI(G1(xi)≠yi)=0.3
注：I(G1(xi)≠yi)表示當G1(xi)不等于yi時 函數I()的值為1，等于時值為0。這里只有i=7,8,9時函數I值為1，其余為0。?
（c）計算G1(x)的系數
α1=12log1?e1e1=12log1?e1e1=0.4236
（d）更新訓練數據的權值分布：
D2=(w21,...,w2i,...,w210)
w2i=w1iZ1exp(?α1yiG1(xi)),i=1,2,...,10
Z1=∑i=1Nw1iexp(?α1yiG1(xi))=∑i=11?6,10110exp(?0.4236?1)+∑i=79110exp(?0.4236??1)=0.4583+0.4582=0.9165
w2i=w1iZ1exp(?α1yiG1(xi))=1100.9165exp(?0.4236?1)=0.07143,i=1,2,...,6,10
w2i=w1iZ1exp(?α1yiG1(xi))=1100.9165exp(?0.4236??1)=0.16667,i=7,8,9
D2=(w21,...,w2i,...,w210)=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143,)
f1(x)=α1G1(x)=0.4236G1(x)
分類器sign[f1(x)]在訓練數據集上有3個誤分點。?
對m=2，?
（a）在權值分布為D2的訓練數據上，閾值v取8.5時分類誤差率最低，故基本分類器為
G2(x)={1,x8.5?1,x>8.5
（b）顯然序號為4、5、6數據產生了錯誤。G2(x)在訓練數據集上的誤差率等于將這3個數據的權值相加，即
e2=P(G2(xi)≠yi)=∑i=1nw2iI(G2(xi)≠yi)=0.07143?3=0.2143
注：I(G2(xi)≠yi)表示當G2(xi)不等于yi時 函數I()的值為1，等于時值為0。這里只有i=4,5,6時函數I值為1，其余為0。?
（c）計算G2(x)的系數
α2=12log1?e2e2=12log1?e2e2=0.6496
（d）更新訓練數據的權值分布：
D3=(w31,...,w3i,...,w310)
w3i=w2iZ2exp(?α2yiG2(xi)),i=1,2,...,10
Z2=∑i=1Nw2iexp(?α2yiG2(xi))=∑i=11?3,100.07143exp(?0.6496?1)+∑i=790.16667exp(?0.4236?1)+∑i=460.07143exp(?0.4236??1)=0.14922+0.26113+0.41032=0.82067
w3i=w2iZ2exp(?α2yiG2(xi))=0.071430.82067exp(?0.6496?1)=0.0455,i=1,2,3,10
w3i=w2iZ2exp(?α2yiG2(xi))=0.071430.82067exp(?0.6496??1)=0.1667,i=4,5,6
w3i=w2iZ2exp(?α2yiG2(xi))=0.166670.82067exp(?0.6496?1)=0.1060,i=7，8，9
D3=(w31,...,w3i,...,w310)=(0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)
f2(x)=α1G1(x)+α2G2(x)=0.4236G1(x)+0.6496G2(x)
分類器sign[f2(x)]在訓練數據集上有3個誤分點。?
對m=3，?
（a）在權值分布為D3的訓練數據上，閾值v取5.5時分類誤差率最低，故基本分類器為
G3(x)={1,x>5.5?1,x5.5
（b）顯然序號為1、2、3、10的數據產生了錯誤。G3(x)在訓練數據集上的誤差率等于將這4個數據的權值相加，即
e3=P(G3(xi)≠yi)=∑i=1nw3iI(G2(xi)≠yi)=0.0445?4=0.1820
注：I(G3(xi)≠yi)表示當G3(xi)不等于yi時 函數I()的值為1，等于時值為0。這里只有i=1,2,3,10時函數I值為1，其余為0。?
（c）計算G3(x)的系數
α3=12log1?e3e3=12log1?e3e3=0.7514
（d）更新訓練數據的權值分布：
D4=(w41,...,w4i,...,w410)
w4i=w3iZ3exp(?α3yiG3(xi)),i=1,2,...,10
Z3=∑i=1Nw3iexp(?α3yiG3(xi))=∑i=11?3,100.0455exp(?0.7514??1)+∑i=790.1060exp(?0.7514?1)+∑i=460.1667exp(?0.7514?1)=0.38593+0.15000+0.23590=0.77183
w4i=w3iZ3exp(?α3yiG3(xi))=0.04550.77183exp(?0.7514??1)=0.125,i=1,2,3,10
w4i=w3iZ3exp(?α3yiG3(xi))=0.16670.77183exp(?0.7514?1)=0.102,i=4,5,6
w4i=w3iZ3exp(?α3yiG3(xi))=0.10600.77183exp(?0.7514?1)=0.065,i=7，8，9
D4=(w41,...,w4i,...,w410)=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
f3(x)=α1G1(x)+α2G2(x)+α3G3(x)=0.4236G1(x)+0.6496G2(x)+0.7514G3(x)
分類器sign[f3(x)]在訓練數據集上有0個誤分點。?
于是最終分類器為：
