中國科學院大學機器學習——AdaBoost(共12頁)

1、 Boosting主要(zhyo)內容：AdaBoost簡介(jin ji)訓練誤差(wch)分析測試誤差分析貝葉斯最大后驗前向遞增建模一、AdaBoost簡介：1.1 算法簡介給定訓練集：，其中，表示的正確的類別標簽，訓練集上樣本的初始分布：對，計算弱分類器，該弱分類器在分布上的誤差為：計算該弱分類器的權重：更新訓練樣本的分布：，其中為歸一化常數(shù)。最后的強分類器為：.1.2. AdaBoost過程舉例因為權重更新依賴于,而又依賴于,所以我們直接將權重更新公式用表示。樣本權重更新公式：，其中，當樣本分錯時，當樣本(yngbn)分對時，錯誤(cuw)分類樣本更新因子：正確分類樣本(yngbn)更

2、新因子：例：給定如圖1所示的樣本，弱分類器采用平行于坐標軸的直線 （1）得到第一個弱分類器：正確分類樣本權重：（7個）錯誤分類樣本權重：(3個)此時強分類器的訓練錯誤為：0.3（2）繼續(xù)計算第二個弱分類器：正確(zhngqu)分類樣本權重：（7個）又分為(fn wi)兩種： 第一輪正確(zhngqu)：（4個）第一輪錯分：（3個）錯誤分類樣本權重：(3個)第一輪正確: (3個)：此時強分類器的訓練錯誤為：0.3（3）繼續(xù)計算第三個弱分類器： 正確(zhngqu)分類樣本權重：（7個）又分為(fn wi)三種情況： 前兩輪(lin ln)都正確：（1個）第一輪錯分、第二輪正確：（3個）第一輪正確

3、、第二輪錯分：（3個）錯誤分類樣本權重：(3個)前兩輪正確: (3個)：此時強分類器的訓練錯誤為：0二、訓練誤差分析記，由于弱分類器的錯誤率總是比隨機猜測（隨機猜測的分類器的錯誤率為0.5），所以，則訓練誤差為：。記，則。證明：1、對進行迭代展開令。由于(yuy)是一個(y )分布，所以(suy)：所以。訓練誤差為 * 。所以，為訓練誤差的上界。相當于損失(snsh)函數(shù)取，則經驗(jngyn)風險/訓練(xnlin)誤差為，使該經驗風險最小的估計為。該風險稱為指數(shù)風險。*當樣本分對時，所以，是一個較小的正數(shù)。當樣本分錯時，所以。所以將變?yōu)?，相當于對上述兩種錯誤率都放大了，這樣不等式成立。證明

4、；問題：給定弱分類器的集合：，確定弱分類器及其權重。具體實現(xiàn)時，首先選一個錯誤率最小的弱分類器，然后確定其權重，所以是一個貪心算法。（相當于對，前向逐步遞增特征選擇，后面再詳細描述），因為即為分類正確(zhngqu)的樣本的集合，為分類(fn li)錯誤的樣本的集合。，兩邊(lingbin)同乘以正確率=，錯誤率=，所以所以。當很小時，很大，即錯誤率很小的弱分類器的權重很大。訓練誤差令（t = “edge”），由于弱分類器的錯誤率總是比隨機猜測（隨機猜測的分類器的錯誤率為0.5），所以，所以（不等式可利用(lyng)在處Taylor展開(zhn ki)得到(d do)）令，即為所有中最小的一個

5、。則訓練誤差的上界為：。所以，當，即訓練誤差的上界隨T的增加指數(shù)減小。三、測試誤差分析最終的強分類器為：。T為算法中唯一需要調整的參數(shù)，那么T該取多大值？初步猜測：T太大，模型會變得很復雜，會發(fā)生過擬合。但實際的運行結果為當訓練誤差已經等于0后，測試誤差仍然沒有增加，即使T已經達到1000。更好的解釋：Margin訓練誤差只考慮了分類是否正確，還應該(ynggi)考慮分類的信度。由于為弱分類器的投票權重，可將定義(dngy)為Margin，表示分類的信度。上述實驗(shyn)Margin的累積分布：可以證明，隨著T的增加，訓練樣本的Margin會增大（證明過程類似訓練誤差的證明）；而大的Mar

6、gin會帶來更好的泛化性能（如果所有樣本的Margin都很大，可以用一個很簡單的分類器實現(xiàn)分類）理論上，測試誤差的界：，其中D為弱分類器的復雜度。事實上，AdaBoost也可能發(fā)生過擬合（如下圖所示）。通常(tngchng)當滿足下述條件時，發(fā)生過擬合的可能性很?。喝醴诸惼鞯?edge)較大(jio d)（），即弱分類器不太弱，錯誤率不太低，從而(cng r)Margin較大；弱分類器相對樣本規(guī)模不太復雜。事實上上述heart-disease dataset就是數(shù)據規(guī)模太小，弱分類器的edge也較小。四、AdaBoost相當于最大貝葉斯后驗，當損失函數(shù)取時，則上述表達式為經驗風險，當樣本很多時

7、，樣本均值趨近于期望，即期望風險/測試誤差為。對上述風險，我們在每個樣本點(x)上最小化， 我們目標是風險最小的，即所以，即所以(suy)，為最大貝葉斯后驗。四、AdaBoost相當于前向逐步(zhb)遞增(dzng)建模，可視為基展開，其中為基函數(shù)，為對應基函數(shù)的權重。對基展開，通常是給定基函數(shù)，一次聯(lián)合求出所有的基函數(shù)中的參數(shù)及其權重（如用最小二乘法或極大似然估計方法）。而AdaBoost可視為一個逐步遞增的方式增加基函數(shù)，并計算其權重，不調整已添加的基函數(shù)中的參數(shù)及其權重。因此亦被稱為前向逐步遞增建模（forward stagewise additive modeling）.假設第步的模

8、型為：當損失函數(shù)取時，則第T步新增加的基函數(shù)及其權重要使得訓練誤差/經驗風險最小，即， ，其中。因為每個不依賴于，所以可以看作是應用于每個觀測的權值，該權值依賴于，所以，每個樣本的權值隨每次迭代改變。上述問題可以分兩步實現(xiàn)：第一步：首先選一個錯誤率最小的弱分類器，。第二步：然后確定(qudng)其權重， 因為(yn wi)將代入，即可得到(d do)，其中表示錯誤率。指數(shù)損失對outliers比較敏感，且也不是任何二值變量y的概率密度取log后的表示。因此另一種選擇是損失函數(shù)取負log似然損失，得到logitBoost （算法16.3）.對回歸問題，損失函數(shù)可取L2，得到L2boosting.圖：不同損失函數(shù)的比較。內容總結（1）Boosting主要內容：AdaBoost簡介訓練誤差分析測試誤差分析貝葉斯最大后驗