[转]Boosting

1 Boosting算法的起源

Boosting方法是一种用来提高弱分类算法准确度的方法,这种方法通过构造一个预测函数系列,然后以一定的方式将他们组合成一个预测函数。Boosting是一种提高任意给定学习算法准确度的方法。

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

PAC学习模型中弱学习算法和强学习算法的等价性问题：即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。

1990年, Schapire最先构造出一种多项式级的算法 ,对该问题做了肯定的证明 ,这就是最初的 Boosting算法。一年后 ,Freund提出了一种效率更高的Boosting算法。但是,这两种算法存在共同的实践上的缺陷 ,那就是都要求事先知道弱学习算法学习正确的下限。1995年 , Freund和 Schapire改进了Boosting算法 ,提出了 AdaBoost 算法该算法效率和 Freund于 1991年提出的 Boosting算法几乎相同 ,但不需要任何关于弱学习器的先验知识 ,因而更容易应用到实际问题当中。之后， Freund和 Schapire进一步提出了改变 Boosting投票权重的 AdaBoost .M1，AdaBoost . M2等算法 ,在机器学习领域受到了极大的关注。

转自：百度百科-Boosting

2 Boosting算法的发展

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

Boostrapping

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

Bagging

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

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

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

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

到了1995年，Freund and schapire提出了现在的adaboost算法，其主要框架可以描述为：

　　1. 循环迭代多次

　　    更新样本分布

　　    寻找当前分布下的最优弱分类器

　　    计算弱分类器误差率

　　2. 聚合多次训练的弱分类器

转自：Boosting

3 Adaboost算法 

AdaBoost 是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，即弱分类器，然后把这些弱分类器集合起来，构造一个更强的最终分类器。(很多博客里说的三个臭皮匠赛过诸葛亮)

算法本身是改变数据分布实现的，它根据每次训练集之中的每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融合起来，作为最后的决策分类器。

完整的adaboost算法如下

转自：  浅谈AdaBoost算法