Adaboost 總結的很好
from https://stblog.baidu-tech.com/?p=19
wiki https://en.wikipedia.org/wiki/AdaBoost
一、Boosting算法的發展曆史
Boosting算法是一種把若幹個分類器整合為一個分類器的方法,在boosting算法產生之前,還出現過兩種比較重要的將多個分類器整合 為一個分類器的方法,即boostrapping方法和bagging方法。我們先簡要介紹一下bootstrapping方法和bagging方法。
1)bootstrapping方法的主要過程
主要步驟:
i)重複地從一個樣本集合D中采樣n個樣本
ii)針對每次采樣的子樣本集,進行統計學習,獲得假設Hi
iii)將若幹個假設進行組合,形成最終的假設Hfinal
iv)將最終的假設用於具體的分類任務
2)bagging方法的主要過程 -----bagging可以有多種抽取方法
主要思路:
i)訓練分類器
從整體樣本集合中,抽樣n* < N個樣本 針對抽樣的集合訓練分類器Ci
ii)分類器進行投票,最終的結果是分類器投票的優勝結果
但是,上述這兩種方法,都隻是將分類器進行簡單的組合,實際上,並沒有發揮出分類器組合的威力來。直到1989年,Yoav Freund與 Robert Schapire提出了一種可行的將弱分類器組合為強分類器的方法。並由此而獲得了2003年的哥德爾獎(Godel price)。
Schapire還提出了一種早期的boosting算法,其主要過程如下:
i)從樣本整體集合D中,不放回的隨機抽樣n1 < n個樣本,得到集合 D1
訓練弱分類器C1
ii)從樣本整體集合D中,抽取 n2 < n個樣本,其中合並進一半被C1 分類錯誤的樣本。得到樣本集合 D2
訓練弱分類器C2
iii)抽取D樣本集合中,C1 和 C2 分類不一致樣本,組成D3
訓練弱分類器C3
iv)用三個分類器做投票,得到最後分類結果
到了1995年,Freund and schapire提出了現在的adaboost算法,其主要框架可以描述為:
i)循環迭代多次
更新樣本分布
尋找當前分布下的最優弱分類器
計算弱分類器誤差率
ii)聚合多次訓練的弱分類器
在下圖中可以看到完整的adaboost算法:
圖1.1 adaboost算法過程
現在,boost算法有了很大的發展,出現了很多的其他boost算法,例如:logitboost算法,gentleboost算法等等。在這次報告中,我們將著重介紹adaboost算法的過程和特性。
二、Adaboost算法及分析
從圖1.1中,我們可以看到adaboost的一個詳細的算法過程。Adaboost是一種比較有特點的算法,可以總結如下:
1)每次迭代改變的是樣本的分布,而不是重複采樣(re weight)
2)樣本分布的改變取決於樣本是否被正確分類
總是分類正確的樣本權值低
總是分類錯誤的樣本權值高(通常是邊界附近的樣本)
3)最終的結果是弱分類器的加權組合
權值表示該弱分類器的性能
簡單來說,Adaboost有很多優點:
1)adaboost是一種有很高精度的分類器
2)可以使用各種方法構建子分類器,adaboost算法提供的是框架
3)當使用簡單分類器時,計算出的結果是可以理解的。而且弱分類器構造極其簡單
4)簡單,不用做特征篩選
5)不用擔心overfitting!
總之:adaboost是簡單,有效。
下麵我們舉一個簡單的例子來看看adaboost的實現過程:
圖中,“+”和“-”分別表示兩種類別,在這個過程中,我們使用水平或者垂直的直線作為分類器,來進行分類。
第一步:
根據分類的正確率,得到一個新的樣本分布D2,一個子分類器h1
其中劃圈的樣本表示被分錯的。在右邊的途中,比較大的“+”表示對該樣本做了加權。
第二步:
根據分類的正確率,得到一個新的樣本分布D3,一個子分類器h2
第三步:
得到一個子分類器h3
整合所有子分類器:
因此可以得到整合的結果,從結果中看,及時簡單的分類器,組合起來也能獲得很好的分類效果,在例子中所有的。
Adaboost算法的某些特性是非常好的,在我們的報告中,主要介紹adaboost的兩個特性。
一是訓練的錯誤率上界,隨著迭代次數的增加,會逐漸下降;
二是adaboost算法即使訓練次數很多,也不會出現過擬合的問題。
下麵主要通過證明過程和圖表來描述這兩個特性:
1)錯誤率上界下降的特性
從而可以看出,隨著迭代次數的增加,實際上錯誤率上界在下降。
2)不會出現過擬合現象
通常,過擬合現象指的是下圖描述的這種現象,即隨著模型訓練誤差的下降,實際上,模型的泛化誤差(測試誤差)在上升。橫軸表示迭代的次數,縱軸表示訓練誤差的值。
而實際上,並沒有觀察到adaboost算法出現這樣的情況,即當訓練誤差小到一定程度以後,繼續訓練,返回誤差仍然不會增加。
對這種現象的解釋,要借助margin的概念,其中margin表示如下:
通過引入margin的概念,我們可以觀察到下圖所出現的現象:
從圖上左邊的子圖可以看到,隨著訓練次數的增加,test的誤差率並沒有升高,同時對應著右邊的子圖可以看到,隨著訓練次數的增 加,margin一直在增加。這就是說,在訓練誤差下降到一定程度以後,更多的訓練,會增加分類器的分類margin,這個過程也能夠防止測試誤差的上 升。
三、多分類adaboost
在日常任務中,我們通常需要去解決多分類的問題。而前麵的介紹中,adaboost算法隻能適用於二分類的情況。因此,在這一小節中,我們著重介紹如何將adaboost算法調整到適合處理多分類任務的方法。
目前有三種比較常用的將二分類adaboost方法。
1、adaboost M1方法
主要思路: adaboost組合的若幹個弱分類器本身就是多分類的分類器。
在訓練的時候,樣本權重空間的計算方法,仍然為:
在解碼的時候,選擇一個最有可能的分類
2、adaboost MH方法
主要思路: 組合的弱分類器仍然是二分類的分類器,將分類label和分類樣例組合,生成N個樣本,在這個新的樣本空間上訓練分類器。
可以用下圖來表示其原理:
3、對多分類輸出進行二進製編碼
主要思路:對N個label進行二進製編碼,例如用m位二進製數表示一個label。然後訓練m個二分類分類器,在解碼時生成m位的二進製數。從而對應到一個label上。
四、總結
最後,我們可以總結下adaboost算法的一些實際可以使用的場景:
1)用於二分類或多分類的應用場景
2)用於做分類任務的baseline
無腦化,簡單,不會overfitting,不用調分類器
3)用於特征選擇(feature selection)
4)Boosting框架用於對badcase的修正
隻需要增加新的分類器,不需要變動原有分類器
由於adaboost算法是一種實現簡單,應用也很簡單的算法。Adaboost算法通過組合弱分類器而得到強分類器,同時具有分類錯誤率上界隨著訓練增加而穩定下降,不會過擬合等的性質,應該說是一種很適合於在各種分類場景下應用的算法。
最後更新:2017-04-03 05:39:58