AdaBoost基本原理與算法描述

Y學(xué)習(xí)使我快樂(lè)V 2018-08-21 19:59:33  11303  收藏 28

分類(lèi)專(zhuān)欄： 機(jī)器學(xué)習(xí)

版權(quán)

一. 前言

最近在看集成學(xué)習(xí)方法，前面已經(jīng)對(duì)XGBoost的原理與簡(jiǎn)單實(shí)踐做了介紹，這次對(duì)AdaBoost算法做個(gè)學(xué)習(xí)筆記，來(lái)鞏固自己所學(xué)的知識(shí)，同時(shí)也希望對(duì)需要幫助的人有所幫助。

關(guān)于集成學(xué)習(xí)主要有兩大分支，一種是bagging方法，一種是boosting方法。

bagging方法的弱學(xué)習(xí)器之間沒(méi)有依賴(lài)關(guān)系，各個(gè)學(xué)習(xí)器可以并行生成，最終通過(guò)某種策略進(jìn)行集成得到強(qiáng)學(xué)習(xí)器（比如回歸問(wèn)題用所有弱學(xué)習(xí)器輸出值的平均值作為預(yù)測(cè)值；分類(lèi)問(wèn)題使用投票法，即少數(shù)服從多數(shù)的方法來(lái)得到最終的預(yù)測(cè)值；也可以使用學(xué)習(xí)法，即每個(gè)弱學(xué)習(xí)器的輸出值作為訓(xùn)練數(shù)據(jù)來(lái)重新學(xué)習(xí)一個(gè)學(xué)習(xí)器，而該學(xué)習(xí)器的輸出值作為最終的預(yù)測(cè)值，代表方法有stacking方法，感興趣的同學(xué)可以自己去了解一下）。bagging方法采用自助采樣法，即在總樣本中隨機(jī)的選取m個(gè)樣本點(diǎn)作為樣本m1，然后放回，繼續(xù)隨機(jī)選取m個(gè)樣本點(diǎn)作為樣本m2，如此循環(huán)下去直到選取的樣本個(gè)數(shù)達(dá)到預(yù)設(shè)定值n，對(duì)這n個(gè)樣本進(jìn)行學(xué)習(xí)，生成n個(gè)弱學(xué)習(xí)器。隨機(jī)森林算法就是bagging方法的代表算法。

boosting方法的若學(xué)習(xí)器之間有強(qiáng)的依賴(lài)關(guān)系，各個(gè)弱學(xué)習(xí)器之間串行生成。它的工作機(jī)制是初始給每個(gè)樣本賦予一個(gè)權(quán)重值（初始權(quán)重值一般是1/m，m表示有m個(gè)樣本），然后訓(xùn)練第一個(gè)弱學(xué)習(xí)器，根據(jù)該弱學(xué)習(xí)器的學(xué)習(xí)誤差率來(lái)更新權(quán)重值，使得該學(xué)習(xí)器中的誤差率高的訓(xùn)練樣本點(diǎn)（所有的訓(xùn)練樣本點(diǎn)）的權(quán)重值變高，權(quán)重值高的訓(xùn)練樣本點(diǎn)在后面的弱學(xué)習(xí)器中會(huì)得到更多的重視，以此方法來(lái)依次學(xué)習(xí)各個(gè)弱學(xué)習(xí)器，直到弱學(xué)習(xí)器的數(shù)量達(dá)到預(yù)先指定的值為止，最后通過(guò)某種策略將這些弱學(xué)習(xí)器進(jìn)行整合，得到最終的強(qiáng)學(xué)習(xí)器。boosting方法的代表算法有AdaBoost和boosting tree算法，而AdaBoost算法就是本文接下來(lái)要介紹的算法。

在介紹AdaBoost之前，要先搞清楚boosting系列算法主要解決的一些問(wèn)題，如下：

弱學(xué)習(xí)器的權(quán)重系數(shù)如何計(jì)算？

樣本點(diǎn)的權(quán)重系數(shù)如何更新？

學(xué)習(xí)的誤差率如何計(jì)算？

最后使用的結(jié)合策略是什么？

下面我們就來(lái)看看AdaBoost是如何解決以上問(wèn)題的。

