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