提升方法

提升方法（Boosting）是一種機器學習中的集成學習元啟發算法，主要用來減小監督式學習中偏差並且也減小方差^[1]，以及一系列將弱學習器轉換為強學習器的機器學習算法^[2]。面對的問題是邁可·肯斯（Michael Kearns）和萊斯利·瓦利安特(Leslie Valiant)提出的：^[3]一組「弱學習者」的集合能否生成一個「強學習者」？弱學習者一般是指一個分類器，它的結果只比隨機分類好一點點；強學習者指分類器的結果非常接近真值。

Robert Schapire在1990年的一篇論文中^[4]對肯斯和瓦利安特的問題的肯定回答在機器學習和統計方面產生了重大影響，最顯着的是導致了提升方法的發展^[5] 。

提升算法[編輯]

大多數提升算法包括由迭代使用弱學習分類器組成，並將其結果加入一個最終的成強學習分類器。加入的過程中，通常根據它們的分類準確率給予不同的權重。加和弱學習者之後，數據通常會被重新加權，來強化對之前分類錯誤數據點的分類。

一個經典的提升算法例子是AdaBoost。一些最近的例子包括LPBoost、TotalBoost、BrownBoost、MadaBoost及LogitBoost。許多提升方法可以在AnyBoost框架下解釋為在函數空間利用一個凸的誤差函數作梯度下降。

批評[編輯]

2008年，谷歌的菲利普·隆（Phillip Long）與哥倫比亞大學的羅可·A·瑟維迪歐（Rocco A. Servedio）發表論文指出這些方法是有缺陷的：在訓練集有錯誤的標記的情況下，一些提升算法雖會嘗試提升這種樣本點的正確率，但卻無法產生一個正確率大於1/2的模型。^[6]

實現[編輯]

Orange, a free data mining software suite, module Orange.ensemble （頁面存檔備份，存於互聯網檔案館）
Weka is a machine learning set of tools that offers variate implementations of boosting algorithms like AdaBoost and LogitBoost
R package GBM （頁面存檔備份，存於互聯網檔案館） (Generalized Boosted Regression Models) implements extensions to Freund and Schapire's AdaBoost algorithm and Friedman's gradient boosting machine.
jboost; AdaBoost, LogitBoost, RobustBoost, Boostexter and alternating decision trees

參考文獻[編輯]

腳註[編輯]

^ Leo Breiman. BIAS, VARIANCE, AND ARCING CLASSIFIERS (PDF). TECHNICAL REPORT. 1996 [19 January 2015]. （原始內容 (PDF)存檔於2015-01-19）. Arcing [Boosting] is more successful than bagging in variance reduction
^ Zhou Zhi-Hua. Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. 2012: 23. ISBN 978-1439830031. The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners
^ Michael Kearns (1988); Thoughts on Hypothesis Boosting （頁面存檔備份，存於互聯網檔案館）, Unpublished manuscript (Machine Learning class project, December 1988)
^ Schapire, Robert E. The Strength of Weak Learnability (PDF). Machine Learning. 1990, 5 (2): 197–227 [2012-08-23]. CiteSeerX 10.1.1.20.723 . S2CID 53304535. doi:10.1007/bf00116037. （原始內容 (PDF)存檔於2012-10-10）.
^ Leo Breiman. Arcing classifier (with discussion and a rejoinder by the author). Ann. Stat. 1998, 26 (3): 801–849. doi:10.1214/aos/1024691079 . Schapire (1990) proved that boosting is possible. (Page 823)
^ Philip M. Long, Rocco A. Servedio, "Random Classiﬁcation Noise Defeats All Convex Potential Boosters" (PDF). [2014-04-17]. （原始內容存檔 (PDF)於2021-01-18）.

其他參考資料[編輯]

Yoav Freund and Robert E. Schapire (1997); A Decision-Theoretic Generalization of On-line Learning and an Application to Boosting （頁面存檔備份，存於互聯網檔案館）, Journal of Computer and System Sciences, 55(1):119-139
Robert E. Schapire and Yoram Singer (1999); Improved Boosting Algorithms Using Confidence-Rated Predictors （頁面存檔備份，存於互聯網檔案館）, Machine Learning, 37(3):297-336

外部連結[編輯]

Robert E. Schapire (2003); The Boosting Approach to Machine Learning: An Overview （頁面存檔備份，存於互聯網檔案館）, MSRI (Mathematical Sciences Research Institute) Workshop on Nonlinear Estimation and Classification
An up-to-date collection of papers on boosting

[1] Leo Breiman. BIAS, VARIANCE, AND ARCING CLASSIFIERS (PDF). TECHNICAL REPORT. 1996 [19 January 2015]. （原始內容 (PDF)存檔於2015-01-19）. Arcing [Boosting] is more successful than bagging in variance reduction

[2] Zhou Zhi-Hua. Ensemble Methods: Foundations and Algorithms. Chapman and Hall/CRC. 2012: 23. ISBN 978-1439830031. The term boosting refers to a family of algorithms that are able to convert weak learners to strong learners

[Kearns88-3] Michael Kearns (1988); Thoughts on Hypothesis Boosting （頁面存檔備份，存於互聯網檔案館）, Unpublished manuscript (Machine Learning class project, December 1988)

[Schapire90-4] Schapire, Robert E. The Strength of Weak Learnability (PDF). Machine Learning. 1990, 5 (2): 197–227 [2012-08-23]. CiteSeerX 10.1.1.20.723 . S2CID 53304535. doi:10.1007/bf00116037. （原始內容 (PDF)存檔於2012-10-10）.

[5] Leo Breiman. Arcing classifier (with discussion and a rejoinder by the author). Ann. Stat. 1998, 26 (3): 801–849. doi:10.1214/aos/1024691079 . Schapire (1990) proved that boosting is possible. (Page 823)

[6] Philip M. Long, Rocco A. Servedio, "Random Classiﬁcation Noise Defeats All Convex Potential Boosters" (PDF). [2014-04-17]. （原始內容存檔 (PDF)於2021-01-18）.

[1]

[2]

[3]

[4]

[5]

[6]