算法起源
Boosting是一種提高任意給定學習算法準確度的方法。它的思想起源於 Valiant提出的 PAC ( Probably Approximately Correct)學習模型。Valiant和 Kearns提出了弱學習和強學習的概念 ,識別錯誤率小於1/2,也即準確率僅比隨機猜測略高的學習算法稱為弱學習算法;識別準確率很高並能在多項式時間內完成的學習算法稱為強學習算法。同時 ,Valiant和 Kearns首次提出了 PAC學習模型中弱學習算法和強學習算法的等價性問題,即任意給定僅比隨機猜測略好的弱學習算法 ,是否可以將其提升為強學習算法 ? 如果二者等價 ,那么只需找到一個比隨機猜測略好的弱學習算法就可以將其提升為強學習算法 ,而不必尋找很難獲得的強學習算法。1990年, Schapire最先構造出一種多項式級的算法 ,對該問題做了肯定的證明 ,這就是最初的 Boosting算法。一年後 ,Freund提出了一種效率更高的Boosting算法。但是,這兩種算法存在共同的實踐上的缺陷 ,那就是都要求事先知道弱學習算法學習正確的下限。1995年 , Freund和 schap ire改進了Boosting算法 ,提出了 AdaBoost (Adap tive Boosting)算法[ 5 ],該算法效率和 Freund於 1991年提出的 Boosting算法幾乎相同 ,但不需要任何關於弱學習器的先驗知識 ,因而更容易套用到實際問題當中。之後 , Freund和 schapire進一步提出了改變 Boosting投票權重的 AdaBoost . M1,AdaBoost . M2等算法 ,在機器學習領域受到了極大的關注。
方法概述
Boosting方法是一種用來提高弱分類算法準確度的方法,這種方法通過構造一個預測函式系列,然後以一定的方式將他們組合成一個預測函式。他是一種框架算法,主要是通過對樣本集的操作獲得樣本子集,然後用弱分類算法在樣本子集上訓練生成一系列的基分類器。他可以用來提高其他弱分類算法的識別率,也就是將其他的弱分類算法作為基分類算法放於Boosting 框架中,通過Boosting框架對訓練樣本集的操作,得到不同的訓練樣本子集,用該樣本子集去訓練生成基分類器;每得到一個樣本集就用該基分類算法在該樣本集上產生一個基分類器,這樣在給定訓練輪數 n 後,就可產生 n 個基分類器,然後Boosting框架算法將這 n個基分類器進行加權融合,產生一個最後的結果分類器,在這 n個基分類器中,每個單個的分類器的識別率不一定很高,但他們聯合後的結果有很高的識別率,這樣便提高了該弱分類算法的識別率。在產生單個的基分類器時可用相同的分類算法,也可用不同的分類算法,這些算法一般是不穩定的弱分類算法,如神經網路(BP) ,決策樹(C4.5)等。
基本算法
由於Boosting算法在解決實際問題時有一個重大的缺陷,即他們都要求事先知道弱分類算法分類正確率的下限,這在實際問題中很難做到。後來 Freund 和 Schapire提出了 AdaBoost 算法,該算法的效率與 Freund 方法的效率幾乎一樣,卻可以非常容易地套用到實際問題中。AdaBoost 是Boosting 算法家族中代表算法,AdaBoost 主要是在整個訓練集上維護一個分布權值向量 Dt( x) ,用賦予權重的訓練集通過弱分類算法產生分類假設 Ht ( x) ,即基分類器,然後計算他的錯誤率,用得到的錯誤率去更新分布權值向量 Dt( x) ,對錯誤分類的樣本分配更大的權值,正確分類的樣本賦予更小的權值。每次更新後用相同的弱分類算法產生新的分類假設,這些分類假設的序列構成多分類器。對這些多分類器用加權的方法進行聯合,最後得到決策結果。這種方法不要求產生的單個分類器有高的識別率,即不要求尋找識別率很高的基分類算法,只要產生的基分類器的識別率大於 0.5 ,就可作為該多分類器序列中的一員。
尋找多個識別率不是很高的弱分類算法比尋找一個識別率很高的強分類算法要容易得多,AdaBoost 算法的任務就是完成將容易找到的識別率不高的弱分類算法提升為識別率很高的強分類算法,這也是 AdaBoost 算法的核心指導思想所在,如果算法完成了這個任務,那么在分類時,只要找到一個比隨機猜測略好的弱分類算法,就可以將其提升為強分類算法,而不必直接去找通常情況下很難獲得的強分類算法。通過產生多分類器最後聯合的方法提升弱分類算法,讓他變為強的分類算法,也就是給定一個弱的學習算法和訓練集,在訓練集的不同子集上,多次調用弱學習算法,最終按加權方式聯合多次弱學習算法的預測結果得到最終學習結果。包含以下2 點:
樣本的權重
AdaBoost 通過對樣本集的操作來訓練產生不同的分類器,他是通過更新分布權值向量來改變樣本權重的,也
就是提高分錯樣本的權重,重點對分錯樣本進行訓練。
(1) 沒有先驗知識的情況下,初始的分布應為等概分布,也就是訓練集如果有 n個樣本,每個樣本的分布機率為1/ n。
(2)每次循環後提高錯誤樣本的分布機率,分錯的樣本在訓練集中所占權重增大,使得下一次循環的基分類器
能夠集中力量對這些錯誤樣本進行判斷。
弱分類器的權重
最後的強分類器是通過多個基分類器聯合得到的,因此在最後聯合時各個基分類器所起的作用對聯合結果有很大的影響,因為不同基分類器的識別率不同,他的作用就應該不同,這裡通過權值體現他的作用,因此識別率越高的基分類器權重越高,識別率越低的基分類器權重越低。權值計算如下:
基分類器的錯誤率:
e = ∑( ht ( x i) ≠yi) Di (1)
基分類器的權重:W t = F( e) ,由基分類器的錯誤率計算他的權重。
算法流程及偽碼描述
算法流程描述
圖 1 算法流程算法流程可用結構圖 1 描述,如圖 1 所示 AdaBoost重複調用弱學習算法(多輪調用產生多個分類器) ,首輪調用弱學習算法時,按均勻分布從樣本集中選取子集作為該次訓練集,以後每輪對前一輪訓練失敗的樣本,賦予較大的分布權值( Di 為第i 輪各個樣本在樣本集中參與訓練的機率) ,使其在這一輪訓練出現的機率增加,即在後面的訓練學習中集中對比較難訓練的樣本進行學習,從而得到 T個弱的基分類器, h1 , h2 , …, ht ,其中 ht 有相應的權值 w t ,並且其權值大小根據該分類器的效果而定。最後的分類器由生成的多個分類器加權聯合產生。
算法偽碼描述
輸入: S = { ( x1 , y1 ) , …( x i , y i) …, ( x n , y n) } , x i ∈X
yi ∈Y ;訓練輪數為 T; 初始化分發權值向量:
公式(2)
for t = 1 , …, T :
(1) 使用分發權值向量 Dt訓練基分類器ht = R( x , y ,Dt) ; R為一弱的分類算法;
(2) 計算錯誤率:e = ∑( ht ( x i) ≠y i) Di (3)
(3) if e≥ 0.5 ,break ;
(4) 計算基分類器的權值 ht :wt ∈w;
(5) 更新權值:Dt ( i+1) = Dt ( i) ×F( e) (4)
其中 F( x)為更新函式,他以該次得到的基分類器的分類
錯誤率 e為自變數;
(6) 將多個基分類器進行聯合,輸出最後的分類器。
在上面的算法中:
①x i ∈X , yi ∈Y , x i 表示樣本屬性組成的向量, yi 表示該樣本的類別標籤;
②Dt 為樣本的分發權值向量:沒有先驗知識的情況下,初始的分布應為等機率分
布,也就是訓練集如果有 n個樣本,每個樣本的分布機率為1/ n;
每次循環後提高錯誤樣本的分布機率,分錯的樣本在訓練集中所占權重增大,使得下一次循環的弱學習算法能
夠集中對這些錯誤樣本進行判斷;Dt 總和應該為1 ;
③wt 為分類器的權值:準確率越高的分類器權重 w越大。
