重采樣方法與機(jī)器學(xué)習(xí)綜述

1、《計(jì)算機(jī)學(xué)報(bào)》2009年第5期1重采樣方法與機(jī)器學(xué)習(xí)綜述畢華梁洪力王玨（中國科學(xué)院自動化研究所復(fù)雜系統(tǒng)與智能科學(xué)重點(diǎn)實(shí)驗(yàn)室北京100190）摘要摘要Boosting算法試圖用弱學(xué)習(xí)器的線性組合逼近復(fù)雜的自然模型，以其優(yōu)秀的可解釋性和預(yù)測能力，得到計(jì)算機(jī)界的高度關(guān)注。但只是將Boosting看作是一種特定損失下的優(yōu)化問題，其統(tǒng)計(jì)學(xué)本質(zhì)未曾得到充分的關(guān)注。本文追根溯源，提出從統(tǒng)計(jì)學(xué)看待boosting方法：在統(tǒng)計(jì)學(xué)框架下，Boosting算

2、法僅僅是重采樣方法的一個(gè)有趣的特例。本文希望改變計(jì)算機(jī)科學(xué)家只重視算法性能忽略數(shù)據(jù)性質(zhì)的現(xiàn)狀，以期找到更適合解決“高維海量不可控?cái)?shù)據(jù)”問題的方法。關(guān)鍵詞關(guān)鍵詞重采樣；自助法；Boosting；機(jī)器學(xué)習(xí)中圖法分類號中圖法分類號TP18ResamplingMethodsMachineLearning:ASurveyBIHuaLIANGHongLiWANGJue(KeyLabatyofComplexSystemsIntelligenceSci

3、enceInstituteofAutomation，ChineseAcademyofSciences，Beijing100190)AbstractInboostingalgithmcomplexnaturalmodelisapproximatedbythelinearcombinationofweaklearners.Duetoitsexcellentinterpretabilitypredictionpowerboostinghasb

4、ecomeanintensivefocusamongcomputersciencefield.Howeveritisonlyconsideredasanoptimizingprocedurewithaspecificlossfunctionwhosenatureinstatisticshasneverobtainedsufficientattention.Inessenceastatisticalperspectiveofboostin

5、galgithmisbroughtoutinthispaperi.e.aninterestingspecialcaseofresamplingmethods.Wehopethecurrentsituationofexcessiveattentionbeingpaidtotheperfmanceofalgithmwhiletheacteristicofdatabeingignedwillbechangedsuchthatthetaskso

6、f“highdimensionallargevolumedatageneratedinanuncontrolledmanner”couldbetackledmeappropriately.KeywdsresamplingbootstrapBoosting；machinelearning1.引言引言1984年，Valiant[1]在他的論文中提出機(jī)器學(xué)習(xí)的另類理念。他認(rèn)為，學(xué)習(xí)模型無需絕對精確，只需概率近似正確(ProbablyAppro

7、ximatelyCrect，簡寫為PAC)即可。由此，他建立了PAC的理論基礎(chǔ)。這個(gè)理論可以簡單描述如下：令是自然模型，是從樣本集學(xué)習(xí)后建立的模型，以概()Fx()fx()()Fxfx???率成立。這里的關(guān)鍵是，“概率成立”，而不是以概率1成立。這個(gè)理1??1??論對Vapnik建立有限樣本統(tǒng)計(jì)機(jī)器學(xué)習(xí)理論有重要的意義。Kearns和Valiant《計(jì)算機(jī)學(xué)報(bào)》2009年第5期3這個(gè)過程來看，特別是基于給定樣本集的采樣方式，其主要貢獻(xiàn)是

8、解決算法設(shè)計(jì)復(fù)雜性問題，尤其是針對非線性問題的算法設(shè)計(jì)。如果我們使用的每個(gè)學(xué)習(xí)算法是線性的話，上述的學(xué)習(xí)過程就有些類似分段線性的思想。對機(jī)器學(xué)習(xí)來說，這個(gè)方法涉及四個(gè)重要的要素：樣本采集、采樣策略、算法類型、集群方法。這四個(gè)要素將是本文展開討論的線索。與Schapire以及他的合作者發(fā)表他們的研究結(jié)果的同時(shí)，統(tǒng)計(jì)學(xué)界也開始從模型角度關(guān)注重采樣方法。Breiman很快發(fā)表了他設(shè)計(jì)的方法Bagging[8](BaggingPredicts)

