算法描述
集成学习是涉及利用多个学习器来解决问题的方法。 集成的泛化能力通常明显优于单个学习器，因此集成方法非常有吸引力。 Yoav Freund和Robert Schapire提出的AdaBoost算法是最重要的集成方法之一，因为它具有坚实的理论基础，非常准确的预测能力，非常简单（Schapire说它”只需$10$行代码”）），并且有广泛而成功的应用。
设$X$表示实例空间，$Y$表示类标签集。假设$Y = {-1，+1}$。给定一个弱或基本的学习算法和一个训练集${(x_1，y_1),(x_2，y_2),…,(x_m，y_m)}$其中$x_i∈X$和$y_i∈Y(i = 1，…，m)$，AdaBoost算法如下工作。
首先，它为所有训练样例$(x_i，y_i)(i∈{1，…，m})$赋予相等的权重。将第$t$个学习轮的权重分布表示为$D_t$。从训练集和$D_t$中算法通过调用基础学习算法生成一个弱或基本的学习器$h_t：X→Y$。
然后，它使用训练样例来测试$h_t$，并且将增加错误分类的示例的权重。因此，获得一个更新的权重分布$D_{t+1}$。从训练集和$D_{t+1}$中AdaBoost再次通过调用基础学习算法生成另一个弱学习器。这样一个过程被重复$T$轮，并且通过$T$个弱学习器的加权多数表决来导出最终模型，其中学习器的权重在训练过程中被确定。实际上，基础学习算法可能是一个可以直接利用加权训练样例的学习算法;否则，可以通过根据权重分布$D_t$对训练样本进行采样来利用权重。 AdaBoost的伪代码如图$5$所示。
为了解决多分类问题，Freund和Schapire提出了AdaBoost。
M1算法要求即使在AdaBoost过程中生成的硬分布上弱学习器也足够强大。 另一个流行的AdaBoost多分类版本是AdaBoost。MH 通过将多分类任务分解为一系列二分类任务来工作。 AdaBoost算法用于处理回归问题也已被研究。 自从AdaBoost的许多变体在过去十年被开发以来，Boosting已经成为集成方法中最重要的“家族成员”。
算法的影响
正如在$7.1$节中所提到，AdaBoost是最重要的集成方法之一，所以在各个地方可以观察到它的高度影响并不奇怪。在这篇短文中我们只简要介绍两个问题，一个是理论问题，另一个是应用问题。
$1988$年，Kearns和Valiant*提出了一个有趣的问题，即，一个比随机猜测稍好一点的弱学习算法是否可以“提升”为任意精确的强学习算法。换句话说，是否对于两个复杂性分类而言，弱学习问题和强学习问题是等价的。 *Schapire 发现问题的答案是“肯定的”，他给出的证据是一个结构那也就是第一个Boosting算法。因此，显然AdaBoost诞生时具有理论意义。AdaBoost已经在集成方法的理论层面引出了大量研究，这些研究可以很容易在机器学习和统计文献中找到。值得一提的是，对于他们的AdaBoost论文，Schapire和Freund在$2003$年获得了Godel奖，这是理论计算机科学中最负盛名的奖项之一。
AdaBoost及其变体已经应用于各种领域并取得了巨大成功。 例如，Viola和Jones将AdaBoost与用于面部检测的级联过程相结合。他们认为矩形特征是弱学习器，并且通过使用AdaBoost对弱学习器进行加权，获得了非常直观的面部检测的特征。为了获得高精度和高效率，他们使用了级联过程（那超出了本文范畴）。结果，他们发明了一种非常强大的面部检测器：在$466MHz$的机器上，在一张$384×288$的图像上的面部检测仅耗时$0.067$秒，比当时最先进的面部检测器快$15$倍但有相似的准确率。这个面部检测器被认为是过去十年计算机视觉（特别是面部检测）中最令人兴奋的突破之一。”Boosting“已成为计算机视觉和许多其他应用领域的流行语并不奇怪。
更深一步的研究
许多有趣的主题值得更深一步的研究。这里我们只讨论一个理论主题和一个应用主题。
许多实证研究表明AdaBoost往往不会过拟合，即，即使在训练误差为零之后，AdaBoost的测试误差也往往会降低。许多研究人员对此进行了研究，并给出了几种理论解释。 Schapire等人提出了基于极限的解释。他们认为，即使在训练误差为零之后，*AdaBoost*也能够增加极限，因此即使在大量轮次之后它也不会过拟合。然而，Breiman 指出，更大的极限并不一定意味着更好的泛化能力，这严重挑战了基于极限的解释。最近，Reyzin和Schapire发现Breiman考虑的是最小极限而不是平均极限或中位数极限，这表明基于极限的解释仍有存在的意义。如果这个解释成立，就可以找到AdaBoost和SVM之间的强力联系。很明显这个主题值得研究。
现实世界中的许多应用天生具有高维，即具有大量输入特征。有两种范例可以帮助我们处理这种类型的数据，即降维和特征选择。降维方法通常基于数学的投影，试图将原始特征映射到一个合适的特征空间。在降维后，特征的原始含义通常会丢失。特征选择方法直接选择一些原始特征来使用，因此它们可以保留特征的原始含义，这在许多应用中是非常可取的。然而，特征选择方法通常基于启发式，缺乏扎实的理论基础。受到Viola和Jones的工作的启发，我们认为AdaBoost在特征选择方面非常有用，特别是考虑到它具有扎实的理论基础。目前的研究主要集中在图像上，但我们认为基于AdaBoost的一般特征选择技术也值得研究。