Boosting/AdaBoost —— 多級火箭助推

Boosting/AdaBoost —— 多級火箭助推

Boosting(提升)

Boosting 是一類演算法的統稱,它們的主要特點是使用一組弱分類器來構造一個強分類器。弱分類器意思是預測的準確性不高,可能只比隨便亂猜稍好一點。強分類器指準確性較高的分類器。簡單來說的話,Boosting 可以理解為俗話所說的「三個臭皮匠頂個諸葛亮」。

Boosting 並沒有規定具體的實現方法,不過大多數實現演算法會有以下特點:

  1. 通過迭代生成多個弱分類器
  2. 將這些弱分類器組合成一個強分類器,通常會根據各弱分類器的準確性設置相應的權重
  3. 每生成一個弱分類器,會重新設置訓練樣本的權重,被錯誤分類的樣本會增加權重,正確分類的樣本會減少權重,即後續生成的分類器將更多的關注之前分錯的樣本。(不過也有些演算法會對總是分錯的樣本降低權重,視之為噪音)

Boosting家族有一系列演算法,常見的比如 AdaBoost、GDBT、XGBoost,還有 BrownBoost、LogitBoost、RankBoost 等等。

Bagging/Boosting/Stacking

順便說一下幾種集成學習(Ensemble)方法的區別,集成方法是指構造多種模型,並通過一定的方法組合起來,綜合下來的預測效果高於單個模型的預測效果。

集成學習有幾種方式,Boosting原理 中有幾張圖很直觀,借用在這裡。

Bagging/投票

Bagging 是一種投票機制,先生成多個模型,然後讓它們投票決定最終的結果。典型的比如隨機森林演算法。

Boosting/迭代提升

Boosting 是迭代生成模型,每個模型要基於上一次模型的效果。每次迭代,模型會關注之前的模型預測效果不好的那些樣本。本文下面要講述的就屬於這類演算法。

Stacking/多層疊加

Stacking 是多層疊加的意思。也是先生成多個模型,但是用這些模型的預測結果作為下一層模型的輸入,有點像多層神經網路的意思。

AdaBoost(Adaptive Boosting/自適應增強)

AdaBoost 是上述 Boosting 思想的一種具體實現演算法,一般採用決策樹作為弱分類器。那麼看一下 AdaBoost 是如何實現迭代生成一系列弱分類器、調整樣本權重,以及設置弱分類器權重從而構造出一個強分類器的。

AdaBoost 演算法步驟

以離散型AdaBoost(Discrete AdaBoost) 為例:

假設有N個樣本 (x1,y1), (x2,y2)…(xN,yN),其中 y1…yN ∈{-1, 1},即二分類問題。

  1. 設每個樣本初始權重相同,都是 1/N。即各樣本的權重 w1…wN = 1/N
  2. 訓練分類器時Loss函數採用指數誤差

3. 開始進行T次迭代(每次生成一個弱分類器ht,t=1…T)

3.1 對第t次迭代,使用樣本(考慮各樣本權重為(w1…wN))訓練得到一個弱分類器ht。ht預測的輸出也是 {-1, 1}。

3.2 ht對樣本分類的錯誤率為

,即所有誤分類樣本(ht(xi) != yi)的權重的和。

3.3 計算該分類器 ht 在最終的強分類器中的權重

。這個公式意味著ht的預測準確率越高,在強分類器中的權重越大(下文還有說明)。

3.4 迭代中的強分類器

3.5 更新樣本權重,對所有樣本計算

,其中

是 第t輪迭代(當前迭代)第 i 個樣本的權重,

是該樣本下一輪(t+1)的權重。這個公式意味著正確的樣本將減少權重,錯誤的樣本將增加權重(下文還有說明)。

3.6 將所有樣本的權重重新歸一化,即使得所有樣本的權重和為1。可知 (t+1)輪所有樣本權重和為

,令

,即可使得

3.7 t = t + 1,進行下一輪迭代

4. 迭代完成後,得到強分類器 F(x)=sign Big ( sum_{t=1}^T alpha_t h_t(x) Big ) ,sign是符號函數,使得輸出是 {-1, 1}。

上面的步驟中,我們討論幾個問題:

  1. 步驟 3.3 中,分類器權重

,該函數圖像如下圖所示。當錯誤率 εt 越小,係數 αt 越大,意味著誤差小(準確性高)的分類器,在最後的強分類器中有更大的權重。反之,當誤差 εt 越大,係數 αt 越小,即在強分類器中的權重較小。另外可以看出當分類器的 錯誤率 < 0.5 時,αt > 0;如果分類器的 錯誤率 > 0.5,意味著該分類器預測反了,此時 αt < 0 將該分類器的預測結果反過來使用。

