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

1、《計(jì)算機(jī)學(xué)報(bào)》2009年第5期1重采樣方法與機(jī)器學(xué)習(xí)綜述畢華梁洪力王玨（中國(guó)科學(xué)院自動(dòng)化研究所復(fù)雜系統(tǒng)與智能科學(xué)重點(diǎn)實(shí)驗(yàn)室北京100190）摘要摘要Boosting算法試圖用弱學(xué)習(xí)器的線性組合逼近復(fù)雜的自然模型，以其優(yōu)秀的可解釋性和預(yù)測(cè)能力，得到計(jì)算機(jī)界的高度關(guān)注。但只是將Boosting看作是一種特定損失下的優(yōu)化問(wèn)題，其統(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ù)”問(wèn)題的方法。關(guān)鍵詞關(guān)鍵詞重采樣；自助法；Boosting；機(jī)器學(xué)習(xí)中圖法分類(lèi)號(hào)中圖法分類(lèi)號(hào)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í)的另類(lèi)理念。他認(rèn)為，學(xué)習(xí)模型無(wú)需絕對(duì)精確，只需概率近似正確(ProbablyAppro

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

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

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

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

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

12、得的樣本集，并應(yīng)用統(tǒng)計(jì)方法獲得的結(jié)論，對(duì)自然模型的真實(shí)性擬合仍然是統(tǒng)計(jì)學(xué)的本質(zhì)。目前，高維海量不可控?cái)?shù)據(jù)的涌現(xiàn)對(duì)統(tǒng)計(jì)學(xué)提出了挑戰(zhàn)性的問(wèn)題，為了解釋這些問(wèn)題，我們需要了解統(tǒng)計(jì)學(xué)對(duì)數(shù)據(jù)統(tǒng)計(jì)分析的發(fā)展歷程。2.高維數(shù)據(jù)的兩個(gè)基本問(wèn)題高維數(shù)據(jù)的兩個(gè)基本問(wèn)題統(tǒng)計(jì)學(xué)始于被觀測(cè)的數(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ā)展可