從離散型adaboost 到概率型 adaboost

  • 2020 年 6 月 27 日
  • AI

最近整理gbdt知識點的時候，重新溫習了一下這篇神論文，整理了一些要點：

adaboost被提出之初，其版本是Discrete AdaBoost，也就是離散型adaboost，就是我們目前在百度上最常見的那個解釋版本：

這裡展開說下吧，adaboost和gbdt一樣，整個演算法可以用簡單的公式進行表示：

也就是我們常說的「加性模型」，然後我們寫出adaboost的目標函數的形式：

這是前向分布法的目標函數的形式，其中：

前向分步演算法就通過不斷迭代求得了從m=1到m=M的所有基分類器及其權重，問題得到了解決。

那麼adaboost和指數損失函數是什麼關係呢？首先我們需要知道，指數損失函數的地位和二元的logloss損失函數是一樣的，他們都是作為0-1損失函數的代理函數來代替原始問題的目標函數的：

我們將其帶入adaboost的目標函數的式子可以得到：

令

我們知道：

是前面m-1輪的基學習器的求和與yi的乘積，在本輪即第m輪的計算過程中，前面的m-1個基學習器已經是固定的了（例如tree的深度、tree的葉子節點以及葉子節點值等都已經是固定的），yi表示實際的標籤值也是固定的，因此，常量對於優化問題來說是可以忽略的，所以最終原始的目標函數可以轉化為：

這裡，yi是-1或者1（注意，離散adaboost的標籤是和svm一樣設為1或者-1的），G(xi)，即第m輪的基學習器的輸出，離散adaboost的基學習器是卡閾值直接輸出-1或1的。

這個時候，我們需要求解兩個變數：

離散adaboost採用的是分布求解的策略，即先固定 \alpha ，求解G，然後求解出G之後再求解\alpha。

此時，我們就可以將上式繼續轉化：

這裡的轉化就很有靈性了，針對於：

\alpha固定並且yi和G(xi)輸出均為1或者-1的情況下，上述的兩個最優化的函數時等價的，因為其最優值都是在y1=G（xi）=1或-1的情況下取到的。那麼此時我們的目標函數就是：

這個問題如何求解呢，實際上這個時候的Gm(xi)就是一個基學習器正常訓練的過程，具體的過程是，我們在當前的權重和樣本上，正常fit一個cart tree，僅此而已，cart tree的擬合過程和上述的目標函數是無關的。

這樣，我們就求解出了Gm(xi)了。（這裡為了方便省事，Gm(xi)）,Gm(x),G(xi),G(x)都是一個意思。。懶得改了， \alpha 也是一樣的處理）

此時我們又回到了當初的起點：

只不過這個時候Gm(x)已經求解出來了，就好像分手之後你前女友嫁人了一樣是沒法改變的事實了。此時我們的重心就放在了\alpha 的求解上了，對上式進行展開：

注意，這裡

這裡是把分段函數合併成一個了，當yi=G(xi)的時候只有第一個式子參與了計算，當yi!=G(xi)的時候只有第二個式子參與了計算，這一點要注意清楚。

這一步的推導，這個挺簡單的但是說起來很麻煩，就是構造新式子，懶得寫了。。自行體會吧，然後就是求導了，可以得到：

其中em是帶權分類誤差率：

注意啊，這裡樣本是帶權重的和我們常規的所有樣本等權計算是不一樣的。並且分母加入了

是希望整體的樣本權重為1。


這裡我們貼出這篇文章的作者寫的ppt上的演示圖:

這裡作者為了畫圖方便用了決策樹狀，因此每一個基cart的分介面都是一條線，實際上如果樹的深度較大的化分介面是一條折線的。

這裡作者做了一個測試，左邊這個圖不用注意主要是為了讓你知道每條線代表了啥，右邊才是需要注意的，stumps使用的是決策樹樁，可以看到bagging對決策樹狀進行集成效果是很渣的，bagging框架只能減少方差而無法降低偏差，因此對於基學習器的擬合能力是有要求的，但是adaboost就很神奇了，不僅能降低偏差還能降低方差！降低偏差好理解，每一輪的基學習器都是擬合上一輪的預測偏差，那麼為啥adaboost還能降低方差呢？

主要原因就在於，adaboost每一輪的樣本權重都是在變化的，實際上使用的是廣義的取樣方案。我們知道bagging每一輪是隨機選擇部分樣本進行訓練的，實際上這等同於每一輪對部分樣本賦權為0，部分樣本賦權為1。

而adaboost則是通過對每一樣本進行賦權從而達到了bagging的效果。因此，實際上boosting的框架是既能起到減少方差的效果也能起到降低偏差的效果的。。

上圖我們還看到，有一個叫做real adaboost的東西。我們前面提到過離散型的adaboost每一輪直接輸出分類標籤，因此需要我們去卡不同的分類閾值，大佬不甘寂寞，又想到了一種更好的處理方法：

我們之前求解兩個參數的時候 \alpha 和G的時候，是先固定了 \alpha也就是上面的偽程式碼中的Cm，先訓練了G，然後再去求Cm的。如下圖

上面是離散adaboost，下面是概率型adaboost，我們做一下比較；

而real adaboost則使用了另一種方式：

1、標籤換成了我們熟悉的0，1而不是-1和1；

2、G不再是簡單的卡閾值輸出1或者-1，而是輸出

這裡的fm(x)對應的就是我們的G了；這裡pm(x)是G輸出的樣本的概率值。。。其實就是輸出兩種類別預測概率的比值

然後進行了下一步的權重更新：

具體的推導可見原論文...太麻煩了就不寫了

adaboost和gbdt是兩種不同的boost思路 前者通過樣本的reweight進行訓練 後者則是通過計算梯度直接使用梯度作為新標籤進行每一輪的訓練。也就是說 adaboost的樣本權重每一輪都在變化而gbdt則是樣本的標籤每一輪都在變化，gbdt可以使用更多的損失函數 應用範圍更廣

Tags:

VirMach 便宜 VPS