北京大学本科生毕业论文 Hm (T, x) = Am ( ( x1,hT (x1) ),?,( xm ,hT (xm ) ) )

则 Hm (T, x) 就是目标概念T，对样本x1,?,xm 的一个假设。

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

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

p(m, 1/e, 1/d)时间内就可以获得一个成功假设，那么称L为可PAC学习的。

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

4.3 弱学习与强学习

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

基于 AdaBoost 算法的人脸检测 赵楠 24

北京大学本科生毕业论文 随机猜测一个是或否的问题，将会有 50%的正确率。如果一个假设能够稍微地提高猜测正确的概率，那么这个假设就是弱学习算法，得到这个算法的过程称为弱学习。可以使用半自动化的方法为好几个任务构造弱学习算法，构造过程需要数量巨大的假设集合，这个假设集合是基于某些简单规则的组合和对样本集的性能评估而生成的。如果一个假设能够显著地提高猜测正确的概率，那么这个假设就称为强学习。生成只比随机猜测好一点的弱学习算法很容易，但是构造一个强学习算法却是一件相当困难的事情。Kearns[14]提出了弱学习算法与强学习算法间的等价问题——是否能把弱学习算法转化为强学习算法。如果两者等价，则只需要找到一个弱学习算法就可以直接将其提升为强学习算法。Kearns 和 Valiant 证明[15]：只要有足够的数据，弱学习算法就能通过集成的方式生成任意高精度的假设（强学习方法）。

4.4 Boosting 方法

Boosting 原意为提升、加强。现在一般指的是将弱学习算法提升为强学习算法的一类算法。Boosting 算法是在 Kearns 和 Valiant 证明[15]后才真正成熟起来的。

1990 年，Schapire 最先构造出一种多项式级的算法[16]，即最初的 Boosting 算法。这种算法可以将弱分类规则转化成强分类规则。一年后，Freund 提出了一种效率更高的 Boosting 算法[17]。1993 年，Drucker 和

基于 AdaBoost 算法的人脸检测 赵楠

25

北京大学本科生毕业论文 Schapire 第一次以神经网络作为弱学习器，应用 Boosting 算法来解决实际的 OCR 问题[18]。

Boosting 算法在分类、建模、图像分割、数据挖掘等领域均已得到简单而有效的应用。

1995 年，Freund 和 Schapire 提出的 Adaboost，是对 Boosting 算法的一大提高。下面章节将逐步具体说明 AdaBoost 算法。

5 矩形特征与积分图

5.1 引言

本章节描述了对 AdaBoost 人脸检测训练算法速度很重要的两方面，特征的选取和特征值的计算。

将矩形作为人脸检测的特征向量，称为矩形特征。本算法选取了最简单的 5 个矩形特征模板进行训练，以得到一套用于人脸检测的最适合的矩形特征，事实证明，这种特征选取方法的训练速度虽然不快，但是检测效率很高。

基于 AdaBoost 算法的人脸检测 赵楠 26

北京大学本科生毕业论文 Viola 提出将积分图(integral image)应用到特征值的计算之中[19]。积分图的引用，可以只对图像进行一次遍历计算，就能够在用常量时间完成每个特征值的计算，这使得训练和检测的速度大大提升。

5.2 矩形特征 Rectangle Feature

5.2.1 概述

在给定有限的数据情况下，基于特征的检测能够编码特定区域的状态，而且基于特征的系统比基于象素的系统要快得多。

矩形特征对一些简单的图形结构，比如边缘、线段，比较敏感，但是其只能描述特定走向（水平、垂直、对角）的结构，因此比较粗略。如图 9，脸部一些特征能够由矩形特征简单地描绘，例如，通常，眼睛要比脸颊颜色更深；鼻梁两侧要比鼻梁颜色要深；嘴巴要比周围颜色更深。

对于一个 24×24 检测器，其内的矩形特征数量超过 160,000 个，必须通过特定算法甄选合适的矩形特征，并将其组合成强分类器才能检测人脸。

基于 AdaBoost 算法的人脸检测 赵楠 27

北京大学本科生毕业论文

图 9 矩形特征在人脸上的特征匹配。上行是 24×24 子窗口内选出的矩形特征，下行是子窗口检测到的与矩形特征的匹配。

5.2.2 特征模版

我们将使用简单矩形组合作为我们的特征模板。这类特征模板都是由两个或多个全等．．的矩形相邻组合而成，特征模板内有白色和黑色两种矩形（定义左上角的为白色，然后依次交错），并将此特征模板的特征值定义为白色矩形像素和减．．．．．．．．．．．．．．．．．．．．．去黑色矩形像素和．．．．．．．．。

最简单的 5 个特征模板：

名称（模板号） 特征模板 边缘特征 (1)(2) 基于 AdaBoost 算法的人脸检测 赵楠 28