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 那样受到计算机学界的关注。在算法类型和集群方法两个方面，Baggin
12、g 与 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 准则：当样本集在二图
17、1: 高维空间的维数灾难(引自17)至三维空间时，采用高斯函数，可以证明，90%以上的样本集分布在3 范围以内。然而，当维数显著增加时，样本集的分布更多的集中在高斯函数的边界(3计算机学报2009 年第 5 期5以外)而不是中间。这表明在高维样本集中，数据可能大多数分布在超球的外壳，而不是在球的中心。由此产生的困难是，在多元数据分析中缺乏一般性的方法来直接分析高维空间的密度估计和几何性质，因为相对低密度的区域包含了样本集的大部分，反而高密度区域可能完全没有数据存在 18。其二，不适定问题。我们对自然模型，几乎一无所知，如果使用传统统计学的理论、方法和理念，估计概率密度函数，这一定是一个不适定问
18、题 19。20世纪初 Hadamard 在某些情况下求解线性算子方程 的问题(寻找满,AfF足这一等式的函数 )是不适定的。即使方程存在唯一解，如果方程右边有一个f微小变动( 如用 取代 ，其中 任意小)，也会导致解有很大的变化FF(即可能导致 很大)。20 世纪后半叶，人们发现根据数据估计密度函数这f个统计学中的主要问题是不适定的：使泛函 最小化的函数 并2(FAfRf不能保证在 时是方程真实解的一个好的近似。0高维空间的数据在拟合模型时的稀疏性，使得所获得的样本集不足以表现自然模型；传统统计学的不适定问题使得我们无法在高维复杂数据的情形下精确估计自然模型。这两个有关高维的、复杂的、自然涌现
19、数据的问题，是重采样方法出现与成长的温床。特别是，当前一些重要的领域，例如，银行交易数据、文本数据、Web 数据都是自然涌现的，不但数据量庞大，而且维数很高，并且可能不能简单以一个固定的样本空间进行描述，即，数据不能使用相同维数的向量表述。而重采样方法恰恰为处理这类数据提供了工具，并在理论上给出了统计解释。3. 重采样方法的思想来源重采样方法的思想来源大致有两个方面：其一，试验设计，其二，抽样调查。其出现的本原是为了更准确地获得“有代表性的样本” 1。由于当前海量涌现的高维数据具有天生的稀疏性，因此，“获得有代表性样本”对需要满足同分布条件的各种机器学习研究具有重要的现实意义。重采样方法最早可
20、以追溯到上个世纪 30 年代 Fisher(1935)提出的配对随机化检验(Randomization Test)和 Pitman(1937)提出的两个独立样本 2的随机化检验20。对两样本情形，试验者从可能不同的自然模型中得到两个样本，希望用统计假设检验来判断两个自然模型是否相同，以决定“两个自然模型相同”这个零假设是否被拒绝 3。一个直观的方法是将两个样本组合成一个有序的样本，不1 其本质就是同分布条件。2 这里的“样本”就是“样本集”，在统计学中，由于一般不考虑单独样本的问题，因此，在计算机科学中使用的“样本集”，在统计学中就称为样本。由于本文涉及统计学的内容，对它的概念和事实，使用“样
21、本集”很别扭且可笑，因此，在不致引起混乱时，我们有可能不加指出地使用“样本”一词，但是，其含义就是计算机科学中的“样本集”。3 零假设：关于自然模型未知分布的信息所做的统计假设。根据零假设可以构造出一个性质优美的统计量，计算机学报2009 年第 5 期6管每个值是来自哪个自然模型，从小到大给样本赋“秩”，而检验统计量就可能是来自其中一个自然模型观测值的“秩和”。如果这个秩和太小(或者太大)，就意味着来自这个自然模型的值趋向于比来自另一自然模型的值小(或者大，视具体情况而定)。由此可知，如果与一个样本相关的秩趋向于比另一个样本相关的秩大，则“两个自然模型相同”这个零假设可能被拒绝。Fisher(
22、1935)用数据本身作为秩来解决配对数据是否来自同一自然模型，描述如下：两个独立的随机样本集 分别来自两个自然模型 ,yz GF,),(1mnyGzF希望根据样本检验“两个自然模型相同”这个零假设， ，如果H:0为真，两样本来自同一自然模型。检验统计量是观测值之和： ，将0H 1niTz混合成一个样本集，从中抽取出 个样本，在 假设条件下，每一种 个,yz n0样本的组合方式都是等概率的，考虑所有组合的可能性，可得零分布 4。之后采用标准的假设检验原理构造概率 值，做出接受或者拒绝的结论。p在随机化检验中采用数据组合的方式构造假设检验的过程，体现出了早期的重采样思想，当两个样本集融合在一起时，
23、除非来自不同自然模型，否则重新采样后的统计指标和原样本统计指标应没有差别。此方法先于计算机发展，所以一般限制在小样本数据上，在样本容量较大的情形下，需要的计算工作量很大，在当时，其应用必然受到限制。几乎是同一时期，抽样调查方面也开始冒出了重采样的萌芽，这种早期的重采样思想是从有限自然模型中无重复采样。在 Pearson 的统计框架中，针对一个自然模型，其对应着一个庞大的却有限的样本的集合。在理想情况下，科学家会搜集所有的这些样本，并确定其分布参数。如果无法搜集到全部样本，那么就搜集一个很大的并且具有代表性的数据子集。通过大量的且具有代表性的子集计算模型的参数，如果数据具有足够的代表性，被计算出
24、的参数将与自然模型的参数相同。然而 Pearson 学派的方法存在一个根本性的缺陷，如果所获得的数据被称为“ 便利样本 ”(opportunity sample)，即，属于那些最容易得到的数据，这些数据并不能真正代表自然模型。 20 世纪 30 年代的早期，印度发现了一个便利抽样的典型案例，为了估计孟买码头上大批黄麻的价值，需要从每包中抽取一些样品，黄麻的质量由这些样品来确定。抽样是将一把中空的圆形刀片插入包中，再拔出来，刀片中央的通过这个统计量来做统计推断。4 承认零假设成立的基础上，构造一个统计量，这个统计量的分布即为零分布。计算机学报2009 年第 5 期7空处带出了少量的黄麻，但是由于
25、天气和包装运输的原因，外层黄麻会变质，而由于在中间的黄麻被压紧，并结成一块，导致空心刀片难以插入，这样，所取的样本多是外层已经变质的黄麻，这种“便利样本”就会产生偏差，由此，导致评价整包黄麻质量偏低，实际上整包黄麻的质量要高得多 21。这个例子说明，收集具有代表性样本对估计模型准确性的的重要性。为了收集能够准确估计自然模型的具有代表性的子样本，当时出现了“判断样本”(Judgment Sample)的方法 21。这个方法是将自然模型划分为几个子模型，每个子模型上都由某些样本来“代表”，这些“代表”的样本组成的集合作为判断样本。但是只有对自然模型有充分了解之后，才能将自然模型划分为一些能用个体样
26、本来代表的子模型，这样判断样本才具有代表性，如果我们对自然模型已经了解的那么清楚，就无需进行抽样 21。Mahalanobis21建议采用随机样本（Random Sample）来推断有限自然模型。这种采样得到的样本优于便利样本和判断样本。最初 Mahalanobis(1946)在研究作物产量上使用交叉抽样方法(Half Sample)，之后 McCarthy(1966)将其扩展到抽样调查领域。在抽样调查领域，仅从自然模型随机抽取，得到所有可能样本中的一次采样，并依此来推断自然模型，其推断结果是否准确可靠，无法衡量，通过重复采样法进行抽样得到 个子样本集，由于各个子样本集都独立且采样K方式相同，
27、若各子样本集的估计结果一致或者比较接近时，推断结果的真实性比较容易让人信服。此时的采样方法是基于从自然模型上重复采样的原则。1969 年 Hartigan 提出了 Random Sub-sampling 方法，并首次将此方法用在统计量估计中 22。传统统计学需要研究的问题是：如何利用样本 中的信息，,1nX对自然模型分布做出判断。将样本中的信息加工处理，用样本上的函数来构造统计量 (如样本均值，样本方差，回归曲面，分类函数等 )，用统计量)XT来体现自然模型的信息。统计量只依赖于样本，而与参数无关。无偏性是衡量统计量的一个基本准则，其实际意义是无系统误差，即统计量的数学期望等于自然模型的参数
28、( )。对实际问题，无偏估计一般是ET不可能的，我们只是希望能够找到偏差较小的统计量，或者采用某种方法降低统计量的偏差。重采样方法刀切法 9,20 就是其中一种。4. 刀切法1949 年，Quenouille 提出了刀切法，这是近代重采样方法的标志，以后，由 Quenouille(1949，1956) 和 Tukey(1958)不断完善，重采样方法成为统计学的重要方法之一。计算机学报2009 年第 5 期8刀切法的原始动机是降低估计的偏差。常用做法是：每次从样本集中删除一个或者几个样本，剩余的样本成为“刀切” 样本，由一系列这样的刀切样本计算统计量的估计值。从这一批估计值，不但可以得到算法的稳
29、定性衡量(方差)，还可以减少算法的偏差。这个方法暗示，刀切法的样本集需要事先给定，即，它的重采样过程是在给定样本集上的采样过程。最简单的一阶刀切法描述如下 9：假设独立同分布的样本 来自一个未知概率模型 ，1,nX F是未知参数， 是估计统计量，则 的刀切法估计为：)(F()Tniin1)(其中 是刀切样本集 上的统计量，()iiTX()iX，是把原样本集中第 个样本剔除后剩余的 个()11,i in i 1n样本组成的集合。刀切法的最重要的性质是：刀切估计可以将偏差从 减少到 ，(1/)O2(/)并可以修正估计为无偏估计，但是并不能保证减少方差。这个性质描述如下 23：设 为独立同分布样本集
30、， ，其中 为未知参1,nX ),(xFXi 数，统计量 为 的估计，若其偏差为：()T1)()()(knobTEBias则 的刀切法估计的偏差为 2noiJ虽然刀切法可以降低估计偏差，但当参数不光滑(Smooth) 时，刀切法会失效。此处光滑是指样本集上的微小变化，只会引起统计量的微小变化。最简单的不光滑的统计量是中位数(Median) ，中位数是刻画随机变量分布 “中心”的统计量。满足 且 的实数 称为中位数，()1/2PXm()1/2PXm()mX在样本集上，样本中位数定义为 。通俗地说，将一/1)n维样本排序，处在最中间位置的那个数据(或最中间两个数据的平均数)即为这组数据的中位数。E
31、fron 指出 24刀切法在估计中位数时会失效，而自助法可以有效地给出中位数的估计。用老鼠数据 24的例子来说明，9 个排好序的样本分别为:10，27，31，40，46，50，52，104，146计算机学报2009 年第 5 期9这个样本集的中位数是 46(样本个数是奇数，中位数为最中间位置的样本)。如果改变第四个样本 ，当 增加至并且超过 46，中位数才会改变，之前40xx中位数不改变。当样本从 46 继续增加直至 50，中位数和此样本值相同，超过50 之后，中位数变为 50。使用一阶刀切法估计中位数，先去掉第一个样本，剩余 8 个样本的中位数是 48（46 与 50 的算术平均值），依次去
32、掉相10x应的第 个样本，得到如下中位数估计结果：i48，48，48，48，45，43，43，43，43刀切法只得到 3 个不同的中位数估计，方差较大。而自助法的采样方法使得样本集变化较大，会得到比较敏感的中位数变化。并且，在大样本性质上，中位数的刀切法估计的标准差是不相合的(不能收敛到真实的标准差)。而自助估计是相合的。5. 自助世界1979 年 Standford 大学统计系的 Bradley Efron 在统计学刊物The Annals of Statistics上发表了开创性论文-“自助法: 从另一个角度看刀切法(Bootstrap Methods：Another Look at th
33、e Jackknife)”10。发表过程具有戏剧性，最初，杂志编辑毫不客气地拒绝了这篇文章，理由是“太简单 ”，目前，这个方法的影响可从有影响的重要杂志发表有关文章上得到证实：从 1982 年开始几乎在每个数理统计期刊上都刊登一篇或者多篇与自助法相关的文章。并且关于自助法主题的论文也不断出现在计算机学科的杂志上。Efron1979 年这篇文章指出了自助法与刀切法的关系。首先，自助法通过经验分布函数构建了自助法世界，将不适定的估计概率分布的问题转化为从给定样本集中重采样。第二，自助法可以解决不光滑参数的问题。遇到不光滑(Smooth)参数估计时，刀切法会失效，而自助法可以有效地给出中位数的估计。
34、第三，将自助法估计用泰勒公式展开，可以得到刀切法是自助法方法的一阶近似。第四，对于线性统计量的估计方差这个问题，刀切法或者自助法会得到同样的结果。但在非线性统计量的方差估计问题上，刀切法严重依赖于统计量线性的拟合程度，所以远不如自助法有效。Efron 的这篇文章是对刀切法的一种新的统计学解释。Efron 将刀切法纳入了自助法的体系中，并构建了从真实世界(自然模型)到自助世界的采样过程。这里，自助世界是基于经验分布函数从给定样本集重采样获得。样本集 来自一个未知概率模型 ， 是我们关注的1,nX F()未知参数， 是估计参数的统计量，它们可以通过传统统计方法(极大似)T然，MAP 等 )获得，定
35、义 。然而我们不仅关注估计值本身，,)()RFTX同时也关注统计量的准确程度，是无偏估计吗？距离真实值的偏差是多少？稳计算机学报2009 年第 5 期10定吗？方差是多少？但是这样的问题往往无法回答，因为我们不了解自然模型本身，我们面对的只有从自然模型中的采样结果-样本集。我们可以在给定样本 的条件下，构造 的估计 ，然后从分布 中重新XFnnF生成一批随机样本 。如果 是 的一个足够好的估计，那么*1(,)m n与 的关系会从 和 的关系中体现出来(图 2)。XFnF自助法定义如下 10: 样本集 来自一个未知概率模型 ，关注统,1nX计量 ，定义 : (其中 为示性函数)是样);,(1Tn
36、 niixIx)IA本集 上的经验分布函数(Empirical Distribution Function)，其中每个样本的概率均为 。从 上 次随机采样得到自助样本集为 ，目的nFm,*1mX是用自助样本集上的统计量 的分布去逼近原样本集上统计量);,(*1nmFXT的分布。其中 表示自助样本集中样本的个数， 表示原始样本);,(1XTn n集中样本的个数。产生过程如下： );,(,11 FXTFnnid *11inXnn图 2: 自助采样示意图(引自24)从自然模型采样得到样本集，基于此样本集进行学习。如果样本集是对自然模型的独立同分布的采样，那么，在统计上，这样的样本集对自然模型是理想的，它可以很好的拟合自然模型。传统统计学的样本是定义在事先给定的空间上，即，空间维数确定，通常可以理解为欧式空间中的点。对自然模型进行估计，并基于这个估计使用自助法得到自助样本集，可以不受样本空间维数固定的制约，并且可以追加新样本。学习的模型在统计意义下可对自然模型可以解释。重采样的次数是有限的，需要我们设计采样方法使得重采样样本构建的
