Ｂｏｏｓｔｉｎｇ算法研究

摘要：Boosting 算法是近年來在機器學習領域中一種流行的用來提高學習精度的算法。文中以AdaBoost算法為例來介紹Boosting的基本原理。

關鍵詞：機器學習；Boosting；泛化誤差；分類

中圖分類號：TP181文獻標識碼：A文章編號：1009-3044(2008)36-2698-02

A Study of Boosting Algorithm

LU Gang1， CHEN Yong1， FAN Yong-xin2， HU Cheng1

(1.The Artillery Academy of PLA， Hefei 230031， China;2.China Construction Bank Yunnan Branch， Kunming 650021， China)

Abstract: Boosting is a general method for improving the accuracy of any given learning algorithm.This short overview paper introduces the boosting algorithm AdaBoost， and explains the underlying theory of boosting.

Key words: machine learning; boosting; generalization error; classification

1 引言

Freund 和 Schapire的AdaBoost算法問世便引起了機器學習和數理統計兩大領域的廣泛關注。它的思想起源于Valiant提出的PAC ( Probably Approximately Correct)學習模型。Kearns 和Valiant首次提出PAC學習模型中任意給定僅比隨機猜測略好的弱學習算法是否可“boosted”為強學習算法。1990年，Schapire構造出一種多項式級的算法，對該問題做了肯定的證明，這是最初的Boosting算法。一年后，Freund提出了一種效率更高的Boosting算法。但是，這兩種算法存在共同的實踐上的缺陷，那就是都要求事先知道弱學習算法學習正確率的下限。這些早期的Boosting 算法首先被Drucker、Schapire和Simard應用于一次OCR工作中。1995年，Freund和schapire改進了Boosting算法，提出了AdaBoost (Adaptive Boosting)算法，此算法不需要任何關于弱分類器的先驗知識，可以非常容易地應用到實際問題中。

2 AdaBoost算法

在機器學習領域中，AdaBoost算法得到極大的重視。實驗結果顯示，AdaBoost能顯著提高學習精度和泛化能力，已經成為Boosting 系列中的代表算法。之后出現的各種Boosting算法都是在AdaBoost算法的基礎之上發展而來的。對AdaBoost算法的研究應用大多集中在分類問題中，近年來也出現了一些在回歸問題上的研究。尋找多個識別率不是很高的弱分類算法比尋找一個識別率很高的強分類算法要容易得多，AdaBoost算法的任務就是完成將容易找到的識別率不高的弱分類算法提升為識別率很高的強分類算法，這也是AdaBoost 算法的核心指導思想所在，如果算法完成了這個任務，那么在分類時，只要找到一個比隨機猜測略好的弱分類算法，也就是給定一個弱學習算法和訓練集，在訓練集的不同子集上，多次調用弱學習算法，最終按加權方式聯合多次弱學習算法的預測結果就可得到最終學習結果。

AdaBoost算法的基本思想是：首先給出任意一個弱學習算法和訓練集(x1，y1)， (x2， y2 ) ，...， (xm， ym) ，此處，xi∈X， X表示某個域或實例空間，在分類問題中是一個帶類別標志的集合，yi∈Y={+1， -1}。初始化時， Adaboost為訓練集指定分布為1/m，即每個訓練例的權重都相同為1 /m 。接著，調用弱學習算法進行T次迭代，每次迭代后，按照訓練結果更新訓練集上的分布，對于訓練失敗的訓練例賦予較大的權重，使得下一次迭代更加關注這些訓練例，從而得到一個預測函數序列h1，h2，...，ht，每個預測函數ht也賦予一個權重，預測效果好的，相應的權重越大。T次迭代之后，在分類問題中最終的預測函數H采用帶權重的投票法產生。單個弱學習器的學習準確率不高，經過運用Boosting算法之后，最終結果準確率將得到提高。每個樣本都賦予一個權重， T次迭代，每次迭代后，對分類錯誤的樣本加大權重。

離散的AdaBoost算法，給定訓練樣本集S={(x1，y1)，(x2，y2))，…， (xl，yl)∈Rn×{-1，+1}}。其中xi(i=1，2，…，l)服從獨立同分布。

離散的AdaBoost 算法的偽碼描述如下：

1) 初始化權重：wi=1/l，i=1，2，…，l

2) 循環：Repeat from m=1，2，…，M:

① 使用權值wi，用弱分類器fm(x)擬合訓練數據；

② 計算：

；

① 計算:Cm=log((1-errm)/errm)；

