0. 引言

学习和使用AdaBoost算法来研究人脸检测有好几个月了，一直以来想对AdaBoost的算法和原理做一个总结，在网上也参考了很多牛人的博客和看了一些专业论文，总是觉得总结的不够全面和详细，因此想对AdaBoost的来龙去脉做一个详细的总结，对算法里涉及到的原理，自己经过细致考证和推理，给出了详细的理论证明和代码验证，而不仅仅是停留在只知结果而不知推理的层面上。因此需要花不少时间来总结和写下自己在AdaBoost道路上学习和研究的心路历程！在后面会给出所有的参考文献，对网上众多的未曾谋面的牛人表示感谢！

1. AdaBoost身世之谜

Boost 算法系列的起源来自于PAC学习模型。这套理论主要研究的是什么时候一个问题是可被学习的，当然也会探讨针对可学习问题的具体的学习算法。这套理论是由Valiant提出来的，也因此（还有其他贡献哈）他获得了2010年的图灵奖。这里也贴出Valiant的头像，表示下俺等菜鸟的膜拜之情。

1.1 PAC学习模型

1.1.1 概述

可学习理论可以分为统计学习理论和计算学习理论两大部分[1]。统计学习理论与经验过程有着密切的联系，而计算学习理论是概率理论中发展比较成熟的一个重要分支，它主要用于处理在实验的基础上进行的各种量的估计，研究当采样越来越多的时候，这些估计值是否收敛到未知的真值的问题，它的理论基础主要是概率理论；计算学习理论主要研究如何构造有效的学习算法以及讨论学习算法的计算复杂性问题。

PAC（Probably Approximately Correct）模型是计算学习理论中常用的模型，它是由Valiant于1984年首先提出来的[2]。这篇论文认为“学习”是模式明显清晰或模式不存在时仍能获取知识的一种“过程”，并给出了一个从计算角度来获得这种“过程”的方法，这种方法包括：（1）适当信息收集机制的选择；（2）学习的协定；（3）对能在合理步骤内完成学习的概念的分类。虽然内在的算法复杂性限制了能够学习的概念的范围，论文仍然给出了一些有现实意义的，重要的，能够学习的概念例子。

PAC学习的实质就是在样本训练的基础上，使算法的输出以概率接近未知的目标概念。PAC学习模型是考虑样本复杂度（指学习器收敛到成功假设时至少所需的训练样本数）及计算复杂度（指学习器收敛到成功假设时所需的计算量）的一个基本框架，成功的学习被定义为形式化的概率理论。

简单说来，PAC学习模型不要求你每次都正确，只要能在多项式个样本和多项式时间内得到满足需求的正确率，就算是一个成功的学习。

1.1.2 PAC数学描述

下面简要描述PAC学习模型：
① Х<script type="math/tex" id="MathJax-Element-281">Х</script>为样本空间，包含所有可以用于学习的样本集合;
② Ｃ<script type="math/tex" id="MathJax-Element-282">Ｃ</script>为概念空间，包含所有可以选取的目标概念T<script type="math/tex" id="MathJax-Element-283">T</script>；
③ Ｖ<script type="math/tex" id="MathJax-Element-284">Ｖ</script>为分类集合，其值为目标概念的所有分类 {v1,...,vk<script type="math/tex" id="MathJax-Element-285">v_1, ... ,v_k</script>}。最简单的情况为二值，V<script type="math/tex" id="MathJax-Element-286">V</script>={0,1<script type="math/tex" id="MathJax-Element-287">0,1</script>};
④ Ｈ<script type="math/tex" id="MathJax-Element-288">Ｈ</script>为假设空间，包含算法所输出的所有假设Hm(T,x)<script type="math/tex" id="MathJax-Element-289">H_m (T,x)</script>.

