您的位置: 首页  >  文章  >  Boosting

Boosting

分类: 文章 • 2024-06-23 13:31:52

一、起源

Boosting是一种提高任意给定学习算法准确度的方法。

Boosting的提出与发展离不开Valiant和 Kearns两位大牛的不懈努力，下面是他们的“奋斗史”：

Boosting的思想起源于 Valiant提出的 PAC ( Probably Approximately Correct)学习模型。Valiant和 Kearns提出了弱学习和强学习的概念：
弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
强学习：识别准确率很高并能在多项式时间内完成的学习算法

同时 ,Valiant和 Kearns首次提出了 PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。1990年, Schapire最先构造出一种多项式级的算法 ,对该问题做了肯定的证明 ,这就是最初的 Boosting算法。一年后 ,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷 ,那就是都要求事先知道弱学习算法学习正确的下限。1995年 , Freund和 Schapire改进了Boosting算法 ,提出了 AdaBoost 算法该算法效率和 Freund于 1991年提出的 Boosting算法几乎相同 ,但不需要任何关于弱学习器的先验知识 ,因而更容易应用到实际问题当中。之后， Freund和 Schapire进一步提出了改变 Boosting投票权重的 AdaBoost .M1，AdaBoost . M2等算法 ,在机器学习领域受到了极大的关注。

参考：
百度百科-Boosting

二、发展

Boosting算法是一种把若干个分类器整合为一个分类器的方法，也就是一种集成分类方法（Ensemble Method）。比较简单的集成分类方法在boosting之前出现过boostrapping和bagging方法，我们先简要介绍一下这两个方法。

Boostrapping

  1. 重复地从一个样本集合D中采n个样本
  2. 针对每次采样的子样本，进行统计学习，获得假设Hi
  3. 将若干个假设进行组合，形成最终的假设Hfinal
  4. 将最终的假设用于具体的分类任务

Bagging

  1. 从整体样本集合中抽样产生不同的训练集并训练弱分类器
  2. 用分类器对分类进行投票，最终的分类结果是弱分类器投票的优胜结果

但是，上述这两种方法，都只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。直到1989年，Freund与Schapire提出了一种可行的将弱分类器组合为强分类器的方法。并由此而获得了2003年的哥德尔奖（Godel price）。

Schapire还提出了一种早期的boosting算法，其主要过程如下：

  1. 从样本整体集合D中，不放回的随机抽样n1<n 个样本，得到集合 D1训练弱分类器C1
  2. 从样本整体集合D中，抽取 n2<n 个样本，其中合并进一半被 C1 分类错误的样本。得到样本集合 D2训练弱分类器C2
  3. 抽取D样本集合中，C1 和C2分类不一致样本，组成D3训练弱分类器C3
  4. 用三个分类器做投票，得到最后分类结果

参考：
浅谈AdaBoost算法

三、AdaBoost (Adaptive Boosting)算法

可以看出，早期的boosting算法已经在尝试通过突出错分样本的方法，提高分类器准确度。但是通过重复抽样的方法略显粗糙，且存在较大的随机性和不稳定性，为此提出了AdaBoost算法。
AdaBoost通过改变样本的分布突出错分类，并进而训练弱分类器得到弱分类器的权重，最终根据权重整合在一起得到最终的强分类器。
AdaBoost方法大致有：Discrete Adaboost， Real AdaBoost，LogitBoost和Gentle AdaBoost。所有的方法训练的框架的都是相似的。

Discrete Adaboost
通常使用最多的应该是Discrete AdaBoost（离散的AdaBoost）即AdaBoost.M1算法，主要因为它的简单却不俗的表现。原文中的伪代码如下：

Boosting

输入:样本容量为m的训练集、弱学习算法WeakLearn以及循环次数T
初始化：每个样本相同的权重1/m
循环T次：

  1. 使用加权的样本训练弱学习算法
  2. 得到弱分类器ht:x→y
  3. 计算分类错误样本的权重之和et（为了方便称其为错误率），如果et>1/2，证明分类器效果不好，跳出循环（弱学习算法以minimize et为目标）
  4. 计算βt，显然0<βt<1
  5. 将正确分类的样本的权重缩小，并将修改后的权重再次归一化（这样错误分类样本的权重就会增大）