② 置wi<—wiexp[Cm#8226;I(yi≠fn(xi))]，i=1，2，…，l，并且重新正則化權重使得 wi=1。

3）輸出：分類器決策函數。

一個弱分類器的誤差率只比隨機猜測略好一些。Boosting的目的就是連續對反復修改的數據應用弱分類算法，由此產生一個弱分類器序列fm(x)，m=1，2，…，M。然后，通過一個加權的多數表決來合并全部預測，以產生最終預測：

這里，C1，C2，…，Cm由boosting算法來計算，并對每個fm(x)的貢獻加權。它們的作用是對序列中較精確的分類器給予較高的影響。

在每個boosting迭代中，數據修改就是對每一訓練樣本(xi，yi)(i=1，2，…，l)實施加權w1，w2，…，wl。開始，所有權都被置成wi=1/l，以便第一步能夠簡單地用通常的方式在數據上訓練分類器。對每一個相繼的迭代m=2，3，…，M，樣本的權值被分別修改，并且分類算法被再次應用于加權樣本。在第m步，那些被前一個迭代步驟導出的分類器fm-1(x)誤分類的樣本權值提高，而被正確分類的樣本權值降低。這樣，隨著迭代的進行，那些很難正確分類的樣本受到了權重不斷增長的影響。因此，每個后繼分類器被強制關注那些被前面的分類器誤分類的訓練樣本。

離散的AdaBoost算法中，步驟2（a）在加權樣本上導出當前的分類器fm (x)。步驟2（b）計算當前加權誤差率，步驟2（c）計算權值Cm，該權值在產生最終分類器f(x)時（步驟3）賦予fm(x)。在步驟2（d），為下一步迭代更新每個樣本的權值。被fm(x)誤分類的樣本的權值被放大一個因子exp(Cm)，增加了對導出序列中下一個分類器fm+1(x)的相對影響。

離散的AdaBoost算法中弱分類器fm(x)返回離散的類標號。如果弱分類器改為實數值預測（如映射到區間[0，1]的概率），則可以對離散的AdaBoost做適當的修改，即下面所述的Real AdaBoost算法。

Real AdaBoost算法的偽碼描述如下：

1）初始化權重：wi=1/l，i=1，2，…，l。

2）循環：Repeat for m=1，2，…，M:

① 在加權為wi的訓練數據上擬合分類器以獲得在區間[0，1]上的類概率估計Pm(x)=Pw(y=1|x)；

② 置弱分類器: ；

③ 置權重，wi<—wiexp[-yifm(xi)]，i=1，2，…，l，重新正則化權重使得 wi=1。

3）輸出：分類器決策函數 。

以離散AdaBoost為例，如圖1所示，其中弱分類器僅僅是個樹樁——兩個端節點的分類樹。

初始的時候，只用單個弱分類器的分類錯誤率較高，但隨著boosting迭代的進行，分類錯誤率明顯減小，可見AdaBoost算法能夠顯著提升很弱的分類器的性能。

3 Boosting算法理論分析

Schapire， Singer和Freund首先從理論上推導出最終預測函數的訓練誤差：定義f(x)=αtht(x)，則有H(x)=sign(f(x))，推出誤差邊界為：

式中我們可以看出，可以通過選擇每一輪中的αt和ht來最小化Zt，使得訓練誤差迅速減小。大量的試驗表明，Boosting不但能夠提高學習精度，而且在訓練了幾千輪之后也不會發生過適應現象，而且其泛化誤差在訓練誤差已經降到零后仍會繼續降低。Schapire和Freund用Boosting C4.5對UCI中的“letter”樣本集進行分類，圖2是得出的相對于迭代次數T的誤差曲線。

圖2 圖3

圖2中，上面一條曲線是泛化誤差，下面一條曲線是訓練誤差。從圖中我們可以看出，在訓練誤差已經達到零后， Boosting仍能繼續降低泛化誤差，而不會因此出現泛化誤差惡化的現象。泛化誤差與訓練輪數T無關，也就是說泛化誤差不受訓練輪數影響。圖3反映出Boosting對邊界的影響。當訓練誤差降為零后，Boosting仍然會繼續提高訓練樣本的邊界值，從而增大了最小邊界，使分類的可靠性增加，使得泛化誤差也能夠繼續下降。（下轉第2708頁）

（上接第2699頁）

4 結束語

Boosting是近十幾年來提出的最有效的學習思想之一，它最初是為分類問題而設計的，但也可以對它進行擴充以解決回歸問題，并且Boosting的思想已被用到ranking和cost-sensitive上，也有一些研究者將Boosting應用到非監督學習問題上。Boosting在實際當中也得到了很多應用，例如，語音識別、醫療診斷等。目前，Boosting算法仍有許多值得研究的方向。Boosting中迭代次數是一個經驗值，如何選擇合適的迭代次數；Boosting在某些情況下會發生過適應現象，找到產生過適應的條件也是一個值得研究的方面；如何減少Boosting對噪聲的敏感；Boosting和模糊集理論相結合在多分類中的應用等。近年來，張通等人在分析了一些流行的學習算法后，從一致性的觀點對一些流行的學習算法如最小二乘法、支持向量機、Boosting等等進行了理論分析，發現這些學習算法都具有逼近貝葉斯最優解的性能，只是使用了不同的損失函數而已。這種理論分析的方法進一步完善了統計學習理論體系，得到了研究者們的普遍關注。另外，Boosting在實際應用中也有廣泛的前景，例如：圖像識別及檢索、手寫體字符識別、語音識別、文本分類等。

參考文獻：

[1] ValiantL G .A Theory of the Learnable[J].Communications of the ACM，1984，27(11):1134-1142.

[2] Schapire R E， Freund Y， Bartlett P et al.Boosting the Margin: a New Explanation for the Effectiveness of Voting Methods [J].The Annals of Statistics，1998，26(5):1651-1686.

[3] Freund Y， Robert E. Schapire. A Short Introduction to Boosting[J].Journal of Japanese Society for Artificial Intelligence，1999，14(5):771-780.

[4] Freund Y， Schapire R. Experiments with a new boosting algorithm[C].In: Proceedings of the Thirteenth International Conference.San Francisco: Machine Learning，1996:148-156

[5] Zhang T. Statistical behavior and consistency of classification methods based on convex risk minimization[J].Annals of Statistics，2004(32):56-85

[6] Friedman J， Hastie T， Tibshirani R. Additive logistic regression: a statistics view of boosting[J].Annals of Statistics， 2000(28):337-407.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”