北京大学本科生毕业论文
图 8 人脸高斯簇和非人脸高斯簇
3.4 支持向量机 Support Vector Machine (SVM)
支持向量机(Support Vector Machines，SVM)是一种基于统计学习理论的模式识别方法，它在结构风险最小化基础上，为两种不同类别的样本数据找到一个最优分类面，可以说是一个受限二次规划问题。此方法由 Boser、Guyon、Vapnik 在 COLT-92 上首次提出。
最先将此方法应用于人脸检测的是 Osuna 等人[8]，他们采用这个方法的检测效果和 Sung 等人[7]的方法相似，然而速度却提高了 30 倍。
Heiselet 等人[9]采用两级 SVM 的方法来检测人脸。根据一些预定义的特征点，从训练集中提取人脸和非人脸图像最有区别的多个局部区域。检测时，根
基于 AdaBoost 算法的人脸检测 赵楠 19
北京大学本科生毕业论文 据多个简单的线性 SVM 分别检测各个人脸特征区域。并用一个简单的线性 SVM 检测各个可能的人脸部分的几何组合是否符合人脸结构。相比于将整个人脸作为特征，该方法获得了更高的检测率。
3.5 隐马尔科夫模型 Hidden Markov Model (HMM)
隐马尔科夫模型(Hidden Markov Model，HMM)是用于描述信号统计特性的一组统计模型。HMM 使用马尔科夫链来模拟信号统计特征的变化，而这种变化又是间接地通过观察序列来描述的，因此，隐马尔科夫过程是一个双重的随机过程。在 HMM 中，节点表示状态，有向边表示状态之间的转移，一个状态可以具有特征空间中的任意特征，对同一特征，不同状态表现出这一特征的概率不同。由于 HMM 是一个统计模型，对于同一特征序列，可能会对应于许多状态序列，特征序列与状态序列之间的对应关系是非确定的。这种模型对于状态序列来说是隐的，故称为隐马尔科夫模型。
Nefian 等采用隐马尔可夫模型检测人脸[10]。检测区域中的每个子区域采用主要的 Karhunen-Loève 变换系数作为观察矢量，通过 Baum-Welch 算法和 Viterbi 分割算法获得 HMM 的模型参数，根据检测区域的观察序列的输出概率进行判决。
基于 AdaBoost 算法的人脸检测 赵楠 20
北京大学本科生毕业论文 4 AdaBoost方法概述
4.1 引言
PAC 学习模型的提出，计算学习理论得到了很大的发展，从而使“ 学习” 有了计算上的判定方法。PAC 模型中提出了弱学习和强学习的概念，后来证明通过某种方法（后称为 Boosting）可以将弱学习提升为强学习——这使得训练机器学习来得更加方便。
1995 年，Freund 和 Schapire 提出了 AdaBoost 算法[11]。AdaBoost 全称为 Adaptive Boosting，作者说取名叫作 AdaBoost 是因为这个算法和以前的 Boosting 算法都不同（原先的 Boosting 算法需要预先知道假设的错误率下限），它根据弱学习的反馈适应性地（adaptively）调整假设的错误率——也就是说， AdaBoost 算法不需要任何关于弱学习器性能的先验知识，加上它和原来 Boosting 算法的效率一样，因此可以非常容易地应用到实际问题中。
AdaBoost 算法提出后在机器学习领域受到了极大的关注，实验结果显示无论是应用于人造数据还是真实数据，AdaBoost 都能显著提高学习精度。下面的章节将简述 AdaBoost 发明之前的 Boosting 算法发展过程。
4.2 PAC 学习模型
基于 AdaBoost 算法的人脸检测 赵楠 21
北京大学本科生毕业论文 4.2.1 概述
可学习理论可以分为统计学习理论和计算学习理论两大部分[12]。统计学习理论与经验过程有着密切的联系，而计算学习理论是概率理论中发展比较成熟的一个重要分支，它主要用于处理在实验的基础上进行的各种量的估计，研究当采样越来越多的时候，这些估计值是否收敛到未知的真值的问题，它的理论基础主要是概率理论；计算学习理论主要研究如何构造有效的学习算法以及讨论学习算法的计算复杂性问题。
PAC（Probably Approximately Correct）模型是计算学习理论中常用的模型，它是由Valiant于1984年首先提出来的[13]。这篇论文认为“ 学习” 是当明显清晰的过程或模式不存在时仍能获取知识的一种“ 过程”，并给出了一个从计算角度来获得这种“ 过程” 的方法，这种方法包括：（1）适当信息收集机制的选择；
（2）学习的协定；（3）对能在合理步骤内完成学习的概念的分类。虽然内在的算法复杂性限制了能够学习的概念的范围，论文仍然给出了一些有现实意义的，重要的，能够学习的概念例子。
PAC学习的实质就是在样本训练的基础上，使算法的输出以概率接近未知的
基于 AdaBoost 算法的人脸检测 赵楠 22
北京大学本科生毕业论文 目标概念。PAC学习模型是考虑样本复杂度及计算复杂度2的一个基本框架，成功的学习被定义为形式化的概率理论。
4.2.2 数学描述
下面简要描述PAC学习模型。给出：
1、 Х 为样本空间，包含所有可以用于学习的样本集合； 2、Ｃ为概念空间，包含所有可以选取的目标概念T；
3、 Ｖ为分类集合，其值为目标概念的所有分类{v1,?,vk }。最简单的情况
为二值，Ｖ={0,1}；
4、
Ｈ为假设空间，包含算法所输出的所有假设 Hm (T, x)
学习器L的目的是找到目标概念的一个假设，使其能对每个样本进行分类。我们按照某种固定的（可能未知的）分布P(x)独立抽取样本x1,?,xm ，L返回hT (xt ) 的值：hT (xt )∈Ｖ为T的指示函数，表示L对xt 的分类。
于是可以获得一组数据：
[(x1,hT (x1)),?,(xm ,hT (xm ))]∈[ Ｘ × Ｖ ]m
构造适当的算法{Am}，Am 为到概念空间的映射 Am :[Ｘ × Ｖ]m →Ｃ，并定义：
2
样本复杂度(sample complexity)指学习器收敛到成功假设时至少所需的训练样本数。 计算复杂度(computational complexity)指学习器收敛到成功假设时所需的计算量。
基于 AdaBoost 算法的人脸检测 赵楠 23