Boosting（提升）

Boosting 是一類(lèi)算法的統(tǒng)稱，它們的主要特點(diǎn)是使用一組弱分類(lèi)器來(lái)構(gòu)造一個(gè)強(qiáng)分類(lèi)器辩块。弱分類(lèi)器意思是預(yù)測(cè)的準(zhǔn)確性不高靴寂，可能只比隨便亂猜稍好一點(diǎn)。強(qiáng)分類(lèi)器指準(zhǔn)確性較高的分類(lèi)器轴捎。簡(jiǎn)單來(lái)說(shuō)的話鹤盒，Boosting 可以理解為俗話所說(shuō)的“三個(gè)臭皮匠頂個(gè)諸葛亮”蚕脏。

Boosting 并沒(méi)有規(guī)定具體的實(shí)現(xiàn)方法，不過(guò)大多數(shù)實(shí)現(xiàn)算法會(huì)有以下特點(diǎn)：

1. 通過(guò)迭代生成多個(gè)弱分類(lèi)器
2. 將這些弱分類(lèi)器組合成一個(gè)強(qiáng)分類(lèi)器侦锯，通常會(huì)根據(jù)各弱分類(lèi)器的準(zhǔn)確性設(shè)置相應(yīng)的權(quán)重
3. 每生成一個(gè)弱分類(lèi)器驼鞭，會(huì)重新設(shè)置訓(xùn)練樣本的權(quán)重，被錯(cuò)誤分類(lèi)的樣本會(huì)增加權(quán)重尺碰，正確分類(lèi)的樣本會(huì)減少權(quán)重挣棕，即后續(xù)生成的分類(lèi)器將更多的關(guān)注之前分錯(cuò)的樣本。（不過(guò)也有些算法會(huì)對(duì)總是分錯(cuò)的樣本降低權(quán)重亲桥，視之為噪音）

Boosting家族有一系列算法洛心，常見(jiàn)的比如 AdaBoost、GDBT题篷、XGBoost皂甘，還有 BrownBoost、LogitBoost悼凑、RankBoost 等等偿枕。

Bagging/Boosting/Stacking

順便說(shuō)一下幾種集成學(xué)習(xí)（Ensemble）方法的區(qū)別，集成方法是指構(gòu)造多種模型户辫，并通過(guò)一定的方法組合起來(lái)渐夸，綜合下來(lái)的預(yù)測(cè)效果高于單個(gè)模型的預(yù)測(cè)效果。

集成學(xué)習(xí)有幾種方式渔欢，Boosting原理 中有幾張圖很直觀墓塌，借用在這里。

Bagging/投票
Bagging 是一種投票機(jī)制奥额，先生成多個(gè)模型苫幢，然后讓它們投票決定最終的結(jié)果。典型的比如隨機(jī)森林算法垫挨。

image

Boosting/迭代提升
Boosting 是迭代生成模型韩肝，每個(gè)模型要基于上一次模型的效果。每次迭代九榔，模型會(huì)關(guān)注之前的模型預(yù)測(cè)效果不好的那些樣本哀峻。本文下面要講述的就屬于這類(lèi)算法。

image

Stacking/多層疊加
Stacking 是多層疊加的意思哲泊。也是先生成多個(gè)模型剩蟀，但是用這些模型的預(yù)測(cè)結(jié)果作為下一層模型的輸入，有點(diǎn)像多層神經(jīng)網(wǎng)絡(luò)的意思切威。

image

AdaBoost（Adaptive Boosting/自適應(yīng)增強(qiáng)）

AdaBoost 是上述 Boosting 思想的一種具體實(shí)現(xiàn)算法育特，一般采用決策樹(shù)作為弱分類(lèi)器。那么看一下 AdaBoost 是如何實(shí)現(xiàn)迭代生成一系列弱分類(lèi)器先朦、調(diào)整樣本權(quán)重缰冤，以及設(shè)置弱分類(lèi)器權(quán)重從而構(gòu)造出一個(gè)強(qiáng)分類(lèi)器的犬缨。

AdaBoost 算法步驟

以離散型AdaBoost(Discrete AdaBoost) 為例：
假設(shè)有N個(gè)樣本 (x1,y1), (x2,y2)…(xN,yN)，其中 y1...yN ∈{-1, 1}锋谐，即二分類(lèi)問(wèn)題遍尺。

