（信号与信息处理专业论文）基于核的学习方法及其在人脸识别中的应用研究.pdf

中国科学技术大学博士学位论文 中文摘要 摘要 本文主要研究基于核函数的机器学习方法( 以下简称核学习方法) 的理论、算法和应用。 针对目前核学习方法中存在的一些问题：如何提高现有的核学习算法的速度、性能，如何扩 大核学习方法的应用范围，增加核函数的种类、核函数的选择、核参数的选择等问题，本文 对核学习方法理论展开了较深入地分析和研究，并取得了一些有意义的成果，解决了核学习 方法中存在的一些问题。本文主要研究工作和创新成果如下： ( 1 ) 核学习方法支持向量机( 简称s v m ) 学习算法的研究：探讨了s v m 算法原理和 有解条件，同时分析和比较了现有的几种s v m 学习算法性能。提出了一种快速s v m 增量学 习算法。该算法通过选择那些可能成为支持向量的边界向量以达到减少训练样本的数量和提 高训练速度的目的，在训练阶段，利用所选择的边界向量进行增量学习，该算法在保证s v m 精度和推广能力的同时，能进行快速增量学习。 ( 2 ) 核学习方法中核函数的研究：核函数是核学习方法的核心部分。本文中，我们研 究和分析了核函数与非线性映射以及所映射空间之间的关系。研究了核函数以及核参数对学 习机器性能的影响，并给出了选择核函数的几条原则。最后提出了一类新的核函数自相关 核函数。通过对核函数构成条件的深入研究，我们总结了自相关核函数的构成条件，即所有 能量有限信号( 单位冲激信号除外) 的自相关函数都可以作为核学习方法中的核函数，或所 有在h i l b e r t 空间l ：。j 中函数的自相关函数都可以作为核学习方法中的核函数。并从理论 上给予了证明，实验结果也验证了自相关核函数的正确性和有效性。 ( 3 ) 核主分量分析( 简称k p c a ) 算法的研究：探讨了k p c a 算法原理，并将该算法 应用于特征提取中，通过实验将该算法与其它一些特征提取算法进行了分析和比较。同时提 出了两种基于k p c a 的高性能特征提取方法：“基于全局特征和局部特征组合的特征提取方 法”，该方法将k p c a 所提取特征与i c a 所提取特征进行组合构成高质量的组合特征。“利用 组合核函数提高核主分量分析的性能”，该方法将一个全局核函数与一个新的局部核函数条件 正定( 简称c p d ) 核函数进行台理组合，从而提高k p c a 所提取特征的质量。实验结果验证 了这两种方法的有效性。 ( 4 ) 核f i s h e r 判决分析( 简称k f d a ) 算法的研究：探讨了k f d a 算法的原理，并将 该算法应用于特征提取中，通过实验对该算法与其它一些特征提取算法进行分析比较。提出 了一种快速、简单的基于k f d a 的多类分类算法。该算法简单、准确、快速。并通过一定的 中国科学技术大学博士学位论文 中文摘要 实验比较了我们的算法与常用的两种多类分类算法o n e - t o o n e ，o n e - t o - a l l 的性能，实验结果 验证了我们方法的良好性能。 ( 5 ) 核聚类算法的研究：探讨了k ，均值聚类算法，通过将核学习理论与k _ 均值聚类算 法结合，提出了一种基于c p d 核函数的快速核k 均值聚类算法，并将该算法与基于m e r c e r 核的核聚类算法进行了比较，实验结果显示，我们的方法不仅比k 均值聚类算法的聚类效果 好，而且聚类速度快。与基于m e r c e r 核的核聚类算法相比，两者聚类效果相当，但我们的方 法聚类速度较快。 ( 6 ) 核学习方法在人脸识别上的应用研究：提出了一种基于核学习方法的高性能人脸 识别方法。该方法是核学习方法研究成果的综合应用，方法首先将k p c a 与k f d a 所提取的 人脸特征进行合理组台，构成高质量的人脸组合特征向量，这种特征向量对轻度的光照变化、 姿势变化、表情变化不敏感，这种特征提取方法简单、快速。在识别阶段，选用线性s v m 作为分类器，采用我们的快速增量算法对s v m 进行训练，因此s v m 的训练速度非常快。值 得一提的是。在我们的识别系统中，当有人员增减时或有新增样本时，我们的方法可以很容 易实现增减或进行增量学习，非常实用。 关键词： 核函数，核学习，支持向量机，核主分量分析，核f i s h e r 判决分析，核聚类 人脸识别。 i l ! 里型兰垫查盔兰塑主鲎垡笙三一一 英文摘要 a b s t r a c t t h i sd i s s e r t a t l o nd e a l sw i t h t h ey e s e a r c h e so nt h e o r i e sa n da p p l i c a t i o n s o fk 。”。l - b 8 8 。d l e a r n i n ga 1 9 0 r i t l l m s t h em a i n w o r ka n dc o n t r i b u t i o n so f t h ed i s s e r t a t i o na r es u m m a r i z e d 8 5 f o i l o w s ： ( 1 ) r e s e a r c h e s o n s u p p o r t v e c t 。rm a c h i n e s ( s v m ) l e a r n i n ga l g o r i t h m w e r e s e a r c h e dt h e o r yo fs v m a i l dt h ec o n d i t i o n st oa c q u i r eas o l u t i o no f s v m p r o b l 。m - s e v e r a l k i n d so fa i g o r i t h m s o fs v mw h i c he x i s tp r e s e n t l y a r ec o m p a r e d - w ep r o p 0 5 e d 8t 8 8 t i n c r e m e n t a ls v ml e a r n i n ga l g o r i t h m t h ea l g o r i t h mf i r s ts e l e c t se d g 。v e c t o r st or e d u c et h e n u m b e ro ft r a i n i n gv e c t o r s t h e nt h ea l g o r i t h md o e si n c r e m e n t a ll e a r n i n gb y “s i n g t h e s ee d g e v e c t o r s c o m p a r i n g w i t ho t h e rs v ml e a r n i n ga l g o r i t h m s ，t h ea l g o r i t h m c a nn o to “l yl 。a r nf 8 5 t b u ta l s og i v ea r le x a c ts o l u t i o n - ( 2 ) r e s e a r c h e s o nk e r n e l f u n c t i o n so fk e r n e l - b a s e dl e a r n i n g a l g o r i t h m s k e 。”。l f u n c t i o n sa r ek e yp a r to fk e r n e l b a s e dl e a r n i n ga l g o r i t h m s i nt h ed i s s e r t a t i o n ，w e e 8 e a r c h a n da n a l v s et h er e l a t i o no fk e r n e l f u n c t i o n sa n dn o n l i n e a rm a p p i n g sa n dm a p p 。d5 p a n 。8 b e c a u s et h ec h o i c eo fk e r n e lf u n c t i o n sh a sac r u c i a le f f e c 【o n t h ep e r f o r m a n c eo fl e a r n i n g m a c h i n e s 、w eg i v es e v e r a lr u l e sf o rs e l e c t i n gk e r n e lf u n c t i o n sa n d k e r n e lp a r a m e t e r s t h e nw e p r o p o s e an e wk i n do fk e r n e l f u n c t i o n a u t o c o r r e l a t i o n k e r n e lf u n c t i o n t h e o r y a n d e x d e r i r a e n th a v ev e r i f i e dt h a ta u t o c o r r e l a t i o n k e r n e lf u n c t i o ni sc o r r e c ta n de r i e c t i v 。 ( 3 ) r e s e a r c h e so nk e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ( k p c a ) a l g o r i t h m - w e r e s e a r c ha n da n a l y s et h et h e o r y a n da l g o r i t h mo fk p c a t h e nw ea p p l yk p c a f u r f e 咖r e se x t r a c t i n g t h ep e r f o r m a n c e so fk p c a a n dt h o s eo fo t h e rf e a t u r e se x t r a c t i n g a i g o r i t h m s a r ec o m p a r e d m e a n w h i l ew ep r o p o s e t w oe f f e c t i v em e t h o d so ff e a t “e s e x t r a c t i n g o i st h em e t h o db a s e do nc o m b i n a t i o nf e a t u r e so f g l o b a la n d l o c a lf e a t u r e s t h e m e t h o dc o n s 仃u c t st h eh i g hq u a l i t yf e a t u r e sb yc o m b i n i n g t h eg l o b a lf e a t u r e so fk p c a a n dt h el o c a lf e a t u r e so fi n d e p e n d e n tc o m p o n e n ta n a l y s i s ( i c a ) - t h ee x p e r i m 。n t 。s ”i t 8 i n d i c a t et h em e t h o dc e r t a i n l yi m p r o v e s t h eq u a l i t yo fe x t r a c t e df e a l u r e s a n o t h e rm e t h 。di si m p r o v i n gp e r f o r m a n c eo f k p c ab yu s i n gc o m b i n a t i o nk e r n e l f u n c t i o n s t h em e t h o di m p r o v e sp e r f o r m a n c eo f k p c ab yr e a s o n a b l yc o m b i n i n g al o c a l i i l 中国科学技术大学博士学位论文 英文摘要 c o n d i t i o n a l l yp o s i t i v ed e f i n i t e ( c p d ) k e m e la n d a g l o b a lk e r n e l t h ee x p e r i m e n tr e s u l t s i n d i c a t et h en e wk e r n e lf u n c t i o nc e r t a i n l yi m p r o v e st h ep e r f o r m a n c eo fk p c a ( 4 ) r e s e a r c h e so nk e r n e l f i s h e rd i s c r i m i n a n ta n a l y s i s ( k f d a ) t h et h e o r yo f k f d aa r er e s e a r c h e da n da n a l y s e d a f t e ra p p l y i n gk f d ai nf e a t u r e e x t r a c t i n g ，w e c o m p a r et h ep e r f o r m a n c eo fk f d aa n dt h o s eo fo t h e rf e a t u r ee x t r a c t i n ga l g o r i t h m s f i n a l l y , w ep r o p o s e af a s ta n ds i m p l em u l t i c l a s s i f i c a t i o nm e t h o d t h em e t h o dc a n c l a s s i f ym u l t i c l a s sf a s ta n ds i m p l yc o m p a r i n gw i t ho n e - t o o n em e t h o da n do n e t o a l l m e t h o d ，t h ee x p e r i m e n tr e s u l t si n d i c a t e st h a to u rm e t h o di s c e r t a i n l yf a s t e ra n ds i m p l e r j nc l a s s i f i c a t i o nt h a no t h e rt w om e t h o d s ( 5 ) r e s e a r c h e so nk e r n e l c l u s t e r i n ga l g o r i t h m s a f t e rc o m b i n i n gk - m e a n s c l u s t e r i n ga l g o r i t h ma n dt h et h e o r yo fk e r n e l - b a s e dl e a r n i n ga l g o r i t h m s ，w ep r o p o s ea f a s tk e r n e lk m e a n sc l u s t e r i n gm e t h o dw h i c hi sb a s e do nc p d k e r n e l t h ee x p e r i m a n t r e s u l t si n d i c a t et h a tt h ec l u s t e r i n ge f f e c to f t h ea l g o r i t h mi sb e t t e rt h a nt h a to fk m e a n s a l g o r i t h m ，t h ec l u s t e r i n gs p e e do ft h ea l g o r i t h mi sa l s of a s tt h a nt h a to fk m e a n s a l g o r i t h m c o m p a r i n gw i t ho t h e rk e r n e lc l u s t e r i n ga l g o r i t h m s ，t h ec l u s t e r i n ge f f e c to fa l l a l g o r i t h m sa r ee q u a l i t y , b u tt h ec l u s t e r i n gs p e e do fo u ra l g o r i t h mi sf a s tt h a nt h o s eo f o t h e r a l g o r i t h m s ( 6 ) r e s e a r c h e so nt h em e t h o do ff a c er e c o g n i t i o n i nt h ed i s s e r t a t i o n ，w ep r o p o s ea “o ”e lf a c e r e c o g n i t i o n m e t h o dw h i c hi sb a s e do n k e r n e l l e a r n i n ga l g o r i t h m s p e r f o r m a n c eo ft h em e t h o di s v e r yp l e a s i n g ，a t i e rd e t e c t i n gt h ef a c e so fi m a g e s ，t h e m e t h o de x t r a c t sh i g hq u a l i t yf e a t u r e so ff a c e sb yu s i n gk p c a a n dk f d a t h ef e a t u r e s a r en o to n l yi n c l u d i n ga g r e a td e a lo fi n f o r m a t i o no ff a c ei m a g e s ，b u ta l s oi n s e n s i t i v et o m i n u t ec h a n g eo f i l l u m i n a t i o na n d p o s e ，i nt h es t e po f r e c o g n i t i o n ，c l a s s i f i e r sa r et r a i n e d b yf a s ti n c r e m e n t a ll i n e a rs v m l e a r n i n ga l g o r i t h mw h i c hi sm e n t i o n e di nc h a p t e r2 n d w eh a v ep r e s e n t e dt h ef a c e r e c o g n i t i o ne x p e r i m e n t sb yu s i n go r la n du m i s tf a c e d a t a b a s e c o m p a r i n gw i t ho t h e rm e t h o d s ，t h ep e r f o r m a n c eo fo u rm e t h o di ss u o e r i o rt o t h e s eo fo t h e r m e t h o d s e s p e c i a l l y , o u rm e t h o di ss i m p l e ra n df a s t e rt h a no t h e rm e t h o d s k e yw o r d s ：k e r n e lf u n c t i o n ，k e r n e l - b a s e d l e a r n i n g ，s u p p o r tv e c t o rm a c h i n e s k e r n e l p 7 i “。i p a lc o m p o n e n ta n a l y s i s ，k e m e lf i s h e rd i s c r i m i n a n t a n a l y s i s ，k e r n e i b a s e dc i u s t e r i n g ， f a c er e c o g n i t i o n i v 中国科学技术火学博士学位论文 符号说明 符号说明 原空间( d 维空间) 高维空间 v c 维 概率分布 经验风险 期望风险 置信范围 非线性映射 核函数( 核) 核矩阵 原空间中的向量 高维空间中的向量 原空间中向量 高维空间中的向量 原空间协方差矩阵 高维空间协方差矩阵 原空间内类散度矩阵 原空间类间散度矩阵 高维空间内类散度矩阵 高维空间类间散度矩阵 原空问中训练样本集合 原空间中测试样本集合 高维空间训练样本集合 x z 大写黑体字母 小写黑体字母 白体字母 高维空间测试样本集合 矩阵，向量空间，集合 向量 标量 ，“ ， 力 日厅唯如m如置x州wc 曲 & 蹄 础 主里型兰茎查奎兰塑主堂竺垒奎 茎二兰兰! 鱼 1 1 引言 第一章绪论 机器学习是一种现代智能技术，学习机器通过对一些学习样本( 或数据) 的学习， 从而总结出未知系统的输入和输出之间存在的固有规律，并利用这些规律对未知样本进 行预测和分析。 基于核函数的学习方法( 以下简称核学习方法) 就是建立在统计学习理论i ”1 基础之 上，用于机器学习的新方法，与传统的一些机器学习方法相比，核学习方法【4 4 1 具有很多 新的优点。它在机器学习领域开拓了一个崭新的天地，它在统计学习理论的指导下，已 成功地应用于统计模式识别中，如；目标识别”、文本分类1 1 3 - 1 5 】、时间序列预测1 6 “】、 基于内容的图像分类 1 9 , 2 0 、生物信息处理以及其它应用【2 2 2 ”，无论是在有监督学习和 无监督学习方面都取得了非常好的应用效果，充分展示了此类方法的优越性能。这类学 习机器的主要代表有：支持向量机( 简称s v m ) 、核主分量分析( 简称k p c a ) 以及核 f i s h e r 判决分析( 简称k f d a ) 。对此类方法的研究将会进一步推进统计模式识别领域的 技术进步。产生出更多、更好的识别和分类方法。不断开辟此类方法新的应用领域，克 服现有核学习方法的缺点以改善其性能。提出更多、更好的核学习方法以及提出更多核 函数将是值得我们进一步研究的课题，本文就是围绕着这些问题对核学习方法理论进行 了深入地分析和研究，并将其应用于人脸图象识别中。 1 2 统计学习理论 统计学习理论 1 - s i 是v a p n i k 等人在2 0 世纪7 0 年代所创立的，9 0 年代才完善的针对 小样本情况研究统计学习规律的理论。是传统统计学的重要发展和补充，为研究有限样 本情况下机器学习的理论和方法提供了理论依据。传统的统计学所研究的主要是渐进理 论，即当样本趋于无穷多时的统计性质。而实际中所获得的样本数总是有限的，如果还 是按照传统的统计学中假设样本数趋于无穷时，来推导各种算法，结果所获得的学习机 器的推广能力( 所谓的学习机器推广能力就是学习机器对未知样本的预测能力) 将可链 很差，例如：当样本数很少时，神经网络往往会出现过学习现象。 中国科学技术大学博士学位论文 第一章绪论 统计学习理论被认为是针对小样本统计估计和预测学习的最佳理论，它从理论上系 统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系以 及如何利用这些理论找到新的学习原则和方法等问题。其内容主要包括以下四个方面： ( 1 ) 经验风险最小化原则下统计学习一致性的条件； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建立的小样本归纳推理原则； ( 4 ) 实现这些新的原则的实际方法。 统计学习理论核心思想是：通过控制学习机器的容量实现对其推广能力的控制。基 于这一理论v a p n i k 等人于2 0 世纪9 0 年代发明了著名的支持向量机( 简称s v m ) ，随后 一些核学习方法的研究者又在此基础上提出了一些其它的核学习方法。统计学习理论将 机器学习问题看作是利用有限数量的观察来寻找待求的依赖关系的问题。即：从给定的 函数集中选择出能够最好地逼近训练器响应的函数。机器学习的目的就是能根据给定的 有限学习样本估计出输入和输出之间的固有的依赖关系，使得训练好的学习机器能够准 确地对未知样本进行预测。 1 2 1v c 维 统计学习理论中的一个重要的概念是v c 维 1 ( v a p n i k ，c h e r v o n e n k i sd i m e n s i o n ) ， 它是对函数集学习性能进行描述的一个重要指标。v c 维的定义：一个指示函数集的v c 维，是能够被集合中的函数以所有可能的2 6 种方式分成两类的向量的最大数目h ( 也就 是用这个函数集中的函数能够打散的最大样本集的样本数目) 函数集的v c 维用h 表示。 例如：在露4 中( 一个d 维空间中) ，有向超平面函数集的v c 维是d - i - l ( 如：在二维平 面中，一个有向直线的函数集的v c 维是d + 1 = 3 ，它有2 3 = 8 种方式将3 个数据点打 散) ，如下图所示： o 卜义 o 图1 - 1 在二维空间且2 中三个样本点被有向直线打散( 8 种方式) 2 卜 l 卜 0 o o 叉。 也。 中国科学技术大学博士学位论文 第一章绪论 函数集越复杂，则此函数集的v c 维就越大。函数集具有有限的v c 维是学习过程 一致收敛的充要条件。 1 2 2 机器学习模型 机器学习问题可表示为，已知变量y 与输入x 之间存在一定的未知依赖关系，印存 在一个未知的联合概率p ( x ，y ) ，在典型的两类分类问题中，学习机器根据n 个独立同分 布( 概率分布未知) 训练样本对：( x 1 , 儿) ，k ，儿) x x y ，y = 1 ，+ 1 ，估计出 一个函数x 。y ，使得函数，能正确地分类任一个未知样本x 。函数f 可以通过 最小化下面的期望风险求得： n l e ：f l ( f ( x 。w ) ，如( 置y ) ( 1 】) 其中i 是损失函数，w 是函数的广义参数，e ( x ，) 是概率分布。在模式识别中，0 1 损 失函数的基本定义是； 魄咖，= 依震暑 c j 一：， 斟j - 2 机器学习基本搂型 一般来说，一个好的学习机器，对于相似的输入，总是可以获得相似的输出。 1 2 3 经验风险最小化原则 在( i 1 ) 式中r 因为概率分布p g j ，) 未知，所以不能直接最，j 、化期望风险，只能 根据训练样本和函数集的属性估计出一个最佳函数，虽简单的方法就是通过最小化下 中国科学技术大学博士学位论文 第一章绪论 面的经验风险( e m p i r i c a lr i s k ) 皿。= 丢喜w ( 1 3 ) 这种估计最佳函数。用经验风险的最小值来代替期望风险的最小值就是所谓的经 验风险最小化( e m p i r i c a l r i s k m i n i m i z a t i o n 简称e r m ) 原则。概率论中的大数定理说明， 在一定条件下，当样本数趋于无穷多时，经验风险r 一在概率上趋近于期望风险r ，但 并不能保证当经验风险矗最小时的i ，+ 与期望风险r 最小时的w 。是同一个值，更不 能保证经验风险丑【1 , v ) 趋近于期望风险r ( ，”) 。在早期的神经网络研究中，一味地 追求经验风险r w 最小，学习机器的推广能力并不好，甚至当经验风险冠。越小，学 习机器的推广能力反而变差，这就是所谓的过学习现象。因此，对于有限样本情况，要 想获得推广能力很好的学习机器，不能只是简单地追求经验风险r 一最小，必须寻求其 它的优化准则。 1 2 4 学习机器推广能力的界 统计学习理论指出，学习机器的实际风险( 期望风险) 是由两部分组成 ，假定h 是某函数集的v c 维，丑。是经验风险，对所有的占 0 ，经验风险和实际风险至少以 概率l 一占满足下式： r + 即学习机器的实际风险( 期望风险) 是由两部分组成： 胄( w ) k ( w ) + 吖鲁) ( 1 4 ) ( 1 5 ) 其中，不等式右边的第一项是经验风险；第二项是置信范围( c o n f i d e n c ei n t e r v a j ) w 是权向量，n 是样本数，h 是v c 维。 主里型兰垫查查兰堡主堂垡望苎 丝二：兰! ! 鱼 j 7 | | 1 7 o0 10 2 “3 n ：v c 彗样本蠹6 。7。8。9 n n = v c 雏， 奉奉敲 图1 - 3 置信范围是v c 维的单调增函数 当h n 较大时，置信范围较大，用经验风险最小化取得的最优解可能具有较差的推 广性；当样本数较多时，h n 较小，则置信范围就会很小，经验风险最小化的最优解就 接近于实际的最优解。如果，对于一个给定数目的训练数据，设计一个过于复杂的机器， 即逼近函数集复杂( v c 维较高) ，则置信范围将会很大，这时即使可以将经验风险最小 化为0 ，在测试集上的错误率仍会很高，这种现象叫做过学习。为了避免过学习现象( 为 了获得小的置信范围) ，我们尽量构造v c 维小的学习机器，例如：线性函数的v c 维就 较小。 1 2 5 结构风险最小化原则 由上面的分析知，要最小化期望( 实际) 风险，我们必须同时对上式右边中的两项 进行最小化，不等式右边的第一项经验风险取决于函数集中的个特定的函数，第二项 取决于整个函数集的v c 维。在设计分类器时，我们不但要使经验风险最小化，还要使 v c 维尽量小，从而缩小置信范围，使得期望风险最小。结构风险最小化归纳原则1 , 2 6 1 ( 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 ) 就是针对经验风险和置信范围这两项进行期望 风险最小化的归纳原则。即：s r m 是对给定数据逼近的精度和逼近函数的复热性之间的 一种折衷。 结构风险最小化原则：首先将函数集j = 沙g ，w l ，q 分解成子集序列，即： e 围范信量 中国科学技术大学博士学位论文 第一章绪论 s 1c s 2 s t c c s ( 1 - 6 ) 使得各个子集按照置信范围的大小排列，也就是按照v c 的大小排列，即 h l h 2 - sh k ， ( 1 - 7 ) 这样当选择经验风险与置信范围之和为最小的子集时，就可以达到期望风险最小，这个 子集中使经验风险最小的函数就是所求的最优函数。这就是结构风险最小化原则。 下图显示了期望风险和经验风险以及置信范围的关系曲线。要想获得期望风险的最 小化，我们必须兼顾经验风险和置信范围，在它们之间寻找一个最佳点。 图1 - 4 期望风险与经验风险和v c 维的关系示意图 1 2 6 学习机器的实现方法 由上面的分析可知，在针对实际问题时，若要最小化期望风险，我们必须首先找到 学习机器的适当结构，然后在这个机器中寻找使得在训练数据上错误最少的函数。我们 有两种方法可以完成对期望风险的最小化： ( 1 ) 保持置信范围固定( 通过选择一个适当构造的机器) ，然后晟小化经验风险： ( 2 ) 保持经验风险值固定( 例如：对于线性可分情况，经验风险为零) ，然后最小化置 信范围。 传统的神经网络所采用的就是第( 1 ) 种方案，即首先确定网络的层和节点，也就是 固定了置信范围中，然后最小化经验风险，来达到最小化实际风险的目的。因为人们缺 6 中国科学技术大学博士学位论文 第一章结论 乏对置信范围。的了解，所以神经网络结构的选择往往凭经验，而且经常不能获得很好 的效果。 而支持向量机所采用的是第( 2 ) 种方法，即在保证经验风险为一定值时( 如线性可 分时，经验风险等于0 ) ，通过最小化置信范围。来最小化期望风险，即通过选择简单的 线性函数集使得置信范围。较小，从而最小化实际风险【1 - 4 】。 支持向量机就是基于结构风险最小化原则来实现期望风险最小化的机器学习算法， 其算法思想是：对于两类分类问题，当两类样本线性可分样本时，选择一个最优线性超 平面( 因为超平面v c 维较小) 使得两类样本不仅线性可分，而且两类分开的间隔最大。 当两类样本线性不可分时，首先通过某种事先选择的非线性映射将原空间的数据映射到 一个高维特征空间( 可以是无穷维) 中，然后在这个高维的特征空间中构造最优的分类 超平面( 因为超平面v c 维较小) 。在1 9 9 2 年，v a p n i k 等人发现：为了能在这个高维的 特征空间中构造最优的分类超平面，并不需要以显式形式来考虑特征空间，只需要能够 计算支持向量与高维特征空间中向量的内积核函数。这一伟大发现奠定了核学习方法的 理论基础，为核学习方法的研究和发展提供了理论保障。 1 3 核学习方法介绍 继核学习方法支持向量机( 简称s v m ) 发明之后，核学习方法的研究者们又不断提 出颞的核学习方法，近年来又出现了如：核主分量分析( 简称k p c a ) 、核f i s h e r 判决分 析( 简称k f d a ) 等，这些方法都获得了较好的应用效果，如：用于图象特征的提取以 及不同模式分类等。目前，在机器学习领域，对核学习方法及其应用研究非常活跃。 这类核学习算法的基本思想f 4 , 6 1 是：对于原空间中线性不可分的数据，首先经过一个 非线性映射j r 4 _ h ，x - 9 扛) ，将原空问的数据映射到一个高维的特征空间( 也 称核空间，维数可以无穷大) 中，只要选择满足m e r c e r 条件的核函数k ，就可以在这个 特征空间中隐含地进彳亍运算，实现数据在高维空间中的线性分类( 或近似线性分类) 这 样就可以利用一些线性算法来实现相对于原空间为非线性的算法，从而提高算法的性麓。 利用核函数k 代替原空间中的内积，就对应于将数据通过一个映射，映射到某个高 维的特征空间中，高维特征空间是由核函数定义的。选定了一个核函数，也就对应地定 义了一个高维特征空间。特征空间中所有的运算都是通过原空问中的内积核函数来隐含 实现。即：任何( 线性) 只用到标量内积的算法都可以通过一个核函数在高维特征空间 中国科学技术大学博士学位论文 第一章绪论 中隐含地进行运算。我们可以利用此思想，在特征空间中实现一般的线性算法，但却能 实现相对于原空间来说是非线性的算法。这将会大大地提高学习算法的效率，改进现有 算法，提高各类模式识别任务的识别率。 。 1 4 核学习方法和传统模式识别方法的主要区别 核学习方法和传统模式识别方法的思路是不同的p j 。传统方法进行模式识别时，首 先应用一些特征提取和选择方法，将原空间中的特征降维，然后进行识别。而核学习方 法则正相反，首先将原空间的数据通过一个非线性映射，映射到一个高维空闯( 可以是 无穷维) 中，以求在高维空间中问题变得线性可分( 或近似线性可分) ，然后在这个高维 空间中利用核技巧进行有关的运算。有人可能会提出问题，在这个高维的特征空间中， 进行运算是不可能的，即所谓的维数灾难。需要强调的是：升维后，只是改变了内积运 算，并没有使算法的复杂性随着维数的增加而增加，而且在高维空问中的推广能力并不 受维数影响。值得注意的是：在核学习方法中，我们并不是在整个高维特征空间中进行 运算，丽是在一个相对较小的线性子空间中进行运算，它的维数最多等于样本的数量。 在核学习方法中，这个子空间是通过训练自动选择的，我们甚至不必知道具体的非线性 映射。特征空间的内积运算完全通过输入空间中定义的内积核函数来隐含地实现，这也 是核学习方法可行的关键。 1 5 核学习方法的主要特点 ( 1 ) 核学习方法具有坚实的理论基础核学习方法以统计学习理论为指导。 ( 2 ) 核学习方法具有较好的推广能力利用核学习方法所训练的学习机器具有非常好 的推广能力，因为它遵守了结构风险最小化原则。 ( 3 ) 核学习方法比较稳健核学习方法的抗干扰能力较强。 ( 4 ) 核学习方法具有强大的非线性和高维处理能力核学习方法利用核函数在高维空 间中处理非线性问题时，很好地解决了高维空间中维数灾难问题。 8 主里型兰垫查查堂堡主堂焦堡奎 笙二童堕鱼 1 6 核学习方法的研究现状 目前，国内外对核学习方法的研究正处于方兴未艾阶段，对此类算法的研究主要集 中在以下几个方面： ( 1 ) 如何进一步提高s v m 学习算法的速度。包括新的和各种改进的s v m 算法研 究，目的就是在保证精度的同时，提高算法的速度。 ( 2 ) 利用核学习方法的思想，进行其它非线性算法的研究。将核学习方法的思想进 一步应用于其它学习方法( 包括有监督和无监督学习) 中，目的是提高原有算法的性能 和效率。 ( 3 ) 探索核学习方法新的应用领域和对现有算法进行有效改进。将核学习方法应用 于实际中，以解决那些传统方法所不能解决的问题，同时结合实际问题对核学习方法作 出适当的修改以期达到最佳效果。 ( 4 ) 核学习方法中核函数的研究。包括产生和发现新的核函数，以及如何根据实际 情况选择核函数以及确定核函数的参数等。 总之，所有的研究都是为了进一步提高核学习方法的性能和有效性以及拓展其应用 范围。核学习方法的创新研究，将会给机器学习领域带来更多更好的方法。 1 7 本文主要研究内容 为了能充分展示和发掘核学习方法的优越性能，本文对核学习方法进行了较全面和 深入地研究，从基本理论、算法到实际应用。具体的研究内容如下： 第一章：绪论。介绍了统计学习理论中的一些基本概念，核学习方法的基本概念、 特点和基本理论。 第二章：主要探讨了支持向量机算法的基本理论。分别研究了s v m 用于分类和回 归的算法。介绍了现有的各种s v m 优化算法，并分析和比较了这些算法的性能，最后 提出了一种快速s v m 增量学习算法，并通过实验验证了算法的有效性。 第三章；对核学习方法中的核函数进行了深入地研究，分析了核函数与所映射空间 之间的关系，分析了核函数的构造，说明了核函数的本质。研究了核函数及其参数的选 择对学习机器性能的影响；在充分研究核函数构成条件的基础上，提出了一类新的核函 数自相关核函数，即所有能量有限信号( 单位冲激信号除外) 的自相关函数都可以作 9 中国科学技术大学博士学位论文 第一章绪论 为核学习方法中的核函数。并从理论上给予了证明。同时提出了根据训练样本的分布 选择自相关核函数的指导性原则。 自相关核函数不仅扩大了核函数的选择范围，而且可以与样本的分布联系起来，从 而为选择合适的核函数提供指导性的原则。而目前选择m e r c e r 核函数只能用诸如 c r o s s v a i i d a t i o n 方法，通过大量的实验来选择。因此自相关核函数的发现对核学习方法 的发展和应用有着重要意义。 第四章：主要探讨了k p c a 算法理论和应用。研究了k p c a 算法与其它一些传统的 特征提取方法之间的区别，通过大量的实验充分验证了k p c a 方法的优良性能。在此基 础上提出了两种基于k p c a 的特征提取方法。实验验证了我们方法的有效性。 第五章：主要探讨了k f d a 算法理论和应用。通过将k f d a 算法应用于数据和图象 的特征提取中，发现k f d a 所提取的特征非常有利于数据的分类。在充分研究k f d a 算 法的基础上，我们提出了一种基于k f d a 的快速多类分类方法，并通过实验验证了我们 方法的有效性。 第六章：主要研究了k 一均值聚类算法。利用核学习算法的基本原理，对现有k 均值 算法进行改进，提出了一种基于c p d 核函数的快速核k 一均值算法，不仅提高了聚类的 效果，而且提高了聚类的速度。 第七章：将核学习方法应用于人脸识别中，利用核学习方法，提出了一个高性能的 脸谱识别方法，较好地解决了脸谱识别中轻度人脸光照变化、姿势变化、表情变化等问 题给脸谱识别所带来的困难。同时，我们的人脸识别方法速度快、方法简单、识别率高， 菲常适合于人脸识别的实时处理系统。 第八章：全文总结与展望。 1 0 中国科学技术大学博士学位论文 第二章核学习方法支持向量机算法研究 第二章核学习方法支持向量机 2 1 引言 算法研究 支持向量机2 7 3 2 1 ( s u p p o r tv e c t o rm a c h i n e 简称s v m ) 是建立在统计学习理论基础之 上由v a p n i k 等人发明的一种核学习机器，由于其在解决小样本问题时所表现出的卓越性 能以及具有强大的非线性和高维处理能力，而倍受关注。核学习方法$ v m 学习算法是 一种有监督学习方法，就是已知训练样本的类别所进行的机器学习方法。s v m 不仅可以 进行样本的分类，而且可以进行函数的回归( 实值函数的估计) 。 2 2 支持向量机分类算法 s v m 就是遵循