学习器L<script type="math/tex" id="MathJax-Element-290">L</script>的目的是找到目标概念的一个假设，使其能对每个样本进行分类。我们按照某种固定的（可能未知的）分布 P(x)<script type="math/tex" id="MathJax-Element-291">P(x)</script> 独立抽取样本x1,…,xm<script type="math/tex" id="MathJax-Element-292">x_1,…,x_m</script>，L<script type="math/tex" id="MathJax-Element-293">L</script> 返回 hT(xt)<script type="math/tex" id="MathJax-Element-294">h_T (x_t)</script>的值：hT(xt)∈V<script type="math/tex" id="MathJax-Element-295">h_T (x_t )∈V</script> 为 T<script type="math/tex" id="MathJax-Element-296">T</script> 的指示函数，表示 L<script type="math/tex" id="MathJax-Element-297">L</script> 对 xt<script type="math/tex" id="MathJax-Element-298">x_t</script> 的分类。

于是可以获得一组数据：

<script type="math/tex; mode=display" id="MathJax-Element-299"> [(x_1,h_T (x_1)),…,(x_m,h_T (x_m))]∈[X \times V]^m </script>

构造适当的算法 {Am<script type="math/tex" id="MathJax-Element-300">A_m</script>}，Am<script type="math/tex" id="MathJax-Element-301">A_m</script>为到概念空间的映射 Am:[X×V]m→C<script type="math/tex" id="MathJax-Element-302">A_m:[X \times V]^m→C</script> ，并定义：

