理解AdaBoost算法

AdaBoost看上去是一個腦洞大開想出來的算法，你可能會問：為什麼弱分類器的權重計算公式是這樣的？為什麼樣本權重的更新公式是這樣的？事實上，它們是有來歷的。我們可以用廣義加法模型+指數損失函數來推導出AdaBoost的訓練算法。

廣義加法模型擬合的目標函數是多個基函數的線性組合：

其中為基函數的參數，為基函數的權重係數。訓練時這個模型要確定的是基函數的參數和權重值。訓練的目標是最小化對所有樣本的損失函數：

訓練算法依次確定每個基函數的參數和它們的權重。接下來將從廣義加法模型推導出AdaBoost的訓練算法。首先定義強分類器對單個訓練樣本的損失函數：

這是指數損失函數。如果標籤值與強分類器的預測值越接近，損失函數的值越小，反之越大。使用指數損失函數而不用均方誤差損失函數的原因是均方誤差損失函數對分類問題的效果不好。將廣義加法模型的擬合函數代入指數損失函數中，得到算法訓練弱分類器時要優化的目標函數為：

這裡將指數函數拆成了兩部分，已有的強分類器，以及當前弱分類器對訓練樣本的損失函數，前者在之前的迭代中已經求出，可以看成常數。目標函數可以簡化為：

其中：

它只和前面的迭代得到的強分類器有關，與當前的弱分類器、弱分類器權重無關，這就是樣本權重。這個最優化問題可以分兩步求解，首先將看成常數，由於yi和f(xi)的取值只能為+1或-1，要讓上面的目標函數最小化，必須讓二者相等。因此損失函數對f(x)的最優解為：

其中I是指標函數，根據括號裡的條件是否成立其取值為0或1。上式的最優解是使得對樣本的加權誤差率最小的分類器。得到弱分類器之後，優化目標可以表示成的函數：

上式前半部分是被正確分類的樣本，後半部分是被錯誤分類的樣本。這可以寫成：

具體推導過程為：

函數在極值點的導數為0，即：

由此得到關於的方程：

最優解為：

其中errj為弱分類器對訓練樣本集的加權錯誤率：

對逼近函數做如下更新：

導致下次迭代時樣本的權重為：

這就是樣本權重的更新公式。AdaBoost訓練算法就是求解上述最優化問題的過程。