Some theoretical notes on boosting By ingott@smth

目录 集成学习简介 弱可学习定理、AdaBoost及其泛化界 泛函梯度下降法

集成学习：动机 在机器学习中，直接建立一个高性能的分类器是很困难的。 但是，如果能找到一系列性能较差的分类器，并把它们集成起来的话，也许就能得到更好的分类器。 日常生活中，所谓的民主决策，便是部分的利用了这种想法。 譬如选总统，每个人都以自己的考虑，投下自己的一票，但最后由多数人选出的总统，似乎应该好于由一个人指定的总统。

集成学习：动机 集成学习，就是一种把输入送入多个学习器，再通过某种办法把学习的结果集成起来的办法。 这每一个学习器，也就相应的被称为“弱学习器”。 集成学习最早也叫做“Committee Voting Method”，也就是因为它和投票的过程相似。 这里区分学习器和分类器的区别。学习器泛指任意的学习问题，分类器指分类问题（一般限制在两类）

集成学习：图示 Classifier ensemble Σαihi(x) hn(x) h2(x) h1(x) Input vector …… Classifier N Combine Classifiers Output x

集成学习：如何构造？ 我们一般选定加权平均的方法来构造集成学习的最终学习器。 但是里面的每一个Classifier i怎样做呢？ 有一些研究，是针对每个学习器都不同构的情况，比如识别一个人，一个学习器考虑脸，另一个考虑步态，另一个考虑指纹。这种研究通常称为Information Fusion，不在我们今天讨论的范畴。 我们今天讨论的，是用同样的学习算法来构造不同的弱学习器的方法。

集成学习：如何构造？ 办法就是改变训练集。 通常的学习算法，根据训练集的不同，会给出不同的学习器。这时就可以通过改变训练集来构造不同的学习器。然后再把它们集成起来。

随机采样 在原来的训练集上随机采样，可以得到新的训练集。

带权的采样 采样时，我们可以给训练集里的每个元素不同的权。 权值可以通过上一次训练的结果来确定。

带权的采样：讨论 通过给训练数据赋以不同的权，实际上使得每个学习器关注训练集中的某一部分，这也符合我们最初民主投票的想法。 直观上，每个学习器关注训练集中的某一部分，很多个训练集应该可以覆盖训练集中的大部分，只要巧妙的选择加权平均的权，就可以得到更好的学习效果。

用多个学习器覆盖样本空间 如果来来去去都是覆盖同一块，就没有意思了。

集成学习：评述 集成学习实际上代表了一种与传统不同的思维理念。 传统的机器学习一般都自认为是单模型的，对于模型的分析总是在整体上完成。 Rosenblatt：Perceptron Rumelhart: BP Vapnik: SVM 但是，所有这些模型其实都可以看作是一种加权平均的多模型。

集成学习：评述 所以，当然应该考虑研究一般的多模型。 实际上，从90年代开始，对集成学习的研究取得了一系列突破进展。 在算法上，集成学习的典型代表AdaBoost算法，已经成为与SVM并立的方法。而且，集成学习比SVM更为一般，可能可以有更广阔的前景。 Return to TOC

弱可学习定理 简单的讲，弱可学习定理就是说：如果一个弱学习器能保证分类错误率小于50%，那么就可以由此构造一个强学习器，让分类错误率达到任意小。 弱可学习定理是集成学习的基本定理。由此引发了一系列集成学习的研究。 为了研究弱可学习定理，我们要先回顾一下PAC学习的概念。

简化的PAC学习 令Xn为n维样本空间。 D为样本v在空间Xn上的分布。 c(v): Xn->{-1,1}为未知的两类分类函数。 H为定义在样本空间上的一个分类器集合。 学习的目标是，在H中寻找一个分类器h(v)，使得它能够逼近未知的分类函数c(v)。 学习算法拥有一个抽取器，可以从分布D中任意抽取独立同分布样本。 逼近的错误率定义为 抽取器的地方可以有很多讨论

PAC可学习 对于一个概念c，如果存在一个算法，对于任何 ，能够给出一个分类器h(x)，使得h的错误率小于ε的概率： 并且算法在n, ε和δ的多项式时间内完成，则称c是PAC可学习的（或强可学习的）。 弱可学习的概念与此几乎完全相同，只是把ε的取值范围改成了 ，其中的γ可以看成是一个很小的正数。 这个时间复杂度和抽取有很大关系。 由于时间关系，这里我们省略了PAC学习中的一个重要参数，实际上，算法应该同时在s的多项式时间内完成，这里的s是概念c的最小描述长度，同样，弱学习里面的γ=1/p(n,s)，p(n,s)是一个关于n和s的多项式。

PAC学习的背景 PAC学习是除了Vapnik的统计学习理论以外，用概率方法来研究学习问题的另一个尝试。 它与Vapnik不同的地方就是不强调固定的样本集(训练集)，PAC采用的是一种在线的模型，可以任意的得到新的样本。 但是它使用另外一种方法来控制学习算法：时间复杂性。 控制了时间复杂性，也就控制了抽样本的次数。

