AdaBoost基本原理與算法描述
Y學(xué)習(xí)使我快樂V 2018-08-21 19:59:33 11303 收藏 28
分類專欄： 機器學(xué)習(xí)
版權(quán)
一. 前言
最近在看集成學(xué)習(xí)方法，前面已經(jīng)對XGBoost的原理與簡單實踐做了介紹，這次對AdaBoost算法做個學(xué)習(xí)筆記，來鞏固自己所學(xué)的知識，同時也希望對需要幫助的人有所幫助。
關(guān)于集成學(xué)習(xí)主要有兩大分支，一種是bagging方法，一種是boosting方法。
bagging方法的弱學(xué)習(xí)器之間沒有依賴關(guān)系，各個學(xué)習(xí)器可以并行生成，最終通過某種策略進行集成得到強學(xué)習(xí)器（比如回歸問題用所有弱學(xué)習(xí)器輸出值的平均值作為預(yù)測值；分類問題使用投票法，即少數(shù)服從多數(shù)的方法來得到最終的預(yù)測值；也可以使用學(xué)習(xí)法，即每個弱學(xué)習(xí)器的輸出值作為訓(xùn)練數(shù)據(jù)來重新學(xué)習(xí)一個學(xué)習(xí)器，而該學(xué)習(xí)器的輸出值作為最終的預(yù)測值，代表方法有stacking方法，感興趣的同學(xué)可以自己去了解一下）。bagging方法采用自助采樣法，即在總樣本中隨機的選取m個樣本點作為樣本m1，然后放回，繼續(xù)隨機選取m個樣本點作為樣本m2，如此循環(huán)下去直到選取的樣本個數(shù)達(dá)到預(yù)設(shè)定值n，對這n個樣本進行學(xué)習(xí)，生成n個弱學(xué)習(xí)器。隨機森林算法就是bagging方法的代表算法。
boosting方法的若學(xué)習(xí)器之間有強的依賴關(guān)系，各個弱學(xué)習(xí)器之間串行生成。它的工作機制是初始給每個樣本賦予一個權(quán)重值（初始權(quán)重值一般是1/m，m表示有m個樣本），然后訓(xùn)練第一個弱學(xué)習(xí)器，根據(jù)該弱學(xué)習(xí)器的學(xué)習(xí)誤差率來更新權(quán)重值，使得該學(xué)習(xí)器中的誤差率高的訓(xùn)練樣本點（所有的訓(xùn)練樣本點）的權(quán)重值變高，權(quán)重值高的訓(xùn)練樣本點在后面的弱學(xué)習(xí)器中會得到更多的重視，以此方法來依次學(xué)習(xí)各個弱學(xué)習(xí)器，直到弱學(xué)習(xí)器的數(shù)量達(dá)到預(yù)先指定的值為止，最后通過某種策略將這些弱學(xué)習(xí)器進行整合，得到最終的強學(xué)習(xí)器。boosting方法的代表算法有AdaBoost和boosting tree算法，而AdaBoost算法就是本文接下來要介紹的算法。
在介紹AdaBoost之前，要先搞清楚boosting系列算法主要解決的一些問題，如下：
弱學(xué)習(xí)器的權(quán)重系數(shù)如何計算？
樣本點的權(quán)重系數(shù)如何更新？
學(xué)習(xí)的誤差率如何計算？
最后使用的結(jié)合策略是什么？
下面我們就來看看AdaBoost是如何解決以上問題的。
二. AdaBoost基本原理介紹
2.1 AdaBoost分類問題
以二分類為例，假設(shè)給定一個二類分類的訓(xùn)練數(shù)據(jù)集，其中表示樣本點，表示樣本對應(yīng)的類別，其可取值為｛-1，1｝。AdaBoost算法利用如下的算法，從訓(xùn)練數(shù)據(jù)中串行的學(xué)習(xí)一系列的弱學(xué)習(xí)器，并將這些弱學(xué)習(xí)器線性組合為一個強學(xué)習(xí)器。AdaBoost算法描述如下：
輸入：訓(xùn)練數(shù)據(jù)集
輸出：最終的強分類器G(x)
(1) 初始化訓(xùn)練數(shù)據(jù)的權(quán)重分布值：（ 表示第m個弱學(xué)習(xí)器的樣本點的權(quán)值）
(2) 對M個弱學(xué)習(xí)器，m=1，2，...，M：
（a）使用具有權(quán)值分布的訓(xùn)練數(shù)據(jù)集進行學(xué)習(xí)，得到基本分類器 ，其輸出值為｛-1，1｝；
（b）計算弱分類器在訓(xùn)練數(shù)據(jù)集上的分類誤差率，其值越小的基分類器在最終分類器中的作用越大。
其中，取值為0或1，取0表示分類正確，取1表示分類錯誤。
（c）計算弱分類器的權(quán)重系數(shù)：（這里的對數(shù)是自然對數(shù)）
一般情況下的取值應(yīng)該小于0.5，因為若不進行學(xué)習(xí)隨機分類的話，由于是二分類錯誤率等于0.5，當(dāng)進行學(xué)習(xí)的時候，錯誤率應(yīng)該略低于0.5。當(dāng)減小的時候的值增大，而我們希望得到的是分類誤差率越小的弱分類器的權(quán)值越大，對最終的預(yù)測產(chǎn)生的影響也就越大，所以將弱分類器的權(quán)值設(shè)為該方程式從直觀上來說是合理地，具體的證明為上式請繼續(xù)往下讀。
（d）更新訓(xùn)練數(shù)據(jù)集的樣本權(quán)值分布：
對于二分類，弱分類器的輸出值取值為｛-1，1｝，的取值為｛-1，1｝，所以對于正確的分類 ，對于錯誤的分類，由于樣本權(quán)重值在[0，1]之間，當(dāng)分類正確時取值較小，而分類錯誤時取值較大，而我們希望得到的是權(quán)重值高的訓(xùn)練樣本點在后面的弱學(xué)習(xí)器中會得到更多的重視，所以該上式從直觀上感覺也是合理地，具體怎樣合理，請往下讀。
其中，是規(guī)范化因子，主要作用是將的值規(guī)范到0-1之間，使得。
(3) 上面我們介紹了弱學(xué)習(xí)器的權(quán)重系數(shù)α如何計算，樣本的權(quán)重系數(shù)W如何更新，學(xué)習(xí)的誤差率e如何計算，接下來是最后一個問題，各個弱學(xué)習(xí)器采用何種結(jié)合策略了，AdaBoost對于分類問題的結(jié)合策略是加權(quán)平均法。如下，利用加權(quán)平均法構(gòu)建基本分類器的線性組合：
得到最終的分類器：
以上就是對于AdaBoost分類問題的介紹，接下來是對AdaBoost的回歸問題的介紹。
2.2 AdaBoost回歸問題
AdaBoost回歸問題有許多變種，這里我們以AdaBoost R2算法為準(zhǔn)。
（1）我們先看看回歸問題的誤差率問題，對于第m個弱學(xué)習(xí)器，計算他在訓(xùn)練集上的最大誤差：
然后計算每個樣本的相對誤差：（計算相對誤差的目的是將誤差規(guī)范化到[0，1]之間）
， 顯然
這里是誤差損失為線性時的情況，如果我們用平方誤差，則，如果我們用指數(shù)誤差，則
最終得到第k個弱學(xué)習(xí)器的誤差率為：
，表示每個樣本點的加權(quán)誤差的總和即為該弱學(xué)習(xí)器的誤差。
（2）我們再來看看弱學(xué)習(xí)器的權(quán)重系數(shù)α，如下公式：
（3）對于如何更新回歸問題的樣本權(quán)重，第k+1個弱學(xué)習(xí)器的樣本權(quán)重系數(shù)為：
其中是規(guī)范化因子：
（4）最后是結(jié)合策略，和分類問題不同，回歸問題的結(jié)合策略采用的是對加權(quán)弱學(xué)習(xí)器取中位數(shù)的方法，最終的強回歸器為：
，其中是所有的中位數(shù)（m=1，2，...，M）。
這就是AdaBoost回歸問題的算法介紹，還有一個問題沒有解決，就是在分類問題中我們的弱學(xué)習(xí)器的權(quán)重系數(shù)是如何通過計算嚴(yán)格的推導(dǎo)出來的。
2.3 AdaBoost前向分步算法
在上兩節(jié)中，我們介紹了AdaBoost的分類與回歸問題，但是在分類問題中還有一個沒有解決的就是弱學(xué)習(xí)器的權(quán)重系數(shù)是如何通過公式推導(dǎo)出來的。這里主要用到的就是前向分步算法，接下來我們就介紹該算法。
從另一個角度講，AdaBoost算法是模型為加法模型，損失函數(shù)為指數(shù)函數(shù)，學(xué)習(xí)算法為前向分步算法時的分類問題。其中，加法模型表示我們的最終得到的強分類器是若干個弱分類器加權(quán)平均得到的，如下：
損失函數(shù)是指數(shù)函數(shù)，如下：
學(xué)習(xí)算法為前向分步算法，下面就來介紹AdaBoost是如何利用前向分布算法進行學(xué)習(xí)的：
（1）假設(shè)進過m-1輪迭代前向分布算法已經(jīng)得到：
在第m輪的迭代得到，和.
目標(biāo)是使前向分布算法得到的和使在訓(xùn)練數(shù)據(jù)集T上的指數(shù)損失最小，即
上式即為我們利用前向分步學(xué)習(xí)算法得到的損失函數(shù)。其中，。因為既不依賴也不依賴于G，所以在第m輪迭代中與最小化無關(guān)。但依賴于，隨著每一輪的迭代而發(fā)生變化。
上式達(dá)到最小時所取的和就是AdaBoost算法所得到的和。
（2）首先求分類器：
我們知道，對于二分類的分類器G(x)的輸出值為-1和1，表示預(yù)測錯誤，表示正確，每個樣本點都有一個權(quán)重值，所以對于一個弱分類器的輸出則為：，我們的目標(biāo)是使損失最小化，所以我們的具有損失最小化的第m個弱分類器即為：
其中，
為什么用表示一個弱分類器的輸出呢？因為我們的AdaBoost并沒有限制弱學(xué)習(xí)器的種類，所以它的實際表達(dá)式要根據(jù)使用的弱學(xué)習(xí)器類型來定。
此分類器即為Adaboost算法的基本分類器，因為它是使第m輪加權(quán)訓(xùn)練數(shù)據(jù)分類誤差率最小的基本分類器。
（3）然后就是來求，
將代入損失函數(shù)（1）式中，得：
我們的目標(biāo)是最小化上式，求出對應(yīng)的。
由于，
注意：這里我們的樣本點權(quán)重系數(shù)并沒有進行規(guī)范化，所以
（2）式為：
則我們的目標(biāo)是求：
上式求偏導(dǎo)，并令偏導(dǎo)等于0，得：
，進而得到：
，求得：，其中為誤差率:
（4）最后看樣本權(quán)重的更新。
利用前面所講的，以及權(quán)值
可以得到如下式子：
這樣就得到了我們前面所講的樣本權(quán)重更新公式。
2.4 AdoBoost算法的正則化
為了防止過擬合，AdaBoost算法中也會加入正則化項，這個正則化項我們稱之為步長也就是學(xué)習(xí)率。定義為v，對于前面的弱學(xué)習(xí)器的迭代有：
加入正則化項，就變成如下：
v的取值范圍為(0，1]。對于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的v意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用學(xué)習(xí)率和迭代最大次數(shù)一起來決定算法的擬合效果。
到這里，我們的AdaBoost算法介紹完畢。
三. AdaBoost算法流程描述
3.1 AdaBoost分類問題的算法流程描述
關(guān)于AdaBoost的分類問題，sklearn中采用的是SAMME和SAMME.R算法，SAMME.R算法是SAMME算法的變種。sklearn中默認(rèn)采用SAMME.R，原因是SAMME.R算法比SAMME算法收斂速度更快，用更少的提升迭代次數(shù)實現(xiàn)了更低的測試誤差。接下來我們先介紹AdaBoost的分類算法流程，可以將二元分類算法視為多元分類算法的一個特例。
3.1.1 SAMME算法流程描述：
輸入：樣本集，輸出為，弱分類器的迭代次數(shù)為M，樣本點的個數(shù)為N。
輸出：最終的強分類器
（1）初始化樣本點的權(quán)重為：
（2）對于m=1,2,..,M
（a）使用帶有權(quán)重的樣本來訓(xùn)練一個弱學(xué)習(xí)器;
（b）計算弱分類器的分類誤差率：
（c）計算弱分類器的系數(shù)：
，
其中，K表示K元分類，可以看出當(dāng)K=2時，，余下的與我們二元分類算法所描述的弱分類器系數(shù)一致。
（d）更新樣本的權(quán)重分布：
（3）構(gòu)建最終的強分類器：
3.1.2 SAMME.R算法流程描述：
輸入：樣本集，輸出為，弱分類器的迭代次數(shù)為M，樣本點的個數(shù)為N。
輸出：最終的強分類器
（1）初始化樣本點的權(quán)重為：
（2）對于m=1,2,..,M
（a）使用帶有權(quán)重的樣本來訓(xùn)練一個弱學(xué)習(xí)器;
（b）獲得帶有權(quán)重分類的概率評估：
，
其中表示第m個弱學(xué)習(xí)器將樣本分為第k類的概率。k=1，2，...，K，K表示分類的類別個數(shù)。
（c） 使用加權(quán)概率推導(dǎo)出加法模型的更新，然后將其應(yīng)用于數(shù)據(jù)：
，
（d）更新樣本點權(quán)重系數(shù)：
（e）標(biāo)準(zhǔn)化樣本點權(quán)重;
（3）構(gòu)建最終的強分類器：
，表示使最大的類別即為我們所預(yù)測的類別。
3.2 AdaBoost回歸問題的算法流程描述
在sklearn中，回歸使用的算法為 AdaBoost.R2算法，具體的流程描述如下：
輸入：樣本集，輸出為，弱分類器的迭代次數(shù)為M，樣本點的個數(shù)為N。
輸出：最終的強分類器
（1）初始化樣本點的權(quán)重為：
（2）對于m=1,2,..,M
（a）使用具有權(quán)重的樣本集來訓(xùn)練數(shù)據(jù)，得到弱學(xué)習(xí)器
（b）計算訓(xùn)練集上的最大誤差
，
（c）計算每個樣本點的相對誤差：
如果是線性誤差：則
如果是平方誤差，則
如果是指數(shù)誤差，則
（d）計算回歸誤差率：
（c）計算弱學(xué)習(xí)器的系數(shù)：
（d）更新樣本集的權(quán)重分布：
，其中是規(guī)范化因子，
（3）構(gòu)建最終的強學(xué)習(xí)器：
，其中是所有的中位數(shù)（m=1，2，...，M）。
四. AdaBoost算法的優(yōu)缺點
4.1 優(yōu)點
（1）不容易發(fā)生過擬合；
（2）由于AdaBoost并沒有限制弱學(xué)習(xí)器的種類，所以可以使用不同的學(xué)習(xí)算法來構(gòu)建弱分類器；
（3）AdaBoost具有很高的精度；
（4）相對于bagging算法和Random Forest算法，AdaBoost充分考慮的每個分類器的權(quán)重；
（5）AdaBoost的參數(shù)少，實際應(yīng)用中不需要調(diào)節(jié)太多的參數(shù)。
4.2 缺點
（1）AdaBoost迭代次數(shù)也就是弱分類器數(shù)目不太好設(shè)定，可以使用交叉驗證來進行確定。
（2）數(shù)據(jù)不平衡導(dǎo)致分類精度下降。
（3）訓(xùn)練比較耗時，每次重新選擇當(dāng)前分類器最好切分點。
（4）對異常樣本敏感，異常樣本在迭代中可能會獲得較高的權(quán)重，影響最終的強學(xué)習(xí)器的預(yù)測準(zhǔn)確性。
五. 參考文獻/博文
（1）李航，《統(tǒng)計學(xué)習(xí)方法》 第八章
（2）Multi-class AdaBoost 論文
（3）Boosting for Regression Transfer AdaBoost回歸論文
（4）https://www.cnblogs.com/pinard/p/6133937.html
————————————————
版權(quán)聲明：本文為CSDN博主「Y學(xué)習(xí)使我快樂V」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/qq_24519677/java/article/details/81910112
