当我们用某种特征工具（如Haar特征模板）从图像的某个位置某个特定大小的区域提取到一个显著的特征，能否说这个特征就是我们下一步进行分类的依据呢？
假如我们提取到若干简单的特征，如何判定它们已经提供了足够的分类依据，还是依然需要增加更多的简单的特征？
我们已经说了，要解决这个问题，需要用到统计学上的一种方法：训练，或者说学习。
本文介绍的训练方法叫做AdaBoost（它是由Adaptive Boost两个单词组成的）算法，是一系列叫Boost算法中的一种，Boost算法的中文译法叫“提升”，是基于一种这样的思想：如果一个概念是“弱可学习”的，那么它就可以提升为“强可学习”。
在统计学的历史上，Kearns和Valiant提出了“强可学习(strongly learnable)”和“弱可学习(weakly learnable)的概念。指出：在概率近似正确(probably approximate correct, PAC，有机会的话，我会在本文的附录中专门介绍一下这个概念)学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的；一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好（比如51%判断对，49%判断错)，那么就称这个概念是弱可学习的。
他们并且还提出了一个问题：一个概念如果是“弱可学习”的，是否能推导出它是“强可学习”的，即“弱可学习”和“强可学习”是不是等价的。后来由Schapire证明了，它们确实是相等的，即一个概念是“强可学习”的，其充分必要条件是这个概念是“弱可学习”的。Schapire也是Boosting算法的提出人。
上面这段话读起来可能略微有些抽象，我换一种“民科”一点的风格来叙述一下，就比较好理解了：假设我们要干一件事情叫分类，分类是什么意思呢？我们举两个例子，例一：给你一堆图像，判断哪些是人脸，哪些不是，即是与否的二分法问题；例二：给你十个预先设计好的分类，比如说人，汽车，摩托车，道路，树，等等，判断一张图片属于这里边哪个分类，这两个例子就是分类问题。
那么这时候如果你发现一种分类算法，不大准确，比如只有60%左右的准确率，这算是一个“弱可学习”算法，那么有没有可能通过不断地累积这类算法（提升），最终得到一个“强可学习”算法，比如是准确率达到99%？
Schapire说这是有可能的。
Freund和Schapire于1995年改进了boosting算法，取名为AdaBoost，下面先简单介绍一下其原理，然后重点用网上和书本中用到的一个重要方法——举例法来详细解释一下这个算法是如何工作的。
对于分类问题而言，给定一个训练样本集，求比较粗糙的分类规则（弱分类器）要比求精确的分类规则（强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。
这样，对提升方法来说，有两个问题需要回答：一是在每一轮如何改变训练数据的权值或概率分布；二是如何将弱分类器组合成一个强分类器。关于第1个问题，AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器“分而治之”。至于第2个问题，即弱分类器的组合，AdaBoost采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
AdaBoost的巧妙之处就在于它将这些想法自然且有效地实现在一种算法里。
现在叙述AdaBoost算法。假设给定一个二类分类的训练数据集
T={(x1,y1),(x2,y2),…,(xN,yN)}
其中，每个样本点由实例与标记组成。实例xi∊x⊆Rn，标记yi∊ y＝{-1,+1}，x是实例空间，y是标记集合。AdaBoost利用以下算法，从训练数据中学习一系列弱分类器或基本分类器，并将这些弱分类器线性组合成为一个强分类器。
AdaBoost算法：
输入：训练数据集T＝{(x1，y1),(x2，y2),…,(xN,yN)}，其中xi∊x⊆Rn，yi∊＝{-1,+1}；弱学习算法；
输出：最终分类器G(x)。
- 初始化训练数据的权值分布
（2）对M＝1,2,…,m
（a）使用具有权值分布Dm的训练数据集学习，得到基本分类器
（b）计算Gm(x)在训练数据集上的分类误差率
（c）计算Gm(x)的系数
这里的对数是自然对数。
（d）更新训练数据集的权值分布
这里，Zm是规范化因子
它使Dm+1成为一个概率分布。
- 构建基本分类器的线性组合
得到最终分类器
对AdaBoost算法作如下说明：
步骤（1） 假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同，这一假设保证第1步能够在原始数据上学习基本分类器G1(x)。
步骤（2） AdaBoost反复学习基本分类器，在每一轮m＝1,2,…,M顺次地执行下列操作：
（a）使用当前分布Dm加权的训练数据集，学习基本分类器Gm(x)。
（b）计算基本分类器Gm(x)在加权训练数据集上的分类误差率：
这里，wmi表示第m轮中第i个实例的权值。
这表明，Gm(x)在加权的训练数据集上的分类误差率是被Gm(x)误分类样本的权值之和，由此可以看出数据权值分布Dm与基本分类器Gm(x)的分类误差率的关系。
（c）计算基本分类器Gm(x)的系数am。am表示Gm(x)在最终分类器中的重要性。由式（8.2）可知，当em≤时，am≥0，并且am随着em的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。
（d）更新训练数据的权值分布为下一轮作准备。式（8.4）可以写成
由此可知，被基本分类器Gm(x)误分类样本的权值得以扩大，而被正确分类样本的权值却得以缩小。两相比较，误分类样本的权值被放大倍。因此，误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用，这是AdaBoost的一个特点。
步骤（3） 线性组合f(x)实现M个基本分类器的加权表决。系数am表示了基本分类器Gm(x)的重要性，这里，所有am之和并不为1.f(x)的符号决定实例x的类，f(x)的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点。
注：这一段关于AdaBoost原理的介绍抄录于《统计学习方法》一书，其中不好理解的是它的“损失函数”，它是一个指数函数，至于为什么AdaBoost的损失函数选择了一个指数函数，有机会我们专门在本文的附录部分开一个章节来论述这一问题。
下面重点来了，我们将通过一个例子来说明：一个准确率不高的“弱可学习”分类器，是如何通过学习，提升为一个“强可学习”分类器的。