中國科學(xué)院大學(xué)機(jī)器學(xué)習(xí)——AdaBoost(共12頁)

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

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

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

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

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

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

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

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