AdaBoost算法介紹

1. Boosting

Boosting（提升方法）是將弱學(xué)習(xí)器算法提升為強(qiáng)學(xué)習(xí)算法的統(tǒng)計(jì)學(xué)習(xí)方法博烂。在分類問題中，提升方法通過反復(fù)修改訓(xùn)練數(shù)據(jù)的權(quán)值分布傍妒，構(gòu)建一系列基本分類器（也稱為弱分類器）夺饲，并將這些基本分類器線性組合，構(gòu)成一個(gè)強(qiáng)分類器坷虑。AdaBoost就是Boosting中的代表性算法。Boosting原理可由下面這張圖所示：

Boosting.png

2. AdaBoost

2.1 AdaBoost算法過程

輸入：訓(xùn)練數(shù)據(jù)集 $T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$ 埂奈，其中 $x_i\in \chi \subseteq R^n$ 迄损；弱學(xué)習(xí)器算法；
輸出：最終分類器 $G(x)$
(1)初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布
$D_i=(W_{11},...,W_{1i},...,W_{1N}), \quad W_{1i}=\frac{1}{N},\quad i=1,2,...,N$

(2)對 $m$ 個(gè)基本分類器 $m=1,2,...,M$
(a)使用具有權(quán)值分布 $D_m$ 的訓(xùn)練數(shù)據(jù)集账磺，學(xué)習(xí)得到基本分類器 $G_m(x):\chi \to \{-1,+1 \}$

(b)計(jì)算 $G_m(x)$ 在訓(xùn)練數(shù)據(jù)集上的分類誤差率 $e_m=\sum_{i=1}^{N}P(G_m(x)\not=y_i)=\sum_{i=1}^{N}W_{mi}I(G_m(x)\not=y_i)$

(c)計(jì)算 $G_m(x)$ 的權(quán)重 $\alpha_m =\frac{1}{2}ln\frac{1-e_m}{e_m}$

(d)更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布 $D_{m+1}=(W_{m+1,1},...,W_{m+1,i},...,W_{m+1,N})$

$W_{m+1,i}=\frac{W_{mi}}{Z_{m}}exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,...,N$

其中芹敌， $Z_m$ 是規(guī)范化因子 $Z_m=\sum_{i=1}^{N}W_{mi}exp(-\alpha_my_iG_m(x_i))$

(3)構(gòu)建基本分類器的線性組合 $f(x)=\sum_{m=1}^{M}\alpha_mG_m(x)$

得到最終分類器 $G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x))$

其中， $sign(x)$ 是符號函數(shù)垮抗，取某個(gè)數(shù)的符號(正或負(fù))氏捞。

對上述過程的說明：
??步驟(1)：假設(shè)訓(xùn)練數(shù)據(jù)集具有均勻的權(quán)值分布，即每個(gè)訓(xùn)練樣本在基本分類器的學(xué)習(xí)中作用相同借宵，這一假設(shè)可以保證第1步能夠在原始數(shù)據(jù)集上學(xué)習(xí)得到基本分類器 $G_1(x)$
??步驟(2)：AdaBoost反復(fù)學(xué)習(xí)基本分類器幌衣，在每一輪 $m=1,2,...,M$ 依次執(zhí)行下列操作：
??(a)使用當(dāng)前權(quán)值分布為 $D_m$ 的訓(xùn)練數(shù)據(jù)集矾削，學(xué)習(xí)得到基本分類器 $G_m(x)$
??(b)計(jì)算基本分類器 $G_m(x)$ 在加權(quán)訓(xùn)練數(shù)據(jù)集上的分類誤差率： $e_m=\sum_{i=1}^{N}P(G_m(x_i)\not=y_i)=\sum_{G_m(x)\not=y_i}W_{mi}$

