（应用数学专业论文）核机器理论及在人脸识别中的应用.pdf

摘要 人脸识别早在2 0 世纪6 0 年代就引起了人们的研究兴趣近几年，它在安 全验证系统、信用卡验证、档案管理系统、人机交互系统等领域有着广泛的应 用前景，已经成为计算机视觉和模式识别领域的个研究热点人脸识别中的 一个关键问题就是设计有效的分类算法核机器学习是现在比较流行的一种 学习算法，主要有支持向量机( s v m ) 、核主成分分析( k p c a ) 、核f i s h e r 判 别分析( k f d ) 本文主要讨论目前比较流行的核学习算法，阐述它们之间的区别和联系 相比其它的学习算法，s v m s 有较好的推广能力和解的稀疏性因此，我们将 核f i s h e r 判别分析展成类似支持向量机的数学模型，使之也具有稀疏性此 外，我们还利用误差修正码( e c o c ) 改进了多分类s v m ，降低了多分类s v m 的求解难度在人脸识别的仿真实验中，我们用改进的s v m 算法与其它的核 学习算法进行比较，实验结果表明这种算法具有较高的识别率和稳定性 本文总共分为五个部分：第一部分，介绍了核函数与其相关的特征空间 第二部分，介绍了核主成分分析的无监督学习第三部分，分析并改进了基于 f i s h e r 判别分析的核学习机器第四部分，简要介绍了支持向量机的理论，采 用误差修正码改进了l s - s v m 多分类算法第五部分，通过人脸识别的仿真实 验测试改进的s v m 算法的有效性，并与其它的核学习算法进行比较 关键词 m e r c e r 核；主成分分析；f i s h e r 字l 别分析；支持向量机；误差修正码 i i i a b s t r a c t f a c er e c o g n i t i o nh a sb e e ns t u d i e ds i n c e1 9 6 0 s i th a sb e c o m eah o tp o i n ti n m a c h i n el e a r n i n ga n dp a t t e r nr e c o g n i t i o n ，b e c a u s ei th a se x t e n s i v e l ya p p l i c a t i o n p r o s p e c t si ns a f e t yc e r t i f i c a t i o ns y s t e m ，c r e d i tc a r dc o n f i r m a t i o n ，d o c u m e n tm a n a g e m e n ts y s t e m ，e t c o n eo ft h em o s ti m p o r t a n tp r o b l e m si nf a c er e c o g n i t i o ni s t od e s i g ne f f e c t i v ec l a s s i f i c a t i o na l g o r i t h m s o v e rt h el a s tf e wy e a r s ，k e r n e l b a s e d l e a r n i n gm a c h i n e s ，e g ，s u p p o r tv e c t o rm a c h i n e s ( s v m s ) jk 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 n dk e r n e lf 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 ) ，h a v ea r o u s e d c o n s i d e r a b l ei n t e r e s ti nt h ef i e l d so fp a t t e r nr e c o g n i t i o na n dm a c h i n el e a r n i n g t h i sa r t i c l em a i n l yd i s c u s s e s t h ep o p u l a rk 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 ，e l a b o r a t e st h e i rd i f f e r e n c ea n dr e l a t i o n s h i p c o m p a r e dw i t ho t h e rk 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 ，s v m sh a v ep r e f e r a b l eg e n e r a l i z a t i o na n ds p a r s i t y s o ，w ep r e s e n ta s u p p o r tv e c t o r sm a c h i n ef o r m u l a t i o nt ok p c aa n dk f d m u l t i c a l s ss v mi sa l s o d i s c u s s e dw ed e c o m p o s eam u l t i c a l s ss v mp r o b l e mi n t os e v e r a lt w o - c l a s sl s - s v m p r o b l e m sb a s e do ne c o c t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h m h a sh i g h e rr e c o g n i t i o nr a t ea n ds t a b i l i t y t h i sa r t i c l ei sd i v i d e di nf i v ep a r t s ：t h ef i r s tp a r ti n t r o d u c e st h ek e r n e la n d f e a t u r es p a c e i np a r tt w o ，b a s e do 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 sw es t u d y u n s u p e r v i s e dm a c h i n el e a r n i n g i np a r tt h r e e ，w ei m p r o v ek e r n 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 i np a r tf o u r ，w ei n t r o d u c et h et h e r o yo fs v m ，a n dm a i n l yd i s c u s sl s - s v m f i n a l l y lw ei n t r o d u c et h ec u r r e n tr e s e a r c ha b o u tf a c er e c o g n i t i o n ，a n dh a v ec a r r i e d o nt h es i m u l a t i o ne x p e r i m e n t k e yw o r d s m e r c e rk e r n e l ；p r i n c i p a lc o m p o n e n ta n a l y s i s ；f i s h e rd i s c r i l n i n a n ta n a l y s i s ；s u p p o r t v e c t o rm a c h i n e s ；e r r o rc o r r e c t i n go u t p u tc o d e s i v 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明t 所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他 个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本声明的法律后果由本人承担。 论文作者签名：；名、d l 豸 签名日期；凶一肄6 月7 日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即：按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供耳录检索与阅览服务；学校可以采用影印、缩印、数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容。( 保密论文在解密后遵守此规定) 论文作者签名：弓台l 备 签名日期t 友一0 年b 月7 日 导师签名 签名日期 菇撅隧 2 曲锌月7 日 特征空间与核 m i n s k y 和p a p e r t 在2 0 世纪6 0 年代明确指出线性学习机器计算能力有 限总体上，现实世界复杂的应用需要有比线性函数更富有表达能力的假设空 间换言之，就是目标概念通常不能由给定属性的简单线性函数组合产生，而 是应该一般地寻找待研究数据的更抽象的特征自v a p n i k 等人于1 9 9 5 年提出 支持向量机1 3 6 】，随后它被成功地应用于非线性分类和函数估计支持向量机 最重要就是引入了与m e r c e r 定理相关的正定核 s c h 5 1 k o p f 在 3 】中做了大量 有关核学习方法的工作 1 1 特征空间 给定训练集x i i n ，锄z ，给定一个非线性映射，将输入空间老映射 到特征空问h ： 击：z _ h 。一 ) ， 这样输入空间的原始数据被映射到高维的特征空间“中，由于特征空间h 可 能是无限维的，而且我们需要在这个空问中刻划正交性因此为了更好的刻 划这个空间，我们常常可以将其看成h i l b e r t 空间在本论文中我们总认为州 是h i i b e r t 空间 定义1 1 样本集在特征空间h 中的协方差算子 ，n 露= 寺( ( q ) 一m g ) ( 巧) 一m 8 ) t ， 类问散度算子 霹= 丙1 l i ( r n ? 一 ) ( m ? 一m 孵 = 1 和类内散度算子 c h 础= 面1 ( ( 。“) 一m 蜥( z t j ) 一m ” i = l j = 1 其中记。订为i 类的第j 个训练样本，k 是i 类的训练样本的数目，m ? 是第 i 类样本的均值，嘲；是总训练样本的均值 】 通过上面的定义，我们容易证明霹= 霹+ 础 定义1 2 称矩阵算子a 是半正定的，如果对任意的u = ( u h 一，“。) 7 r n ， 有 n ，a u = a ( x i ，x j ) u i u j 0 i , j = l 定理1 1 彩，露和础都是h i l b e r t 空问“中的自共轭半正定算子 在h i l b e r t 空间中，半正定算子的每个特征值都是非负的由定理1 1 可 知霹，韶和础的非零特征值都是正的，又它们是自共轭算子，则 ( p ，醪妒) = ( 四妒，妒) 垒 p t 5 雪妒0 ， ( 妒，础妒) = ( 离妒，妒) 垒妒7 ，观妒o 定理1 2 ( h i l b e x t - s c h m i d t 定理 3 5 】) 若a 是h f l b e r t 空间上的一个紧共轭 算子，则它的特征向量系构成h 的一组标准正交基 定理1 3 ( f 4 4 j ) 矩阵算子是半正定的，则存在着n 个非负特征值和互相正 交的单位特征向量 t ；饥= ( n ，一，。h ) t ，l l 饥| | = 1 ，t = 1 ，n 使得 a ( 町) = a t l v t j ，i ，j = 1 ，n = 1 例1 1 考虑二维输入空间的情况，假定关于问题的先验知识提示相关信 息已经编码到自由度为2 的单项式的形式因此，要试图将问题在一个特征 空间中表示，一个可能的映射是： ( 2 ；1 ，2 ) 一( z l ，z 2 ) = ( 。；，z ；，z l z 2 ) 同样的方式，我们若想使用自由度为d 的特征，就得给出( “弋“) 维的特征空 间，很快特征空间的维数变得不可计算使用这种类型的特征空间需要一种特 殊的核技术，它是将数据隐式映射到特征空间爿中 在下一节，我们可以在特征空间中利用核函数对定理1 3 推广得到m e r c e r 定理 2 1 2 核函数 核学习机器的思想是将数据映射到高维的特征空间，寻找特征空闻的线 性学习机器而这种线性学习机器在对偶空问是以特征映射内积的形式出现 的，此时内积对应着原始空间的某个核函数通过选择恰当的核函数来代替内 积，可以隐式地将训练数据非线性映射到高维空间核的使用使得将数据隐式 表达为特征空间，从而越过了本来需要的计算特征映射的问题所以核是有效 运用高维特征空间的关键 1 2 1m e r c e r 核 定义1 3 映射 蜀：爿x 爿_ r ( x ，t ) 一k ( x ，t ) 记j 毛( t ) = k ( x ，t ) ，对每个固定。爿，j 0 ( - ) 是爿上的函数若k ( z ，t ) = k ( t ，z ) 对所有( x ，t ) z 刀成立，则称k 是对称的若k 同时还关于两个变量连 续，则称k ( t ，。) 为核函数 下面是几种常见的核函数； 多项式核k ( 。，x i ) = ( 。戤) + 1 1 d ， r b f 核脚，蜘= 唧f 一峻笋) 然后我们从内积具有对称性中得到启发： k ( 。，z ) = 曲( z ) - ( z ) ) = ( ( z ) - ( 。) ) = g ( z ，。) ， 于是可以在h i l b e r t 空间通过为每个特征引入权重九推广内积，得到； ( 口( z ) t j 5 ( z ) ) = 九也( 。) 幽( z ) = k ( x ，。) t = l 定理1 4 ( m e r c e r 定理【2 5 】) 令石是r “的紧子集假定k 是连续对称函 数，存在积分算子t k ：l 2 ( x ) 一l 2 ( x ) ，使得 ( 7 k ，) ( ) = 7k ( ，z ) ，( z ) 如， 是正的，也就是； 耳( 毛z ) f ( x ) f ( z ) d x d z 0 ，v f l 2 ( x ) ， 3 对所有的f l 2 ( z ) 成立然后可以将k ( x ，z ) 展成一个一致收敛的序列，这个 序列由强的特征函数如l 2 ( x ) 构成，归一化使得 i c j l i l ：= 1 ，并且0 ， 则有： k ( z , z ) = 奶扛) 奶( z ) 7 = 1 定义1 4 设函数k ：zx z - - - 4 r 满足条件： ( 1 ) k 是对称的； ( 2 ) 对任意z 1 ，。爿，g r a m 矩阵 k = ( 甄，) ) 乙：i ， 满足z “，z t k x 0 ，则称耳为正定核进一步，若k 连续，则称其为 m e r c e r 核 多项式核，r b f 核都是m e r c e r 核，此论文中如果不作特殊说明所指的核 都是m e r c e r 核 1 2 2 再生核 一个学习机器总是在一定的函数集上实现某种算法的，函数集的类型和 性质很大程度上决定着算法实现的难易程度给定的函数空间称为假设空间 ( 模型函数集) ，其中的每个函数均称为假设s v m 属于核机器学习的范畴， 不过它选择的核为再生核，它的假设空间是由这个核导出的再生核希尔伯特 空间( 记为r k h s ) 定理1 5 ( 2 5 1 ) 设函数耳：疋疋+ 酞是m e r c e r 核，则存在定义在z 上 的连续函数组成的希尔伯特空间h 耳满足下面| 陛质， v t z ，v ，( ) 7 k ，有，( z ) = ，( ) ，k ；( ) ) 日 我们把满足这个性质称为再生隍，满足再生性的核被称为再生核我们把 h 叫做由核导出的再生核希尔伯特空间 下面我们来考察7 - k 的结构，令蜀是爿刀，r 的m e r c e r 核，定义积 分算子 7 k ，= 7g ( x ，z ) ，( z ，) d z j 记扎和圣；( z ) 分别是殛的特征值和特征函数根据m e r c e r 定理有 o 。 g ( x ，z ) = 奶( z ) q ( z 气 7 = i 4 令南( z ) = 、呜( z ) 则 考虑函数集 在，中定义内积 k ( x ，z 7 ) = 如( 。) 奶( 。7 ) j = l ，= ，：，( z ) = q 咖) ) j = l ， 、 ( q 奶 ) ，如奶扛) ) = q b 、j = 1j = l h j = l 则，关于上面定义的内积是一个r k h s ，即，是由核导出的再生核希尔伯 特空间“不难验证再生性成立： ，。 。 、 ( ，( z ) ，k ( x ，。，) ) 日= ( q 如( z ) ，由( z ) 屯( 。) ) 、j 2 l j = l h = a j c j ( x 7 ) = ，( 。，) 1 2 3 核函数的构造 确定一个新的对称函数是一个核函数的关键条件在于它在任意有限点集 上定义的矩阵是半正定的应用这个条件确认新核是不是m e r c e r 核 定理1 6 ( 【2 5 ) 设匝和鲍是刀x 爿上的核，石r “，a r + ，那么下面 的函数均是核； 1 k ( x ，：) = k 1 ( $ ，z ) + 鲍( z ，。) ， 2 k ( z ，z ) = a k l ( x ，z ) ， 3 耳( z ，z ) = k t ( x ，z ) k 2 ( z ，o ) 根据定理1 6 ，我们可以用不同核的线性组合构造混合核函数若需要构 造特殊的核，还可采用两种技术： ( 1 ) 1 构造逼近一维函数的核， ( 2 ) 用一维核来构成多维核 例如核k l ( x ，瓤) = 1 + z 戤+ 扛一x i ( x a 岛) 2 + 扛a 蛳) 3 就是线性样条逼 近的核 5 定理1 7 ( 【4 2 】) 设一个多维函数集合是由作为单位坐标基函数值之张量积 的基函数定义的，那么定义了这个n 维基上内积的核是一维核的积 根据定理1 ，7 ，我们可以用一维核的张量积构造多维核函数 6 二基于主成分分析的无监督核学习 主成分分析( p r i n c i p a lc o m p o n e n ta n a l y s i s ，简称p c a ) 是j o l l i f f e 在1 9 8 6 1 9 】 中提出一种流行的数据处理和降维的技术作为一种无监督学习方法，p c a 被很好地应用于手写识别( h a s t i ee ta 1 2 0 0 1 3 3 ) 和人脸识别( h a n c o c ke t a 1 1 9 9 6 2 8 ) 在1 9 9 8 1 2 1 中s c h s l k o p f 对线性p c a 进行了推广得到核主成分分析 ( k p c a ) ，得到了更好的分类效果 2 1 主成分分析简介 如图1 所示，主成分分析的目的是寻找在最小均方意义下最能够代表原 始数据的投影方法它将原始属性线性组合，并根据数据展示在每个特征方 向的方差大小排序维数约简有时会简单地去除那些方差很小的方向上的特 征，尽管不能保证这些特征对于分类不重要 - 懑滋 攀繁鬻 早。f 鹫撼 图1 ：数据在原始空间中的线性p c a 投影 考虑这样的问题，有个n 维的样本x 2 ，x n ，如何能够用仅仅一 个n 维的向量z o 来最好的代表这个样本，或者更确切的说，我们希望这个 代表向量z o 与各个样本的距离的平方之和越小越好定义平方误差准则函 数j o ( x o ) 如下； 而( z o ) = f 怖一x i 悒( 2 1 ) t = 1 容易证明样本均值m 0 = 斋篓1 就是最小化而( 。o ) 的那个n 维向量x 0 样本均值是样本数据集的零维表达，不能反映出样本之间的不同通过把 全部样本向通过样本均值的一条直线作投影，即z = m o + o e ，其中e 表示m o 7 方向上的单位向量，则( 2 1 ) 式变为 ( 口l ，o , n ，e ) = l l ( m o + a i e ) 一悒 ( 2 2 ) 对a 。求偏导，得 。t = e t ( x 。一m o ) ，i = 1 ，一，n 将a ，代入上式中 j 1 ( e ) = 一e 7 最e + 恢一m o l l 2( 2 3 ) ( 23 ) 式中的第二项是一个常数项，那么使得e t 岛e 最大的e 就是最小化 以的向量我们使用拉格朗日乘子法来最大化e 7 & e ，约束条件为等式l l e l l ：1 ， 则有 二( e ) = e t 岛e a ( e r e 一1 ) ， 对e 求偏导， 豢：o 辛最。：旭 d e 因为e t s t e = a e 7 e = a ，为了最大化e t e ，我们选取总散度矩阵的最大本征值 对应的那个特征向量作为投影直线e 的方向 这一结论可以立刻从一维空间的映射推广到d 维空间的映射我们重写 z = m o + ：l a k e k ，( 2 2 ) 式变为 矗= 龇音啪小t n 僻t ， 当向量e l ，e d 分别为岛的前d 个最大的特征值所对应的特征向量时，如 取得最小值 现在问题就转化为求最的特征值的问题 & 是n n 的矩阵，对于某些 问题( 如人脸识别) 样本的维数n 非常大，不利于计算机的存储与计算由于 最= 嘉( 瓤一m o ) ( 粕一m 。) t = 赏贾7 ， 其中贾= 【由( z 1 一m o ) ，去( z 一m o ) l ，贾是n 的矩阵利用下面的定 理，我们可以通过计算的贾7 贾的特征值得到s t 的特征值 8 定理2 1 ( s v d 定理 4 3 】) 设a 是一秩为r 的n r 维矩阵，则存在两个正 交矩阵： u = 阻o ，u l ，r - - 1 冗”。7u 7 u = j ； y = 【 o ，蛆，口卜1 】冗7 。 y ? y = ，； 以及对角阵 a = d i a g a o ，a l ，一，a r - 1 】7 f 。，且a o a l - - a ，一1 ， 满足 a ：u a v t ， 其中t九a = o ，1 ，一，r 一1 ) 为矩阵a a 7 和a 7 a 的非零特征值，啦和仇分 别为a a 7 和a 7 a 对应于丸的特征向量上述分解称为矩阵a 的奇异值分解 ( s i n g u l a rv a l u ed e c o m p o s i t i o n ，简称s v d ) ，焉为a 的奇异值 2 2 核主成分分析( k p c a ) 由于主成分分析是在最小误差平方和准则下，找到一个d 维子空间，使 其能够最好地表达原始的高维数据，如果原始数据的特征存在复杂的非线性 关系，那么线性子空间的表示性能将很差 1 9 9 8 年s c h s l k o p f 在【2 中对线性 p c a 进行了推广得到核主成分分析( k p c a ) 它的思想是将原始数据映射到高 维的线性特征空间去，利用核技术寻找最好的投影方向如下图所示： 图2 ：原始数据被映射到特征空问中的投影 在特征空间h 中，样本集的协方差矩阵为 n 霹= 专( ( 趿) 一m 3 ) ( 毋( 观) 一m 8 ) r = 寺甄醒 9 因为岛是半正定矩阵，所以其非零特征值都是正的，它们正是我们所需要 的 霹的每个特征向量“都可以被线性展开 再利用核技术 ( 。f ) 7 ( ) = ( ( z ；) ( q ) ) = k ( x l ，协) 则 f p 鼠= ( i - 斋1 。) k ( j 一嘉1 。- v ) ， 其中凰= 旧 i ) 一m 0 ，- - - ，曲( z ) 一m 翻h 。 记q = 【( 。1 ) ，( 2 ) ，并计算上咿皿的前d 个最大特征值a 1 a 2 a d ，和对应的标准正交特征向量饥，他，则甜是标准正交特征向量 为 蛳2 去注1 ，吐 一曼睫三缝。0 盏5 一：) 盎 图3 ：t o y 人工数据集的k p c a 投影 1 0 z o 。 i | u 叠一k ， 。 一 缝一 ” ， 。 一 鲤一 1l：_l叫ljl爨。 这样我们就得到一组最佳投影方向p = ( 虬，u d ) 具体的，第，个 k p c a 特征是 y ；= u f ( 。) = 牟谚0 7 ( z ) v a i = 妄7 t k ( x l ，。) ，k ( x 2 ，z ) ，k ( x n ，。) ，i = 1 ，d v a i 下面我们对t o y 人工数据集进行k p c a 投影，t o y 数据是服从三种g a u s - s i a l l 分布的高维点集，特征维数是1 0 图3 表示的是选取霹的前8 个最大的 特征值分别进行k p c a 投影的结果显然，选取的特征值越大，投影的效果 越好然后，我们采用融均值聚类算法来进行分类，表示样本的数量，k 表示类别的数量我们随机从样本中取出k 个作为初始的聚类中心聚类算 法如下： 算法2 1 ( k - 均值聚类 4 5 j ) ( 1 ) 初始化n ，k ，p l ，“； ( 2 ) 按照最近邻m 分类个样本； ( 3 ) 重新计算m 直到不再改变 ( 4 ) 返回p 1 ，p 三基于f i s h e r 准则的核学习机器 自f i s h e r l 9 3 6 年提出f i s h e r 判别分析以来，f l d a ( f i s h e rl i n e a rd i s c r i m i n a n ta n a l y s i s ，简称f l d a ) 已经成功应用于人脸识别 b e l h u m e u r 等在f 2 9 1 中指出f l d a 比p c a 有更好的识别效果对于非线性情形，m i l m 在3 0 1 中 首先将f l d a 推广到k f d 然而，对于小样本问题( s s s p ) ，由于类内散度矩阵 总是奇异的， y u 和y a n g 提出了直接线性判别( d i r e c tl i n e a rd i s c r i m i n a n t a n a l y s i s ，简称d l d a 8 ) 解决这个问题随后，l u 等在【1 4 】中利用核技术将其 推广到k d d a c h e n 在 2 0 】中强调了s 山零空间的重要性，他提出了一种使用 零空间的方法一n l d a 这部分我们充分考虑的零空间和非零空间，提 出了一种改进的双重判别分析( d u a i - k f d ) 方法，它的优点是不损失任何氏 的信息，进一步提高了分类效果 3 1 核f i s h e r 判别分析( k f d ) 虽然p c a 方法对于代表数据样本非常有效，但是并没有理由表明主成分 分析对区分不同的类别有什么大作用如果我们把所有类别的样本都放在一 起，则被p c a 方法抛弃的那些成分方向可能正是能够把不同的类别区分开来 的分布方向例如，在印刷体字符识别中，如果需要识别的是大写字母”o ”和 ”q ”，用p c a 方法能够发现这两种字母之间的相似之处，却可能把区分字母的 那个”尾巴”特征抛弃掉也就是说，p c a 方法寻找的是用来有效表示的主 轴方向，而f i s h e r 判别分析方法寻找的是用来有效分类的方向 假设我们有一组个n 维的样本z l ，z ，它们分属于两个不同的类 别我们考虑把d 维空间中的数据点投影到一条直线上去当然，即使不同 类别的样本点在n 维空间中能够形成互相分离，各自内部紧凑的集合，向任 意的直线作投影也有可能把这些不同类的数据点混在一起，反而降低了分类 效果然而通过适当的选择投影直线，我们还是有可能找到能够最大限度的区 分各类数据点的投影方向w 如图4 所示； 唾嘹。j 。? ， 0 j f 0 ，冉 f ，f t t k j j “ f 十f 电、 警一j 。越? 图4 ：把同一组样本点向两个不同的方向作投影右边的图中的投影方向使得 投影后的点比左边更容易分开( 实线对的点，虚线对的点) 现在我们来定义f i s h e r 准则函数我们希望投影后，在一维空间里各类 样本尽可能分得开些，即希望两类的类间距越大越好，而各类样本内部尽量密 集于是定义f i s h e r 准则函数为： 踟) = 而w t s b w ， ( 3 1 ) ( 3 1 ) 式可以看成一个广义的r a y l e i g h 熵问题因此在考虑它的极性时，可以 只在椭圆面s = 伽i ”r “，”r w = 1 ) 上讨论，即最大化j ( w ) 可以转化成 下面约束优化问题t 呼一i w t s b w s t w r = 1 ，( 32 ) 采用拉格朗日乘子法，有 l ( ”) = 一i 1 ”7 s b u + ；a ( w t 鼠”一1 ) ， 对w 求偏导，有 s b w = a 鼠w ， ( 3 3 ) 假设非奇异，则 瓦1 岛 = a ( 3 4 ) 1 3 易见，瓦1 岛的最大特征值所对应的特征向量w 就是使得j ( w ) 最大化 的解，即w 是能够最大限度的区分各类数据点的投影方向这样得到线性判 决函数为 g ( z ) = w 7 z w o ， 其中”o 是个常数，称为阈值对于两类问题的线性分类器可以采用下述决策 规则： j9 ( z ) 0 ，则决策z u 1 ， i9 ( z ) c 一1 然而，我们在原始数据空间并不是总能找到这样的投影方向 这时，我们用一个非线性映射将输入空间r n 映射到特征空问h ，在h 中最大化 啦) = 蒜， ( 3 5 ) 由于w 在爿的展开得 w = a t 妒( ) ， 所以( 3 2 ) 式可以化为 ，( 口) = i a t 丽m o ：， ( 3 6 ) 其中 m = ( 愧哥一一一7 ) ， n = k 2 一“k 一， 1i ， 心= ；确， 一，= 1 一= 嘉“2 面乙 玎 设a l ，a 2 ，扎( d c 一1 ) 是- 1 m 的d 个非零特征值，其对应的正交 特征向量为w l ，”2 ，一，跏，则w = ( w l ，w 2 ，”d ) 就是数据点在特征空间h 中能够最大限度的区分各类数据点的投影方向 1 4 若n 奇异，我们使用正则化技术，用吼：= + 1 j 代替n ，则 m ) = 蒜 ( 3 7 ) 3 2 核f i s h e r 直接判别分析( k d d a ) 事实上，当韶的投影不为零时，兜包含有绝大多数区别信息 k d d a 算法的思想就是首先除去霹的零空间，同时在霹的非零子空间寻找最优的 投影方向，即 w 7 露w = ，7 础w = d 。 ( 3 8 ) 这样首先要解决韶的特征值求解问题，霹可以重写为： m ) ( m ? 一m 8 ) t = 凰h 手 其中h b = 【、每( m 一m 8 ) ， 鲁( m 喜一n 。8 ) _ 由于特征空间h 的维数h 很 大，很可能是无穷的，所以直接计算h h 的矩阵霹的特征值是非常困难的 我们可以通过计算c c 的占曙h b 的特征值利用核函数，我们定义任意两 类2 rx l 。点积矩阵 坼。= ( b ) o “，i = 1 ，f r ，j = 1 ，l ，r ，s = 1 ，c 对于所有的c 类，定义nx n 的核矩阵 k = ( k r ，) ，r ，s = 1 ，一，c 我们将霹b 改写成如下的形式： 西风= 丙1 b 陬。g k a n x c - 丙14 寻。c k l 一斋，j ；。g k 。e + 丽i 爵。c k l g b = 丙i 叭 t 。g 一丙11 哥。g ) k ( a n x c - - 丙11 _ x g ) b ， 其中 b = d i a g i 2 1 a 一。e = u ，。出a t 瞎岳，西1 - z 。 1 5 廿i m g m 一 | | 醪 算法3 1 ( 1 ) 对角化霹有 y 7 霹v = 如， 取非零特征值对应的特征向量组成新的特征向量阵y ，有 y r 霹y = d b o ； ( 2 ) 令z = y d i5 ，则 ( y d i ) t 霹y w j ：j ，z r s z = ， 对角化z t 或z ， 旷汐础z u = d 。，u 7 u = j ； ( 3 ) w = z u , w 7 露w = ，w r 或w = d 。 3 3 基于零空间的核f i s h e r 判别分析( n k f d a ) 因为r ( 韶) g l ，r ( 或) 冬n c ，所以一般的r ( 霹) sr ( 或) 如果我们 用k d d a 算法，除去四零空间的同时，可能会丢失兜的部分零空间或者全 部零空间，所以础的零空间包含的区分信息就可能丢失n k f d a 算法的基 本思想是将所有的样本投影到础的零空间上去，即 t 观w = 0 ，w 7 霹w = a b ， ( 3 9 ) 这样，类内散度为零，只需要最大化类问散度 算法3 2 ( 1 ) 首先对角化黜： cl 。 础2 寺蚤薹( m 玎) 一m ? ( 训一曲l 凰瑶， 同样，我们只需要计算 瑶凰= 专( j 一万1n t 。g ) k ( j 一嘉a 。) ， 的特征向量矩阵矿，则有y 7 或y = a 。令y 为础的零特征值对应的特征向 量阵，则 y 7 础y = o ； 1 6 ( 2 ) 对角化y 7 霹k 则 u t y t 霹y u = a 6 ，u 7 u = ，； ( 3 ) 令= y 阢则w 7 霹w = a b 3 4 核f i s h e r 双重判别分析( d u a l - k f d ) 对于小样本问题，s 。的零空间维数是非常大的，但并非整个零空间都有 作用由于霹，础都是对称半正定的，有( 霹) = ( 四) n ( 础) 由于霹 的零空间对区分样本没有任何贡献，我们改进算法的思想是在h i b e r t 空间h 中，我们先出去霹的零空间， 妒s p = d t 0 ，p t s p = s b ，p t s ：e = 氏， 0 3 1 0 ) 因为甜是自共轭紧算子，由定理1 2 知掣的特征向量系 觑 构成“的 一组标准正交基假设伪，肪是霹的正特征值对应的特征向量，其中 m = r ( 霹) n 一1 我们定义子空问吼= s p a n c ：，风) ，其正交补空间记 为皿 事实上，皿 就是霹的零空i ；7 由于霹是h 的紧子空间，我们有下 面的定理： 定理3 1 在映射 ，：t _ + 山t 妒= w + _ ， f i s h e r 判别准则满足下面的性质： t ，( 妒) = ，( 叫) 若类问散度算子可逆，即对于每个非零的向量w ，都有w r 氏w 0 在这 种情况下，我们就直接采用标准的k f d 算法作f i s h e r 判决函数 圳= 竺w t 鱼s w w ，u 。 ( 3 1 1 ) 然而，在高维的甚至是无限维的特征空间h 中，由于训练样本是有限的， 这使得氏可逆几乎是不可能的也就是说，总存在向量满足w 7 氏u = 0 ，w v ( 瓦) 这些向量同时也满足w t 鼠” 0 ，因为当类内散度为零，正的类间散 度可以使得数据被更好的分开，于是它们显得尤为的重要在这种情况下， f i s h e r 判别准则退化为； 也( ) = 7 乳 ，| | w | | = 1 ，( 3 1 2 ) 注意到， ( ”) 可以视为r a y l e i g h 熵，因为w t i ”( 1 lwj = 1 ) 等价于! ；乎 我们将用( 3 1 1 ) 标准的f i s h e r 判别准则从( 氏) 的补空间中提取非奇异 的区分向量，而用( 3 1 2 ) 定义的类问散度标准从( 氏) 中提取奇异的区分向 量根据定理3 1 ，这两种区分向量可以从吼中提取出来，而不损失任何的有 用的区分信息 现在我们的任务是在特征空间h 经过p 投影后的空间奶提取这两种非 常有效的区分信息首先我们把毋t 划分为氏的两个子空间；象空间和零空 间然后我们用f i s h e r 判别准则从象空间中提取非奇异的区分向量，而用类 问散度准则从零空间中提取奇异的区分向量 假设a 1 ，。是氏的正特征值对应的特征向量，其中q = r ( 瓦) n c 我们定义子空问虬= s p a n c q ，口q ) ，其正交补空间记为皿= s p a n a 。+ 1 ，一，o l m ) ，事实上，皿。就是氏的象空问，古就是氏的零空问 算法3 3 ( 1 ) 首先除去兜的零空间，令p = ( p l ，皿。) ， p t s p = d t 0 ，p r s l p = b ，p t s 皂p = 氏l ( 2 ) 提取非奇异的区分特征，令p 1 = ( 。 一，n 。) ， 碍氏p 1 = 风 0 ，u 丁砰鼠p l 矿= a 1 ；u t u = j ； 则非奇异的投影方向为m = p 尸1 u ( 3 ) 提取奇异的区分特征，令p 2 = ( a 1 ，。) ， 胃氏p 2 = 0 ，v 7 醪# b p 2 v = h 2 ；v 7 v = j ； 则奇异的投影方向为w j = p p 2 v ( 4 ) 混合两种区分特征进行分类 1 8 四基于统计学习理论的支持向量机 1 9 9 5 年v a p n i k 3 6 】在统计学习理论的基础上提出一种通用的机器学习方 法一支持向量机近年来，支持向量机已经取得重大进展，现已发展了一系列 用于分类和回归的s v m s 算法s c h s l k o p f 等在2 0 0 0 【4 l 中提出了s v m ，他采 用一种新的参数控制支持向量和误差然而，s v m s 仍然面临求解二次优化问 题，s u y k e n s 和v a n d e w a l l e 在1 9 9 9 1 1 0 中提出了l s s v m ，它只需要求解一个 线性规划问题在这一部分我们利用误差修正码( e c o c ) 改进了多分类s v m ， 将它分解为若干个l s s v m 求解问题，从而降低了多分类s v m 的求解难度 另外，虽然目前k p c a 和k f d 都使用核技术，但与s v m 相比它们没有s v m 那样的推广能力和稀疏性因此，我们将k f d 展成类似支持向量机的数学模” 型，提出了一种s k f d 算法 4 1 支持向量机理论 支持向量机( s v m ) 建立在统计学习理论的v c 维理论和结构风险最小化 ( s r m ) 原则基础上，它根据有限样本信息在模型的复杂性和学习能力之间寻 求最佳折衷以期获得最好的推广能力目前，支持向量机已经成功地应用于三 维物体识别、时间序列分析、文本自动分类、遥感图像分析、人脸检测、手写 体数字识别、蛋白质结构预测等诸多方面s v m s 有着坚实的理论背景，其 中的一个重要成份就是m e r c e r 核的使用，可以有效解决非线性分类问题 在模式识别中，当训练数据是线性可分时，可构造最优超平面将两类样本 正确分开，这一思想可推广到不可分数据的情况利用最优超平面技术及相应 的核技术，我们可得到通用的学习机器一s v m 4 1 1 最优超平面 ( 1 ) 可分情况 假定训练数据 可被一个超平面 ( x l ，y 1 ) ，一，( x ，y t ) ，x r “，y + l ，一1 ) ( w x ) 一b = 0 1 9 ( 4 1 ) 分开如果这个向量集合被超平面没有错误地分开，并且离超平面最近的向量 与超平面之间的距离是最大的，则我们说这个向量集合被这个最优超平面( 或 最大间隔超平面) 分开 这一思想可形式化表述为：假定所有的训练数据满足下列约束条件： ( x i ) 一b 1 ，若们= 1 ， ( x i ) 一b - 1 ，若挑= 一1 ( 4 2 ) 将( 4 2 ) 写成一种紧凑的形式： y i l ( w 粕) 一酬1 ，i = 1 ，( 4 3 ) 容易验证，最优超平面就是满足条件( 4 3 ) 并且使得 西( ) = 忡n( 4 4 ) 最小化的超平面 要找到这个超平面，需要求解下面的二次优化问题： m i n 垂( ”