Some theoretical notes on boosting

Presentation on theme: "Some theoretical notes on boosting"— Presentation transcript:

1 Some theoretical notes on boosting
By

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24 学习算法 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

25 学习算法 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)

26 学习算法 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)

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

28 收敛速度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49 参考文献 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), , 1998 Friedman. Greedy function approximation: a gradient boosting machine, Annals of Statistics, 29, , 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, , 2000

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

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

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

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

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

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

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