? 姓名：崔升? ? 學號：14020120005
? 轉(zhuǎn)載自：http://www.cnblogs.com/en-heng/p/5173704.html
【嵌牛導讀】：
? AdaBoost是一種通過多個基分類器來完成學習任務的一種算法
【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之AdaBoost算法的簡單介紹
【嵌牛提問】：PageRank是一種怎么的算法，其如何通過多個分類的任務來完成學習系統(tǒng)呢？
【嵌牛正文】：
1. 集成學習
集成學習（ensemble learning）通過組合多個基分類器（base classifier）來完成學習任務，頗有點“三個臭皮匠頂個諸葛亮”的意味。基分類器一般采用的是弱可學習（weakly learnable）分類器，通過集成學習，組合成一個強可學習（strongly learnable）分類器。所謂弱可學習，是指學習的正確率僅略優(yōu)于隨機猜測的多項式學習算法；強可學習指正確率較高的多項式學習算法。集成學習的泛化能力一般比單一的基分類器要好，這是因為大部分基分類器都分類錯誤的概率遠低于單一基分類器的。
偏差與方差
“偏差-方差分解”（bias variance decomposition）是用來解釋機器學習算法的泛化能力的一種重要工具。對于同一個算法，在不同訓練集上學得結(jié)果可能不同。對于訓練集D={(x1,y1),(x2,y2),?,(xN,yN)}D={(x1,y1),(x2,y2),?,(xN,yN)}，由于噪音，樣本xx的真實類別為yDyD（在訓練集中的類別為yy），則噪聲為
ξ2=ED[(yd?y)2]ξ2=ED[(yd?y)2]
學習算法的期望預測為
fˉ(x)=ED[f(x;D)]fˉ(x)=ED[f(x;D)]
使用樣本數(shù)相同的不同訓練集所產(chǎn)生的方法
var(x)=ED[(f(x;D)?fˉ(x))2]var(x)=ED[(f(x;D)?fˉ(x))2]
期望輸入與真實類別的差別稱為bias，則
bias2(x)=(fˉ(x)?y)2bias2(x)=(fˉ(x)?y)2
為便于討論，假定噪聲的期望為0，即ED[yd?y]=0ED[yd?y]=0，通過多項式展開，可對算法的期望泛化誤差進行分解（詳細的推導參看[2]）：
ED[(f(x;D)?yD)2]=ED[(f(x;D)?fˉ(x)+fˉ(x)?yD)2]=ED[(f(x;D)?fˉ(x))2]+(fˉ(x)?y)2+ED[(yD?y)2]=bias2(x)+var(x)+ξ2ED[(f(x;D)?yD)2]=ED[(f(x;D)?fˉ(x)+fˉ(x)?yD)2]=ED[(f(x;D)?fˉ(x))2]+(fˉ(x)?y)2+ED[(yD?y)2]=bias2(x)+var(x)+ξ2
也就是說，誤差可以分解為3個部分：bias、variance、noise。bias度量了算法本身的擬合能力，刻畫模型的準確性；variance度量了數(shù)據(jù)擾動所造成的影響，刻畫模型的穩(wěn)定性。為了取得較好的泛化能力，則需要充分擬合數(shù)據(jù)（bias?。?，并受數(shù)據(jù)擾動的影響?。╲ariance?。?。但是，bias與variance往往是不可兼得的：
當訓練不足時，擬合能力不夠強，數(shù)據(jù)擾動不足以產(chǎn)生較大的影響，此時bias主導了泛化錯誤率；
隨著訓練加深時，擬合能力隨之加強，數(shù)據(jù)擾動漸漸被學習到，variance主導了泛化錯誤率。
Bagging與Boosting
集成學習需要解決兩個問題：
如何調(diào)整輸入訓練數(shù)據(jù)的概率分布及權(quán)值；
如何訓練與組合基分類器。
從上述問題的角度出發(fā)，集成學習分為兩類流派：Bagging與Boosting。Bagging（BootstrapAggregating）對訓練數(shù)據(jù)擦用自助采樣（boostrap sampling），即有放回地采樣數(shù)據(jù)；每一次的采樣數(shù)據(jù)集訓練出一個基分類器，經(jīng)過MM次采樣得到MM個基分類器，然后根據(jù)最大表決（majority vote）原則組合基分類器的分類結(jié)果。
Boosting的思路則是采用重賦權(quán)（re-weighting）法迭代地訓練基分類器，即對每一輪的訓練數(shù)據(jù)樣本賦予一個權(quán)重，并且每一輪樣本的權(quán)值分布依賴上一輪的分類結(jié)果；基分類器之間采用序列式的線性加權(quán)方式進行組合。
從“偏差-方差分解”的角度看，Bagging關注于降低variance，而Boosting則是降低bias；Boosting的基分類器是強相關的，并不能顯著降低variance。Bagging與Boosting有分屬于自己流派的兩大殺器：Random Forests（RF）和Gradient Boosting Decision Tree（GBDT）。本文所要講的AdaBoost屬于Boosting流派。
2. AdaBoost算法
AdaBoost是由Freund與Schapire [1] 提出來解決二分類問題y∈{0,1}y∈{0,1}，其定義損失函數(shù)為指數(shù)損失函數(shù)：
L(y,f(x))=exp(?yf(x))(1)(1)L(y,f(x))=exp(?yf(x))
根據(jù)加型模型（additive model），第mm輪的分類函數(shù)
fm(x)=fm?1(x)+αmGm(x)fm(x)=fm?1(x)+αmGm(x)
其中，αmαm為基分類器Gm(x)Gm(x)的組合系數(shù)。AdaBoost采用前向分布（forward stagewise）這種貪心算法最小化損失函數(shù)(1)(1)，求解子模型的αmαm
αm=12log1?ememαm=12log?1?emem
其中，emem為Gm(x)Gm(x)的分類誤差率。第m+1m+1輪的訓練數(shù)據(jù)集權(quán)值分布Dm+1=(wm+1,1,?,wm+1,i,?,wm+1,N)Dm+1=(wm+1,1,?,wm+1,i,?,wm+1,N)
wm+1,i=wm,iZmexp(?αmyiGm(xi))wm+1,i=wm,iZmexp(?αmyiGm(xi))
其中，ZmZm為規(guī)范化因子
Zm=∑i=1Nwm,i?exp(?αmyiGm(xi))Zm=∑i=1Nwm,i?exp(?αmyiGm(xi))
則得到最終分類器
sign(f(x))=sign(∑m=1MαmGm(x))sign(f(x))=sign(∑m=1MαmGm(x))
αmαm是emem的單調(diào)遞減函數(shù)，特別地，當em≤12em≤12時，αm≥0αm≥0；當em>12em>12時，即基分類器不滿足弱可學習的條件（比隨機猜測好），則應該停止迭代。具體算法流程如下：
1D1(i)=1/ND1(i)=1/N% Initialize the weight distribution
2 form=1,?,Mm=1,?,M:
3 learn base classifierGm(x)Gm(x);
4 ifem>0.5em>0.5then break；
5 updateαmαmandDm+1Dm+1;
6 end for
在算法第4步，學習過程有可能停止，導致學習不充分而泛化能力較差。因此，可采用“重采樣”（re-sampling）避免訓練過程過早停止；即拋棄當前不滿足條件的基分類器，基于重新采樣的數(shù)據(jù)訓練分類器，從而獲得學習“重啟動”機會。
AdaBoost能夠自適應（addaptive）地調(diào)整樣本的權(quán)值分布，將分錯的樣本的權(quán)重設高、分對的樣本的權(quán)重設低；所以被稱為“Adaptive Boosting”。sklearn的AdaBoostClassifier實現(xiàn)了AdaBoost，默認的基分類器是能fit()帶權(quán)值樣本的DecisionTreeClassifier。
老師木在微博上提出了關于AdaBoost的三個問題：
1，adaboost不易過擬合的神話。2，adaboost人臉檢測器好用的本質(zhì)原因，3，真的要求每個弱分類器準確率不低于50%
3. 參考資料
[1] Freund, Yoav, and Robert E. Schapire. "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting." Journal of Computer and System Sciences 55.1 (1997): 119-139.
[2] 李航，《統(tǒng)計學習方法》.
[3] 周志華，《機器學習》.
[4] Pang-Ning Tan, Michael Steinbach, Vipin Kumar,Introduction to Data Mining.
[5] Ji Zhu,Classification.
[6] @龍星鏢局，機器學習刀光劍影之 屠龍刀.
