AdaBoost 人脸检测介绍(1) : AdaBoost身世之谜

　　本系列文章总共有7篇，目录索引以下：
　　AdaBoost 人脸检测介绍(1) : AdaBoost身世之谜
　　AdaBoost 人脸检测介绍(2) : 矩形特点和积分图
　　AdaBoost 人脸检测介绍(3) : AdaBoost算法流程

0. 引言

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

1. AdaBoost身世之谜

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

1.1 PAC学习模型

1.1.1 概述

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

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

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

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

1.1.2 PAC数学描写

　　下面扼要描写PAC学习模型：
　　① Х为样本空间，包括所有可以用于学习的样本集合;
　　② Ｃ为概念空间，包括所有可以选取的目标概念T；
　　③ Ｖ为分类集合，其值为目标概念的所有分类 {v1,...,vk}。最简单的情况为2值，V={0,1};
　　④ Ｈ为假定空间，包括算法所输出的所有假定Hm(T,x).

　　学习器L的目的是找到目标概念的1个假定，使其能对每一个样本进行分类。我们依照某种固定的（可能未知的）散布 P(x) 独立抽取样本x1,…,xm，L 返回 hT(xt)的值：hT(xt)∈V 为 T 的唆使函数，表示 L 对 xt 的分类。
　　因而可以取得1组数据：

构造适当的算法 {Am}，Am为到概念空间的映照 Am:[X×V]m→C ，并定义：

则 Hm(T,x) 就是目标概念T 对样本 x1,…,xm 的1个假定。

　　我们希望能够找到1个对所有样本都正确的假定，在实际学习中，这是不可能的。如果学习器 L 终究将以 (1−d) 的几率（d 称为假定的置信度）输出1个假定 h∈H，而且随机样本被毛病分类的几率小于假定毛病率 e，我们就认为这个假定为成功假定。

　　如果学习器 L 只需要多项式 p(m,1/e,1/d) 个样本和在多项式 p(