AdaBoost（自适应提升）

是什么

AdaBoost 全称「自适应提升」（Adaptive Boosting），是一种统计分类的元算法（meta-algorithm）。它本身不是分类器，而是套在其他学习算法外面、用来提升这些算法表现的一套流程^[1]。它由 Yoav Freund 和 Robert Schapire 在 1995 年提出^[1]。最基本的用武之地是二分类，也就是在两个类别之间做判断；这一方法也可以推广到多类别，或推广到取值落在有界区间内的实数^[1]。

怎么工作

AdaBoost 在训练样本上维护一个概率分布（probability distribution）。这个分布一开始是均匀的，每个样本的权重相同，之后每训练一个新的弱分类器（weak classifier），分布就被修改一次^[2]。某个弱学习器（weak learner）训练完之后，被它分错的样本会获得更高的权重，于是后面的弱学习器会更偏向这些先前模型分错的样本，把注意力集中到更难的例子上^[1]。各个弱学习器也不是一人一票：它们的输出被合成一个加权和（weighted sum），这个加权和就是最终提升出来的分类器^[1]。

可以这样粗略地想象：第一个弱学习器可能只是一条很简单的规则，大部分训练样本判对，少数判错。这些判错的样本被调高权重，第二个学习器就被推向它们；前两个仍然判错的样本，再成为第三个学习器的重点，如此继续。单个规则不必有多好，真正承担性能的是它们的加权组合。

理论保证

这套方法自带理论。只要每个弱学习器的表现略好于随机猜测，组合出来的模型就能收敛到一个强学习器（strong learner）^[1]。AdaBoost 还带有一个理论保证：随着弱分类器不断加入，训练集上的误分类率（misclassification rate）可以任意小；与此同时，理论也给出了泛化误差（generalization error）的一个界^[2]。也就是说，分析同时覆盖了对训练数据的拟合和在未见数据上的误差这两件事。

由来

这一方法的主要参考文献是 Freund 和 Schapire 的原始论文《A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting》，发表在 1995 年第 2 届欧洲计算学习理论会议（European Conference on Computational Learning Theory）的论文集上^[2]。Freund 和 Schapire 因此项工作获得了 2003 年的哥德尔奖（Godel Prize）^[1]。

今天用在哪里

作为元算法，AdaBoost 可以搭配许多其他更简单的学习算法使用，而不绑定某一种特定模型^[1]。它真正广为人知，是在 Viola 和 Jones 证明可以用它做出假正率（false-positive rate）低至 10^-6 的人脸检测器之后^[2]。

局限

这些保证是有前提的。每个弱学习器都必须略好于随机猜测^[1]。训练误分类率上的保证本身并不说明模型在新数据上的表现，所以理论中要另外给出泛化误差的界^[2]。此外，基本形式面向二分类，多类别或实数输出需要相应的推广^[1]。