<script type="math/tex; mode=display" id="MathJax-Element-303">H_m (T,x)= A_m ((x_1,h_T (x_1)),…,(x_m,h_T (x_m))</script>

则 Hm(T,x)<script type="math/tex" id="MathJax-Element-304">H_m (T,x) </script> 就是目标概念T<script type="math/tex" id="MathJax-Element-305">T</script> 对样本 x1,…,xm<script type="math/tex" id="MathJax-Element-306">x_1,…,x_m</script> 的一个假设。

我们希望能够找到一个对所有样本都正确的假设，在实际学习中，这是不可能的。如果学习器 L<script type="math/tex" id="MathJax-Element-307">L</script> 最终将以 (1?d)<script type="math/tex" id="MathJax-Element-308">(1-d)</script> 的概率（d<script type="math/tex" id="MathJax-Element-309">d</script> 称为假设的置信度）输出一个假设 h∈H<script type="math/tex" id="MathJax-Element-310">h∈H</script>，而且随机样本被错误分类的概率小于假设错误率 e<script type="math/tex" id="MathJax-Element-311">e</script>，我们就认为这个假设为成功假设。

如果学习器 L<script type="math/tex" id="MathJax-Element-312">L</script> 只需要多项式 p(m,1/e,1/d)<script type="math/tex" id="MathJax-Element-313">p(m,1/e,1/d)</script> 个样本以及在多项式 p(m,1/e,1/d)<script type="math/tex" id="MathJax-Element-314">p(m,1/e,1/d)</script> 时间内就可以获得一个成功假设，那么称 L<script type="math/tex" id="MathJax-Element-315">L</script> 为可PAC学习的。

因为PAC模型不要求学习器输出零错误率的假设，而只要求其错误率被限定在某常数 e<script type="math/tex" id="MathJax-Element-316">e</script> 的范围内(e<script type="math/tex" id="MathJax-Element-317">e</script>可以任意小)；同时也不要求学习器对所有的随机抽取的样本集合都能成功，只要其失败的概率被限定在某个常数 d<script type="math/tex" id="MathJax-Element-318">d</script> 的范围内(d<script type="math/tex" id="MathJax-Element-319">d</script>也可取任意小)即可，所以学习器将学习到一个可能近似正确的假设。

1.2 弱学习与强学习

如何根据观测数据来学习并得到精确的假设是机器学习领域中人们非常关注的一个问题，机器学习的一个重要目标就是对新样本尽可能给出精确的估计。

随机猜测一个是或否的问题，将会有50%的正确率。如果一个假设能够稍微地提高猜测正确的概率，那么这个假设就是弱学习算法，得到这个算法的过程称为弱学习。可以使用半自动化的方法为好几个任务构造弱学习算法，构造过程需要数量巨大的假设集合，这个假设集合是基于某些简单规则的组合和对样本集的性能评估而生成的。如果一个假设能够显著地提高猜测正确的概率，那么这个假设就称为强学习。生成只比随机猜测好一点的弱学习算法很容易，但是构造一个强学习算法却是一件相当困难的事情。

Kearns[3]首次提出了PAC学习模型中弱学习算法和强学习算法的等价性问题，即任意给定仅比随机猜测略好的弱学习算法，是否可以将其提升为强学习算法？如果二者等价，那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法，而不必寻找很难获得的强学习算法。也就是这种猜测，让无数牛人去设计算法来验证PAC理论的正确性。Kearns 和 Valiant 证明[4]：只要有足够的数据，弱学习算法就能通过集成的方式生成任意高精度的假设（强学习方法）。

不过很长一段时间都没有一个切实可行的办法来实现这个理想。细节决定成败，再好的理论也需要有效的算法来执行。终于功夫不负有心人， Schapire在1996年提出一个有效的算法真正实现了这个夙愿，它的名字叫AdaBoost。

1.3 Boosting方法

Boosting算法的思想是学习一系列的分类器，在这个系列中，每个分类器对其前一个分类器产生的错误给予更大的重视，并增加导致错误分类的样本权值，重新对该样本训练分类器后，再学习下一个分类器。该训练过程重复到设定的次数后停止，最终分类器从这一系列的分类器中得出。Boosting是一种把若干个若分类器结合到一个强分类器中，从而大大提高检测性能的方法。强分类器对数据进行分类，是通过弱分类器的多数投票机制进行的，整个过程如下：(1) 先求对N<script type="math/tex" id="MathJax-Element-40">N</script>个训练数据学习得到第一个弱分类器 h1<script type="math/tex" id="MathJax-Element-41">h_1</script>；(2) 将h1<script type="math/tex" id="MathJax-Element-42">h_1</script>分错的数据和剩 余数据构成新的训练样本，通过对其学习得到第二个弱分类器h2<script type="math/tex" id="MathJax-Element-43">h_2</script>；(3) 重复以上过程得到n个弱分类器，最终经过提升的强分类器 h=F(h1,…,hn)<script type="math/tex" id="MathJax-Element-44">h=F(h_1,…,h_n)</script>。强分类器中的F<script type="math/tex" id="MathJax-Element-45">F</script>函数对n<script type="math/tex" id="MathJax-Element-46">n</script>个分类器进行多数投票，其结果作为强分类器的结果。

Boosting 原意为提升、加强。现在一般指的是将弱学习算法提升为强学习算法的一类算法。实际上,1990年 Schapire 就首先构造出一种多项式级的算法[5]，将弱学习算法提升为强学习算法，即最初的 Boosting 算法。1993 年，Drucker 和 Schapire 第一次以神经网络作为弱学习器，应用 Boosting 算法来解决实际的OCR问题[6]。

前面指出，将弱学习算法通过集成的方式提高到任意精度，是Kearns和Valiant在1994年才证明的，虽然Boosting方法在1990年已经提出，但是它是在Kearns和Valiant证明[4]后才真正成熟起来的。1995年，Freund 提出了一种效率更高的 Boosting 算法[7]。

1995 年，Freund 和 Schapire 提出的 Adaboost，是对 Boosting 算法的一大提高。Adaboost是Boosting家族的代表算法之一，全称为Adaptive Boosting。Adaptively，即适应地，该方法根据弱学习的结果反馈适应地调整假设的错误率，所以Adaboost不需要预先知道假设的错误率下限。也正因为如此，它不需要任何关于弱学习器性能的先验知识，而且和Boosting算法具有同样的效率，所以在提出之后得到了广泛的应用。

【同步本人网易博客的文章】 AdaBoost 人脸检测介绍(1) : AdaBoost身世之谜