二. AdaBoost基本原理介紹

2.1 AdaBoost分類(lèi)問(wèn)題

以二分類(lèi)為例，假設(shè)給定一個(gè)二類(lèi)分類(lèi)的訓(xùn)練數(shù)據(jù)集，其中表示樣本點(diǎn)，表示樣本對(duì)應(yīng)的類(lèi)別，其可取值為｛-1，1｝。AdaBoost算法利用如下的算法，從訓(xùn)練數(shù)據(jù)中串行的學(xué)習(xí)一系列的弱學(xué)習(xí)器，并將這些弱學(xué)習(xí)器線性組合為一個(gè)強(qiáng)學(xué)習(xí)器。AdaBoost算法描述如下：

輸入：訓(xùn)練數(shù)據(jù)集

輸出：最終的強(qiáng)分類(lèi)器G(x)

(1) 初始化訓(xùn)練數(shù)據(jù)的權(quán)重分布值：（ 表示第m個(gè)弱學(xué)習(xí)器的樣本點(diǎn)的權(quán)值）

(2) 對(duì)M個(gè)弱學(xué)習(xí)器，m=1，2，...，M：

（a）使用具有權(quán)值分布的訓(xùn)練數(shù)據(jù)集進(jìn)行學(xué)習(xí)，得到基本分類(lèi)器  ，其輸出值為｛-1，1｝；

（b）計(jì)算弱分類(lèi)器在訓(xùn)練數(shù)據(jù)集上的分類(lèi)誤差率，其值越小的基分類(lèi)器在最終分類(lèi)器中的作用越大。

                        其中，取值為0或1，取0表示分類(lèi)正確，取1表示分類(lèi)錯(cuò)誤。

（c）計(jì)算弱分類(lèi)器的權(quán)重系數(shù)：（這里的對(duì)數(shù)是自然對(duì)數(shù)）

一般情況下的取值應(yīng)該小于0.5，因?yàn)槿舨贿M(jìn)行學(xué)習(xí)隨機(jī)分類(lèi)的話，由于是二分類(lèi)錯(cuò)誤率等于0.5，當(dāng)進(jìn)行學(xué)習(xí)的時(shí)候，錯(cuò)誤率應(yīng)該略低于0.5。當(dāng)減小的時(shí)候的值增大，而我們希望得到的是分類(lèi)誤差率越小的弱分類(lèi)器的權(quán)值越大，對(duì)最終的預(yù)測(cè)產(chǎn)生的影響也就越大，所以將弱分類(lèi)器的權(quán)值設(shè)為該方程式從直觀上來(lái)說(shuō)是合理地，具體的證明為上式請(qǐng)繼續(xù)往下讀。

（d）更新訓(xùn)練數(shù)據(jù)集的樣本權(quán)值分布：

對(duì)于二分類(lèi)，弱分類(lèi)器的輸出值取值為｛-1，1｝，的取值為｛-1，1｝，所以對(duì)于正確的分類(lèi) ，對(duì)于錯(cuò)誤的分類(lèi)，由于樣本權(quán)重值在[0，1]之間，當(dāng)分類(lèi)正確時(shí)取值較小，而分類(lèi)錯(cuò)誤時(shí)取值較大，而我們希望得到的是權(quán)重值高的訓(xùn)練樣本點(diǎn)在后面的弱學(xué)習(xí)器中會(huì)得到更多的重視，所以該上式從直觀上感覺(jué)也是合理地，具體怎樣合理，請(qǐng)往下讀。

                  其中，是規(guī)范化因子，主要作用是將的值規(guī)范到0-1之間，使得。

(3) 上面我們介紹了弱學(xué)習(xí)器的權(quán)重系數(shù)α如何計(jì)算，樣本的權(quán)重系數(shù)W如何更新，學(xué)習(xí)的誤差率e如何計(jì)算，接下來(lái)是最后一個(gè)問(wèn)題，各個(gè)弱學(xué)習(xí)器采用何種結(jié)合策略了，AdaBoost對(duì)于分類(lèi)問(wèn)題的結(jié)合策略是加權(quán)平均法。如下，利用加權(quán)平均法構(gòu)建基本分類(lèi)器的線性組合：

     得到最終的分類(lèi)器：