PAC学习的基本方法 Chebyshev不等式： 设随机变量X具有数学期望E(X)=μ，方差D(X)=σ2，则对于任意正数ε，有

弱可学习定理 定理（弱可学习）：如果一个概念是弱可学习的，则其是强可学习的。 这当然是一个不平凡的定理，然而如果不看它的证明，是很难理解这个定理的真正涵义的。这里我们证其中的一个引理，并简要的概述其它部分的证明思路。

证明思路 弱学习的定义是在任意分布上都可以达到一定的错误率（小于1/2），如何利用这一条件？ 假设我们首先学得了一个分类器h1(v)，那么我们应该试图构造一个分布，使得h1(v)在这个分布上的错误尽量的多。 在这个新的分布上再学习一个分类器h2(v)，直观的考虑，h2(v)与h1(v)就覆盖了整个样本空间中不同的部分。

证明思路 但是这样并不能说明h2和h1哪个好，所以再定义一个分类器h3，它定义在分布D3上。D3定义在h1和h2产生矛盾的那些样本上，即在集合 上。 最后的分类器h由h1，h2和h3投票决定。如果h1，h2，h3中有两个认为应该把样本v分为某一类，就把v分为某一类。

证明思路 如果能证明h的错误率严格小于h1, h2和h3的错误率，就可以递归的使用这一步骤，得到任意小的错误率。 Weak1 Weak2

引理1 引理1：对于任何0<ε<1/2，可以用上述方式构造一个错误率不大于ε的分类器。 引理1和整个定理的差别只在两点： 依概率1- δ成立 计算复杂性

学习算法 Learn(ε, EX) if( ) return WeakLearn(EX) α = g-1(ε) h1 = Learn(α, EX1=EX) h2 = Learn(α, EX2) h3 = Learn(α, EX3) return h = sign(h1+h2+h3) g(x) = 3x2 – 2x3

学习算法 Learn(ε, EX) if( ) return WeakLearn(EX) α = g-1(ε) h1 = Learn(α, EX1) h2 = Learn(α, EX2) h3 = Learn(α, EX3) return h = sign(h1+h2+h3) flip coin if heads return the first instance v from EX where h1(v)=c(v) else return the first instance v from EX where h1(v) != c(v)

学习算法 Learn(ε, EX) if( ) return WeakLearn(EX) α = g-1(ε) h1 = Learn(α, EX1) h2 = Learn(α, EX2) h3 = Learn(α, EX3) return h = sign(h1+h2+h3) return the first instance v from EX where h1(v) != h2(v)

引理2 引理2：假设h1, h2, h3在任意分布上的错误率小于等于α，则h=sign(h1+h2+h3)在任意分布上的错误率小于等于g(α)=3α2-2α3。证明

收敛速度

采样的个数 在PAC学习里，采样也需要花费单位时间。因此无限制的采样是不能满足PAC的时间复杂度要求的。 在EXi里采样的期望个数可以通过hi的错误率计算出来。 如EX2中，如果目标是取得EX1分错的第一个样本，则不妨假设它服从一个几何分布。这样，得到一个样本需要的期望时间就是1/a1次。 几何分布 P(x=k) = p*(1-p)^k 我们不特别仔细的描述时间复杂度的问题，因为它主要和PAC学习有关，而跟boosting却关系不大。

寻找弱学习器 在有限样本的情况下，我们没有任意从分布里面抽取样本的能力，所以集成学习基本定理仍然只是一个存在性的定理。 但是，它仍然指出了集成学习方法的前景。

基本的Boosting 如果仍然按照我们刚才描述的那种构造算法（或与其等价的其它构造算法），就得到一类boosting算法，它的性质就变成了在训练集上可以以任意精度学习。 那么，它在独立于训练集的测试集上会有什么表现呢？或者说，它的泛化性能如何？在讨论之前，我们首先看一个实用的Boosting算法，AdaBoost。

AdaBoost Freund和Schapire在1996年根据boosting的基本思想，提出了最重要的实用boosting算法—AdaBoost。 AdaBoost通过在训练集上带权的采样来训练不同的弱分类器。 由于AdaBoost速度快，性能出众，又有boosting理论的坚实基础，它成为90年代与SVM齐名的两大算法之一。

AdaBoost算法 AdaBoost算法由如下的步骤组成： 每执行一次迭代称为一代，整个算法唯一的一个参数就是执行的代数T。 训练弱分类器 根据训练结果更新权值 每执行一次迭代称为一代，整个算法唯一的一个参数就是执行的代数T。 AdaBoost是一个PAC-boosting算法，也就是说它可以把弱分类器的组合变成强分类器。

AdaBoost的VC维 对于AdaBoost有以下结果： 设弱分类器的VC维为d，则AdaBoost的VC维不超过 根据这个结果，可以用Vapnik的VC维理论写出AdaBoost的泛化界。

边缘界 同样，对于AdaBoost，也有相应的边缘界，但是这个界很松，基本没有什么实用价值。

