參考資料：
《機器學習》周志華
《統計學習方法》李航
【知乎】adaboost為什麼不容易過拟合呢？
內建學習AdaBoost原理小結——劉建平
————————————————————————————————————
簡介
關于內建學習中的boosting和bagging我就不多說了，都是将弱學習器通過不同的內建方法變成強學習器的過程。而AdaBoost是Boosting算法中最著名的代表。
AdaBoost的原理非常簡單：先從初始訓練集訓練出一個基學習器，再根據基學習器的表現對訓練樣本分布進行調整，具體來說是提高預測結果中錯誤樣本的權重，降低預測結果中正确樣本的權重，使得先前基學習器做錯的訓練樣本在後續得到更多的關注，然後基于調整後的權重來訓練下一個基學習器；如此重複進行，直至基學習器數量達到了事先指定的數量。
從上面的原理簡介中可以抛出兩個問題：
- 權重調整具體是怎麼操作的？
- 如何将多個基學習器組合起來？
算法流程
基于上一節提出的兩個問題，我們先來走一遍AdaBoost算法的數學流程，看一下它的内部運作原理。
以二分類問題為例，給定一個資料集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) . . . , ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2)...,(x_n,y_n)\} T={(x1,y1),(x2,y2)...,(xn,yn)}，其中 y y y取1和-1分類别代表兩類。
1、第一步首先要對權值初始化，因為後面要調整權值，自然就有權值的初始化。第一輪對每個訓練樣本肯定是一視同仁的，是以每個樣本的權值都相等。
D 1 = ( w 11 , . . . , w 1 N ) ， w 1 i = 1 N ， i = 1 , 2 , . . . , N D_1=(w_{11},...,w_{1N})，w_{1i}=\frac{1}{N}，i=1,2,...,N D1=(w11,...,w1N)，w1i=N1，i=1,2,...,N其中 D 1 D_1 D1為第一輪的權重集合， w 1 i w_{1i} w1i代表第一輪第 i i i個樣本的權值。
2、第二步就要對于這個帶有初始化權值的訓練樣本，訓練出第一個基分類器。也就是說，此時對于帶有權值 D 1 D_1 D1的訓練樣本，得到基分類器：
G m ( x ) : x — — > { − 1 , + 1 } G_m(x):x——>\{-1,+1\} Gm(x):x——>{−1,+1}其中m代表這是第m輪疊代産生的基分類器。
3、計算基分類器 G m ( x ) G_m(x) Gm(x)在訓練資料上的分類誤差率
e m = P ( G m ( x i ) ≠ y i ) = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e_m=P(G_m(x_i)\neq y_i)=\sum^{N}_{i=1}w_{mi}I(G_m(x_i)\neq y_i) em=P(Gm(xi)̸=yi)=i=1∑NwmiI(Gm(xi)̸=yi)注意這裡計算的是分類誤差率，其中 I I I為一個輸出隻有0和1的函數，當括号裡的條件成立時，輸出1，反之輸出0。
我們可以看出，誤差率的就是錯誤分類的樣本的權值之和，其實這也很好了解，所有樣本的權值都相同且權值之和為1，那麼自然權值之和就能代表誤差率。從這一點出發我們就能想到，在之後調整權值之後，也就是分類錯誤的樣本權值增大後，下一輪疊代為了降低誤差率（錯誤樣本權值之和），自然會盡量把擁有較大權值的上一輪分類錯誤樣本判斷正确。（隻要在這一步了解了将權值之和設為誤差率的原因，整個AdaBoost的優化機制就通透很多了）
4、接下來這一步計算 G m ( x ) G_m(x) Gm(x)的系數，也就是我們上面抛出的兩個問題的第二個問題，基學習器是怎麼結合的，答案是通過特定的系數線性加和，系數計算如下：
a m = 1 2 l o g 1 − e m e m a_m=\frac{1}{2}log\frac{1-e_m}{e_m} am=21logem1−em這裡的對數是自然對數。
從這個式子可以知道，這個系數實際是在衡量基分類器在最終分類器重的作用大小。當 e m ≤ 1 2 e_m\leq\frac{1}{2} em≤21時， a m ≥ 0 a_m\geq0 am≥0，并且 a m a_m am随着 e m e_m em的減小而增大，也就是說分類誤差率越小的基分類器在最終分類器中的作用越大。
然而此時還能抛出一個問題，使得 a m a_m am随着 e m e_m em的減小而增大的表達形式有很多，為啥偏偏長這個樣子呢？其實這個系數長成這種形式的出發點并不是專門為了實作 a m a_m am随着 e m e_m em的減小而增大設計出來的，而是從AdaBoost原理出發就能推導出來。具體推導後面再說，先走通算法流程。
5、計算完基學習器的系數，基學習器就可以帶權加到總學習器中，那麼接下來就該整下一個基學習器了，當然，學習下一個基學習器之前要根據之前的預測結果來調整權值。
D m + 1 = ( w m + 1 , 1 , . . . , w m + 1 , i , . . . , w m + 1 , N ) D_{m+1}=(w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N}) Dm+1=(wm+1,1,...,wm+1,i,...,wm+1,N) w m + 1 , i = w m i Z m e x p ( − α m y i G M ( x i ) ) ， i = 1 , 2 , . . . , N w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_M(x_i))，i=1,2,...,N wm+1,i=Zmwmiexp(−αmyiGM(xi))，i=1,2,...,N其中， Z m 是 規 範 化 因 子 Z_m是規範化因子 Zm是規範化因子
Z m = ∑ i = 1 N w m i e x p ( − α m y i G M ( x i ) ) Z_m=\sum^{N}_{i=1}w_{mi}exp(-\alpha_my_iG_M(x_i)) Zm=i=1∑Nwmiexp(−αmyiGM(xi))它使 D m + 1 D_{m+1} Dm+1成為一個機率分布。其實說白了這個規範化因子就是個總和，作為分母使得權值即使調整但仍然壓縮在0到1之間，因為誤差率就是錯誤樣本的權值之和，而壓縮在0到1之間對成為機率是非常必要的。
那麼問題來了，權值為什麼要這麼調整？壓縮到0到1之間好了解，也就是說分母好了解，分子怎麼了解呢？一會兒再說，先把算法流程跑通。
6、調整完權值之後，我們像第2步一樣學出一個基學習器就好了，剩下的就是無限循環直至基學習器的數量到達實作的設定。那麼最後一步就是将所有的基分類器線性組合起來，非常簡單：
f ( x ) = ∑ m = 1 M α m G m ( x ) f(x)=\sum^{M}_{m=1}\alpha_mG_m(x) f(x)=m=1∑MαmGm(x)得到最終分類器
G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) G(x)=sign(f(x))=sign(\sum^{M}_{m=1}\alpha_mG_m(x)) G(x)=sign(f(x))=sign(m=1∑MαmGm(x))其中 s i g n ( ) sign() sign()函數是符号函數，自變量大于等于0輸出1，否則輸出-1。
tips：
1、上述推導中，如果相對正确分類的樣本來說（把其看作基準），誤分類樣本相當于被放大了 e 2 α m = e m 1 − e m e^{2\alpha_m}=\frac{e_m}{1-e_m} e2αm=1−emem倍
2、線性組合實作了基分類器的權重表決，系數表示了基分類器的重要性，系數的和并不為1
3、最終分類器 f ( x ) f(x) f(x)的符号決定樣本的分類，而 f ( x ) f(x) f(x)的絕對值表示 分類的确信程度。
算法内部原理
這一部分将解決算法流程中的那兩個遺留問題。
AdaBoost的本質是損失函數為指數函數的加法模型，學習過程本質是前向分布算法。聽起來是不是很拗口，加法模型可以了解為一種形式、架構，損失函數就是算法要優化的目标，學習過程就是說算法的尋友過程，就像BP神經網絡的學習過程是誤差逆傳播算法一樣。下面來一個一個解釋。
加法模型
形如：
f ( x ) = ∑ m = 1 M β m b ( x ; γ m ) f(x)=\sum^{M}_{m=1}\beta_mb(x;\gamma_m) f(x)=m=1∑Mβmb(x;γm)其中， b ( x ; γ m ) b(x;\gamma_m) b(x;γm)為基函數， γ m \gamma_m γm為基函數的參數， β m \beta_m βm為基函數的系數。
這樣的模型就是加法模型
前向分布算法
設 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))為損失函數，那麼加法模型的損失函數就是
m i n β m , γ ∑ i = 1 N L ( y i , ∑ m = 1 M β m b ( x i ; γ m ) ) \underset{\beta_m,\gamma}{min}\sum^{N}_{i=1}L(y_i,\sum^{M}_{m=1}\beta_mb(x_i;\gamma_m)) βm,γmini=1∑NL(yi,m=1∑Mβmb(xi;γm))想要優化這個損失函數就非常困難，因為需要協調每個基函數的參數以及系數來達到最優。而前向分布算法的思路是：基于加法模型的每一步，從前向後，每一步隻學習一個基函數及其系數，逐漸逼近優化目标，這樣就可以大大簡化複雜度。這說白了就是每一步都盡量做到目前的最好，但這種做法最後加和起來是否能達到全局最優呢？顯然是不一定的，因為總體最優并不一定是由每一步最優加起來得到的。
那麼具體的，每步隻需要優化以下損失函數：
m i n β , γ ∑ i = 1 N L ( y i , β b ( x i ; γ ) ) \underset{\beta,\gamma}{min}\sum^{N}_{i=1}L(y_i,\beta b(x_i;\gamma)) β,γmini=1∑NL(yi,βb(xi;γ))
總結一下前向分布算法的算法流程就是：
輸入：訓練資料集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} T={(x1,y1),(x2,y2),...,(xN,yN)}；損失函數 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x));基函數集 { b ( x ; γ ) } \{b(x;\gamma)\} {b(x;γ)}
輸出：加法模型f(x)
1、初始化 f 0 ( x ) = 0 f_0(x)=0 f0(x)=0
2、對 m = 1 , 2 , . . . , M m=1,2,...,M m=1,2,...,M（代表第m個基函數），極小化損失函數 ( β m , γ m ) = a r g m i n β , γ ∑ i = 1 N L ( y i , f m − 1 ( x i ) + β b ( x i ; γ ) ) (\beta_m,\gamma_m)=\underset{\beta,\gamma}{argmin}\sum^{N}_{i=1}L(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma)) (βm,γm)=β,γargmini=1∑NL(yi,fm−1(xi)+βb(xi;γ))得到參數 β m , γ m \beta_m,\gamma_m βm,γm
3、更新總模型 f m ( x ) = f m − 1 ( x ) + β m b ( x ; γ m ) f_m(x)=f_{m-1}(x)+\beta_mb(x;\gamma_m) fm(x)=fm−1(x)+βmb(x;γm)
4、循環以上步驟，直到基分類器的個數到達指定數量。
這節的開篇我們說，AdaBoost就是學習過程為前向分布算法、損失函數為指數函數的加法模型，加法模型和前向分布算法都介紹了，現在隻需要指定損失函數就可以得到AdaBoost從損失函數出發的推導過程了。（指數損失函數不介紹了）
AdaBoost從損失函數了解
上面說了，我們隻差個損失函數了，指數損失函數為：
L ( y , f ( x ) ) = e x p [ − y f ( x ) ] L(y,f(x))=exp[-yf(x)] L(y,f(x))=exp[−yf(x)]将指數損失函數代入上面的損失函數内，得到沒更新一個基分類器需要在訓練資料T上極小化以下：
( α m , G m ( x ) ) = a r g m i n α , G ∑ i = 1 N e x p [ − y i ( f m − 1 ( x i ) + α G ( x i ) ) ] (\alpha_m,G_m(x))=\underset{\alpha,G}{argmin}\sum^{N}_{i=1}exp[-y_i(f_{m-1}(x_i)+\alpha G(x_i))] (αm,Gm(x))=α,Gargmini=1∑Nexp[−yi(fm−1(xi)+αG(xi))]推導一下，可以得到
( α m , G m ( x ) ) = a r g m i n α , G ∑ i = 1 N w ˉ m i e x p [ − y i α G ( x i ) ] (\alpha_m,G_m(x))=\underset{\alpha,G}{argmin}\sum^{N}_{i=1}\bar{w}_{mi}exp[-y_i\alpha G(x_i)] (αm,Gm(x))=α,Gargmini=1∑Nwˉmiexp[−yiαG(xi)]其中， w ˉ m i = e x p [ − y i f m − 1 ( x i ) ] \bar{w}_{mi}=exp[-y_if_{m-1}(x_i)] wˉmi=exp[−yifm−1(xi)]。 w ˉ m i \bar{w}_{mi} wˉmi既不依賴 α \alpha α也不依賴 G G G，與最小化無關，但依賴于 f m − 1 ( x ) f_{m-1}(x) fm−1(x)，随着每一輪疊代而發生改變。像不像AdaBoost前面推導中的權值？非常像，但并不完全等價，這個随後解釋。
我們先來讨論一下使上述目标函數最小的 G m ∗ ( x ) G_m^*(x) Gm∗(x)，當 G m ∗ ( x ) G_m^*(x) Gm∗(x)預測正确的時候，它與 y i y_i yi的積必然為1（此處還是二分類情況，1和-1兩類），此時 e x p ( − α ) exp(-\alpha) exp(−α)對于任意 α > 0 \alpha>0 α>0結果都是一個較小的數字。但當 G m ∗ ( x ) G_m^*(x) Gm∗(x)預測錯誤的時候，符号就改變了，此時 e x p ( α ) exp(\alpha) exp(α)對于任意 α > 0 \alpha>0 α>0結果相對于預測正确的時候都是一個較大的數字。 e x p ( ) exp() exp()這一步隻會産生兩種結果，要麼 e x p ( − α ) exp(-\alpha) exp(−α)要麼 e x p ( α ) exp(\alpha) exp(α)，不同的是它所要相乘的為 w ˉ m i \bar{w}_{mi} wˉmi，是以要想使得上述目标函數最小，在 α \alpha α不變的情況下，使其最小的 G ( x ) G(x) G(x)必然由下式得到：
G m ∗ ( x ) = a r g m i n G ∑ i = 1 N w ˉ m i I ( y i ≠ G ( x i ) ) G^*_m(x)=\underset{G}{argmin}\sum^{N}_{i=1}\bar{w}_{mi}I(y_i\neq G(x_i)) Gm∗(x)=Gargmini=1∑NwˉmiI(yi̸=G(xi))這是一個顯而易見的結果。那麼此時這個 G m ∗ ( x ) G_m^*(x) Gm∗(x)是否等價于之前AdaBoost算法流程中推導的那個每一輪疊代的基函數？其實是等價的，但是一眼看不出來，因為要證明等價就需要證明它是使得每一輪誤差率最小的基函數，要證明它是使得每一輪誤差率最小的基函數就需要證明 w ˉ m i \bar{w}_{mi} wˉmi代表着權值，因為錯誤樣本的權值之和才等于誤差率。然而此時這個所謂的權值還不好證明，那麼我們就先放一邊，先看 α \alpha α。
接着上面的損失函數進行推導：
∑ i = 1 N w ˉ m i e x p [ − y i α G ( x i ) ] = ∑ y i = G m ( x i ) w ˉ m i e − α + ∑ y i ≠ G m ( x i ) w ˉ m i e α = ( e α − e − α ) ∑ i = 1 N w ˉ m i I ( y i ≠ G ( x i ) ) + e − α ∑ i = 1 N w ˉ m i \sum^{N}_{i=1}\bar{w}_{mi}exp[-y_i\alpha G(x_i)]\\=\sum_{y_i=G_m(x_i)}\bar{w}_{mi}e^{-\alpha}+\sum_{y_i\neq G_m(x_i)}\bar{w}_{mi}e^{\alpha}\\=(e^{\alpha}-e^{-\alpha})\sum^{N}_{i=1}\bar{w}_{mi}I(y_i\neq G(x_i))+e^{-\alpha}\sum^{N}_{i=1}\bar{w}_{mi} i=1∑Nwˉmiexp[−yiαG(xi)]=yi=Gm(xi)∑wˉmie−α+yi̸=Gm(xi)∑wˉmieα=(eα−e−α)i=1∑NwˉmiI(yi̸=G(xi))+e−αi=1∑Nwˉmi最後一步是把上面推導出來的 G m ∗ ( x ) G_m^*(x) Gm∗(x)代入其中了。損失函數推到現在，也就是說我們需要最小化的就是上面這一堆東西。我們之前說了，先來求 α \alpha α，那麼我們就對其求導并使導數為0，就可以輕松得到結果。
求解過程是非常容易的，但需要一個小的變換：
e m = ∑ i = 1 N w ˉ m i I ( y i ≠ G m ( x i ) ) ∑ i = 1 N w ˉ m i e_m=\frac{\sum^{N}_{i=1}\bar{w}_{mi}I(y_i\neq G_m(x_i))}{\sum^{N}_{i=1}\bar{w}_{mi}} em=∑i=1Nwˉmi∑i=1NwˉmiI(yi̸=Gm(xi))其實從這裡我們依稀可以看出 w ˉ m i \bar{w}_{mi} wˉmi是個什麼東西了，它雖然不完全等價于算法流程中推導的權值，但是它等價于權值的分子啊，也就是說隻相差規範化因子而已。我們這裡可以這麼說，隻要他等價于算法流程中權值的分子，那麼上面推導的這個誤差率的公式就是正确的。那麼，我們目前的遺留問題又變了——證明 w ˉ m i \bar{w}_{mi} wˉmi是權值的分子，一會兒再說。
當這個誤差率公式成立之後，我們可以輕松根據導數為0求出：
α m ∗ = 1 2 l o g 1 − e m e m \alpha_m^*=\frac12log\frac{1-e_m}{e_m} αm∗=21logem1−em這裡推導出來的 α \alpha α的表達形式就與之前算法流程中相同了。接下來我們再來解決權值的問題。
根據：
w ˉ m i = e x p [ − y i f m − 1 ( x i ) ] f m = f m − 1 ( x ) + α m G m ( x ) \bar{w}_{mi}=exp[-y_if_{m-1}(x_i)] \\ f_m=f_{m-1}(x)+\alpha_mG_m(x) wˉmi=exp[−yifm−1(xi)]fm=fm−1(x)+αmGm(x) 可以求得：
w ˉ m + 1 , i = w ˉ m i ( x ) e x p [ − y i α m G m ( x ) ] \bar{w}_{m+1,i}=\bar{w}_{mi}(x)exp[-y_i\alpha_mG_m(x)] wˉm+1,i=wˉmi(x)exp[−yiαmGm(x)]這個更新公式是不是非常面熟，與之前推導的權值就差一個規範化因子了！是以啊，它與之前權值的分子等價，上面的一切也就說得通了。
其實我們将兩個損失函數拿出來看看就會發現是完全等價的：
e m = P ( G m ( x i ) ≠ y i ) = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e_m=P(G_m(x_i)\neq y_i)=\sum^{N}_{i=1}w_{mi}I(G_m(x_i)\neq y_i) em=P(Gm(xi)̸=yi)=i=1∑NwmiI(Gm(xi)̸=yi)這是之前算法流程中誤差率的表達形式，每一輪需要極小化的也是它。
∑ i = 1 N w ˉ m i e x p [ − y i α G ( x i ) ] \sum^{N}_{i=1}\bar{w}_{mi}exp[-y_i\alpha G(x_i)] i=1∑Nwˉmiexp[−yiαG(xi)]這是從加法模型角度推導的損失函數形式，我們需要最小化的是它，而最小化它又等價于最小化：
∑ i = 1 N w ˉ m i I ( y i ≠ G ( x i ) ) \sum^{N}_{i=1}\bar{w}_{mi}I(y_i\neq G(x_i)) i=1∑NwˉmiI(yi̸=G(xi))這和算法流程中需要最小化的東西就是等價的，一個最小化分數的和，一個最小化分子的和，然而分母相同，那麼就是等價的。
兩個性質的一點說明
以上AdaBoost的基本數學原理已經說完了，但我在學習的時候看到兩個性質需要格外說明一下。第一個是AdaBoost的訓練誤差是以指數速率下降的，雖然我不知道這個性質能怎麼應用，但還是要拿出來說一下。（我怎麼想都隻是一個優點。。而已）第二個是AdBoost不容易過拟合，經常有人說AdaBoost不會過拟合，其實是不容易，完全不會是不可能的。這個優點其實作在都沒有一個完全令人信服的答案和嚴謹的推導過程，但前人為證明這個問題做出的貢獻我們也不能忽略。
1、誤差以指數速率下降
這個問題李航的《統計學習方法》中的證明過程已經非常清晰易懂了，我也就不再詳細解讀了，直接把過程截圖過來。
這一部分簡單說就是先證明了權值的累加小于等于 Z m Z_m Zm的累乘，之後又證明 Z m Z_m Zm的累乘小于等于指數形式的累乘。是以，權值的累加（也就是最終誤差）小于等于指數的累乘，也就是說誤差是沿着指數速率下降的。
AdaBoost不容易過拟合
這個問題直到現在都沒有一個完美的答案，我就在這裡引用一個知乎的回答吧，這個回答裡簡要介紹了前人的研究成果，希望能有所啟發。
[知乎] adaboost為什麼不容易過拟合——愈揚的回答
優缺點
Adaboost的主要優點有：
1、AdaBoost作為分類器時，分類精度很高
2、AdaBoost本身是一種架構，可以使用各種回歸分類模型建立弱學習器
3、作為簡單的二進制分類器時，構造簡單，結果可了解。
4、誤差以指數速率下降
5、不容易發生過拟合
AdaBoost的主要缺點有：
對異常樣本敏感，異常樣本在疊代中可能會獲得較高的權重，影響最終的強學習器的預測準确性。
關于AdaBoost在sklearn中的應用，貼上劉建平大佬的部落格，他寫的非常好。
scikit-learn Adaboost類庫使用小結——劉建平