以上就是對(duì)于AdaBoost分類(lèi)問(wèn)題的介紹，接下來(lái)是對(duì)AdaBoost的回歸問(wèn)題的介紹。

2.2 AdaBoost回歸問(wèn)題

AdaBoost回歸問(wèn)題有許多變種，這里我們以AdaBoost R2算法為準(zhǔn)。

（1）我們先看看回歸問(wèn)題的誤差率問(wèn)題，對(duì)于第m個(gè)弱學(xué)習(xí)器，計(jì)算他在訓(xùn)練集上的最大誤差：

然后計(jì)算每個(gè)樣本的相對(duì)誤差：（計(jì)算相對(duì)誤差的目的是將誤差規(guī)范化到[0，1]之間）

                        ，  顯然 

這里是誤差損失為線性時(shí)的情況，如果我們用平方誤差，則，如果我們用指數(shù)誤差，則

最終得到第k個(gè)弱學(xué)習(xí)器的誤差率為：

                    ，表示每個(gè)樣本點(diǎn)的加權(quán)誤差的總和即為該弱學(xué)習(xí)器的誤差。

（2）我們?cè)賮?lái)看看弱學(xué)習(xí)器的權(quán)重系數(shù)α，如下公式：

（3）對(duì)于如何更新回歸問(wèn)題的樣本權(quán)重，第k+1個(gè)弱學(xué)習(xí)器的樣本權(quán)重系數(shù)為：

其中是規(guī)范化因子：

（4）最后是結(jié)合策略，和分類(lèi)問(wèn)題不同，回歸問(wèn)題的結(jié)合策略采用的是對(duì)加權(quán)弱學(xué)習(xí)器取中位數(shù)的方法，最終的強(qiáng)回歸器為：

                  ，其中是所有的中位數(shù)（m=1，2，...，M）。

這就是AdaBoost回歸問(wèn)題的算法介紹，還有一個(gè)問(wèn)題沒(méi)有解決，就是在分類(lèi)問(wèn)題中我們的弱學(xué)習(xí)器的權(quán)重系數(shù)是如何通過(guò)計(jì)算嚴(yán)格的推導(dǎo)出來(lái)的。

2.3 AdaBoost前向分步算法

在上兩節(jié)中，我們介紹了AdaBoost的分類(lèi)與回歸問(wèn)題，但是在分類(lèi)問(wèn)題中還有一個(gè)沒(méi)有解決的就是弱學(xué)習(xí)器的權(quán)重系數(shù)是如何通過(guò)公式推導(dǎo)出來(lái)的。這里主要用到的就是前向分步算法，接下來(lái)我們就介紹該算法。

從另一個(gè)角度講，AdaBoost算法是模型為加法模型，損失函數(shù)為指數(shù)函數(shù)，學(xué)習(xí)算法為前向分步算法時(shí)的分類(lèi)問(wèn)題。其中，加法模型表示我們的最終得到的強(qiáng)分類(lèi)器是若干個(gè)弱分類(lèi)器加權(quán)平均得到的，如下：

損失函數(shù)是指數(shù)函數(shù)，如下：

學(xué)習(xí)算法為前向分步算法，下面就來(lái)介紹AdaBoost是如何利用前向分布算法進(jìn)行學(xué)習(xí)的：

（1）假設(shè)進(jìn)過(guò)m-1輪迭代前向分布算法已經(jīng)得到：

在第m輪的迭代得到，和.

目標(biāo)是使前向分布算法得到的和使在訓(xùn)練數(shù)據(jù)集T上的指數(shù)損失最小，即

上式即為我們利用前向分步學(xué)習(xí)算法得到的損失函數(shù)。其中，。因?yàn)榧炔灰蕾?lài)也不依賴(lài)于G，所以在第m輪迭代中與最小化無(wú)關(guān)。但依賴(lài)于，隨著每一輪的迭代而發(fā)生變化。

上式達(dá)到最小時(shí)所取的和就是AdaBoost算法所得到的和。

（2）首先求分類(lèi)器：

