內(nèi)容
一慎式、Adaboost簡介
二、Adaboost算法過程
三趟径、Adaboost算法的訓(xùn)練誤差分析
四瘪吏、Adaboost算法的解釋
五、提升樹
六蜗巧、詳細理解“梯度提升算法”
##############################################################################
一掌眠、Adaboost簡介
????AdaBoost，是英文"Adaptive Boosting"（自適應(yīng)增強）的縮寫幕屹，由Yoav Freund和Robert Schapire在1995年提出蓝丙。它的自適應(yīng)在于：前一個基本分類器分錯的樣本會得到加強，加權(quán)后的全體樣本再次被用來訓(xùn)練下一個基本分類器香嗓。同時迅腔，在每一輪中加入一個新的弱分類器，直到達到某個預(yù)定的足夠小的錯誤率或達到預(yù)先指定的最大迭代次數(shù)靠娱。
? ? 對于提升方法來說沧烈，有兩個問題需要回答：
? ? （1）在每一輪如何改變訓(xùn)練數(shù)據(jù)的權(quán)值和概率分布？
? ? ? ? ? ? ? 提高那些被前一輪分類器錯誤分類樣本的權(quán)值,而降低那些被正確分類的樣本的權(quán)值像云。
? ? ? ? ? ? ? 這樣大權(quán)值的分類樣本在后一輪的分類器會被更加關(guān)注锌雀。
? ? （2）如何將弱分類器組合成強分類器？
? ? ? ? ? ? ? 強分類器是弱分類器的組合迅诬，adaboost采取多數(shù)表決的方法腋逆。加大誤差小的分類器的權(quán)? ? ? ? ? ? ? ? ? ? 值，使其在表中其較大作用侈贷，減小誤差大的分類器的權(quán)值惩歉，使其在表中其較小作用。
二俏蛮、Adaboost算法過程
1.具體說來撑蚌，整個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)重較大枚抵，否則較小线欲。
2.?Adaboost算法流程
? ? 給定訓(xùn)練數(shù)據(jù)集：（x1,y1）...(xn,yn),其中yi屬于{-1,1}。用于表示訓(xùn)練樣本的類別標(biāo)簽汽摹，i=1,...,N李丰。Adaboost的目的就是從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)一系列弱分類器或基本分類器，然后將這些弱分類器組合成一個強分類器逼泣。
相關(guān)符號說明：
算法流程如下：
相關(guān)說明：
綜合上面的推導(dǎo)趴泌，可得樣本分錯與分對時，其權(quán)值更新的公式為：
另外拉庶，Z的推導(dǎo)過程如下嗜憔；
3.Adaboost算法實例
例：給定如圖所示的訓(xùn)練樣本，弱分類器采用平行于坐標(biāo)軸的直線氏仗，用Adaboost算法的實現(xiàn)強分類過程吉捶。
數(shù)據(jù)分析：
????將這10個樣本作為訓(xùn)練數(shù)據(jù)，根據(jù)?X?和Y?的對應(yīng)關(guān)系皆尔，可把這10個數(shù)據(jù)分為兩類呐舔，圖中用“+”表示類別1，用“O”表示類別-1床佳。本例使用水平或者垂直的直線作為分類器滋早，圖中已經(jīng)給出了三個弱分類器，即：
初始化：
首先需要初始化訓(xùn)練樣本數(shù)據(jù)的權(quán)值分布砌们，每一個訓(xùn)練樣本最開始時都被賦予相同的權(quán)值：wi=1/N杆麸，這樣訓(xùn)練樣本集的初始權(quán)值分布D1(i)：
令每個權(quán)值w1i= 1/N= 0.1搁进，其中，N= 10昔头，i= 1,2, ..., 10饼问，然后分別對于t= 1,2,3, ...等值進行迭代（t表示迭代次數(shù)，表示第t輪）揭斧，下表已經(jīng)給出訓(xùn)練樣本的權(quán)值分布情況：
第1次迭代t=1：
初試的權(quán)值分布D1為1/N（10個數(shù)據(jù)莱革，每個數(shù)據(jù)的權(quán)值皆初始化為0.1），
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D1=[0.1, ?0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1]
在權(quán)值分布D1的情況下讹开，取已知的三個弱分類器h1盅视、h2和h3中誤差率最小的分類器作為第1個基本分類器H1(x)（三個弱分類器的誤差率都是0.3，那就取第1個吧）
在分類器H1(x)=h1情況下旦万，樣本點“5 7 8”被錯分闹击，因此基本分類器H1(x)的誤差率為：
可見，被誤分類樣本的權(quán)值之和影響誤差率e成艘，誤差率e影響基本分類器在最終分類器中所占的權(quán)重α赏半。
然后，更新訓(xùn)練樣本數(shù)據(jù)的權(quán)值分布淆两，用于下一輪迭代断箫，對于正確分類的訓(xùn)練樣本“1 2 3 4 6 9 10”（共7個）的權(quán)值更新為：
? ? ? ?這樣，第1輪迭代后秋冰，最后得到各個樣本數(shù)據(jù)新的權(quán)值分布：D2=[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14]
? ? ? ?由于樣本數(shù)據(jù)“5 7 8”被H1(x)分錯了仲义，所以它們的權(quán)值由之前的0.1增大到1/6；反之丹莲，其它數(shù)據(jù)皆被分正確光坝，所以它們的權(quán)值皆由之前的0.1減小到1/14，下表給出了權(quán)值分布的變換情況：
????????可得分類函數(shù)：f1(x)=?α1H1(x) = 0.4236H1(x)甥材。此時盯另，組合一個基本分類器sign(f1(x))作為強分類器在訓(xùn)練數(shù)據(jù)集上有3個誤分類點（即5 7 8），此時強分類器的訓(xùn)練錯誤為：0.3洲赵。
第二次迭代t=2：
在權(quán)值分布D2的情況下鸳惯，再取三個弱分類器h1、h2和h3中誤差率最小的分類器作為第2個基本分類器H2(x)：
① 當(dāng)取弱分類器h1=X1=2.5時叠萍，此時被錯分的樣本點為“5 7 8”：誤差率e=1/6+1/6+1/6=3/6=1/2芝发；
② 當(dāng)取弱分類器h2=X1=8.5時，此時被錯分的樣本點為“3 4 6”：誤差率e=1/14+1/14+1/14=3/14苛谷；
③ 當(dāng)取弱分類器h3=X2=6.5時辅鲸，此時被錯分的樣本點為“1 2 9”：誤差率e=1/14+1/14+1/14=3/14；
?因此腹殿，取當(dāng)前最小的分類器h2作為第2個基本分類器H2(x)
顯然独悴，H2(x)把樣本“3 4 6”分錯了例书，根據(jù)D2可知它們的權(quán)值為D2(3)=1/14，D2(4)=1/14刻炒，?D2(6)=1/14决采，所以H2(x)在訓(xùn)練數(shù)據(jù)集上的誤差率：
這樣，第2輪迭代后坟奥，最后得到各個樣本數(shù)據(jù)新的權(quán)值分布：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D3=[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22]
? 下表給出了權(quán)值分布的變換情況：
可得分類函數(shù)：f2(x)=0.4236H1(x) + 0.6496H2(x)树瞭。此時，組合兩個基本分類器sign(f2(x))作為強分類器在訓(xùn)練數(shù)據(jù)集上有3個誤分類點（即3 4?6）爱谁，此時強分類器的訓(xùn)練錯誤為：0.3
第三次迭代t=3:
在權(quán)值分布D3的情況下晒喷，再取三個弱分類器h1、h2和h3中誤差率最小的分類器作為第3個基本分類器H3(x)：
① 當(dāng)取弱分類器h1=X1=2.5時管行，此時被錯分的樣本點為“5 7 8”：誤差率e=7/66+7/66+7/66=7/22厨埋；
② 當(dāng)取弱分類器h2=X1=8.5時，此時被錯分的樣本點為“3 4 6”：誤差率e=1/6+1/6+1/6=1/2=0.5捐顷；
③ 當(dāng)取弱分類器h3=X2=6.5時，此時被錯分的樣本點為“1 2 9”：誤差率e=1/22+1/22+1/22=3/22
這樣雨效，第3輪迭代后迅涮，得到各個樣本數(shù)據(jù)新的權(quán)值分布為：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D4=[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38]
? 下表給出了權(quán)值分布的變換情況：
?可得分類函數(shù)：f3(x)=0.4236H1(x) + 0.6496H2(x)+0.9229H3(x)。此時徽龟，組合三個基本分類器sign(f3(x))作為強分類器叮姑，在訓(xùn)練數(shù)據(jù)集上有0個誤分類點。至此据悔，整個訓(xùn)練過程結(jié)束传透。
整合所有分類器，可得最終的強分類器為：
這個強分類器Hfinal對訓(xùn)練樣本的錯誤率為0极颓！
三朱盐、Adaboost算法的訓(xùn)練誤差分析
????Adaboost最基本的性質(zhì)它能夠在學(xué)習(xí)中不斷減少訓(xùn)練誤差，即在訓(xùn)練數(shù)據(jù)集上的分類誤差率菠隆。關(guān)于訓(xùn)練誤差界有如8.5定理兵琳。
證明過程如下：
關(guān)于（8.5）、（8.6）以及（8.7）式子如下所示：
該式子的推導(dǎo)過程分為兩個步驟：左邊“<=”和右邊“=”
對于紅色框I(x)是指示函數(shù)所以取值是{-1,1}骇径，故左邊的證明成立躯肌。
對于綠色框內(nèi)更加詳細的證明過程：
從推導(dǎo)過程可以看出在每一輪選取適當(dāng)?shù)腉(x)使得Zm最小，從而使訓(xùn)練誤差最快破衔。因為選取的G（x）影響am的值清女，所以在推導(dǎo)的過程可以看出G（x）是對誤差率起決定性作用。
注：這里邊我們對adaboost算法的描述以及adaboost算法的例子都是假設(shè)在給定二分類訓(xùn)練數(shù)據(jù)集的晰筛。若不是二分類的數(shù)據(jù)集也可以嫡丙，只不過是在做具體闡述的時候會簡單明了拴袭。
證明用到的相關(guān)公式：
四、Adaboost算法的解釋
????????Adaboost算法還有另外一種解釋迄沫，即可以認為Adaboost算法是模型為加法模型稻扬、損失函數(shù)為指數(shù)函數(shù)、學(xué)習(xí)算法為前向算法時的二分類學(xué)習(xí)方法羊瘩。
前向分布算法的大致描述：
前向算法的具體流程（前向）：
五泰佳、提升樹
????????提升樹是以分類樹或者回歸樹為基本分類器的提升算法。提升樹被認為是統(tǒng)計學(xué)習(xí)中性能最好的方法之一尘吗。
????????提升方法實際采用加法模型（即基函數(shù)的線性組合）與前向分布算法逝她。
????????以決策樹為基函數(shù)的提升算法稱為提升樹。
????????對于分類問題的決策樹是二叉分類樹睬捶，對于回歸問題的決策樹是二叉回歸樹黔宛。
提升樹的模型可以表示為決策樹的加法模型（決策樹是二叉分類樹或者二叉回歸樹）：
提升樹算法：
討論不同問題的提升樹模型的學(xué)習(xí)算法，主要區(qū)別在于使用的損失函數(shù)不同：
? ? ? ? 1.平方誤差損失函數(shù)的回歸問題
? ? ? ? 2.指數(shù)損失函數(shù)的分類問題
? ? ? ? 3.一般損失函數(shù)的一般決策問題
注：就是通過最小化各種損失函數(shù)來更新對應(yīng)的提升樹模型的參數(shù)擒贸，即對提升樹模型學(xué)習(xí)的過程臀晃。
回歸問題的提升樹算法的描述：
回歸樹提升算法的具體過程：
詳細例子見李航，adaboost算法的大框沒變介劫，知識這里邊加了回歸和樹徽惋。所以就命名為回歸樹提升算法。
六座韵、詳細理解“梯度提升算法”
? ? ? ? ? ?提升樹利用加法模型與前向分布算法實現(xiàn)學(xué)習(xí)的優(yōu)化過程险绘。當(dāng)損失函數(shù)是平方損失函數(shù)和指數(shù)損失函數(shù)，利用前向算法每一步的優(yōu)化是很簡單的誉碴。
? ? ? ? ?但對一般的損失函數(shù)而言宦棺。往往不是那么容易。針對這一問題的存在黔帕，F(xiàn)reidman提出了梯度提升算法代咸。
梯度提升算法：
注：紅色框內(nèi)代表梯度提升算法的初始化；
? ? ? ? 綠色框內(nèi)代表計算偽殘差
? ? ? ? 藍色框內(nèi)代表利用線性搜索估計葉節(jié)點區(qū)域的值蹬屹，使損失函數(shù)極小化
? ? ? ? 黃色框內(nèi)代表更新樹
? ? ? ? 黑色代表得到最后的回歸樹
????????結(jié)合圖表理解下該算法：
詳細地址轉(zhuǎn)到：http://www.reibang.com/writer#/notebooks/29268484/notes/34244677
