第4章 Adaboost算法
4.1 概述
4.1.1 Adaboost算法简介
Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。使用Adaboost分类器可以排除一些不必要的训练数据特徵，并将关键放在关键的训练数据上面。Adaboost 算法是1995 年提出的一种快速人脸检测算法，是人脸检测领域里程碑式的进步，这种算法根据弱学习的反馈，适应性地调整假设的错误率，使在效率不降低的情况下，检测正确率得到了很大的提高。
Adaboost算法是目前在人脸检测方面检测速度较快、检测效果较好的一种检测方法，它是一种把弱分类器采用级联的方式训练成为强分类器的方法。这些弱分类器只需要满足比随机猜测好一点，就能通过不断的修正每个弱分类器的权值，即挑选那些比较好的分类器，抛弃不好的分类器，从而最终形成由这些弱分类器组成的强分类器，相比较其他的方法而言，Adaboost方法对每个弱分类器的权值的形成都是无人值守的，完全自动化的，因而Adaboost算法有着比较好的易用性。大量的实验证明，Adaboost算法是有效的将多弱分类器强化成为强分类器的一种方法，经过训练的分类器具有比较好的分类效果，而且速度较快。图4．1给出了Adaboost人脸检测算法进行训练和检测的流程图，本文也将分训练和检测两个方面介绍Adaboost算法。
16
训练过程 人脸 Adaboost训练 分类器 非人脸 检测过程 检测结果 Adaboost检测 输入图像
图4.1Adaboost训练过程
4.1.2 Adaboost人脸检测算法
人体检测属模式识别范畴。模式识别方法多种多样，模式识别系统的最终目标是要在表示空间和解释空间之间找到一种映射关系。这种映射可以是一个分类，也可以是回归或者描述方案。在这里，我们用分类来叙述。分类方法总得来说可以分为两种：监督学习和非监督学习。后来又在前两者的基础上 发展出了半监督学习方法，这种方法的本质仍属于监督学习。
统计分类是模式识别发展过程中建立起来的比较经典的方法，其表达方式有着坚实的理论基础。它主要基于用概率统计模型得到各类别的特征向量分布，以取得分类的功能。特征向量的取得是基于一个类别已知的训练样本集合。因此，这是一种监督学习的模式识别方法。在这个意义上，分类器是概念驱动的，用已知类别标签的样本训练分类器从而得知如何分类。继而对新的样本集达到分类的效果，统计分类方法有很多具体的方法，它们取决于是否采用一个已知的、参数型的分布模型。
Adaboost算法是统计分类方法中一个经典算法，它由Boosting算法发展而来，是由Freund和Schapire在1995年提出的，该算法解决了以前Boosting算法在实践中存
17
在的各种问题。实验表明，Adaboost算法能够显著提高学习精度。
利用Adaboost算法与haar特征（本文将会在第五章详细介绍haar特征）相结合的方法进行人脸检测。Haar特征是一种基于积分图像的特征，主要在灰度图像中使用，该特征计算简单，提取速度较快。Adaboost算法首先提取图像中的haar特征，再将训练得到的haar特征转换成弱分类器，最后将得到的弱分类器进行优化组合用于人脸检测。
Viola等人在2001年提出使用AdaBoost学习算法的快速人脸检测方法，实现了实时的正面人脸检测系统。Viola的系统中主要有三个核心思想：首先，提出了一种称为“积分图像”的图像表示方法，这种表示法能够快速计算出检测器用到的特征；其次，利用基于AdaBoost的学习算法，从一个较大的特征集中选择少量的关键视觉特征，产生一个高效的分类器；最后，再用级联的方式将单个的分类器合成为一个更加复杂的分类器，使图像的背景区域可以被快速地丢弃，而在有可能存在目标(人脸)的区域花费更多的计算。该人脸检测系统在实时正面人脸检测中能够达到15帧／秒的速率。由于该方法能够达到较高的检测率并且具有目前最好的实时性，因此激发了更多研究人员在基于类Haar特征和Boost学习算法的实时人脸检测算法方面的研究。
Intel实验室的Rainer Lienhart扩展了类Haar特征，在Viola提出的类Haar特征的基础上添加了旋转45度的类Haar特征，在与Viola系统相同检测率的情况下，降低了10％的误检率。微软研究院Stan Z.Li的研究小组把floating搜索的方法引入到AdaBoost算法中来，并设计了一个金字塔式的检测器结构用于多视角的人脸检测。
4.2 弱学习与强学习
弱分类器的设计是集成机器学习的重要内容之一，与一般机器学习算法区别在于弱分类器设计无需考虑线性不可分问题，这是集成机器学习吸引大量应用研究者关注的主要原因。
弱分类器的概念来源于Valiant在1984年提出的PAC学习理论，之后Kearns和Valiantl又提出了强PAC学习和弱PAC学习的概念。在PAC学习模型中，若存在一个多项式级学习算法来识别一组概念，并且识别正确率很高，那么这组概念是强可学习的；而如果学习算法识别一组概念的正确率仅比随机猜测略好，那么这组概念是弱可学习的。
随机猜测一个是或否的问题，将会有50%的正确率。如果一个假设能够稍微地提高猜测正确的概率，那么这个假设就是弱学习算法，得到这个算法的过程称为弱学习。可以使用半自动化的方法为好几个任务构造弱学习算法，构造过程需要数量巨大的假设集合，这个假设集合是基于某些简单规则的组合和对样本集的性能评估而生成的。如果一个假设能够显著地提高猜测正确的概率，那么这个假设就称为强学习。
弱分类器就是根据某些单一依据来就行粗略分类的分类器，其分来的准确度要求很低，只要达到50%以上即可。虽然弱分类器的分类效果很差，但是试想如果将很多个这样的弱分类器按照一定的规则组合起来便可以形成一个高度准确的强分类器，这
18
也就是级联分类器。
实际上每一个haar特征都可以对应一个弱分类器，每一个弱分类器都是根据它所对应的haar特征的参数来定义的。如果将所有的haar特征都用来对应一个弱分类器，那么其总个数将超过数十万个。要想从这样庞大数目的弱分类器中训练出最优弱分类器将是一个非常巨大的工程，其训练时间也将达到数天之长。因此，这是该进Adaboost性能的一个关键点所在。
通常情况下，弱学习算法比强学习算法更容易获得。Keams和vallant提出了弱学习算法与强学习算法间的等价问题，即能否把弱学习算法转化为强学习算法。如果两者等价，那么在学习概念时，只需要找到一个比随机猜测略好的弱学习算法，就可以直接将其提升为强学习算法。
Keams和vallant证明：只要有足够的数据，弱学习算法就通过集成的方式生成任意高精度的假设(强学习方法)。
4.3 PAC 基本模型
4.3.1 概述
PAC（Probably Approximately Correct）模型是计算学习理论中常用的模型，是由Valiant于1984年首先提出来的，由统计模式识别、决策理沦提出了一些简单的概念并结合了计算复杂理论的方法而提出的学习模型。它是研究学习及泛化问题的一个概率框架，不仅可用于神经网络分类问题，而且可广泛用于人工智能中的学习问题。
PAC学习的实质就是在样本训练的基础上，使算法的输出以概率接近未知的目标概念。PAC学习模型是考虑样本复杂度及计算复杂度的一个基本框架，成功的学习被定义为形式化的概率理论。 4.3.2 基本概念
实例空间指学习器能见到的所有实例，用xn指示每个大小为n的学习问题的实例集，每个x?X为一个实例， X=Un>1Xn为实例空间。概念空间指目标慨念可以从中选取的所有概念的集合，学习器的目标就是要产生目标概念的一个假设，使其能准确地分类每个实例，对每个n≥1，定义每个Cn?2Xn为Xn上的一系列概念，C?Un?1Cn为X上的概念空间，也称为概念类。似设空间指算法所能输出的听有假设h的集合，用H表示。对每个目标概念c?Cn和实例x?Xn，c(x)为实例x上的分类值，即c(x)?1当且仅当x?CoCn的任一似设h指的是规则，即对给出的x?Xn，算法在多项式时间内为c(x)输出一预测值。样本复杂度(sample complexity)指学习器收敛到成功假设时至少所需的训练样本数。计算复杂度(computational complexity)指学习器收敛到成功假设时所需的计
19
算量。出错界限指在成功收敛到一个假设前，学习器对训练样本的错误分类的次数。在某一特定的假设空间中，对于给定的样本，若能找到一似设h，使得对该概念类的任何概念都一致，且该算法的样本复杂度仍为多项式，则该算法为一致算法。
实例空间为X?{0,1}n，概念空间和假设空间均为{0,1}n的子集，对任意给定的准确度?(0???12)及任意给定的置信度?(0???1)，实例空间上的所有分布D及目标空间中的所有目标函数t，若学习器L只需多项式p(n,1?,1?)个样本及在多项式p(n,1?,1?)时间内，最终将以至少(1??)的概率输出一假设h?H，使得随机样本被错分类的概率errorD(h,t)?P则称学习器L足PAC学习的。它r[x?X:h(x)?t(x)]??，是考虑样本复杂度及计算复杂度的一个基本框架，成功的学习被定义为形式化的概率理沦，其模型如图所示。
分布D及目标概念c?C 对 手 概念类C 样本请求 样本 产生 器EX 准确度? 学 习 器 带标记随机实例 置信度? 图4-1 PAC学习模型
从图中知PAC模型是与分布无关的，因对学习器来说，实例上的分布是未知的。该定义不要求学习器输出零错误率的假设，而只要求其错误率被限定在某常数ε的范围内(ε可以任意小)；同时也不要求学习器对所有的随机抽取样本序列都能成功，只要其失败的概率被限定在某个常数δ的范围内(δ也可取任意小)即可。这样将学习到一个可能近似正确的假设。 4.3.3 PAC模型的不足
在实际的机器学习中，PAC模型的不足有：模型中强调最坏情况，它用最坏情况模型来测量学习算法的计算复杂度及对概念空间中的每个目标概念和实例空间上的每个分布，用最坏情况下所需要的随机样本数作为其样本复杂度的定义，使得它在实际中不可用；定义中的目标概念和无噪声的训练数据在实际中是不现实的。
样本复杂度的最坏情况定义意味着即使能准确地计算出某一算法的样本复杂度，仍
20
