《【2017年整理】重采样方法与机器学习综述》由会员分享，可在线阅读，更多相关《【2017年整理】重采样方法与机器学习综述（27页珍藏版）》请在金锄头文库上搜索。
1、计算机学报2009 年第 5 期1重采样方法与机器学习综述毕 华 梁洪力 王 珏（中国科学院自动化研究所 复杂系统与智能科学重点实验室 北京 100190）摘要 Boosting 算法试图用弱学习器的线性组合逼近复杂的自然模型，以其优秀的可解释性和预测能力，得到计算机界的高度关注。但只是将 Boosting 看作是一种特定损失下的优化问题，其统计学本质未曾得到充分的关注。本文追根溯源，提出从统计学看待 boosting方法：在统计学框架下，Boosting 算法仅仅是重采样方法的一个有趣的特例。本文希望改变计算机科学家只重视算法性能忽略数据性质的现状，以期找到更适合解决“高维海量不可控数据”问
2、题的方法。关键词 重采样；自助法；Boosting；机器学习中图法分类号 TP18Resampling Methods and Machine Learning: A SurveyBI Hua LIANG Hong-Li WANG Jue(Key Laboratory of Complex Systems and Intelligence Science,Institute of Automation， Chinese Academy of Sciences， Beijing 100190)Abstract In boosting algorithm complex natural model
3、 is approximated by the linear combination of weak learners. Due to its excellent interpretability and prediction power, boosting has become an intensive focus among computer science field. However, it is only considered as an optimizing procedure with a specific loss function, whose nature in stati
4、stics has never obtained sufficient attention. In essence, a statistical perspective of boosting algorithm is brought out in this paper, i.e., an interesting special case of resampling methods. We hope the current situation of excessive attention being paid to the performance of algorithm while the
5、characteristic of data being ignored will be changed, such that the tasks of “high dimensional and large volume data generated in an uncontrolled manner” could be tackled more appropriately.Keywords resampling; bootstrap; Boosting；machine learning1. 引言1984 年，Valiant 1在他的论文中提出机器学习的另类理念。他认为，学习模型无需绝对精确
6、，只需概率近似正确(Probably Approximately Correct，简写为PAC)即可。由此，他建立了 PAC 的理论基础。这个理论可以简单描述如下：令 是自然模型， 是从样本集学习后建立的模型， 以概()Fx()fx ()Fxf率 成立。这里的关键是，“概率 成立”，而不是以概率 1 成立。这个理1论对 Vapnik 建立有限样本统计机器学习理论有重要的意义。Kearns 和 Valiant 计算机学报2009 年第 5 期22,3(1988,1994)在 PAC 的基础上，提出弱可学习的理论。他这样描述一个概念是弱可学习： 与 定义如上， 成立的概率大于()Fxf()Fxf。
7、这意味着，一个概念如果是弱可学习的，那么只要求一(1/2),01/2个弱可学习算法产生的模型的精度高于 50%，也就是比随机猜想稍好。同时他将满足 PAC 原始定义的概念可学习称为强可学习。进而，他问了如下一个问题，强可学习在什么条件下与弱可学习等价。1990 年，Schapire 4回答了这个问题。他使用构造的方法证明：一个概念弱可学习的充要条件是这个概念强可学习。这是一个有些“不可思议” 的结论。正是由于这个定理，开始了至今还在人们关注视野中的一类机器学习的研究，机器学习研究者将这类学习方式称为集群学习(Ensemble Learning)5。从此以后，统计学家开始介入机器学习的研究。这是
8、本文讨论的重点，我们将在本文以后部分详细说明统计学家对这个问题的描述。以后 Freund 和 Schapire 提出了Adaboost 算法 6，由于这个算法如此简单且灵活，立即受到计算机科学技术界的推崇。特别是，人们在使用这个算法时，发现很少出现“过学习(Overfitting)”现象，这个性质大大超出了人们的期望，并派生了研究这个问题的很多课题 7。事实上，尽管 Schapire 的定理是基于 PAC 理论，但是，其使用的构造性证明方法与统计学家 Efron 比他早十余年发展的属于重采样方法的自助法(Bootstrap)没有本质区别。如果说有区别，那也只是 Schapire 的方法使用了一
9、种特殊的采样策略。目前，大多数计算科学家称其为“ 富信息” 策略，即，一个弱学习器不能很好学习的样本(概念)，将尽可能成为下一个弱学习器着重学习的样本。这就是 Adaboost 的原理。这里，需要指出，由于机器学从样本学习获得模型，因此，“概念可学习”是指一个基于样本表述的概念，可以通过学习获得一个可以在 PAC 意义下概括这个概念的模型，即，可以概括样本的模型。为了与统计学重采样方法相比较，我们首先简单描述 Schapire 的方法：给定一个样本集，它是与自然模型同分布且独立采样获得。首先，假设样本集上每个样本对模型的贡献是相同的，即每个样本具有相同的权重，使用一个学习算法，建立一个模型；然
10、后，根据这个模型改变样本集上样本的权重(对样本重新排序) ，使得在新的样本集中，不能被这个模型正确概括的样本具有较大的概率；使用这个样本集再次学习，获得另一个模型；重复这个过程，直到满足停止准则，过程结束。由于每个模型只可以正确概括部分样本，故称其为弱模型。然后，使用投票方式将它们集群，构成强模型。由于投票方式可以描述为加性模型形式，这也就是为什么 Adaboost 算法被认为是一种“集群学习”的由来。从计算机学报2009 年第 5 期3这个过程来看，特别是基于给定样本集的采样方式，其主要贡献是解决算法设计复杂性问题，尤其是针对非线性问题的算法设计。如果我们使用的每个学习算法是线性的话，上述的
11、学习过程就有些类似分段线性的思想。对机器学习来说，这个方法涉及四个重要的要素：样本采集、采样策略、算法类型、集群方法。这四个要素将是本文展开讨论的线索。与 Schapire 以及他的合作者发表他们的研究结果的同时，统计学界也开始从模型角度关注重采样方法。Breiman 很快发表了他设计的方法-Bagging 8 (Bagging Predictors)。这个方法与 Adaboost 方法相比较，解决算法复杂性的意图大大降低，统计学的痕迹更为清晰。正是由于其目的与计算机科学家有区别，因此，这项研究没有像 Adaboost 那样受到计算机学界的关注。在算法类型和集群方法两个方面，Bagging 与
12、 Adaboost 没有任何区别，它们最大区别是在于“采样策略”。具体地说， Bagging 沿袭了经典重采样方法 -随机采样策略，而Adaboost 则使用 “富信息”策略。这个差别导致了“ 样本采集”步骤不同，后者暗示，“富信息”策略一定是基于满足独立同分布的当前给定样本集，否则“重采样”过程就没有“富信息”一说了，而前者则没有这个限制，它暗示的样本集既包含已经观测到的样本，也包含以后可能被观测到样本。显然，对关注从样本集通过算法设计，建立模型的计算机学界，后者更具有吸引力。由于在原理上，这些方法没有本质的区别，因此，目前在重采样意义下，大家仍沿用 Schapire 对其的称谓，将这类方法
13、统称为 Boosting 方法。从自然模型或样本集多次采样建模的角度来看，重采样方法已经有很长的历史( 见本文第 2 节) 。然而，将重采样方法引入传统统计学的研究应该是Quenouille9于 1949 年提出的 “刀切法”(Jackknife)。但是，真正包含样本采集、采样策略、算法类型、集群方法四个要素，而目前最具影响力的重采样方法的研究则是 Efron10在 1979 年提出“自助法”。高维海量不可控数据的涌现，对统计学是一个挑战，算法复杂性也已成为统计学家不得不面对的严肃问题。但是，通过“样本采集”获得的样本集，并应用统计方法获得的结论，对自然模型的真实性拟合仍然是统计学的本质。目前
14、，高维海量不可控数据的涌现对统计学提出了挑战性的问题，为了解释这些问题，我们需要了解统计学对数据统计分析的发展历程。2. 高维数据的两个基本问题统计学始于被观测的数据，Wegman 11把统计描述为一种将原数据转化为信息的方法，以区别于传统统计学的描述-传统统计学是关于收集和分析带随机性误差的数据的科学和艺术 12。从统计学的发展可以看出数据的采集方式经历了大样本到小样本，再到大样本的过程。在 1908 年以前统计学的主要用武计算机学报2009 年第 5 期4之地是社会统计(尤其是人口统计)问题，后来加入生物学统计问题。这些问题涉及到的数据一般都是大量的，自然采集的。而所采用的方法，以拉普拉斯
15、中心极限定理为依据，总是归结到正态。到 20 世纪，受人工控制的试验条件下所得数据的统计分析，日渐引人注意。由于试验数据量一般不大，直接导致了依赖于近似正态分布的传统方法的失效，在这种小样本的研究方向上，Gosset 和Fisher 发展了确定正态样本统计量的精确分布的理论 13。无论大样本理论还是小样本理论，它们的共同特点是数据维数一般不大，最多几维，即，自然模型涉及的变量数量很少。然而，现在我们面临自然涌现的数据除了观测的数据数量剧增之外，最大的不同是，数据维数少则几十维，多则上万维。如果再考虑数据性质的复杂性和数据表述的多样性，这不仅对计算机科学是一个挑战性的问题，对统计学同样是一个挑战
16、性的问题。例如，银行的巨额交易数据，电话呼叫记录，文本数据等，数据量达到 GB 甚至 TB 级。适合分析和处理在精心设计实验获得独立同分布、同方差和低维数据的传统统计学理论已不能适应，需要新的思考 14。在统计建模中高维数据会遇到两个困难：其一，Bellman 的维数灾难 (Curse of Dimensionality)现象 15。维数灾难现象表明，在给定模型精度下估计模型，需要的样本数量将随着维数的增加指数增长(图1)。而与此相关的问题是空空间现象(Empty Space Phenomenon )16，即高维空间的本质上是稀疏空间。一个典型的例子是高斯分布中的3 准则：当样本集在二图1: 高维空间的维数灾难(引自17)至三维空间时，采用高斯函数，可以证明，90%以上的样本集分布在3 范围以内。然而，当维数显著增加时，样本集的分布更多的集中在高斯函数的边界(3计算机学报2009 年第 5 期5以外
