重采样方法与机器学习综述

《重采样方法与机器学习综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机学报》2009年第5期重采样方法与机器学习综述毕华梁洪力王珏（中国科学院自动化研究所复杂系统与智能科学重点实验室北京100190）摘要Boosting算法试图用弱学习器的线性组合逼近复杂的自然模型，以其优秀的可解释性和预测能力，得到计算机界的高度关注。但只是将Boosting看作是一种特定损失下的优化问题，其统计学本质未曾得到充分的关注。本文追根溯源，提出从统计学看待boosting方法：在统计学框架下，Boosting算法仅仅是重采样方法的一个有趣的特例。本文希望改变计算机科学家只重视算法性能忽略数据性质的现状，以期找到更适合解

2、决“高维海量不可控数据”问题的方法。关键词重采样；自助法；Boosting；机器学习中图法分类号TP18ResamplingMethodsandMachineLearning:ASurveyBIHuaLIANGHong-LiWANGJue(KeyLaboratoryofComplexSystemsandIntelligenceScience,InstituteofAutomation，ChineseAcademyofSciences，Beijing100190)AbstractInboostingalgorithmcomplexnatur

3、almodelisapproximatedbythelinearcombinationofweaklearners.Duetoitsexcellentinterpretabilityandpredictionpower,boostinghasbecomeanintensivefocusamongcomputersciencefield.However,itisonlyconsideredasanoptimizingprocedurewithaspecificlossfunction,whosenatureinstatisticshasne

4、verobtainedsufficientattention.Inessence,astatisticalperspectiveofboostingalgorithmisbroughtoutinthispaper,i.e.,aninterestingspecialcaseofresamplingmethods.Wehopethecurrentsituationofexcessiveattentionbeingpaidtotheperformanceofalgorithmwhilethecharacteristicofdatabeingig

5、noredwillbechanged,suchthatthetasksof“highdimensionalandlargevolumedatageneratedinanuncontrolledmanner”couldbetackledmoreappropriately.Keywordsresampling;bootstrap;Boosting；machinelearning1.引言1984年，Valiant[1]在他的论文中提出机器学习的另类理念。他认为，学习模型无需绝对精确，只需概率近似正确(ProbablyApproximatelyC

6、orrect，简写为PAC)即可。由此，他建立了PAC的理论基础。这个理论可以简单描述如下：令是自然模型，是从样本集学习后建立的模型，以概率成立。这里的关键是，“概率成立”，而不是以概率1成立。这个理论对Vapnik建立有限样本统计机器学习理论有重要的意义。Kearns和Valiant27《计算机学报》2009年第5期[2,3](1988,1994)在PAC的基础上，提出弱可学习的理论。他这样描述一个概念是弱可学习：与定义如上，成立的概率大于。这意味着，一个概念如果是弱可学习的，那么只要求一个弱可学习算法产生的模型的精度高于50%，也就是

7、比随机猜想稍好。同时他将满足PAC原始定义的概念可学习称为强可学习。进而，他问了如下一个问题，强可学习在什么条件下与弱可学习等价。1990年，Schapire[4]回答了这个问题。他使用构造的方法证明：一个概念弱可学习的充要条件是这个概念强可学习。这是一个有些“不可思议”的结论。正是由于这个定理，开始了至今还在人们关注视野中的一类机器学习的研究，机器学习研究者将这类学习方式称为集群学习(EnsembleLearning)[5]。从此以后，统计学家开始介入机器学习的研究。这是本文讨论的重点，我们将在本文以后部分详细说明统计学家对这个问题的描

8、述。以后Freund和Schapire提出了Adaboost算法[6]，由于这个算法如此简单且灵活，立即受到计算机科学技术界的推崇。特别是，人们在使用这个算法时，发现很少出现“过学习(Over