9、。這個(gè)方法與Adaboost方法相比較，解決算法復(fù)雜性的意圖大大降低，統(tǒng)計(jì)學(xué)的痕跡更為清晰。正是由于其目的與計(jì)算機(jī)科學(xué)家有區(qū)別，因此，這項(xiàng)研究沒有像Adaboost那樣受到計(jì)算機(jī)學(xué)界的關(guān)注。在算法類型和集群方法兩個(gè)方面，Bagging與Adaboost沒有任何區(qū)別，它們最大區(qū)別是在于“采樣策略”。具體地說，Bagging沿襲了經(jīng)典重采樣方法隨機(jī)采樣策略，而Adaboost則使用“富信息”策略。這個(gè)差別導(dǎo)致了“樣本采集”步驟不同，后者暗示

10、，“富信息”策略一定是基于滿足獨(dú)立同分布的當(dāng)前給定樣本集，否則“重采樣”過程就沒有“富信息”一說了，而前者則沒有這個(gè)限制，它暗示的樣本集既包含已經(jīng)觀測到的樣本，也包含以后可能被觀測到樣本。顯然，對關(guān)注從樣本集通過算法設(shè)計(jì)，建立模型的計(jì)算機(jī)學(xué)界，后者更具有吸引力。由于在原理上，這些方法沒有本質(zhì)的區(qū)別，因此，目前在重采樣意義下，大家仍沿用Schapire對其的稱謂，將這類方法統(tǒng)稱為Boosting方法。從自然模型或樣本集多次采樣建模的角度來

11、看，重采樣方法已經(jīng)有很長的歷史(見本文第2節(jié))。然而，將重采樣方法引入傳統(tǒng)統(tǒng)計(jì)學(xué)的研究應(yīng)該是Quenouille[9]于1949年提出的“刀切法”(Jackknife)。但是，真正包含樣本采集、采樣策略、算法類型、集群方法四個(gè)要素，而目前最具影響力的重采樣方法的研究則是Efron[10]在1979年提出“自助法”。高維海量不可控?cái)?shù)據(jù)的涌現(xiàn)，對統(tǒng)計(jì)學(xué)是一個(gè)挑戰(zhàn)，算法復(fù)雜性也已成為統(tǒng)計(jì)學(xué)家不得不面對的嚴(yán)肅問題。但是，通過“樣本采集”獲得的樣

12、本集，并應(yīng)用統(tǒng)計(jì)方法獲得的結(jié)論，對自然模型的真實(shí)性擬合仍然是統(tǒng)計(jì)學(xué)的本質(zhì)。目前，高維海量不可控?cái)?shù)據(jù)的涌現(xiàn)對統(tǒng)計(jì)學(xué)提出了挑戰(zhàn)性的問題，為了解釋這些問題，我們需要了解統(tǒng)計(jì)學(xué)對數(shù)據(jù)統(tǒng)計(jì)分析的發(fā)展歷程。2.高維數(shù)據(jù)的兩個(gè)基本問題高維數(shù)據(jù)的兩個(gè)基本問題統(tǒng)計(jì)學(xué)始于被觀測的數(shù)據(jù)，Wegman[11]把統(tǒng)計(jì)描述為一種將原數(shù)據(jù)轉(zhuǎn)化為信息的方法，以區(qū)別于傳統(tǒng)統(tǒng)計(jì)學(xué)的描述傳統(tǒng)統(tǒng)計(jì)學(xué)是關(guān)于收集和分析帶隨機(jī)性誤差的數(shù)據(jù)的科學(xué)和藝術(shù)[12]。從統(tǒng)計(jì)學(xué)的發(fā)展可以看出