其中壤玫， $W_{mi}$ 表示第 $m$ 輪迭代中第 $i$ 個(gè)樣本的權(quán)值豁护，即 $G_m(x)$ 在加權(quán)訓(xùn)練數(shù)據(jù)集上的分類誤差率就是被 $G_m(x)$ 誤分類樣本的權(quán)值之和。
??(c)計(jì)算基本分類器 $G_m(x)$ 的權(quán)重欲间，即 $G_m(x)$ 在最終分類器中的重要性楚里。由上面(c)中公式可知，當(dāng)分類誤差率 $e_m\le\frac{1}{2}$ 時(shí)猎贴， $\alpha_m\ge0$ 班缎，且 $\alpha_m$ 隨著 $e_m$ 的減小而增大，因此分類誤差率越小的基本分類器在最終分類器中的作用越大她渴。
??(d)更新訓(xùn)練集的權(quán)值分布為學(xué)習(xí)下一個(gè)基本分類器作準(zhǔn)備达址。當(dāng) $G_m(x)\not=y_i$ 時(shí)， $W_{m+1,i}=\frac{W_{mi}}{Z_{m}}e^{\alpha_m}$ 趁耗；當(dāng) $G_m(x)=y_i$ 時(shí)沉唠， $W_{m+1,i}=\frac{W_{mi}}{Z_{m}}e^{-\alpha_m}$ ；由此可知苛败，被基本分類器 $G_m(x)$ 誤分類樣本的權(quán)值得以擴(kuò)大满葛，而被正確分類樣本的權(quán)值卻得以縮小。比較兩者的權(quán)值罢屈，發(fā)現(xiàn)誤分類樣本的權(quán)值被放大了 $e^{2\alpha_m}=\frac{1-e_m}{e_m}$ 倍嘀韧。
??步驟(3)：線性組合 $f(x)$ 實(shí)現(xiàn) $M$ 個(gè)基本分類器的加權(quán)表決。系數(shù) $\alpha_m$ 表示基本分類器 $G_m(x)$ 的重要性缠捌， $\alpha_m$ 的和并不為1锄贷。 $f(x)$ 的符號決定了實(shí)例x的類別， $f(x)$ 的絕對值表示分類的確信度鄙币。

2.2 AdaBoost算法的訓(xùn)練誤差分析

AdaBoost最基本的性質(zhì)是它能在學(xué)習(xí)過程中不斷減少訓(xùn)練誤差肃叶，即不斷減少在訓(xùn)練數(shù)據(jù)集上的分類誤差率。對此十嘿，《統(tǒng)計(jì)學(xué)習(xí)方法》中給出了如下定理：
定理1（AdaBoost的訓(xùn)練誤差界）AdaBoost算法的訓(xùn)練誤差界為 $\frac{1}{N}\sum_{i=1}^{N}I(G_m(x)\not=y_i)\le\frac{1}{N}\sum_{i=1}exp(-y_if(x_i))=\prod_mZ_m$
證明過程如下：

定理1證明.png

該定理說明因惭，可以在每一輪選取適當(dāng)?shù)?img class="math-inline" src="https://math.jianshu.com/math?formula=G_m" alt="G_m" mathimg="1">使得 $Z_m$ 最小，從而使訓(xùn)練誤差下降最快绩衷。對于二分類問題蹦魔，給出了如下定理：

定理2（二分類問題AdaBoost的訓(xùn)練誤差界）
$\prod_{m=1}^MZ_m=\prod_{m=1}^M[2\sqrt{e_m(1-e_m)}]=\prod_{m=1}^M\sqrt{(1-4\gamma^2_m)}\le exp(-2\sum_{m=1}^{M}\gamma^2_m)$ 其中， $\gamma_m=\frac{1}{2}-e_m$
證明過程如下：

定理2證明.png

推論：結(jié)合定理1與定理2咳燕，如果存在 $\gamma>0$ 勿决，對所有的m有 $\gamma_m\ge\gamma$ ，則 $\frac{1}{N}\sum_{i=1}^{N}I(G_m(x)\not=y_i)\le exp(-2M\gamma^2)$
這表明在此條件下AdaBoost的訓(xùn)練誤差是以指數(shù)速率下降的招盲。

2.3 AdaBoost算法的解釋

AdaBoost算法是模型為加法模型低缩、損失函數(shù)為指數(shù)函數(shù)、學(xué)習(xí)算法為前向分布算法的二分類學(xué)習(xí)算法。
加法模型可理解為咆繁，最終的強(qiáng)分類器是由基本分類器加權(quán)平均得到的讳推。
前向分布算法可理解為，在AdaBoost算法中我們利用前一個(gè)基本分類器的結(jié)果來更新后一個(gè)基本分類器的訓(xùn)練集數(shù)據(jù)權(quán)值玩般。假設(shè)經(jīng)過m-1輪的迭代银觅，已經(jīng)得到強(qiáng)分類器 $f_{m-1}(x)=f_{m-2}(x)+\alpha_{m-1}G_{m-1}(x)$

在第m輪迭代得到 $\alpha_m,G_m(x)$ 和 $f_m(x)$ ，則
$f_{m}(x)=f_{m-1}(x)+\alpha_{m}G_{m}(x)$

由此可見強(qiáng)分類器是通過前向分布學(xué)習(xí)算法一步步得到的坏为。

下面介紹AdaBoost的損失函數(shù)
2.1節(jié)中的基本分類器權(quán)重計(jì)算公式和樣本權(quán)值更新公式都可從AdaBoost的損失函數(shù)中推導(dǎo)出來究驴。

alpha與w的推導(dǎo).png

2.4 AdaBoost算法的正則化

