（计算数学专业论文）基于支持向量机的人脸识别技术.pdf

华中科技大学硕士学位论文 摘要 人脸识别是当前模式识别和图像处理领域的热点和难点，而且因其具有广泛 的实际应用背景，开展对人脸识别的研究意义重大人脸作为一个非刚体，具有形 变大、影响因素多且易受干扰的特点而且因为实际条件的限制，不可能对每个人 都采集很多样本，相对于其图像向量维数而言，是一个小样本问题对于这样一个 高维数、非线性的小样本问题，许多传统的模式识别方法都容易出现过学习或欠学 习现象支持向量机专门针对小样本问题设计，基于统计学习理论的结构风险最 小化原则，选用最优分类超平面作为判别函数，以最大化分类间隔为条件。将分类 问题转化为一个简单的二次规划问题，使问题具有唯一的极值点通过引入核函 数，巧妙将线性不可分问题投射到高维空间后转化为线性可分。而且因为采用核 机制，问题的计算复杂度并没有增加通过选取不同的核函数，许多传统的分类方 法都可以在支持向量机里找到相应的作用机理支持向量机在解决小样本问题方 面已经表现出许多特有的优势，并已成为当前国际上模式识别领域的首选分类器 本文对支持向量机技术的理论基础进行了简单的介绍，分析了该技术中核函数的 作用机理，并利用该技术，着重考察t 4 , 波变换和k l 变换结合支持向量机技术在 人脸识别方面的作用。通过对主分量分析和小波技术在人脸识别方面的应用加以 改进，分别得到核主分量分析和小波与支持向量机结合进行人脸识别的方法。在 两个人脸库上的实验结果表明，对两种传统方法进行的改进是卓有成效的。 关键词：人脸识别支持向量机最优分类面核函数主分量分析小波变换 i 华中科技大学硕士学位论文 a b s t r a c t a saf o c u sa n dd i f f i c u l t yi nt h ep a t t e r nr e c o g n i t i o na n di m a g ep r o c e s s i n gf i e l d s ， f a c er e c o g n i t i o n ( f r ) r e s e a r c hh a sa ni m p o r t a n ts i g n i f i c a n c e ，e i t h e r f o ri t s w i d e l y p r a c t i c a la p p l i c a t i o n h u m a n f a c e sh a v el a r g ev a r i a t i o ni ns h a p ea td i f f e r e n tt i m e m a n y i n f l u e n c e s ，s u c ha sl i g h t i n g ，b a c k g r o u n d ，f a c i a le x p r e s s i o n sa n d f a c i a ld e t a i l s ，w i l le a s i l y a f f e c tt h er e c o g n i z er e s u l t l i m i t e db yt h ep r a c t i c e ，w ec a n tc o l l e c ts u f f i c i e n tf a c e i m a g e sf o re v e r yp e o p l e c o m p a r ew i t h t h ef a c ei m a g ev e c t o rd i m e n s i o n ，f ri sas m a l l s a m p l ep r o b l e m w h e ns o l v i n gt h i s s m a l ls a m p l ep r o b l e mw i t l l 1 i g hd i m e n s i o na n d n o n l i n e a r ，m a n yt r a d i t i o n a lp a t t e r nr e c o g n i t i o nm e t h o d sw i l lt e n dt o o c c u i fo v e r f i t t i n g p h e n o m e n o n s u p p o r tv e c t o rm a c h i n e s ( s v m ) i ss p e c i a l l yd e v i s e dt o s o l v et h es m a l l s a m p l ep r o b l e m b a s e d o nt h e s t r u c t u r a lr i s km i n i m i z a t i o n ( s r m ) p r i n c i p l ei 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 y , s v ms e l e c t st h eo p t i m a ls e p a r a t eh y p e r p l a n ea st h es e p a r a t e f u n c t i o n t h e o p t i m a ls e p a r a t eh y p e r p l a n e i st h e h y p e r p l a n e t h a te i t h e r c o r r e c t l y s e p a r a t et h es a m p l es e to rg e t t h eb i g g e s tm a r g i nb e t w e e nt w oc l a s s e s t h u st h es e p a r a t e p r o b l e m c a nb ef o r m u l a t e da saq u a d r a t i c o p t i m i z a t i o np r o b l e m s a t i s f i e d s i m p l e r e s t r i c t i o n t h eq u a d r a t i cp r o b l e mh a ss i n g u l a rg l o b a lm a x i m u m p o i n t b yi n t r o d u c i n g t h ek e r n e lf u n c t i o n ，t h en o n l i n e a rs e p a r a t es a m p l e sa r ep r o j e c t e di n t oa h i g hd i m e n s i o n s p a c e ( s oc a l l “f e a t u r es p a c e ”) n e ws e p a r a t ep r o b l e mi ss o l v e di nt h el i n e a rs e p a r a t e f e a t u r es p a c e a p p l i e dt h ek e r n e lf u n c t i o n ，t h ec o m p u t ec o m p l e x i t yi sn o te n h a n c e d u s i n gd i f i e r e n tk e r n e lf u n c t i o n s s v mw o r k sa st h es a r n ea ss o m et r a d i t i o n a lp a a e m r e c o g n i t i o nm e t h o d s i th a sb e e nt h ep r e f e r e n c ec l a s s i f i e ra tp r e s e n t 。t h i sa r t i c l eu s e t h ek - lt r a n s f o r ma n dw a v e l e tt r a n s f o r mt oe x t r a c tf a c ei m a g ef e a t u r e ，t h e nc l a s s i f y t h e mb a s e do n s v m r e c o g n i t i o nr e s u l td e m o n s t r a t e st h ee f f e c l i v eo f t h es y s t e m k e y w o r d s ：f a c er e c o g n i t i o n ，s u p p o r tv e c t o rm a c h i n e s ，o p t i m a ls e p a r a t eh y p e r p l a n e k e r n e lf u n c t i o n ，p r i m a r y c o m p o n e n ta n a l y s i s ，w a v e l e tt r a n s f o r m i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承 担。 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阙。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于不保密口。 ( 请在以上方框内打“j ”) 学位论文作者签名：1 母知1 j 日期细睁牟月，谓 指导教师签名：沙：匕 日期：沙睁中月，归 1 华中科技大学硕士学位论文 1 1 课题来源和意义 1 绪论 计算机人脸识别技术也就是利用计算机分析人脸图像，进而从中提取出有效 的识别信息，用来“辨认”身份的一门技术人脸识别技术应用背景广泛，可用 于公安系统的罪犯身份识别、驾驶执照及护照与实际持证人的核对、银行及海关 的监控系统及自动门卫系统等虽然人类的人脸识别能力很强，能够记住并辨别 上千个不同人脸，可是计算机则困难多了表现在：人脸表情丰富；人脸随年龄 增长而变化；人脸所成图像受光照，成像角度及成像距离等影响；而且从二维图 像重建三维人脸是病态( i l l - p o s e d ) 过程，目前尚没有很好的描述人脸的三维模型另 外，人脸识别还涉及到图像处理、计算机视觉、模式识别以及神经网络等学科， 也和人脑的认识程度紧密相关这诸多因素使得人脸识别成为一项极富挑战性的 课题支持向量机( s v m ，s u p p o r tv e c t o rm a c h i n e s ) v l a d i m i rn v a p n i k 基于统计学 习理论( s e t , s t a t i s t i c a l l e a r n i n g t h e e r y ) 提出”，对小样本、高维数的模式识别问 题十分有效，因而也逐渐成为模式识别的首选分类器而且传统的模式识别方法 都可以在支持向量机里找到对应的作用机制，所以，将用于人脸识别的诸多方法 与支持向量机技术结合起来进行就是自然的选择本论文主要考察了支持向量机 的作用机制应用于人脸识别研究的具体情况，并给出了相应的识别结果和分析试 验采用的人脸库有两个：个是a t & t 人脸库，也叫o r l ( o l i v e t t ir e s e a r c h l a b o r a t o r y ) 人脸库，由英国剑桥大学a t & t 实验室建立该人脸库有4 0 个人每人 1 0 幅共4 0 0 幅人脸图像，具备不同的光照、表情、发型、睁闭眼和有无眼镜等， 并且人脸有一定的侧转角度。每幅图像均为1 1 2 9 2 的灰度图像，图1 1 给出了部 分图像。 l 华中科技大学硕士学位论文 图1 1a t & t 人脸库的部分图像 另个是y a l e 人脸库，y a l e 大学建立该人脸库包含1 1 个对象的1 6 5 幅正面 人脸图像，图像格式为g i f 口每个人的1 5 幅图像包含有不同的表情和配置：左光、 右光和中心光，高兴、悲哀，眨眼，惊讶，有无眼镜和正常打吨等。图像规格为 3 2 0 2 4 3 大小的灰度图像。下面是该图像库的部分图像( ”) 川”。 图1 - 2y a l e 人脸库的部分图像 1 2 人脸识别的研究背景和现状 计算机人脸识别技术从2 0 世纪6 0 年代开始研究，9 0 年代更成为科研热点早 期人脸识别研究主要有两大方向：一是提取人脸几何特征的方法，包括人脸部件 规一化的点间距离和比率以及人脸的一些特征点，如眼角、嘴角、鼻尖等部位所 构成的二维拓扑结构；二是模板匹配的方法，主要是利用计算模板和图像灰度的 自相关性来实现识别功能目前的研究也主要有两个方向：其一是基于整体的研 究方法，它考虑了模式的整体属性，包括特征脸( e i g e n f a c e s ) 方法、s v d 分解的 方法、人脸等密度线分析匹配方法、弹性图匹配( e l a s t i cg r a p hm a t c h i n g ) 方法、隐马 尔可夫模型( h i d d e nm a r k o vm o d e l ) 方法以及神经网络的方法等；其二是基于特征分 析的方法，也就是将人脸基准点的相对比率和其它描述人脸脸部特征的形状参数 或类别参数等一起构成识别特征向量第一种基于整体脸的识别不仅保留了入脸 2 华中科技大学硕士学位论文 部件之间的拓扑关系，而且也僳留了各部件本身的信息，而基于部件的识别则是 通过提取出局部轮廓信息及灰度信息来设计具体识别算法基于部件的识别比基 于整体的识别来的直观，它提取并利用了最有用的特征，如关键点的位置以及部 件的形状分析等，而对基于整个人脸的识别而言，由于把整个人脸图像作为模式， 那么光照、视角以及人脸尺寸会对人脸识别有很大的影响，因此如何能够有效的 去掉这些干扰很关键虽然如此，但对基于部件分析的人脸识别方法而言也有困 难，其难点在于如何建立好的模型来表达识别部件近年来的一个趋势是将人脸 的整体识别和特征分析的方法结合起来，如k i n m a nl a m 提出的基于分析和整体 的方法，a n d r e a s l a n i t i s 提出的利用可变形模型( f l e x i b l em o d e l s ) 来对人脸进行解释 和编码的方法等 1 3 本论文的编排和结构 这篇文章主要考察了一些基于支持向量机的人脸识别方法，通过对这些方法 的研究，提出了人脸识别的一些新途径，并设计了一个自动人脸识别系统。 第一章是绪论，主要说明一下本论文的研究意义和由来，并介绍了人脸识别 的研究背景和现状、当前国际上关于人脸识别使用的主要方法以及本论文要用到 的几个具体的人脸库 第二章介绍了本论文使用的人脸识别方法一支持向量机的理论基础，即v n v a p n i k 等人提出的统计学习理论该理论的具体内容很多，我们只简略的介绍了 与支持向量机理论紧密相关的部分内容。 第三章重点介绍支持向量机的基本思想和算法支持向量机的核心思想有两 个：一个是最优分类面，另个是核函数最优分类面保证支持向量机具有良好 的分类性能和泛化能力，核函数则巧妙的将线性不可分问题转化为线性可分问题， 且计算复杂度没有增加。 第四章具体介绍了利用主分量分析法结合支持向量机技术对人脸进行识别的 步骤和算法第节介绍主分量分析的概念和相关性质，第二节介绍用主分量分析 华中科技大学硕士学位论文 和支持向量机进行人脸识别的算法，第三节对实验结果进行了分析。 第五章根据小波变换在图像压缩和特征提取方面的特有优势，将第四章的主 分量分析改用小波变换来对人脸特征进行提取，再结合支持向量机来识别人脸 第一节介绍小波和小波变换的定义，第二节介绍了多分辨分析和m a l l a t 算法第三 节将小波变换和支持向量机用于人脸识别，并在最后对实验结果进行了分析对比 第六章是总结，对全文进行了一个拔高式解释，并指出了本文的后续研究方 向。 最后是参考文献和致谢。 一一 4 华中科技大学硕士学位论文 2 统计学习理论 随着计算机的日益普及，人类社会的几乎各个方面都不可避免的被它打上了 深深的烙印，可以毫不困难的预言，未来的社会是计算机技术的天下，因而机器 学习也就成为日益重要的问题所谓机器学习，就是研究如何从些观测数据( 样 本) 出发得出( 模拟) 目前尚不能通过原理分析或实验得到的规律，并利用这些规律 去分析客观对象，对未来数据或无法观测的数据进行预测这种( 基于数据的) 机器 学习问题可以这样来描述： 前提：关系的确存在( 重在特征) 已知：训练样本( x 1y 1 ) ，( x 2 ，y 2 ) ，( x 。，y 。) 求： 分类机器m ：厶( x ) ，岱八 要求：m 不但能正确拟合已知的( x ，y ) 对，且能对新的符合同样规律的x 正 确预测出y = 厶( x ) 目前关于机器学习的方法大多是基于统计学的，而统计学是一种渐进理论， 即研究当样本数目趋向于无穷大时的统计特性，而我们所面对的实际问题大多是 小样本问题，即相对于其维数来说，给定的样本数据很少。在小样本问题上再采 用基于统计学的方法就存在理论上的缺陷。统计学习理论就是一种专门研究小样 本统计学习规律的理论，v n v a p n i k 等人早在2 0 世纪六七十年代就开始研究， 九十年代取得重要进展，得到了广泛重视，而支持向量机就是一种基于统计学习 理论的新的通用学习方法。很多学者认为，统计学习理论和支持向量机方法正在 成为继神经网络后机器学习领域新的研究热点，并将推动机器学习理论和应用有 重大发展。 华中科技大学硕士学位论文 2 1 经验风险最小化原则下统计学习一致性的条件 在机器学习问题中，为了，得到对训练器响应最好的逼近函数( 分类器) ，就要度 量在给定输入x 下训练器响应y 与学习机器给出的响应五( x ) 之间的损失或误差 l ( y ，厶( x ) ) 。考虑损失的数学期望值 r ( a ) = i z ( y ，厶( x ) ) d p ( x ，y )( 2 - 1 ) 它就是风险泛函( 风险函数) 。学习的目标就是在联合概率分布函数p ( x ，y ) 未 知的情况下寻找函数厶( 工) ，使之具有最小风险泛函尺( 口) 。 实际应用问题中，经常把风险泛函r ( 口) 替换为所谓的经验风险泛函 r 一( 甜) 2 吉萋阮( z 卜y ( 2 - 2 ) 通过寻找具有最小经验风险泛函r e m p ) 的函数厶( x ) 来使问题得到解决的 原则被称作经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ) 归纳原则，简称e r m 原 则。e r m 原则在机器学习过程中具有决定性的作用，是目前大多数统计学习方法 的理论基础。 对于基于经验风险最小化原则的学习过程，它在什么时候能够取得最小的实 际风险( 即能够推广) ，而什么情况下不能是我们首先要关心的问题。这个问题也就 是研究经验风险最小化学习过程一致性的充要条件。下面我们就给出统计学习理 沧对该问题的一系列结果。 设正( x ) 是对给定的独立同分布观测x ，x ：，_ 使经验风险泛函 胄e ”( 咖寺善l 厶( 叫i 最小化的函数。 定义2 1 ；口果t n n 个序列依概率收敛于同一个极限，即 6 华中科技大学硕士学位论文 月( d 。j j 蝶月( 口) ，斗o 。) r 。，( 口，) 鸟瑰i r ( 口) ，( n 。) ( 2 3 ) f 2 4 ) 则我们说e r m 原则对函数集厶( x ) ，口a 和概率分布函数p ( z ) 是一致的。( 参 见图2 - 1 ) i n f r 似) 图2 1 如果期望风险和经验风险都收敛到最小可能的风险值 则学习过程是一致的。 也就是说，一个e r m 方法，如果它提供一个函数序列厶( x ) ，= 1 , 2 ，对这 个序列来说期望风险和经验风险都收敛到最小可能的风险值，则这个e r m 方法是 一致的。( 2 - 3 ) 式保证了所达到的风险收敛于最好的可能值，( 2 4 ) 式则保证了可以在 经验风险的取值基础上估计最小可能的风险。 但这种一致性的传统定义也包括了非平凡一致性这种情况。 假设我们已经建立了某个函数集兀( x ) ，口a ，在这个函数集上e r m 原则是 不一致的a 考虑另一个扩展的函数集，它包括了这个函数集和个额外的函数 妒( z ) ，假设该函数满足不等式 7 华中科技大学硕士学位论文 聪a ) 妒【。) ，v x 显然对这个扩展的函数集来说，e r m 原则就是一致的了。事实上，对任何 分布函数和任意数量的观测，经验风险的最小值都将在函数p ( x ) 之上取得，而它 也给出了期望风险的最小值。 为了建立一种依赖于函数集的整体特性( 容量) 的e r m 方法一致性理论，我们 重新下一致性的定义如下： 定义2 2 对函数集五( 芏) ，盘a ，定义其子集a ( c ) 如下： a ( c ) = k ：肛( x ) 卯( x ) c ，口e a 如果对函数集的任意非空子集a ( c ) ，c ( o 。，。) ，都有 2 惑且一( 口) 上一点f 1 r ( 口) ，竹斗o o ( 2 - 5 ) 成立，则我们说e r m 方法对函数集厶( x ) ，口a 和概率分布函数p ( z ) 是非平凡一 致收敛的。 以下所说的一致性都是指的非平凡一致性。 于是我们给出以下定理 定理2 1 设函数集兀( x ) ，d a 满足条件 a j 厶( x ) 卯( z ) 兰凹，( 爿r ( 口) b ) 那么，e r m 原则一致性的充要条件是：经验风险r 。幢) 在函数集厶( x ) ，口a 上 在如下意义下一致收敛于实际风险r m ) ： r 、 ! i m 尸t 8 u p ( r ( a ) 一r 。，( 口) ) s = o ，v 占 0( 2 6 ) k口e j 我们把这种致收敛称作一致单边收敛。 这个定理指出，e r m 原则一致性的条件是必要的( 和充分的) 取决于函数集中 “最坏”的函数，即对e r m 原则的任何分析都必须是“最坏情况分析”。 一一 8 华中科技大学硕士学位论文 与一致单边收敛相对应的是一致双边收敛，即式( 2 6 ) 变成如下形式： r 怒p s u p lr ( 口) 一r w ( 口) j 5 _ o ，v e 0 ( 2 7 ) l 口a j 一致双边收敛包含了一致单边收敛的情况，但在机器学习问题中，我们只要 求最小化经验风险时的一致性，却不关心最大化经验风险时的一致性。因此不需 要一致双边收敛总是满足。一致单( 双) 边收敛的充要条件都要建立在函数集的熵这 一概念的基础之上。 指示函数集的熵 “ 设正( z ) ，口a 是一个指示函数集( 指示函数是只取0 和1 这两个值的函数1 ， 考虑样本 x l ，x 2 ，x n 定义一个量“( x ；，z ：，矗) ，它代表用指示函数集中的函数能够把给定的样本分 成多少种不同的分类。我们用这个量来表征函数集正( x ) ，a a 在给定的数据集上 的多样性。 a a n 上- 说，用样本z ，* ：，r ，x 。和函数集厶( z ) ，口a ，我们可以得到一个n 维超立方体，n “( x l ，x ：，r 。) 就是这个立方体上不同的顶点数目。 我们把值 h “( 。】，一，h ) = i n n “，z 2 ，- - ，以) 叫做随机熵，它描述了函数集在给定数据上的多样性。h “( 一，矗) 是一个随机 数，因为它是建立在独立同分布的数据之上的。考虑随机熵在联合分布函数 e ( x 一，x 。) 上的期望： “( ，) = e l n n “( 。l ，一，x 。) 我们把这个量称作指示函数集厶( r ) ，口e a 在数量为r i 的样本上的熵，它依赖于函 一一 9 华中科技大学硕士学位论文 数集厶( z ) ，a a 、概率测度以及观测数目n ，反映了给定指示函数集在数目为n 的样本上期望的多样性。 实函数集的熵 定义2 3 设爿厶( x ) b ，口a 是一个有界损失函数的集合，用这个函数集和训 练集x l ，x 2 ，x 。可以构成下面的r l 维向量集合： g ( 口) = ( 厶( x 1 ) ，一，：( z 。) ) ，d a 这个向量集合处在n 维立方体之中，并且在c 度量( 或在上。度量) 下有一个有限的 最小s 一网格。令n = n “( 占；一，x n ) 是向量集g ) ，口a 的最小s 一网格的元素数 目，它是一个随机变量。其对数 日“( 并j ，x o ) = i n n “( 盒工【，一，石。) 称作函数集a 兀( x ) 曰，d a 在样本x ，x ：，x 。上的随机v c 熵随机v c 熵的 期望 日“( 自，) = e i n n “( 品x 1 ，x 。) 称作函数集a 厶( x ) b ，d a 在数量为i 1 的样本上的v c 熵。它是对指示函数集 的熵的定义的推广。 利用v c 熵的概念，我们可以得到函数集的一致收敛的条件。 定理2 2 致双边收敛( 式( 2 7 ) ) 的充分必要条件是等式 。l i m 堡竽- o ，v 占 。( 2 - 8 ) 成立。 定理2 3 对完全有界函数集厶( x ) ，口a ，经验均值一致单边收敛于其期望( 式 ( 2 6 ) ) 的充分必要条件是：对任意的正数万，叩和占，存在一个满足式 1 0 华中科技大学硕士学位论文 厶( x ) 一c ( x ) o ，对v x ， 胍。f c ( z ) 妒( 。m 2 _ 9 的函数集五。( x ) ，a + a ，使缛其在n 个样本上的v c 熵满足下面的不等式： l i m 譬竽 占卜坤 ( 华 f 弘 p i 1 tsup型 占 p | 删删【卜 占鲰即 ( 华一钏弘蚴 这两个收敛速度的上晃都要依赖于分布( 因为在构造退火熵函数时用到了观测分布 函数) ，注意到对任何分布函数，生长函数不小于退火熵，我们可以得到与分布无 关的界 ，蚓m 删一；喜删卜s 卜x p f ( 堡产 0 陋切 p i1t s u p型 。l 4 p i 州小m 卜f “ 塑l 上4 ) f p jf 这些界都以至少1 - r 1 的概率取得，并且可以很容易的推广到实函数集上去。 但是，这些学习机器推广能力的界主要是概念性的而不是构造性的，不能直 接用来构造算法。为了使它们具有构造性，我们必须找到对给定的函数集计算其 退火熵和或其生长函数的途径。这就是函数集的v c 维的概念。 一 1 2 ， ，、l p xe 华中科技大学硕士学位论文 函数集的v c 维 ( 1 ) 指示函数集的v c 维 一个指示函数集六 ) ，口a 的v c 维，是能够被集合中的函数以所有可能的 2 h 种方式分成两类的向量_ ，h 的最大数目h ，也就是能被这个函数集打散的向 量的最大数目。如果对任意的i 1 ，总存在一个n 个向量的集合可以被函数集 丘( z ) ，口a 打散，那么函数集的v c 维就是无穷大。 ( 2 ) 实函数集的v c 维 设a 厶( x ) 冬占，口a 是一个以a ，b 为界的实函数集合( a 可以是o 。，b 可 以是。) 。我们考虑它的指示器集合 i ( x ，口，p ) = e f o ( x ) 一卢k 口a ，( 爿，b )( 2 1 5 ) 其中o ( z ) 是阶跃函数 比，= 艇? 实函数集a 厶( 工) 口，口a 的v c 维就定义为相应的指示器集合f 2 1 5 ) 的 v c 维。 例1 n 维坐标空间z = 亿，z n ) 中的线性指示函数集合 脾m 协p = l 矿 厶( z ) = 臼 口，z ，+ 【j 的v c 维是 = ”+ 1 ，因用这个集合中的函数可以最多打散胛+ 1 个向量。 1 3 华中科技大学硕士学位论文 图2 2 平面中直线的v c 维等于3 ，因为它们能打散3 个向量而不能打散4 个 例如向量2 1 ，2 ，不能被直线与向量z z ，z 一分开 2 3 小样本归纳推理准则和实现这些新的准则的实际方法 对于数目为f 的样本，如果比值f h 删1 练模式数目与学习机器函数的v c 维 的比值) 较小，我们就认为样本数是少的，即认为这种样本集是小样本。 e r m 原则是从处理大样本数问题出发的，而对于小样本问题，一个小的经验 风险并不能保证小的实际风险。利用前面得到的关于学习机器推广能力的界的结 论，有 ， r ( a ) r 。 ) + 中e ) ( 2 - 1 6 ) 仃 其中第一项是经验风险，第二项是置信范围。 要最小化实际风险，就要对上述不等式的两边同时最小化。不等式f 2 1 5 ) 的第 一项取决于函数集中的一个特定的函数，第二项则取决于函数集整个的v c 维。所 以要对这两项进行最小化，就要使v c 维成为可以控制的变量。 我们提出一个一般的原则，称作结构风险最小化( s r m ) 归纳原则，它旨在针对 1 4 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 经验风险和置信范围这两项最小化风险泛函。 设函数丘( x ) ，口ea 的集合s 具有一定的结构，这一结构是由一系列嵌套的函 数子集s 。= 厶( x ) ，d ea 。 组成的，它们满足 s 1c s 2c c s 。c ( 2 _ 1 7 ) 其中，结构的元素满足下列两个性质： ( 1 ) 每个函数集s 的v c 维h 。是有限的，因此h i h 2 k ( 2 ) 结构的任意元素邑或者包含一个完全有界函数的集合 0 ，口( x ) b k ，a 或者包含对一定的( p ，靠) 满足下列不等式的函数集合： 氅婴p lipsup鼠，胪： = _ 1 一sf l ，p z a t 丘 i 以( x ) d p ( x ) “1 我们把这种结构叫做一个容许结构。 s r m 原则就是在使风险的上界最小的子集s 。中选择使经验风险最小的函数 o ) 。它提供了在对给定数据逼近的精度和逼近函数的复杂性之间的一种折衷。 随着子集序号n 的增加，经验风险的最小值减少，但决定置信范围的项却增加。 s r m 原则通过选择子集最将这两者都考虑在内，子集s 。的选择是使得在这个子集 中，最小化经验风险会得到实际风险的最好的界。 有两种最小化不等式( 2 1 6 ) 右边的方法。 第一种方法是确定一个v c 维为某个h 的容许函数集，对于给定数量，的训练 数据，h + 的值确定了学习机器的置信范围( 去) 。因此选择一个适当的结构元素就 是一个对特定数目的数据设计学习机器的问题，在学习过程中这个机器最小化界 ( 2 1 6 ) 式的第一项( 经验误差) 。 华中科技大学硕士学位论文 如果对一个给定数目的训练数据，我们设计了一个过于复杂的机器，则置信 7 范围庐( ) 将会很大，这时即使我们可以把经验风险最小化为零，在测试集上的错 门 误数目仍可能很大。这种现象叫做过学习或者过适应。为了避免过学习现象，我 们需要构造v c 维小的学习机器。但另一方面，如果函数集的v c 维小，那么就难 以逼近训练数据( 难以得到式( 2 ，1 7 ) 第一项的小值) 。于是，要在得n d 的逼近误差 的同时保持小的置信范围，我们必须适当选择机器的构造( 这是在过学习和不良逼 近之间折衷的结果) ，然后在这个机器中寻找使在训练数据上错误数最小的函数。 这种最小化方法可以简单描述如下： 保持置信范围固定( 通过选择一个适当构造的机器) 并最小化经验风险。 第二种方法则可以这样表述： 保持经验风险值固定( 比如等于零) 并最小化置信范围。 实际上，实现第一种方法的学习机器就是神经网络，而实现第二种方法的学 习机就是支持向量机。具体的实现方法( 算法) ，神经网络的可以参考关于此方面的 相关资料，支持向量机的我们在第三章讲述( 1 ) ，( 3 ) ，( 5 ) 。 华中科技大学硕士学位论文 3 1 结构风险最小化 3 支持向量机 3 1 1 经验风险和期望风险 对于一个两类的模式识别问题，学习过程可以简单的表述为：假定输出变量 和输入变量之间存在一个未知联合概率p ( x ，y ) ，则要求根据n 个独立分布观测样 本( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x 。，y 。) ，在一( 指示) 函数集 厶：口a ) ，厶：足”寸 - 1 ，1 中 求出最优函数正眈：口ea ，使得预测的期望风险泛函 r ( c t ) = f 吉1 i o ( x ) 一y l d p ( x , y ) 最_ 、。 传统的机器学习方法是基于经验风险最小化原则的，但人们发现，当训练样 本数有限时，赢接最小化经验风险 1，1 r 。= 勺丘( 一) 一y ，i 5 i = l ， 实际上并不能保证能达到一个最小的实际风险( 即：在训练集上的错误率最小并 不意味着测试集上也能达到错误率最小) 。某些情况下，经验误差过小反而会导致 推广能力的下降，这就是过学习问题。学习机器对未来输出进行预测的能力称作 推广性，具有很好推广性的学习机器才是有意义的。 出现过学习现象的原因主要是由于学习样本不充分和学习机器设计不合理。 当试图用一个复杂的模型去拟合有限的样本，必然会丧失推广能力。有限样本下 学习机器的复杂性与推广性之间总存在矛盾：机器的复杂性高，必然会导致其推 广性差：反之，一个推广性好的学习机器，其分类能力必然不够强。于是，设计 一个好的学习机器的目标就变成如何在学习能力和推广性之间取得一个平衡，使 得在满足给定学习能力的前提下，如何提高其推广性。 华中科技大学硕士学位论文 3 1 2 结构风险最小化原则 所谓结构风险最小化原则( sr m ：s t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ) n 5 1 就是在确定的置信范围内，寻找最小经验风险。随着函数子集复杂度的增加，置 信范围会增大，而经验风险会减小。选择最小经验风险与置信范围之和最小的函 数子集，就可以达到期望风险的最小，这个函数子集中使经验风险最小的函数就 是要求的最优函数。 结构风险最小化原则基于下述事实：对上述学习问题，对任何口a ，学习机 器的风险泛函的上界 ， r ( a ) r 。缸) + 中) 至少以1 一刁的概率取得，其中o ( ) = 、 n ，参数h 称为函数集的vc ( v a p n i k c h e r v o n i n k i s ) 维，它描述了学习机器指示函数集的容量。对二类分类问 题，h 是学习机器的指示函数集中的函数以所有可能的2 “种方式分成两类的向量 墨c 岛c 墨，h l 蔓h ：岛 图3 ，l 结构风险最小化原则示意图 1 8 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = ；= 在结构风险最小化原则下，一个分类器的设计过程包括以下两方面的任务： ( 1 ) 选择一个适当的函数子集( 使之对问题有最优的分类能力) ；( 2 ) 从这个子 集中选择一个判别函数( 使经验风险最小) 。第一步相当于模型选择，丽第二步则 相当于在确定了函数形式后的参数估计。 在机器学习的过程中，使用结构风险最小化原则代替经验风险最小化原则， 能很好的解决过学习和欠学习问题。 3 2 最优分类面 支持向量机就是基于结构风险最小化原则的一种分类方法，其模型选择是选 取超平面集合作为分类函数子集s + 。设线性可分样本集为( x ，y ，) ，i = 1 ，n ， x r “，y + 1 ，一1 ) 是类别标号。d 维空间中线性判别函数的一般形式为 g ( x ) = w - z + b ，分类超平面方程为w x + b = 0 。目标是找出个最优分类超平面 ( o s h ：o p t i m a ls e p a r a t eh y p e r p l a u e ) ，将样本集分开。能分开样本集的超平面当然 有可能不止一个，我们要找的最优超平面要求不仅能将两类样本点无错误的分开， 而且还要求使得分开的样本点到超平面的距离( 称作间隔：m a r g i n ) 最大我们将判 别函数进行归一化，使两类所有样本都满足 g ( x ) l ( 只要样本集是线性可分的， 我们就总可以做到这一点) ，使离分类超平面最近的样本的l g ( x ) l = l ，这样分类间 黼z z 2 州卜因此使间隔最大等价于使州i 最小；要求分类面对所有样本正确 分类，即满足： y 。 ( w 工，) + h i 1 2o ，i = 1 , 2 ，一，n( 3 1 ) 因此，满足上述条件且使州j 最小的分类面就是最优分类面。 上述寻找最优分类面的问题实际上归结为一个二重二次规划问题 m i n 翔w 1 9 华中科技大学硕士学位论文 s u b j e c t t oy ， ( w x 。) + 6 卜1 o ，i = l ，2 ，一，n 、v 、。 i t 、 臼 3 l o - 八：、 。 、 、 7 、( w jx ) + b = 0 图3 2 最优分类超平面示意图，中间实线为最优分类面 虚线上的向量为分属于两类的支持向量 针对每个条件引入相应的l a g r a n g e 乘子口，( a ，o ) ，得l a g r a n g e 函数 m i n 抑1 2 一塾( ( w 噶) + 6 ) _ 1 ) s t d ，0 ， y ， ( w x 。) + 6 卜1 0 , i = 1 ，2 ，一，月 f 3 - 2 1 ( 3 3 ) 这是一个二重二次规划问题，对w ，6 求最小而对口求最大。问题的解在l a g r a n g e 函数的鞍点处取得： 等= | f w | i 一塾一。，豢= 一窆i - - i 刚，= 。 2 0 华中科技大学硕士学位论文 耳口 口，y ，珀y ，= 0 f 3 4 1 为支持向量( s v s ：s u p p o r tv e c t o r s ) ，从而w = 口，y ，一。这也是支持向量机名称 m i n 如w 卜窆q ( m ( ( w 一) + 6 ) 一1 ) ” =圭f睦口，y，x，|j2一喜口。cy。cc丕n口。y，z，z，+。，一， = 吉叩”( 一) 一咿肼y 小一，) 一6 刚，+ 口， = 口，一丢a 。a ，y ，y ，( x i , x 1 ) 所以m a x 一寺叩m y j ( x i ，x ) + 吒y ，= 0 引入核函数： k ( x ，) = x i ，x j ) ( 一般的，k ( x ，y ) = ( x ，y ) ) ，内积运算可由核 函数代替，只要事先指定了核函数，就可以求解这个简单的二次规划问题，解得口， 再代回( 3 4 ) 求出w 。至于b ，可由下式求出： 6 = 一号( w ，z ，+ x ，) = 一寻口，y ，( ( _ ，x ，) + ( 一，。，) ) 其中x ，是分属于两不同类的任意一个支持向量。 当然，实际情形不一定存在最优分类超平面，这时可引入松弛因子 一_ 2 l 华中科技大学硕士学位论文 ( s l a c k v a r i a b l e s ) 善或惩罚函数来推广上述过程7 y ， ( w x 。) + 6 l 一善，孝，o ，i = 1 , 2 ，一， 相应的优化问题变为： 1 ” m i n + m t w m t 2 + c 孝，一口，( y ，( ( w - x ，) + 6 ) 一1 + 孝，) 一 f = if = 1 ( 3 5 ) 这里的c o 是一个正则化常数，决定了经验误差和复杂度的平衡点，并控制对错 分样本的惩罚。 上述问题最后归结为： m a x 一昙v t , c t y y , y y ( x i ，x j ) + 窆 s t 0 口，c ( i = 1 ，一，n ) m = 0 由优化问题的k t ( k u h n t u c k e r ) 条件得 盘，= 0 j y ；f ( x ，) l ，口”必，= 0 0 口， c j y 。f ( x 。) = 1 ，口”嘴，= 0 口，= c jy ，f ( x ，) 1 ，d ”始0 这里关于s v m s 的一个很重要的性质就是：问题的解在口，中是稀疏的，即大多数 模式位于边距区( m a r g i na r e a ) 之外，最优的口，都为0 。正因如此，s v m s 才能起 作用并能应用于高维大型数