1. 設(shè)每個(gè)樣本初始權(quán)重相同，都是 1/N涮拗。即各樣本的權(quán)重 w1...wN = 1/N

2. 訓(xùn)練分類(lèi)器時(shí)Loss函數(shù)采用指數(shù)誤差
   image

3. 開(kāi)始進(jìn)行T次迭代（每次生成一個(gè)弱分類(lèi)器ht乾戏，t=1...T）
   3.1 對(duì)第t次迭代，使用樣本（考慮各樣本權(quán)重為(w1...wN)）訓(xùn)練得到一個(gè)弱分類(lèi)器ht三热。ht預(yù)測(cè)的輸出也是 {-1, 1}鼓择。
   

   3.2 ht對(duì)樣本分類(lèi)的錯(cuò)誤率為
   image
   ，即所有誤分類(lèi)樣本（ht(xi) != yi）的權(quán)重的和就漾。
   3.3 計(jì)算該分類(lèi)器 ht 在最終的強(qiáng)分類(lèi)器中的權(quán)重
   image

   呐能。這個(gè)公式意味著ht的預(yù)測(cè)準(zhǔn)確率越高，在強(qiáng)分類(lèi)器中的權(quán)重越大（下文還有說(shuō)明）抑堡。
   

   3.4 迭代中的強(qiáng)分類(lèi)器
   image
   
   3.5 更新樣本權(quán)重摆出，對(duì)所有樣本計(jì)算
   image
   ，其中
   image
   是 第t輪迭代（當(dāng)前迭代）第 i 個(gè)樣本的權(quán)重首妖，
   image
   是該樣本下一輪(t+1)的權(quán)重偎漫。這個(gè)公式意味著正確的樣本將減少權(quán)重，錯(cuò)誤的樣本將增加權(quán)重（下文還有說(shuō)明）有缆。
   3.6 將所有樣本的權(quán)重重新歸一化象踊，即使得所有樣本的權(quán)重和為1∨锉冢可知 (t+1)輪所有樣本權(quán)重和為
   image
   杯矩，令
   image
   ，即可使得
   image
   
   3.7 t = t + 1袖外，進(jìn)行下一輪迭代

4. 迭代完成后史隆，得到強(qiáng)分類(lèi)器
   image

   ，sign是符號(hào)函數(shù)在刺，使得輸出是 {-1, 1}逆害。

上面的步驟中，我們討論幾個(gè)問(wèn)題：

1. 步驟 3.3 中蚣驼，分類(lèi)器權(quán)重
   image

   ，該函數(shù)圖像如下圖所示相艇。當(dāng)錯(cuò)誤率 εt 越小颖杏，系數(shù) αt 越大，意味著誤差刑逞俊（準(zhǔn)確性高）的分類(lèi)器留储，在最后的強(qiáng)分類(lèi)器中有更大的權(quán)重翼抠。反之，當(dāng)誤差 εt 越大获讳，系數(shù) αt 越小阴颖，即在強(qiáng)分類(lèi)器中的權(quán)重較小。另外可以看出當(dāng)分類(lèi)器的 錯(cuò)誤率 < 0.5 時(shí)丐膝，αt > 0量愧；如果分類(lèi)器的 錯(cuò)誤率 > 0.5，意味著該分類(lèi)器預(yù)測(cè)反了帅矗，此時(shí) αt < 0 將該分類(lèi)器的預(yù)測(cè)結(jié)果反過(guò)來(lái)使用偎肃。

image

2. 步驟 3.5 中，樣本權(quán)值更新
   image
   扣蜻。這里面 yi 是樣本的標(biāo)簽懂缕，ht(xi) 是分類(lèi)器對(duì) xi 的預(yù)測(cè)涛舍，如果預(yù)測(cè)正確，則兩者都等于1 或都等于 -1紊馏，所以乘積為1，如果預(yù)測(cè)錯(cuò)誤蒲犬，則乘積為 -1朱监。公式可以改寫(xiě)為
   image
   ，這個(gè)分段函數(shù)的指數(shù)部分的圖像如下暖哨。如果分類(lèi)器的 αt > 0赌朋，我們看函數(shù)圖像中 > 0 的部分，如果分類(lèi)正確篇裁，指數(shù)函數(shù)的值將 < 1（黃線）沛慢，乘以權(quán)重后將減少權(quán)重的值，即分類(lèi)正確的樣本將減少權(quán)重达布；如果分類(lèi)錯(cuò)誤团甲，指數(shù)函數(shù)的值將 > 1（藍(lán)線），即分類(lèi)錯(cuò)誤的樣本將增加權(quán)重黍聂。如果 αt < 0躺苦，看函數(shù)圖像中 < 0 的部分，指數(shù)函數(shù)的值反過(guò)來(lái)了产还，但此時(shí)分類(lèi)器也預(yù)測(cè)反了匹厘，所以結(jié)果依然是正確的樣本將減少權(quán)重，錯(cuò)誤的樣本將增加權(quán)重脐区。