2. 步驟 3.5 中,樣本權值更新

。這裡面 yi 是樣本的標籤,ht(xi) 是分類器對 xi 的預測,如果預測正確,則兩者都等於1 或都等於 -1,所以乘積為1,如果預測錯誤,則乘積為 -1。公式可以改寫為

,這個分段函數的指數部分的圖像如下。如果分類器的 αt > 0,我們看函數圖像中 > 0 的部分,如果分類正確,指數函數的值將 < 1(黃線),乘以權重後將減少權重的值,即分類正確的樣本將減少權重;如果分類錯誤,指數函數的值將 > 1(藍線),即分類錯誤的樣本將增加權重。如果 αt < 0,看函數圖像中 < 0 的部分,指數函數的值反過來了,但此時分類器也預測反了,所以結果依然是正確的樣本將減少權重,錯誤的樣本將增加權重。

AdaBoost的優點

AdaBoost 幾乎可以「開箱即用」,因為它是自適應的,對參數不會太敏感。

它在一定程度上可以避免「維度災難」,我理解主要是 AdaBoost 只需要構造弱分類器,比如決策樹的話,可以只使用那些比較重要的特徵,樹的深度很淺,運行速度較快。

同時多個弱分類器的集成還能提升模型的預測能力。

AdaBoost的缺點

比較明顯的一點是對噪音和異常數據比較敏感,因為演算法中會對分類錯誤的樣本持續提升關注。

AdaBoost公式推導

前面演算法中直接給了幾個公式,比如分類器的權重 α 和 樣本權重更新公式,為什麼採用這樣的計算公式,我們來推導一下。

假設有N個樣本 (x1,y1), (x2,y2)…(xN,yN),其中 y1…yN ∈{-1, 1},即二分類問題。有一系列分類器k 可以線性組合成一個強分類器C,在第 m-1 次迭代,分類器:

這裡C是強分類器,k是弱分類器,α 是 k在 C中的權重,下標 1…m-1 是迭代的輪次。注意這裡所用的記號與前面演算法步驟中的公式的記號有不同,注意各自的含義。

接下來第m輪分類器

因為是採用迭代的方法逐個構造分類器k,所以在第m輪,可以認為 C(m-1) 已經是確定的了,現在需要的是找到一個好的 km 及其係數 αm。

對分類器 Cm 採用指數型誤差

令 m=1時

,m>1時

,上式可寫為 E=sum_{i=1}^{N}w_i^{(m)}e^{-y_i}alpha_mk_m(x_i)

如果km預測正確,則

,如果km預測錯誤,則

,因此上式再分裂為預測正確和預測錯誤的項:

E=sum_{y_i=k_m(x_i)}w_i^{(m)}e^{-alpha_m}+sum_{y_i
eq k_m(x_i)}w_i^{(m)}e^{alpha_m} (公式1)

=sum_{i=1}^{N}w_i^{(m)}e^{-alpha_m}+sum_{y_i
eq k_m(x_i)}w_i^{(m)}(e^{alpha_m}-e^{-alpha_m}) (公式2)

我們希望找到合適的 km 和 αm 使得 E最小。

  1. 先考慮 km。在公式2中,只有

的值受 km 的影響,也就是說,要最小化E,對於km來說,就是要構造一個最小化

的分類器 km。

2. 考慮 αm。用公式1對 αm 求導,當導數 = 0 時 E有最小值。

(e^{alpha_m})^2 = sum_{y_i=k_m(x_i)}w_i^{(m)} igg / sum_{y_i 
eq k_m(x_i)}w_i^{(m)}

如果令錯誤率

ε_m= sum_{y_i
eq k_m(x_i)}w_i^{(m)} Big / sum_{i=i}^{N}w_i^{(m)}

3. 另外看下更新樣本權重。

由於

,於是

所以

參考

深入淺出ML之Boosting家族

維基百科 —— Boosting (machine learning)

維基百科 —— AdaBoost


推薦閱讀:

深度本文匹配發展總結
人工智慧「應該產生」意識嗎?
文因互聯 CEO 鮑捷:確保搞砸人工智慧項目的十種方法
特大好消息!漢遜人工智慧AI電熱水器即將亮相中國市場!
人工智慧的未來 ——記憶、知識、語言

TAG:adaboost | 機器學習 | 人工智慧演算法 |