我們知道，對(duì)于二分類(lèi)的分類(lèi)器G(x)的輸出值為-1和1，表示預(yù)測(cè)錯(cuò)誤，表示正確，每個(gè)樣本點(diǎn)都有一個(gè)權(quán)重值，所以對(duì)于一個(gè)弱分類(lèi)器的輸出則為：，我們的目標(biāo)是使損失最小化，所以我們的具有損失最小化的第m個(gè)弱分類(lèi)器即為：

   其中，

為什么用表示一個(gè)弱分類(lèi)器的輸出呢？因?yàn)槲覀兊腁daBoost并沒(méi)有限制弱學(xué)習(xí)器的種類(lèi)，所以它的實(shí)際表達(dá)式要根據(jù)使用的弱學(xué)習(xí)器類(lèi)型來(lái)定。

此分類(lèi)器即為Adaboost算法的基本分類(lèi)器，因?yàn)樗鞘沟趍輪加權(quán)訓(xùn)練數(shù)據(jù)分類(lèi)誤差率最小的基本分類(lèi)器。

（3）然后就是來(lái)求，

將代入損失函數(shù)（1）式中，得：

我們的目標(biāo)是最小化上式，求出對(duì)應(yīng)的。

由于，

注意：這里我們的樣本點(diǎn)權(quán)重系數(shù)并沒(méi)有進(jìn)行規(guī)范化，所以

（2）式為：   

則我們的目標(biāo)是求：

上式求偏導(dǎo)，并令偏導(dǎo)等于0，得：

       ，進(jìn)而得到：

       ，求得：，其中為誤差率:

（4）最后看樣本權(quán)重的更新。

利用前面所講的，以及權(quán)值 

可以得到如下式子：

這樣就得到了我們前面所講的樣本權(quán)重更新公式。

2.4 AdoBoost算法的正則化

為了防止過(guò)擬合，AdaBoost算法中也會(huì)加入正則化項(xiàng)，這個(gè)正則化項(xiàng)我們稱(chēng)之為步長(zhǎng)也就是學(xué)習(xí)率。定義為v，對(duì)于前面的弱學(xué)習(xí)器的迭代有：

加入正則化項(xiàng)，就變成如下：

v的取值范圍為(0，1]。對(duì)于同樣的訓(xùn)練集學(xué)習(xí)效果，較小的v意味著我們需要更多的弱學(xué)習(xí)器的迭代次數(shù)。通常我們用學(xué)習(xí)率和迭代最大次數(shù)一起來(lái)決定算法的擬合效果。

到這里，我們的AdaBoost算法介紹完畢。

三. AdaBoost算法流程描述

3.1 AdaBoost分類(lèi)問(wèn)題的算法流程描述

關(guān)于AdaBoost的分類(lèi)問(wèn)題，sklearn中采用的是SAMME和SAMME.R算法，SAMME.R算法是SAMME算法的變種。sklearn中默認(rèn)采用SAMME.R，原因是SAMME.R算法比SAMME算法收斂速度更快，用更少的提升迭代次數(shù)實(shí)現(xiàn)了更低的測(cè)試誤差。接下來(lái)我們先介紹AdaBoost的分類(lèi)算法流程，可以將二元分類(lèi)算法視為多元分類(lèi)算法的一個(gè)特例。

3.1.1 SAMME算法流程描述：

輸入：樣本集，輸出為，弱分類(lèi)器的迭代次數(shù)為M，樣本點(diǎn)的個(gè)數(shù)為N。

輸出：最終的強(qiáng)分類(lèi)器

（1）初始化樣本點(diǎn)的權(quán)重為：

（2）對(duì)于m=1,2,..,M

       （a）使用帶有權(quán)重的樣本來(lái)訓(xùn)練一個(gè)弱學(xué)習(xí)器;

       （b）計(jì)算弱分類(lèi)器的分類(lèi)誤差率：

       （c）計(jì)算弱分類(lèi)器的系數(shù)：

                      ，

         其中，K表示K元分類(lèi)，可以看出當(dāng)K=2時(shí)，，余下的與我們二元分類(lèi)算法所描述的弱分類(lèi)器系數(shù)一致。

       （d）更新樣本的權(quán)重分布：

（3）構(gòu)建最終的強(qiáng)分類(lèi)器：

3.1.2 SAMME.R算法流程描述：