image

AdaBoost的優(yōu)點(diǎn)

AdaBoost 幾乎可以“開(kāi)箱即用”愈诚，因?yàn)樗亲赃m應(yīng)的，對(duì)參數(shù)不會(huì)太敏感。
它在一定程度上可以避免“維度災(zāi)難”炕柔，我理解主要是 AdaBoost 只需要構(gòu)造弱分類(lèi)器酌泰，比如決策樹(shù)的話，可以只使用那些比較重要的特征匕累，樹(shù)的深度很淺陵刹，運(yùn)行速度較快。
同時(shí)多個(gè)弱分類(lèi)器的集成還能提升模型的預(yù)測(cè)能力欢嘿。

AdaBoost的缺點(diǎn)

比較明顯的一點(diǎn)是對(duì)噪音和異常數(shù)據(jù)比較敏感衰琐，因?yàn)樗惴ㄖ袝?huì)對(duì)分類(lèi)錯(cuò)誤的樣本持續(xù)提升關(guān)注。

AdaBoost公式推導(dǎo)

前面算法中直接給了幾個(gè)公式际插，比如分類(lèi)器的權(quán)重 α 和 樣本權(quán)重更新公式碘耳，為什么采用這樣的計(jì)算公式，我們來(lái)推導(dǎo)一下框弛。

假設(shè)有N個(gè)樣本 (x1,y1), (x2,y2)…(xN,yN)辛辨，其中 y1...yN ∈{-1, 1}，即二分類(lèi)問(wèn)題瑟枫。有一系列分類(lèi)器k 可以線性組合成一個(gè)強(qiáng)分類(lèi)器C斗搞，在第 m-1 次迭代，分類(lèi)器：

image

這里C是強(qiáng)分類(lèi)器慷妙，k是弱分類(lèi)器僻焚，α 是 k在 C中的權(quán)重，下標(biāo) 1...m-1 是迭代的輪次膝擂。注意這里所用的記號(hào)與前面算法步驟中的公式的記號(hào)有不同虑啤，注意各自的含義。

接下來(lái)第m輪分類(lèi)器

image

因?yàn)槭遣捎玫姆椒ㄖ饌€(gè)構(gòu)造分類(lèi)器k架馋，所以在第m輪狞山，可以認(rèn)為 C(m-1) 已經(jīng)是確定的了，現(xiàn)在需要的是找到一個(gè)好的 km 及其系數(shù) αm叉寂。

對(duì)分類(lèi)器 Cm 采用指數(shù)型誤差

image

image

image

image

image

image

image

image

(公式2)

我們希望找到合適的 km 和 αm 使得 E最小驳遵。

1. 先考慮 km。在公式2中山涡，只有
   image
   的值受 km 的影響超埋，也就是說(shuō)搏讶，要最小化E佳鳖，對(duì)于km來(lái)說(shuō)霍殴，就是要構(gòu)造一個(gè)最小化
   image
   的分類(lèi)器 km。

2. 考慮 αm系吩。用公式1對(duì) αm 求導(dǎo)来庭，當(dāng)導(dǎo)數(shù) = 0 時(shí) E有最小值。

   
   
   image
   
   
   image
   
   
   image
   
   
   image
   如果令錯(cuò)誤率
   image
   
   
   則
   image

3. 另外看下更新樣本權(quán)重穿挨。
   

   由于
   image
   月弛，于是
   image
   
   
   image
   
   
   image
   
   
   image
   
   
   image
   
   
   所以
   image

參考

深入淺出ML之Boosting家族
維基百科 —— Boosting (machine learning)
維基百科 —— AdaBoost