機器學習第九篇:詳解Adaboost算法

01|基本概念：

提升方法的基本思想：對於任何一個複雜任務來說，將多個專家的判斷進行適當的綜合所得出的判斷，要比任何一個專家單獨的判斷好。

先來看兩個概念：強可學習和弱可學習。

在概率近似正確學習的框架中(簡稱PAC)，一個概念（類），如果存在一個多項式的學習算法能夠學習它，並且正確率很高，那麼就稱這個概念是強可學習的；一個概念，如果存在一個多項式的學習算法能夠學習它，學習的正確率僅比隨機猜測略好，那麼就稱這個概念是弱可學習的。

弱可學習與強可學習之間是有一定的差距，如果已經發現弱可學習算法，那麼能否將它提到強可學習算法，這裡的如何提升就是提升方法需要解決的問題。最具代表性的就是AdaBoost算法。

對於分類問題而言，給定一個訓練樣本集，求比較粗糙的分類規則（弱分類器）要比求精確地分類規則（強分類器）容易的多。提升方法就是從弱學習算法，反覆學習，得到一系列分類器（又稱為基本分類器），然後組合這些弱分類器，構成一個強分類器。大多數的提升方法都是改變訓練數據的概率分布（訓練數據的權值分布），針對不同的訓練數據分布調用弱學習算法學習一系列弱分類器。

這樣，對於提升方法來說，有兩個問題需要解決：一是在每一輪如何改變訓練數據的權值或概率分布；二是如何將弱分類器組成一個強分類器。

對於第一個問題，AdaBoost的做法是，提高那些被前一輪弱分類器錯分類樣本的權值，而降低那些被正確分類樣本的權值。這樣一來，那些沒有得到正確分類的數據，由於其權值加大而受到後一輪的弱分類器的更大關注。於是，分類問題被一系列的弱分類器「分而治之」。至於第二個問題，即弱分類器的組合，AdaBoost採取加權多數表決的方法。具體地，加大分類誤差率小的弱分類器的權值，使其在表決中起較大的作用，減小分類誤差率大的弱分類器的權值，使其在表決中起較小的作用。

02|AdaBoost算法：

假設給定一個二分類的訓練數據集

其中，每個樣本點由實例和標記組成。x是實例空間，y是標記集合。AdaBoost利用以下算法，從訓練數據集中學習一系列弱分類器或基本分類器，並將這些弱分類器線性組合成一個強分類器。

算法步驟：

1.初始化訓練數據的權值分布，讓訓練數據集中的每一個樣本均等於1/N。    

                

2.對m=1,2,...,M(m表示反覆訓練的次數)

(a)使用具有權值分布的 Dm的訓練數據集學習，得到基本分類器

               

(b)計算Gm(x)在訓練數據集上的分類誤差率（誤分類樣本權值之和）

                

上式中表示第m輪中第i個實例的權值。

(c)計算Gm(x)的係數

                  

上式中的對數為自然對數，上式的結果是該分類器在最終分類器的所佔的權重，即多項式的係數。

由上式可得，當時，,且隨著的減小而增大，意味著分類誤差越小的基本分類器在最終分類器中的作用越大。

(d)更新訓練數據集的權值分布

                   

                  

這裡，是規範化因子

                   

3.構建基本分類器線性組合

                  

得到的最終分類器

                 

係數表示了基本分類器的重要性，這裡，所有的之和並不為1。f(x)的符號決定實例x的分類，f(x)的絕對值表示分類的確信度。

03|前向分布算法：

考慮加法模型(每一輪迭代的分類函數的加和)

其中，為基函數，為基函數的參數，為基函數的係數。

在給定訓練數據及損失函數L(y,f(x))的條件下，學習加法模型f(x)成為經驗風險極小化即損失函數最小化問題：

通常這是一個複雜的優化問題。前向分步算法求解這一優化問題的想法是：因學習的是加法模型，如果能夠從前向後，每一步只學習一個基函數及其係數，逐步逼近優化目標函數，那麼就可以簡化優化的複雜度。具體地，每步只需要優化如下目標函數：

前向分步算法步驟：

輸入：訓練數據集;損失函數L(y,f(x))；基礎函數集;

輸出：加法模型f(x)

1.初始化

2.對m=1,2,...,M

(a)極小化損失函數

得到參數，

(b)更新

3.得到加法模型

這樣，前向分布算法將同時求解從m=1到M所有參數，的優化問題簡化為逐個求解各個，的優化問題。

04|前向分步算法與AdaBoost關係：

AdaBoost 算法可以認為是模型為加法模型、損失函數為指數函數、學習算法為前向分步算法的二類分類學習方法。