泛化界的缺陷 AdaBoost的VC维界已经证明是与实验相悖的，在实验中，弱分类器的个数并不是越少越好，特别的，在训练集上的错误率已经为0时，增加弱分类器仍然可以导致测试错误率进一步的下降。 边缘界是一个很松的界，并不能用来估计测试错误率，而且用于boosting之后，边缘界已不具有指导算法设计的意义。 新的有限样本的泛化标准仍是待研究的课题。 Return to TOC

更一般的集成学习 重新描述一下弱可学习定理： 如果能够找到一个函数空间，这个函数空间Ω里有一个函数可以弱分类某个问题，那么在Ω的凸包(由Ω中有限个函数的加权平均组成的集合) C(Ω)中，就存在一个函数，这个函数能以任意精度分类这个问题。 我们彻底抛弃其中的构造方法，而只强调存在性。

构造弱学习器 我们讨论一种通用的构造弱学习器的方法。 通常情况下，机器学习的问题都被归结到求某一个优化问题的解。 在最优解的解析形式未知的时候，通常通过梯度下降的方法来求解。

梯度下降 梯度下降的一般方式就是在参数上定义一个损失（能量）函数，然后根据损失函数的梯度 迭代的调整参数的值。

梯度下降 如Perceptron的经典例子： 迭代公式为 把梯度下降写成非迭代的形式： 正好是一些权值的线性组合。

泛函梯度下降 假如引入弱学习器，怎么定义梯度下降呢？ 可以定义一些类似这样的损失（能量）函数： 与传统的定义在权值上的损失函数不同，这些函数是定义在弱学习器上的。 梯度就是 ，由于F是函数，E(y,F)就是定义在F所在空间上的泛函，所以叫做“泛函梯度下降”。

泛函梯度下降 还有最后一个困难，如何更新权值？ 比照经典的 我们试图写出泛函梯度下降的更新公式： 如何得到？ 可以使用一个函数来逼近

算法：泛函梯度下降法 1. 2. for m = 1 to M do: x为训练集输入，y为输出 样本个数 此处的WeakLearn 变成了一个回归

讨论：泛函梯度下降法 包括AdaBoost在内的很多Boosting算法都可以归结为类似于泛函梯度下降法。 梯度下降是优化理论中熟悉的方法，关于它的收敛性、收敛速度、过学习之类的问题都有很多讨论，把boosting类算法放入泛函梯度下降法的框架，可以解释boosting的许多性质。 也可以利用以往梯度下降中常用的技术，定义泛函梯度下降法中的牛顿法，权值衰减等。

损失函数 通过使用不同的损失函数，可以得到不同的梯度下降算法，适用于不同的问题。 Adaboost就是Exponential loss

总结 弱可学习定理说明如何选择函数集，使其中包含最优分类器。 由于对函数集的要求不高，寻找这种函数集并不困难。针对不同的问题，怎样选择不同的弱学习器？这本身就是一个有趣的问题。 采用泛函梯度下降法，可以寻找最优分类器的组成部分。 这个整体框架中，每一部分都有很多扩展的空间和值得研究的问题。

弱学习器 boosting里面最常用的两种树学习器，8-节点树和树桩，是很有趣的学习器。

特征选择和提取 通过这些弱学习器，boosting或泛函梯度下降法可以实现特征选择（树桩）或特征提取（多节点树）的功能。 通过如此简单的弱学习器的线性组合，可以实现和其它复杂而且难以解释的学习器（如SVM等）同样甚至更好的效果。这可以提示我们，现实中的问题可能并没有那么复杂。

参考文献 Schapire. The strategy of weak learnability, Machine Learning 5(2), 1990. Freund, Schapire. A decision-theoretic generalization of online learning and anapplication to boosting Journal of Computer and System Sciences, 55, 1997 (ACM SIGACT Godel Prize paper). Schapire, Freund, Bartlett, Lee. Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods, Annals of Statistics, 26(5), 1651-1686, 1998 Friedman. Greedy function approximation: a gradient boosting machine, Annals of Statistics, 29, 1189-1232, 2001 其它参考文献： Schapire. The Boosting Approach to Machine Learning: An Overview. MSRI Workshop on Nonlinear Estimation and Classification, 2002 Friedman, Hastie, Tibshirani. Additive logistic regression: A statistical view of boosting. Annals of Statistics, 28, 337-407, 2000

备注：引理2的证明 图是引理2那张图

引理2的证明（2） 显然有 我们分别考虑三个抽取器得到的分布： EX1对应的就是原来的分布D: 对于一个样本v来考虑，如何才能让它成为第一个分错的样本呢？

引理2的证明（3） 需要在D中抽出的前面的样本都分对，并且抽出v的时候分错。 这样的概率可以写成

引理2的证明（4） 在整个论域上考虑这个式子： 这实际上就说明了在D1和D2上，h1和h2的分类错误是成比例的。

引理2的证明（5） 把这个式子和前面的两个简单的结论联立起来： 可以把w和z用y，a1和a2表示出来：

引理2的证明（6） 这个时候再看D3的式子（做法同D2）： 最后我们看加权平均后h的错误率：

引理2的证明（7） （接上） 引理得证。