輸入：樣本集，輸出為，弱分類(lèi)器的迭代次數(shù)為M，樣本點(diǎn)的個(gè)數(shù)為N。

輸出：最終的強(qiáng)分類(lèi)器

（1）初始化樣本點(diǎn)的權(quán)重為：

（2）對(duì)于m=1,2,..,M

       （a）使用帶有權(quán)重的樣本來(lái)訓(xùn)練一個(gè)弱學(xué)習(xí)器;

       （b）獲得帶有權(quán)重分類(lèi)的概率評(píng)估：

                  ，

               其中表示第m個(gè)弱學(xué)習(xí)器將樣本分為第k類(lèi)的概率。k=1，2，...，K，K表示分類(lèi)的類(lèi)別個(gè)數(shù)。

       （c） 使用加權(quán)概率推導(dǎo)出加法模型的更新，然后將其應(yīng)用于數(shù)據(jù)：

                   ，

       （d）更新樣本點(diǎn)權(quán)重系數(shù)：

       （e）標(biāo)準(zhǔn)化樣本點(diǎn)權(quán)重;

（3）構(gòu)建最終的強(qiáng)分類(lèi)器：

                   ，表示使最大的類(lèi)別即為我們所預(yù)測(cè)的類(lèi)別。

3.2 AdaBoost回歸問(wèn)題的算法流程描述

在sklearn中，回歸使用的算法為 AdaBoost.R2算法，具體的流程描述如下：

輸入：樣本集，輸出為，弱分類(lèi)器的迭代次數(shù)為M，樣本點(diǎn)的個(gè)數(shù)為N。

輸出：最終的強(qiáng)分類(lèi)器

（1）初始化樣本點(diǎn)的權(quán)重為：

（2）對(duì)于m=1,2,..,M

（a）使用具有權(quán)重的樣本集來(lái)訓(xùn)練數(shù)據(jù)，得到弱學(xué)習(xí)器

（b）計(jì)算訓(xùn)練集上的最大誤差

             ，

（c）計(jì)算每個(gè)樣本點(diǎn)的相對(duì)誤差：

         如果是線性誤差：則

         如果是平方誤差，則

         如果是指數(shù)誤差，則

（d）計(jì)算回歸誤差率：

（c）計(jì)算弱學(xué)習(xí)器的系數(shù)：

（d）更新樣本集的權(quán)重分布：

        ，其中是規(guī)范化因子，

（3）構(gòu)建最終的強(qiáng)學(xué)習(xí)器：

                   ，其中是所有的中位數(shù)（m=1，2，...，M）。

四. AdaBoost算法的優(yōu)缺點(diǎn)

4.1 優(yōu)點(diǎn)

（1）不容易發(fā)生過(guò)擬合；

（2）由于AdaBoost并沒(méi)有限制弱學(xué)習(xí)器的種類(lèi)，所以可以使用不同的學(xué)習(xí)算法來(lái)構(gòu)建弱分類(lèi)器；

（3）AdaBoost具有很高的精度；

（4）相對(duì)于bagging算法和Random Forest算法，AdaBoost充分考慮的每個(gè)分類(lèi)器的權(quán)重；

（5）AdaBoost的參數(shù)少，實(shí)際應(yīng)用中不需要調(diào)節(jié)太多的參數(shù)。

4.2 缺點(diǎn)

（1）AdaBoost迭代次數(shù)也就是弱分類(lèi)器數(shù)目不太好設(shè)定，可以使用交叉驗(yàn)證來(lái)進(jìn)行確定。

（2）數(shù)據(jù)不平衡導(dǎo)致分類(lèi)精度下降。

（3）訓(xùn)練比較耗時(shí)，每次重新選擇當(dāng)前分類(lèi)器最好切分點(diǎn)。

（4）對(duì)異常樣本敏感，異常樣本在迭代中可能會(huì)獲得較高的權(quán)重，影響最終的強(qiáng)學(xué)習(xí)器的預(yù)測(cè)準(zhǔn)確性。

五. 參考文獻(xiàn)/博文

（1）李航，《統(tǒng)計(jì)學(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í)使我快樂(lè)V」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/qq_24519677/java/article/details/81910112