输出：最终的分类器根据各个弱分类器的加权投票决定分类结果，投票的权重为log(1βt)
显然错误率越高的分类器，βt越大,投票权重越低。

疑问：
Q1:βt作为投票权重很合理，但是作为正确分类的样本的权重缩小系数是否合理？
由于βt的取值范围摆在那里，不管具体取值多少，用于扩大错分样本权重的正向目的都是可以达到的。但是扣的细致一点，错误率et越大,βt越大那么错分样本权重的扩大程度反而越小，这是正确的吗？
A1:目前我还没有看到相关的说明，其实从我的直观角度来看这个值未必最为合适，因为这未必是迭代最快的方式，但是最终强分类器的效果怕是没有太大影响，最多是对运行时间有所影响。

Q2:只要AdaBoost.M1中弱分类器的错误率et略低于1/2，就能保证最终分类器的准确率很高吗？
A2: AdaBoost.M1的陈述基于以下理论：
Theorem1
AdaBoost.M1中的T个弱分类器产生T个错误率e1,…,eT，假设每个et≤1/2 并且令γt=1/2−et，那么最终分类器的错误数目有如下上限：

1m|{i:hfin(xi)≠yi}|≤∏t=1T1−4γ2t−−−−−−√≤exp(−2∑t=1Tγ2t)

该理论表明，只要AdaBoost.M1中的弱分类器的错误率略低于1/2，那么最终分类器中的分类错误数就将以指数速度下降至0。

Real Adaboost
可以看出，Discrete AdaBoost的每一个弱分类器的输出结都是单个的类标，并没有属于某个类的概率，略显粗糙。
而且.M1算法要求错误率et≤1/2其实并不很好控制。我们知道随机猜测时的分类错误率为1−1/k，其中k为类别数。因此k=2即二分类问题时，我们仅需要弱分类器比随机猜测的结果略好即可。但是当k=2即面对多分类问题时，这个条件就显得有点苛刻了。
为了解决这两个问题，Freund和Schapire在AdaBoost.M1的基础上提出了泛化的AdaBoost.M2即Real Adaboost算法。
原文中的伪代码如下：

Boosting

输入:样本容量为m的训练集、弱学习算法WeakLearn以及循环次数T
为了体现各个分类的可能性，AdaBoost.M2不再对样本本身进行加权，而是对（i,y）,y≠yi这样一组错分类进行加权，令

B={(i,y):i∈{1,…,m},y≠yi}

初始化：各种错分组合赋相同权重1/|B|
循环T次：

  1. 使用错分组合加权训练弱学习算法
  2. 得到弱分类器ht:X×Y→[0,1]，这里分类器输出的是概率向量，向量的每一个位置代表对应类别的可信度
  3. 计算pseudo-loss.为了对应概率向量，算法提出了一种新的指标去评定弱分类器的错误程度。可见错分组合的权重越高，et越大（且一般认为e_t≤1/2）
  4. 计算βt
  5. 增大错分组的权重，且pseudo-loss越高错分权重增加越多。并将修改后的权重再次归一化。

输出：最终的分类器根据各个弱分类器的加权投票决定分类结果，投票的权重为log(1βt)

疑问：
Q:显然由于pseudo-loss的提出原本的Theorem1已经不成立，那么最终分类器的分类精度还能有所保证吗？
A: AdaBoost.M2的陈述基于如下理论：
Theorem2
AdaBoost.M2中的T个弱分类器产生T个pseudo-loss,e1…eT，假设每个et≤1/2 并且令γt=1/2−et，那么最终分类器的错误数目有如下上限：

1m|{i:hfin(xi)≠yi}|≤(k−1)∏t=1T1−4γ2t−−−−−−√≤(k−1)exp(−2∑t=1Tγ2t)

其中,k为类别数目
值得注意的pseudo−loss≤1/2对于输出单类标的学习算法而言是很容易达到的，进一步地说明无论是几分类问题，只要你的输出分类向量的弱学习算法的pseudo-loss略低于输出单类别的学习算法的pseudo-loss，最终算法的错误数就会以指数速度下降至0.

参考：
1.A decisiontheoretic generalization of online learning and an application to boosting
2.Experiments with a New Boosting Algorithm

相关推荐