（运筹学与控制论专业论文）改进的svm模式识别方法.pdf

北京工业大学理学硕十学位沦文 摘要 人脸识别是当前人工智能和模式识别的研究热点。一个自动的人脸识别系统 包括四个部分，即人脸检测和分割，人脸规范化，人脸特征提取( 也称为人脸表 征) 及人脸识别，其中最关键的技术环节是人脸特征的提取和人脸识别。 本文旨在研究人脸模式识别的方法，使用的是统计学习理论发展起来的一种 新的模式识别方法，即支持向量机。它有两个核一1 1 , 思想，其一就是结构风险最小 化原则，其二就是在最大的样本边缘( m a r g i n ) 的基础上建立一个线性分类器， 其中最大的样本边缘可以通过最大化样本点到超平面的最小距离得到。 由于支持向量机具有许多引人注目的优点以及它在实际应用中的良好表现， 因而在机器学习中备受推崇。本文首先总结了统计学习理论的有关理论和重要结 果，同时独立推导了如何在高维映射空间中构造最优分类超平面的方法，最后提 出了一种改进s v m 的训练算法，即把分段判别的思想引入到s v m 模式识别中， 通过样本训练s v m 得到两个最优分类超平面，从而构造一个分段线性判别器用 于模式识别。实际数据实验的结果表明，本方法的识别效果与传统的s v m 方法 相比有显著提高。在文章的最后，作者对后续工作的前景进行展望，提出了自己 的几个想法。 关键字人脸识别；统计学习理论；经验风险最小化；结构风险最小化：最 优分类超平面；支持向量机。 北京工业大学理学硕十学位沦文 a b s t r a c t f a c er e c o g n i t i o ni sa p o pf o c u si na r t i f i c i a li n t e l l i g e n c ea n dp a t t e r nr e c o g n i t i o n r e s e a r c hi nr e c e n ty e a r s - a na u t o m a t i cf a c er e c o g n i t i o ns y s t e mi n c l u d e sf o u rp a r t s w h i c ha r ef a c ed e t e c t i o na n ds e g m e n t a t i o n ，f a c en o r m a l i z a t i o n ，f a c e r e p r e s e n t a t i o n a n df a c er e c o g n i t i o n a n dt h ef a c er e p r e s e n t a t i o na n df a c er e c o g n i t i o na r et h et w o c r u c i a l p a r t s i nt h i sp a p e r , w es t u d y t h em e t h o di nf a c er e c o g n i t i o n w ew i l li n t r o d u c ean c wp a t t e r nr e c o g n i t i o nm e t h o dw h i c hi sb a s e do nt h e s t a t i s t i c a ll e a r n i n gt h e o r yc - 虹l e ds u p p o f tv e c t o r m a c k i n e s , s v m k h a st w om a i ni d e a s t h ef i r s to n ei ss t r u c t u r a lr i s km i n i m i z a t i o nr u l e a n dt h es e c o n di sb a s e do nal i n e a r c l a s s i f i e rw i t hm a x i m a lm a r g i nw h i c hc a nb eo b t a i n e db ym a x i m i z i n gt h em i n i m u m d i s t a n c ef r o ms a m p l ep o i n t st ot h es e p a r a t i n g h y p e r - p l a n e s v mh a sb e e ng a m i n gm u c hp o p u l a r i t yj dm a c h i n el e a m i d bd u et o 。- m a n y a t t r a c t i v ef e a t h e r sa n d p r o m i s i n gp r a c t i c a lp e r f o r m a n c e i n t h i s p a p e r ，w e f i r s t s u m m a r i z et h em a i nt h e o r i e sa n dt h em o s ti m p o r t a n tc o n c l u s i o n sw h i c ha r ec o n c e r n e d w i t ht h es t a t i s t i c a ll e a r n i n gt h e o r yi nt h e p a t t e r nr e c o g n i t i o n a t t h es a l n et i m e ，h o wt o c o n s t r u c tt h eo p t i m a ls e p a r a t i n gh y p e r - p l a n e i nt h e h i g hm a p p i n gs p a c e i sa l s o i n f e r r e di n d e p e n d e n t t y i nt h e e n d ，b yi n t r o d u c i n gt h ei d e a o f t w o p h a s ec i a s s f f f i n g ， w e g e tt w oo p t i m a ls e p a r a t i n gh y p e r - p l a n e sf r o mt h et r a i n i n gs a m p l e s ，a t e s ts a m p l e w i l lb ed i s c r i m i n a t e du s i n go n eo ft h e na c c o r d i n gag a t e t h er e s u l tu s i n gt h i s m e t h o dt ot h ea c t u a ld a t ai n d i c a t e st h a tt h i sm e t h o di sb e t t e r t h a nt i l et r a d i t i o n a ls v m a tt h ee n do ft h ep a p e r , w ei n t r o d u c et h ep r c , s p e c l so ft h ef o l l o w i n gw o r ka n dg i v e s o m ei d e a sa b o u tt h i sm e t h o d ， k e y w o r d s ：f a c er e c o g n i t i o n ；s t a t i s t i c a ll e a r n i n gt h e o r y ；e m p i r i c a l r i s k m i m m i z a t i o n ；s t r u c t u r a lr i s km i n i m i z a t i o n ；o p t m a a ls e p a r a t i n gh y p e r - p l a n e ；s u p p o r t v e c t o rm a c h i n e s 1 1 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 虢避晰婴丛! 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即； 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵守此规定) 签名：墅幽导师签名绫勉日期：递生1 61 z 北京工业大学理学硕十学位沦文 第1 章绪论 人脸识别是当前人工智能和模式识别的研究热点。它可以用于身份认证、公 共场合对人的监视、图像数据库的检索、提高人与计算机的交互能力等。9 1 1 事 件之后，能够在公众场合自动识别出嫌疑犯的识别系统更成为研究的热点。与其 它身份识别的方法，如虹膜、指纹、d n a 检测相比，人脸识别更加友好、直接、 快速，因此人脸识别在安检系统中的应用一定会大有作为。虽然人类可以轻松 识别出不同人的脸部特征，但机器对人脸的自动识别涉及到模式识别、数字图像 处理、生理和心理学等多方面的课题。一般说来，一个自动的人脸识别系统的可 以划分如下4 个部分【1 | ，它具有如图1 1 的结构( 以基于神经网络的人脸识别系 统为例) ： l 图像预处理( 大l ! ：! ! 里堡一小规一化、灰度l j _ 聂： 厂磊：i ：叫小规一化、灰度卜刊特征提取卜刮神经网络 f 均衡等，f if l 一 | | 呻| | 神经网络训练 人脸图像特征数据库 人脸闺像数据库、卜叫人脸定位l 一预处理l 一特征提取 图卜l 基于人工神经网络的人脸识别系统 ( 1 ) 人脸检测( d e t e c t i o n ) 与分割( s e g m e n t a t i o n ) 。即从任意的场景中检 测人脸的存在并进行定位，提取出一个人脸。 ( 2 ) 人脸的规范化( n o r m a l i z a t i o n ) 。校正人脸在尺度、光照和旋转等方 面的变化。 ( 3 ) 人脸表征( f a c er e p r e s e n t a t i o n ) 。采用某种方法表示出数据库中的已 知人脸和检测出的人脸，通常也称为人脸的特征提取，常用的方法有 北京工业大学理学硕十学位沦文 几何特征、代数特征、特征脸、固定特征模板等。 ( 4 ) 人脸识别( r e c o g n i t i o n ) 。根据人脸的表征方法，选择适当的匹配策 略将得到的人脸与数据库巾的已知人脸相比较。 人脸识别模块是整个人脸识别系统中非常重要的模块。它直接决定了人脸识 别的成功率。 统的人脸识别方法有最近邻法、欧氏距离法、马氏距离法和神经 网络法等。这些方法在某些应用场合下取得了较好的分类效果。但是由于人脸模 式差异性使得人脸识别成为一个非常困难的问题：人脸模式的复杂、高维使得难 以对其建模描述；人脸作为非刚体，微小的形变就有可能使得模式具有很大的差 异，因此人脸模式具有很大的离散性；影响人脸有多种因素如光照、表情、视角、 年龄、饰物、毛发等等，因此人脸模式具有很强的非线性特性。所以到目前为止， 人们还没有找到一种稳健、能够适用于不同场景的识别方法。 本文主要对人脸识别模块中的识别方法进行研究。 由于实际条件的限制，人们无法针对每个人都采集大量的图像样本。相对于 其维数丽言，人脸的样本数很少，是一个小样本闯题。对于人脸识别这个小样本 问题，传统的分类方法一方面容易出现过学习( o v e r - f i t t i n g ) 现象，导致算法的推 广性差：另一方面就是学习性能差，无法胜任人脸分类这个非线性很强的分类模 式。 支撑向量s j t ( s v m ) 是为解决小样本问题学习和分类提出的，一方面可阻克服 神经网络等方法所固有的过学习和欠学习问题，另外一方面又有很强的非线性分 类能力。 人类的智慧中一个很重要的方面就是从实例中学习的能力，通过对已知事实 的分析总结出规律，并用此规律来预测不能直接观测的事实。在这种学习中，重 要的是能够举一反三，即，利用学习得到的规律，不但可以较好地解释已知的实 例，而且能够对未来的现象或无法观测的现象做出正确的预测和判断，这种能力 就是推广能力。 在人们对机器智能的研究中，希望能够用计算机来模拟这种学习能力，这就 是现在常说的基于数据的机器学习问题，通常也简单地称作机器学习问题。机器 学习问题的最终目标就是，设计某种( 某些) 方法，使之能够通过对已知数据的 学习，找到数据内在的相互依赖关系或特征，从而对未知数据进行预测或对其性 2 北京工业大学理学硕十学位沦义 质进行判断。同样，机器学习问题最关心的仍是推广能力的问题。 统计学在解决机器学习问题中起着基础性的作用。但是，传统的统计学所研 究的主要是渐进理论，即当样本数趋于无穷多时的统计性质。在现实的问题中， 我们所面对的样本数目通常是有限的，并且有时候还是十分的有限。虽然人们实 际上也知道这一点，但传统的算法仍是基于样本数目无穷多这个假设上推导或构 造出来的，人们希望这样得到的算法在样本较少时也能有较好的( 至少是可以接 受的) 表现。然而，实际应用却往往出现事与愿违的情况。其中，近年来经常可 以听到人们谈论的所谓神经网络过学习问题就是一个典型的代表：当样本数非常 有限时，本来很不错的一个学习机器却可能表现出很差的推广能力。 人们对于解决此类问题的努力实际上一直在进行着。但是，其中多数工作都 是集中在对已有( 基于传统统计学原则的) 方法的修改和修正上，或者利用启发 式方法设计某些巧妙的算法。 在2 0 世纪末的时候，人们逐渐频繁地接触到一个词，就是“统计学习理论”。 这实际上是早在2 0 世纪7 0 年代就已经建立了其基本体系的一门理论，它系统地 研究了机器学习的问题，尤其是在有限样本情况下的统计学习问题。到了2 0 世 纪9 0 年代，在这一理论框架下产生了“支持向量机( s v m ) ”这一新的通用的 机器学习的方法。或许是由于统计学习理论为人们系统研究有限样本情况下的机 器学习问题提供了有力的理论基础，或许是更因为在这一基础上的支持向量机方 法表现出的令人向往的优良特性，人们迅速开始重视这个早在2 0 年前就该重视 的学术方向。 现在，越来越多的学者认为，关于统计学习理论和支持向量机的研究将很快 出现象在2 0 世纪8 0 年代后期人工神经网络研究那样的飞速发展阶段。所不同的 是，统计学习理论有完备的理论基础和严格的理论体现( 相比之下，神经网络则 更多的带有启发式的成分) ，而且其出发点是更符合实际情况的有限样本假设， 因此，不少学者认为，统计学习理论的这个研究热潮将持续更长久，而且将在人 们关于机器智能的研究中做出更深远的贡献。 v 1 a d i m i r n v a p n i k 是统计学习理论的创立者之一，也是支持向量机方法的主 要发明者。本文将首先介绍统计学习理论最核心的内容和思想，当然包括其中占 有重要地位的支持向量机的核心方法与思想，然后介绍各种情况下支持向量机的 北京工业大学理学硕士学位论文 构造方法，最后提出一种改进的s v m 训练和模式识别方法，我们称之为“分段” s v m 方法。 北京工业大学理学硕十学位沦文 第2 章统计学习理论 本章将简要介绍统计学习理论的有关知识，包括学习问题的研究历史、学习 问题如何表示( 即如何用数学来描述) ，由此导出一种一般性的归纳原则，称为 经验风险最小化原则( e r m ) ，然后讨论学习过程的界的问题，同时引入函数集 v c 维的概念，构造出各种风险函数的上界，下一章将通过讨论这些上界来发展 一种新的学习机器一一支持向量机( s v m ) 。 2 1 机器学习问题的研究历史 有关机器学习问题的研究历史，它大致可以分为四个阶段，每个阶段分别以 下列重要事件为标志： ( 1 ) 第一个学习机器的创立。 ( 2 ) 学习理论基础的创立。 ( 3 ) 神经网络的创立。 ( 4 ) 神经网络替代方法的创立和研究。 在不同的历史阶段有不同的研究重点和主题，每一个新的发现都振奋人心， 而所有这些研究共同勾画出了人们对于学习问题进行探索的一幅复杂丽又充满 矛盾的画面。 2 1 1 第一阶段：r o s e n b l a t t 的感知机 2 0 世纪6 0 年代，f r o s e n b l a t t 提出了第一个学习机器的模型，称为感知机 模型( 如图2 - 1 ) ，这标志着人们对学习过程进行数学研究的真正开始。 从几何上说，神经元把空间x 分为两个区域：一个是输出y 取值为1 的区 域，另一个是输出y 取值为一1 的区域。这两个区域被超平面： ( 形- x ) 一b = 0 分开。向量w 和标量b 决定了分类超平面的位置。在学习过程中，感知机为神 经元选择适当的系数。遗憾的是，那时候人们并不清楚如何同时为感知机的所有 神经元选择参数。 s 北京工业大学理学硕十学位沦文 x lx jz 3z x 图2 一l 感知机模型 2 1 2 第二阶段：学习问题理论基础的创立 关于感知机的实验广为知晓后，人们很快提出了一些其它类型的学习机器， 如学习矩阵等。与感知机不同的是，这些学习机器从一开始就被作为解决现实中 实际问题的工具来研究的，而没有被看作是学习现象的一般模型。对于应用分析 学派来说，在从构造感知机( 1 9 6 0 年) 到实现后向传播( 1 9 8 6 年) 之间的这段 时间里，没有发生什么特别的事情，但在这段时间里，统计学习理论( s t a t i s t i c a l l e a m i n gt h e o r y ，s l t ) 的发展却是成果累累，主要包括下面四个方面： 经验风险最小化原则的理论 解决不适定问题的理论” 密度估计的非参数方法 算法复杂度的思想 2 1 3 第三阶段：神经网络 1 9 8 6 年，几个作者独立提出了同时构造感知机所有神经元的系数向量的方 法，就是称为向后传播的方法( l e c u n ，1 9 8 6 及r u m e l h a r t ，h i n t o n a n d w i l l i a m s ， 1 9 8 6 ) 。这一方法的思想很简单，它不是用m c c u l l o c h p i t t s 的神经元模型，而是 例如，求解线性算子方程a f = f ，f f 时，即使方程存在唯一解，如果方程右边有一个徽i 、 的变动，如用f f 。6 s ) = ，v s , n 2 ( s u p ( r ( a ) 0 0 卜，w d 单从概念的角度看，此定理就是十分重要的，因为它指出了e r m 原则一致 性的条件是必要的( 和充分的) 取决于函数集合中“最坏”的函数，即：根据此 定理，对e r m 原则的任何分析必须是“最坏情况分析”。 北京工业大学理学硕十学位沦文 2 3 2 函数集的v c 维 下而我们引入描述函数集容量的一个新的概念，即函数集的v c 维，我们先 看指示函数集。 指示函数( 即只有0 和1 两种取值的函数) 集的v c 维定义如下( v a p n i k a n d c h e r v o n e n k i s ，1 9 6 8 ，1 9 7 1 ) ： 定义2 2 ：指示函数集的v c 维 一个指示函数集q ( z ，d ) ，dea 的v c 维，是能够被集合中的函数以所有可 能的2 “种方式分成两类的向量z 。z ，的最大数目，也就是说能够被这个函数 集打散的向量的最大数目。如果对任意的n ，总存在一个n 个向量的集合可以被 函数集q ( z ，口) ，口a 打散，则称此函数集的v c 为无穷大。 有了指示函数集的v c 维的概念后，我们可以如下定义实函数集的v c 维。 定义2 3 ：实函数集的v c 维 设a q ( z ，a ) b ，口人是一个以常数a 和b 为界的实函数集合( a 可以是 一m ，b 可以为+ ) 。考虑指示函数集： l ( z ，a ，) = o q ( z ，口) 一卢 ，口a ，卢( a ，b ) ( 2 4 ) 其中口是阶姻数州加倍麓实函数姒础，o t e a 的v c 维就定义为相应的指示函数集( 2 4 ) 式的v c 维。 2 3 3函数集v c 维的举例说明 下面我们以例子说明函数的v c 维。 n 维坐标空间z = ( z l ，z 。) 中的线性指示函数集 o ( z ，口) ：烈窆口p z p + 吼) 的v c 是n + 1 。例如平面直线的v c 维是3 ，也就 p = l 是说用直线把平面上的不同向量划分为所有可能的两类时，向量的个数不能超过 3 个，否则无法实现所有划分。 1 2 l z 2 区z l z 2 z iz 2 z 3 z 4 图2 - 6 平面上的四个点 图2 - 7 不能用直线把这四个点分开 显然，不能只用直线把 1 ，4 2 ，3 分开，因此用直线把平面上的向量划分 为所有可能的两类时，向量的个数不能超过3 ，即平面直线的v c 为3 。 2 3 4 构造性的与分布无关的界p 1 本节给出风险函数的上界，将在第四节用来构造控制学习机器推广能力的 方法( 这里只给出结果而略去其中的推导过程) 。 情况1 ：完全有界函数集 1 3 北京工业大学理学硕十学位沦文 设爿q ( z ，口) 曰，口a 是完全有界函数集，则下面的不等式以至少( 1 7 7 ) 的概率同时对q ( z ，口) ，d a 的所有函数成立( 包括使经验风险最小的函数) ： 地) r e i n p ( 卅垒型拓 情况2 ：完全有界非负函数集 设0 兰q ( z ，口) b ，口a 是完全非负有界函数集，则下面的不等式以至少 ( 1 一r 1 ) 的概率同时对q ( z ，a ) ，a a 的所有函数成立( 包括使经验风险最小的函 数) ： 脚一咖掣 浮 对于上面两种情况，在v c 维有界而函数集中函数数目无限时 。一h ( 1 n ( 2 n 1 + 1 ) - i n ( 翌4 ) “ f 而在v c 维有界且函数集中函数数目有限时 。：21 1 型二! 塑 其中h 为函数集的v c 维，z 为样本个数，n 为函数集中函数的个数， r e m p ( 口) = q ( z ，口) 。 情况3 ：无界非负函数集 设0 茎q ( z ，口) ，口a 是完全非负无界函数集，则下面的不等式以至少( 1 一玎) 的概率同时对满足条件1 的所有函数q ( z ，口) ，“ea 成立( 包括使经验风险最小 的函数) ： 月( 口) 如盟一 ( 卜a ( p ) r q e ) + 其中u + - m a x ( u ，。) ，口( p ) = ：f j l 。雨p - 1 j p - 1 。 1 4 北京工业大学理学硕十学位沦文 条件1 3 】：存在一个( p ，f ) 对，不等式。u p 型登銎! 型：r 1 一“ l q ( z ，a ) d f ( z ) 成立。 2 4 控制学习过程的推广能力 本节讨论控制学习机器推广能力的理论，这理论的目的就是致力于构造一 种利用小样本向量实例来最小化风险泛函的归纳原则。我们将首先重新引用第三 节得到的构造性的与分布无关的风险函数的上界，然后介绍一种所谓的容许结 构，并在此基础上总结出基于小样本的学习机器的归纳原则，即，结构风险最小 化归纳原则。 2 4 1界的讨论 对数目为，的样本，如果比值丢较小，比如小 2 0 ，则可以认为样本数是较 少的，即认为这样的样本集是小样本。 为了构造针对小样本数的学习方法，需要用到第三节中得到的构造性的界， 如完全有界函数集的界： 脚) 蔓( 口) + 堡掣石( 2 _ 5 ) 和完全有界非负函数集的学习机器推广能力的界： 脚一咖掣 俨 以及采用无界函数集的学习机器推广能力的界： r ( 口) 兰垦! 些( 2 6 ) ( 1 - a ( p ) r 4 e ) + 这些上界都是至少以( 1 7 7 ) 的概率成立的。其中函数集中函数的个数有限 时： 占：2 1 n n - ，l n r 而函数的个数无限时： 北京工业大学理学硕十学位沦文 ( 1 n ( 鲁+ 1 ) 一1 n ( 三) 了。 这样，当亡比较大( 即大样本) 时，都比较小，因此( 2 5 ) 式右边筇二项教 小，式( 2 6 ) 右边的分母较大，总之，此时实际风险r ( a ，) 就接近于经验风险 月。，( 口，) 的取值，这时，较小的经验风险值就能够保证( 期望) 风险的值也较小。 ， 然而，当亡较小( 即小样本) 时，一个小的r 。v ( t z ，) 并不能保证小的实际风 险值，这样，要最小化实际风险胄( d ，) ，就必须保证不等式右边的两项同时最小 化。同时又注意到，不等式( 2 5 ) 右边的第一项取决于函数集中的一个特定的函数， 而第二项则取决于整个函数集的v c 维。因此，如果要对式( 2 5 ) ( 或式( 2 6 ) ) 右 边的两项同时最小化，就必须使v c 维成为一个可以控制的变量。 2 4 2 结构风险最小化 f 而我们将给出一个一般的原则，称为结构风险最小化( s t r u c t u r a lr i s k m i n i m i z a t i o n ，s r m ) 归纳原则，这一原则旨在同时针对经验风险和置信范围这 两项最小化风险泛函。 首先定义一个结构，称为容许结构，定义如下： 定义2 4 设函数0 q ( z ，“) ，口a 的集合s 具有一定结构，这个结构是由一系列嵌套 的函数予集j s r 。= 口( z ，口) ，口ea 。) 组成的，它们满足： s ，匕s ：c s 。，其中结构中的元素满足如下两个性质： ( 1 )每个函数集s k 的v c 维h k 是有限的( 但s 的v c 维可以是无穷大) ， 因此h l h 2 h 。 ( 2 )结构的任何元素s 。或者包含一个完全有界函数的集合： 0 q ( z ，a ) 墨b t ，1 2 八女 或者包含对一定的( p ，f ) 对，满足下列不等式的函数集合： i 北京工业大学理学硐十学位沦义 h n ， ! ( i ( q ( z ，口) 9 d f ( z ) ) ) 9 跚p 瓯蕊瓦广钉胪2 我们把上面定义的这种结构称为一个容许结构。 s r m 原则是统计学习理论的核心内容之一，它把函数集构造成一个容许结 构，使各个函数子集按照v c 维的大小排列。随着子集序号n 的增加，经验风险 的最小值减小，但置信范围增加。s r m 原则就是在每个子集中寻找最小经验风 险，同时在各子集间折衷考虑经验风险和置信范围，使取得的实际风险最小，如 图2 8 所示。 图2 - 8 实际风险示意图 按照s r m 的思想，我们在损失函数集s = q ( z ，口) ，口e 八) 中构造一个容许 结构，再选择这个结构的一个适当的元素s 。和这个元素中的一个函数 q ( z ，a ? ) s 。，使相应的界最小，如式( 2 5 ) ： 脚妙掣f 脬1 此时，界( 2 5 ) 式可以重写为如下简单形式【3 ： 脚j ) 飒”( 口? ) 加玄( 2 。) 北尿工业大学理学坝十学位沦义 右边第一项是经验风险，第二项可以认为是誊信范围。 如果对于一个给定数目的训练数据，我们设计了一个过于复杂的学习机器， 置信范同啦( 如将会增大，此时，即使可以把经验风险最小化为0 ，在测试集卜 k 的错误的样本数目仍然可能很大，这种现象称为过学习现象。之所以出现过学习 现象，一是凼为样本不充分，二是学习机器设计不合理，这两个问题是互相关联 的。下面举一个简单的例子，假设有一组实数样本 x ，y ) ，y 取值在( 一1 ，1 ) z f n ， 那么不论样本是依据什么模型产生的，只要用函数f ( x ，a ) = s i n ( a x ) 去拟合它们 ( d 是待定参数) ，总能够找到一个口使训练误差为零，因为对于函数 f ( x ，盘) = s i n ( 似) ，只要选择适当的参数口，它可以逼近以( 1 ，1 ) 为界的任何函 数，如图2 - 9 所示。 八燃 必战vvv - ：1 图2 - 9 过学习现象 显然，这撑得到的“最优”函数并不能正确代表真实的函数模型。究其原因， 就是试图用一个十分复杂的模型去拟合有限的样本，从而导致丧失了推广能力。 在神经网络中，若对非常有限的样本来说网络学习能力过强，足以记住每个样本， 此时经验风险很快就可以收敛到很小甚至零，但却无法保证它对未来样本能给出 好的预测，学习机器的复杂性与推广性之间的这种矛盾同样可以在其它学习方法 中看到。 为避免过学习( 即为了得到较小的置信区间) ，必须构造v c 维较小的学习 机器；另一方面，如果函数集的v c 维较小，那么就难以逼近训练样本( 即难以 lr 北京工业大学理学坝十学位沦义 得到不等式( 2 7 ) 右边第一项的较小值) ，要得到较小的逼近误差的同时保持较小 的置信区间，就必须适当选择机器的构造，使之反映所面对问题的先验知识。 于是，要用这类学习机器解决面对的问题时，首先必须找到学习机器的适当 结构( 这是在过学习和不良逼近之间折衷的结果) ，然后在这个学习机器中寻找 使在训练数据上错误最小的函数，这种方法可以简单描述如下： 保持置信范围固定( 通过选择一个适当结构的机器) 并最小化经验风险。 同样，最小化不等式( 2 7 ) 式右边可以实行如下策略： 保持经验风险值固定( 比如等于0 ) 并最小化置信区间。 归纳起来，实现s r m 原则可以有两种思路，即有两种策略最小化不等式( 2 7 ) 式右边项： 1 保持置信范围固定并最小化经验风险。 2 保持经验风险值固定并最小化置信区间。 根据这两种不同的策略可以构造不同的学习机器，比如，神经网络就是按第 一种策略构造的学习机器，存下一章我们将讨论通过第二种策略构造的学习机 器，称为支持向量机( s u p p o r t v e c t o rm a c h i n e s ，s v m ) 。 北京工业大学理学硕十学位沦文 第3 章支持向量机( s v m ) 这章讨论的是一种新的通用学习机器，它执行的是s r m 原则的第二种策略， 即保持经验风险值固定并最小化置信区间，发展这样的学习方法，就是我们的理 论在构造学习算法方面的目的。 在神经网络中，我们考虑的是线性决策规则，即分类超平面，下面我们采用 一种特殊类型的超平面，即所谓的最优分类超平面。我们将首先考虑训练数据是 线性可分情况下的最优分类超平面，然后把这种思想推广到线性不可分的情况， 利用构造最优超平面的技术，描述- - g e 新的通用学习机器一一支持向量机，我们 将给出构造支持向量机的具体算法和步骤。 3 1 最优分类超平面 本节我们首先介绍针对样本数据线性可分时什么是最优分类超平面，然后根 据最优分类超平面对样本数据的要求得到最优分类超平面的构造方法，并由此得 到支持向量的概念，再把线性可分情况下的最优分类超平面推广到数据线性不可 分的情况，同时引入核函数的概念，构造一个通用的学习机器一一支持向量机。 3 1 1 最优分类超平面 下面首先介绍最优分类超平面的概念。 定义3 1 ：最优分类超平面 假定训练数据集为( 。，m ) 。，( j ，y ，) ，r ”，_ y ， + 1 ，一1 ) ，可以被一个超 平面兀分开： 兀：x4 - b = 0 ( 3 - 1 ) 如果这个向量集( 指训练数据集) 被超平面没有错误地分开，并且离超平面 最近的向量与超平面之间的距离最大，则称此超平面为此向量集的最优超平面， 或称为最优分类超平面。 显然，对( 3 1 ) 式，和b 乘以相同的系数后仍然满足方程，因此，不失 一般性，可以作如下假设： 对于所有样本x ， m i n i w x 。+ b i = 1 这样，最优分类超平面应该满足如下条件： 形x ，+ b 1 ，当y 。= 1 x ，+ 6 s l ，当y ，= 一1 即：y 。( w - x ，+ b ) 1 根据向量投影的有关性质： ( 云) j 。篙 对于超平面兀，知其法失量为w ，把样本x 看成向量，在超平面兀上任取 一点x o = ( x ? ，x ? ，x ：) 7 ，则x 到平面n 的距离为向量 ( x x o ) = ( _ ) c 1 一x o ，x 。一x ：) 7 在上的投影的绝对值，如图3 - 1 所示： 图31 点到超平面的距离 吼d = l ( x - x 。川= 带 x w x 。w 一 t 1 。网 l 彳+ b l 一 圳 北京l 业大学理学硕十学位沦文 3 1 2 构造最优超平面 要找到l 二节中提到的最优超平面，可以转化为如一f 的二次规划问题： m i n ( 矿) 2 圭缈( 。一：， 【s 7 1 ：y 。 ( x 。) + 6 】1 ，i = l l 显然，此规划是一个凸规划，因此其局部最优解即为全局最优解，为解此规 划，引入l a g r a n g e 函数： 1 f l ( w ，b ，口) = 寺一 a ， ( j f 。r v ) + 6 y ，一1 ) ( 3 3 ) 其中d ，为非负的l a g r a n g e 乘子。 对函数l 关于和b 求偏导，且令其偏导数为0 ，得到鞍点处的，b o ，a 。， 1 = 岛，y x ( 3 4 ) ， 口0 y ，= o ( 3 5 ) j = 1 把( 3 - 4 ) 式和( 3 5 ) 式代入( 3 3 ) 式，得到： i， d 。 ”【( 肖，) + + 口 f _ lj = l = 去口，口，y ，y ，( x 。爿，) 一口， ( x ，- r v ) - b 。口，n + a 。1 j = ij = 1t = 1 ，f， ( 岔，y ，x ) 一b 。y + 口 f ；1i = 1f = 1 ：二w w w 一0 + 5 - 口 7_ ：一去矽+ 窆a ，兰缈 ) 1一 、 因此可以把原二次规划化为如下形式： m a x w ( a ) = 一寺o t 口，”，( x 。x ，) + q k 0 ( 3 6 ) 叠r ：怪哪，：。 j 珈 却 钇栅乩曲 ，!【 日n )y 盯 ， o 对应的向量x ，称为支持向量。则 形。= y 隅x ， x e 支扦同量 即最优超平面的法矢量可以表示为支持向量的线性组合，因此l a g r a n g e 乘子和 支持向量就完全确定了超平面兀，这也是支持向量的命名根据。 3 1 4 问题的求解 根据上面的分析，要构造最优超平面，只需求解二次规戈l j ( 3 6 ) a 设a 。= ? ，口? ) 为此规划问题的解，则基于最优超平面的分类规则就是如 下的指示函数： ，( ) = s g n ( 儿a ，o ( x ，并) + ) i = l 其中b o 可以按如下方式求得： b o = 去【( ，。- x ( 1 ) ) + ( h ，。- ? ，( 一1 ) ) 】 其中，x + ( 1 ) 表示属于第一类得某个( 任意一个) 支持向量。 x ( 一1 ) 表示属于第二类得某个( 任意一个) 支持向量。 北京工业大学理学硕士学位论文 3 1 5 不可分情况下的推广 m ；n 爹( ) 一三，+ c 吝茧 f；i：嚣sw，苫，一舅，z_l，f。c37， 工w , b , a ) 三缈+ c 砉茧+ 妻州【皤；+ 聊+ 6 协一，+ 戛 + 砉n o l ；0 a 堕。0 。 a 6 o l 。o a 善a ? y - 卸 矾。酗劲， c o j y i 一0 将上面三式代入l a g r a n g e 函数中，得到： 五眠a ； 馨m y j ( x i x i ) + 善1 口 第3 章支持向量机( s v m ) 再看原来对l a g r a n g e 函数的优化要求：和b 以及l 最小化，而对和y ；最 大化，因此可以把上式写成统一目标的优化形式 l 眠扣) _ 一主1 弘i 叩( 置x ，) + 善。；= ( ，a 再考虑约束条件： f 条件1 ：善口? ) ，z 。o 条件( 2 ) ：由c 一口j y f 一0 ，得0 s 口fs c 因此，在输入样本线性不可分时，要求最优分类超平面，只需要求解如下的 二次规划： m a x w ( a ) 一一吉芝叩讲y ，。j j ) + q j 1 t = l f 0s 口js c 盯：k 胪犷一。“ 对于0 吼 c ，知道o 0 展开成 k ( “，v ) = 荟仇纯 ) 缈。( v ) 即k ( “，v ) 描：, 1 - z 一i b 中的一个内 积) ，充分必要条件是，对使得 f g2 ( “) d u o 成立。 在s v m 中，满足卜面定理的函数k ( “，v ) 通常称为核函数，可以验证，下列 函数均可作为核函数： x ( x ，y ) = ( x 1 ，) 4 ，d o ( 多项式核函数) k ( x ，y ) ：e x p ( 一! ：二垂) ( 径向矢函数核函数) 2 0 r 利用核函数的技术，就可以构造在输入空间中非线性的决策函数 厂( 片) = s g n ( ( m k ( 置，x ) + 6 ) ， 。v ，为支持向置 它们等价于在高维特征空间中，( ) ，o ：( x ) ，中。( ) 中的线性决策函 数，在线性可分的情况下，通过解决如下的二次规划问题： s i ：口0 口y ，= o 得到决策函数 1 j 一去a ，d ，y ，y ，k ( x x ) + 口 z j ，= i i = 1 = y ，口? 巾( ，) 6 = w 0 o ( x ( 1 ) ) + ，m ( x 4 北京工业大学理学硕十学位沦文 朋) = 刚，k ( x ) + ；【刚，k ( x 卟i ) ) + 叫，k ( x 1 ) ) 】在线 性不可分的情况下，可以通过解如下的二次规划问题 1 ， m a x w ( a ) 一寺叩y ，k ( x ，) + 窆a ， f ，f = 1：1 sf：0口，sc=， d y = 0 口o = ( 口? ，口? ) 甄= y ，窿? 中) 6 = w o 中( 彳4 ( 1 ) ) + 中( 五+ ( 1 ) 同样得到上面形式的决策函数( 系数不同) ： ，( x ) = q 只k ( 置，x ) + 三 m k ( 五，+ ( 一1 ) ) + q 只世( 置，肖t ( + 1 ) ) 3 2 3 用s v m 训练最优分类超平面的算法步骤 用s v m 训练最优分类超平面( 样本空问) 的具体算法如下： 1 。输入训练样本对( x ，y ，) ，其中x ，胄”，y ， l ，一】) 。 2 令 口= y i ( ，j ，) y ，得到正定的实对称矩阵h = ( f ) 。把缈( d ) 表示 成矩阵形式矿陋) = 一要蒯口r + ，口r ，同时约束条件吒y 。：o 也化为 矩阵形式：y a = 0 ，其中：口= ( 口，口，) 为待求的系数向量， i ，= ( 1 , 1 ，1 ) ，y = ( y l ，y ，) a 3 调用数学工具软件m a t l a b 求解二次规划： ( d ) 一三a r i a 7 1 + ，口7 ， s t ：y a 7 = 0 ，矗0 ，得n a = ( 口l ，嘶) 。 4 求q o 对应的样本，并计算出x ， o 的样本数k ，求得= a 。x