為了防止AdaBoost過擬合，通常也會加入正則化項(xiàng)匀伏，這個(gè)正則化項(xiàng)被稱為步長(learning rate)洒忧。記為v，對于前面的基本分類器的迭代 $f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)$
如果加上了正則化項(xiàng)够颠，則有 $f_m(x)=f_{m-1}(x)+v\alpha_mG_m(x)$

$v$ 的取值范圍為 $0<v\le1$ 跑慕。對于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的 $v$ 意味著需要更多的基本分類器的迭代次數(shù)摧找。通常用步長和迭代最大次數(shù)來一起決定算法的擬合效果核行。

3. 總結(jié)

AdaBoost算法的兩大特點(diǎn)：

特點(diǎn)1：通過迭代，每次學(xué)習(xí)一個(gè)基本分類器蹬耘；每次迭代中芝雪，提高那些被前一輪分類器錯(cuò)誤分類的數(shù)據(jù)的權(quán)值，同時(shí)降低那些被正確分類的數(shù)據(jù)的權(quán)值综苔；使得誤分類樣本在下一輪學(xué)習(xí)中起更大的作用惩系。即不改變所給的訓(xùn)練數(shù)據(jù)，而是通過不斷改變訓(xùn)練數(shù)據(jù)的權(quán)值分布如筛，使得訓(xùn)練數(shù)據(jù)在基本分類器的學(xué)習(xí)中起不同的作用堡牡。
特點(diǎn)2：利用基本分類器的線性組合構(gòu)建最終分類器。對分類誤差率小的基本分類器賦予大的權(quán)值杨刨，使其在最終的模型中起較大的作用晤柄，對分類誤差率大的基本分類器賦予小的權(quán)值，使其在最終的模型中起較小的作用妖胀。

參考

1.《統(tǒng)計(jì)學(xué)習(xí)方法》-李航著

https://www.cnblogs.com/pinard/p/6133937.html

最后編輯于：2019.03.10 16:21:56

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末芥颈，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子赚抡，更是在濱河造成了極大的恐慌爬坑，老刑警劉巖，帶你破解...
沈念sama閱讀 212,294評論 6贊 493
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件涂臣，死亡現(xiàn)場離奇詭異盾计，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,493評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門署辉，熙熙樓的掌柜王于貴愁眉苦臉地迎上來灼舍，“玉大人，你說我怎么就攤上這事涨薪。” “怎么了炫乓？”我有些...
開封第一講書人閱讀 157,790評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵刚夺，是天一觀的道長。經(jīng)常有香客問我末捣，道長侠姑，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 56,595評論 1贊 284
?港島之戀（遺憾婚禮）
正文為了忘掉前任箩做，我火速辦了婚禮莽红，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘邦邦。我一直安慰自己安吁，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,718評論 6贊 386
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布燃辖。她就那樣靜靜地躺著鬼店，像睡著了一般。火紅的嫁衣襯著肌膚如雪黔龟。梳的紋絲不亂的頭發(fā)上妇智，一...
開封第一講書人閱讀 49,906評論 1贊 290
城市分裂傳說
那天，我揣著相機(jī)與錄音氏身，去河邊找鬼巍棱。笑死，一個(gè)胖子當(dāng)著我的面吹牛蛋欣，可吹牛的內(nèi)容都是我干的航徙。我是一名探鬼主播，決...
沈念sama閱讀 39,053評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼陷虎，長吁一口氣：“原來是場噩夢啊……” “哼捉偏！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起泻红，我...
開封第一講書人閱讀 37,797評論 0贊 268
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤夭禽，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后谊路，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體讹躯，經(jīng)...
沈念sama閱讀 44,250評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,570評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了潮梯。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片骗灶。...
茶點(diǎn)故事閱讀 38,711評論 1贊 341
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖秉馏，靈堂內(nèi)的尸體忽然破棺而出耙旦，到底是詐尸還是另有隱情，我是刑警寧澤萝究，帶...
沈念sama閱讀 34,388評論 4贊 332
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布免都，位于F島的核電站，受9級特大地震影響帆竹，放射性物質(zhì)發(fā)生泄漏绕娘。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 40,018評論 3贊 316
男人毒藥：我在死后第九天來索命
文/蒙蒙一栽连、第九天我趴在偏房一處隱蔽的房頂上張望险领。院中可真熱鬧，春花似錦秒紧、人聲如沸绢陌。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,796評論 0贊 21
一樁弒父案熔恢，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽下面。三九已至，卻和暖如春绩聘，著一層夾襖步出監(jiān)牢的瞬間沥割，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,023評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工凿菩，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留机杜，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,461評論 2贊 360
代替公主和親
正文我出身青樓衅谷，卻偏偏與公主長得像椒拗，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子获黔，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,595評論 2贊 350