（信号与信息处理专业论文）模式识别中核方法若干问题研究.pdf

摘要 核方法是新近发展起来的一种模式识别方法，它的理论基础来自于统计学习 理论。统计学在解决模式识别问题中发挥了基础的作用，但是传统的统计学所取 得的成果大多建立在渐近理论之上，即样本观测数量趋于无穷多的时候的统计 性质。这个条件在现实中是比较苛刻的，也是难以满足的。虽然如此，传统上仍 然以样本观测数目无穷多为前提来推演各种算法，这不能不说是一个缺陷，它 也是造成神经网络等算法中的过学习问题的原因之一。 相比之下，统计学习理论的出发点就是研究有限样本观测情形下的模式识 别问题，经过几十年的发展，它已经具备完备的理论基础和严格的理论体系。统 计学习理论已经成为机器学习的一个重要的研究方向。 本文主要讨论模式分类与聚类中的核方法，以及其它相关的理论和应用的 关键问题。初步取得的研究成果和创新有： 第一，经典的核函数作用在欧氏空间的向量上，作者从空间旋转的角度，提 出了把核函数的作用域扩展到向量集合之上的方法，使之能够胜任需要表示和 处理更复杂的数据对象的机器学习任务。与类似的工作相比，它不需要预先假 定数据服从某个概率分布，也不需要利用数值方法计算复杂的积分。在人脸识 别的实验中，本方法比类似的工作达到了更低的误识率。 第二，e i g e n f a c e 和f i s h e r f 如e 是两种常用的人脸识别算法，它们本质上是线 性的，且着重发掘和利用映像空间的全局结构。对于非线性结构，它们无能为 力。本文讨论了局部空间结构对人脸识别的意义，我们认为局部空间结构可以 用线性或近似线性的方法学习和表示，并且可以通过对局部结构的逐段线性化， 来学习和表示全局的非线性结构。结合l l e 算法，提出了利用逐段线性化学习 和表示局部结构的核方法。在人脸识别的实验中，它比e i g e n f k e 和f i s h e r f a c e 表现出更好的识别能力。 第三，l p p 算法是一种数据降维和数据可视化方法，它是基于谱图理论的。 由于谱图理论与微分流形具有密切的关系，且对于流形来说，测地线距离比欧 氏距离更能准确揭示数据间的相似性，将l p p 算法推广到利用测地线距离进行 数据降维，并把这一方法扩展到核函数特征空间。在多个降维后的人脸识别实 验中，它比l p p 算法取得了更好的性能。 第四，尽管有众多的核函数可供利用，但是如何为特定的机器学习任务选择 合适的核函数，是核方法的理论研究中一个具有挑战性和开放性问题。从流形 学习和保形映射的角度，利用核函数特征空间中的流形学习算法，提出了一种 试探性解决方法。与作者类似的工作是针对某一个核函数进行调整和选择来提 高分类性能，而这里则从整体的角度对核函数进行选择。 第五，随着以科学研究为目的的合作进行模式识别的任务越来越广泛，嚏口何 保护合作双方的数据库安全的问题日益突出。提出了核函数的保密多方计算的 问题，并将它转化为向量内积的保密多方计算问题，利用不经意传输协议，提 出了一种解决方法。与已有的方法相比，它计算复杂度低，且通信负载大幅度 降低。 本文以构造新的核函数为主要研究方向，对于核方法在实际应用中的问题， 如支持向量的选取、如何提高训练速度、减少噪音对支持向量选择的影响，则 讨论不足，这将在以后的研究工作中予以关注。 关键词：模式识别；核方法；核函数；统计学习理论；分类；聚类；谱图理论； 局部近邻关系；空间旋转；保密多方计算：不经意传输协议 a b s t r a c t k e m e im e t h o di sap o w e r f u lm a c h i n e1 e a m i n gm e i h o dd e v e l 叩e dr e c e m l y nb u i l d s0 nt 1 1 e s 州s t i c a l i e a r n i n gt h e o 叫s t a t i s t i c sb a v eb e e np l a y i “ga ni m p o r t o mr o l ei nm a c h j n e1 e a m i n g 卸d p 肆n e mr e c o g n i t i o n ，b u tm o s to fr e s u l t so fc l 粘s i c a ls t a t i s t i c sd e r i v ef 沁ma s y m p t o t i ca s s u m p 廿o n ， i e s t a t i s t i c a lp r o p e r t i e sw h i c hw i l lp r e s e mw h e nt h eo b s e r v a t i o ns a m p l e st e n d st 0i n f i n i 吼i ti ss o r i 9 0 m u sac o n s i n tt l a t m dt om e e ti np r a c t i c e a l t h o u g h 卵p a r e n t l yad r a w b k ，m a n y a l g o r i t h m si nm a c h m ei e a h l i n gs t i ua d o p tt h i sp r e s u p p o s n i o n a sac o n ”曲t ，s t a t i s t i c a ll e a m i r 培t h e o r ys t u d i e sm a c h i n e1 e a r n i n gp r o b i e mi nt h ec a s eo ff i n i t e s a m p l e0 b s e a t i o t l s a 缸rs e v e r a ld e c a d e so fd e v e l o p m e n t ，i th a se m e 唱e d 、v i ms o u i l d 血e o r y f o u n d a 在o n i tr e g a r d sm a c h m el e a m i n gp r o b l e m 孙ag e n e r a lp m b l e mw h i c hp e r f o 咖sf h n c t i o n e v a l u a t i o nw i t l ln n i 把s a m p l eo b s e r v a t i o n s i ts y 玎c h e 石c a l l ys t u d i e sw h e n 恤ep r i n c i p l eo f e m p i f i c a l r i s km i n i m i z a t i o nw i l lh o l d ，t h er e l a t i o l l s i l i pb e t w e e ne m p i r i c a lr i s k 锄de x p e c t a t i o nr i s ka i l dh o w t os e e k i n gn e wa l g o m h m sw n i l i nm i s 龀l m e w o r k t h er e p r e s e r l 乜廿v ea k o r i t l l i l li ns t a t i s t i c a l l e 踟i n gt l l e o i yi sk e m e lm e t l l o do rs o c a l l e ds u p p o r t v e c 幻埽m a c h i n em e t h o d ，w h i c hc a l lb ea p p “e dt om a n yp a 始ma n a l y s i sp r o b i e m ss u c h 船p 硼锄 c l a s s 碾c a t i o n ，c l u s t e r i n g ，r e g r e s s i o na n a l y s i sa n dn o v e l 可d e t c c t i o n i nt h i sp 印e r1 w i l ld i s c u 船 i s s u e sa b o u tk e m e lm 劬o d si np a 仕e mc i 够s m c a t i o n ，c l u s t e r i n ga n ds e v e r a lo 劬e rk e yp r o b l e m si n k e 兀l e lt h e o r y 锄dn s 印p l i c a t i o n c 1 a s s i c a lk e r n e lm e m o dm a i n l yd e f i n e so nv e c t o r si ne u c l i d e a ns p a c e am e m o dt og e n e m l i z e k e m e lm e t h o dt 0s e 拓o fv e c t o r sf b mt h ev i e wo fs p a c er o t a 廿o ni sp r o p o s e d w h i c hi sa b l et o p r e s e n ta n dp r o c e s sm o r ec o m p l i c a t e dd a t ao b j e c t 呻e s c o m p a r e dw i t hs i m i l a rs c h e m e s ，n e i 也e r i tn e e d st oi m p o s eah y p o t h e t i c a lp r o b 曲i l i i yd e 工l s i t y 如n c t i o no nd a t ai na d v 姐c e ，n o rc o m p l i c a l e d n 啪e r i c a l i n t e g m lc o m p u 删o ni n v o l v e di no r d e rt oa p p i yk e m e lm e t h o d f naf a c cr e c o 删d o n b e n c h m a r ke x p e r h n e n t ，ha c h i v e sp o s n i v er e s u l “m do u t p e r f o r m ss h n i l a rw o r k e i g e n f a c e 锄df i s h e r f 缸ea r et w op o p u l a rm e 血o d si nf 缸er e c o g n i t i o n t h e yb o t ha r el i n e 甜 o n e sa i l da i mt oe x p i o r eg l o b a ls t m c t l l r ei ni m g es p a c e l e a m i n gn o n l i n e a rs t r u c n j f ei sb e y o n g d t h e i rs c o p e s t h es i g l l i f i c a f l c eo fl o c a ls t r u 蛐i n 缸er e c o g f i i 虹o ni sd i s c u s s e d d e e m i n gt h a t 1 0 c a ls 廿u c t u r ec a nb el e a n l e da n dr e p r e s e n t e db ym e a n so fl i n e a ro ra p p r o x i m a t e l yl i n e a rp 执m ， g i o b a ir l o n l i n e a rs t r u c t i l r ec a nb el e a m e da n dr e p r e s e m e db yw a yo fs e g m e mb ys e g m e n t l i n e a r i z a t i o n ，am e t h o d1 e a m i n gg l o b a lr 1 0 n l i n e a rs t r u c t u r ec o m b i n e dw i t hl l ea l g o r i t h mi s p r o p o s e d 【naf a c er e c o g n n i o nb e n c h r n a r ke x p e r i m e n t ，i te x c e e d sb o t he 螗e n f k ea n df i s h e 血c e a l g o r i t h m l p pi sad a t av i s u a l i z a t i o na n dd i m e n s i o m l 时r e d u c t i o na i g o t h mw h i c hb a s e do ns p e c t r a l g r a p ht h e o r y f o rs p e c n 甚1g r a p hp r e s e n i s at i g h tc o n n e c i i o n 、v i t hd i 行e r c l l t i a lm a n i f o l da n d g e o d e s i cd i s t a n c ei sm o r ea c c u a r a t et h a r ie u c l i d e a nd i s t a n c ei nd i s c l o s i n gs i m i l a r i t i e sb 嘶v e 髓 堡苎望型主鳖查望董王塑壁堑塞 d g aw h e nt h e yl i eo nam a l l i f o l d ，g e n e 豫l j z el p pw i mg e o d e s i cd j s 纽n c ea n dk e m e 】m e t l l o d 如 s e v e r a if a c er e c o 肛i t i o n b e i l c h m a r ke x p e r i m e n t s 曲e rd l m e i l s i 叻a 1 时r e d u d i o n ， na c h v e sb c t t e r p e r f o r n l a n c e t h a n 廿戚o f l p p c 1 l i s t e r i n gi san a t l l r a lm e t h o dt ol e 锄c o n c e p t am e 廿1 0 dt ol e a m 蚰dr e p r e s e n tl a t e n tc o n c e p t 州t l lk e m e lm e h o dj sp f o p o s e d a l l h o u 曲卸a 驯c a lr e ；鹏s e n t a 石o no f 幽el a t 蛐tc o n c e p ti su n 曲1 e t or e 订i e v e ，让s t i l lc a nb ea v a i l e do fi nm a c l l i n el e 唧i 1 1 9t a s k sb 够e di nd i s t a n c e i na 把吐 c a t e g o r i z a t i o ne x p e r i m en t ，i to 唧e 仃o m ss e v e r a ld m e ra l g o r i t l l m si i l c l u d i l l gk n n a n db a y e si n i n d “si i k ep r e c i s i o na n dr e c a l l a l t h o u 曲t h e r ea 糟m a n ya l t e m a l i v ek e m e lf u n c t i o 舾，i tr e m a i n s 锄o p e n 衄dc b a l 】e n g j n g p r o b l e mo nh o wt os e l e c tap r o p e rk e m e lf 研s o m es p e c i f i cm a c h i n el e 枷i n g 协s k f mm ev i e w o fm 锄i f 0 1 di e a m i n ga n dc o n f o m a lm a na ne x p l o r a t o 叫m e t l o dt ot a c k l et h ep r o b l e mw i t h m 枷f 0 i dl e a m j n ga 1 9 0 r n h r ni nk e r n e lf e a h 盯咛s p a c ei sp r o p o s e d s i m i l a rw o r kp a y sa t c e l m o nt 0 a d j u s t i n gas p e c i f i ct y p eo fk e m e lt 0h n p r o v ec i a s s 讯c a 士i o np e r f o m a n c e ，w t l i l et h i sa l g o r i 恤m d i s c u s st h ep m b l e m 州t hag l o b a lv i e w n o wj tb e c o m e sp o p l l l a rt oc o c o n d u c tam a c l l i n el e a r n i i l gt a s ko nu n i o n e dd a t a b 鹊e sb e l o n g i l l g t od i 丘b r e n tg r 0 i l p 8 ，w h i c hm a yb ev a l u a b l ea n d c 谢t y 锄dp r i v a c yb e c o m eak e yp r o b l e m t h e p r o b l e mo fs e c u f em u m p a r i yc o m p u t a t i o nf o rk e m e lf i i n c t i o n si sp r o p o s e da i l dn 螂f o r f n e dt oa p r o b l e mo fs e c u r em u l t i - p a f c yc o m p u t a t i o nf 曲s c a l a rp r o d u c t ；as c h e m et 0f i l l n l l i r 培m ep r o b l 咖 i sp r e s e n 饴d c o m p a r c dw i l hs i m i l 盯m e t h o d ，i t 。印r e s n 协m u c hl o w e rt r a f f | co v e r h e a d 锄d c o m p u t a t i o nc o m p l e x i t y 1 ( e yw o r d s ： p a t t e mr e c o g n n i o n ；s 忸t i s t i c a l l e a n l i n gt h e o l y ；c l 越s 强c a t i o n ； c l u s t 耐n g ；s p e c 乜鼍l g r 印h ；l o c a ln e i g h b o r h o o dr e l a t i o n s h i p ；s u b s p e ；s e c u r em u l t i p a r c yc o m p u t a t i o n ；o b l i v i o l 】s t r 舳s f e r 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列 的内容以外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得北京邮电大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：迈渔至 日期：型兰：! ：驾 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京邮电大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权 书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：盈i 鱼至 导师签名： 铲 日期： 日期： 第一章模式识别导论 在过去的几千万年里，人类进化出高度复杂和灵敏的感知系统。我们能够轻 易的辨识人脸、识别说话者、阅读，驾车时根据路面状况躲避障碍物，根据颜 色判断香蕉是否成熟。这些人类习以为常的识别行为，貌似简单，然而其背后 却隐藏了极其复杂的信息感知和处理过程。模式识别对我们的生存至关重要， 它输入原始数据并根据其类别采取相应行为的能力，是生命智能的重要特征。 模式识别是一门以应用为基础的学科，目的是将对象进行分类。这些对象与 应用领域有关，它们可以是图像，信号波形或者任何可测量且需要分类的对象， 可以用术语“模式”来称呼这些对象。模式识别具有悠久的历史，但是在2 0 世 纪6 0 年代以前，模式识别主要是统计学领域中的理论研究。同其他事物一样， 计算机的出现提高了对模式识别实际应用的需求，而这又对理论的发展提出了 更高的要求。就像人类社会从工业化到后工业化阶段一样，工业生产中的自动 化以及信息处理的需求变得臼益重要，这种趋势使得模式识别在今天的工程应 用和研究中发挥了重要的作用。在大多数机器智能系统中，模式识别是用于决 策的主要部分。 模式识别也是一门边缘学科，它与人工智能、信号处理、计算机科学与技术、 概率统计、模糊集论、信息论、数字图象处理、形式语言学、心理学、语言学 等都有密切的关系，而且随着模式识别这门学科的发展，还会与其它更多的学 科发生关系。另一方面，许多不同学科的人们也从各自的角度对它产生了越来 越多的兴趣。 1 1 模式识别的应用 在机器视觉中，模式识别是非常重要的。机器视觉系统通过摄像设备捕捉图 像，然后通过分析生成图像的描述信息。典型的机器视觉系统主要应用在制造 业中，作为自动化视觉检验或装配线的自动化。例如，在自动化视觉检验应用 中，生产的产品通过传送带移动到检验站，检验站的照相机确定产品是否合 格。因此，必须在线分析图像，模式识别系统必须将产品分为合格和不合格两 类，然后根据分类结果采取相应的行动，比如丢弃不合格的产品。在装配线上， 必须对不同的对象进行定位和识别，也就是说，将对象分类到已知类别中的某 类，如螺丝刀等工具制造单元，然后机器手把这些对象放置在正确的位置。 模式识别中核方法若干问题研究 语音识别是模式识别的另一个研究领域，语音是人类最自然的沟通和交换 信息的方式。因此，与机器进行语音交流，让机器理解人类语言，是人们长期 以来梦寐以求的事情。语音识别是一门交叉学科，近二十年来，语音识别技术 取得显著进步，开始从实验室走向市场。在西方经济发达国家，大量的语音识 别产品已经进入市场和服务领域，一些用户交机、电话机、手机已经包含了语 音识别拨号功能，还有语音记事本、语音智能玩具等产品也包括语音识别与语 音合成功能，人们可以通过电话网络用语音识别口语对话系统查询有关的机 票、旅游、银行信息，并且取得很好的结果，调查统计表明8 5 以上的人对语 音识别的信息查询服务系统的性能表示满意。 前面提到的只是众多可能应用中的几个例子，典型的应用包括指纹识别、 签名认证、文本检索、表情和手势以及唇语识别。当然，要是这些应用达到完 美的境界，模式识别还依赖于其他一些学科的发展，如语言学、计算机图形学、 计算机视觉等“2 。”。 1 2 模式识别系统 有两种基本的模式识别系统，即统计模式识别( s t a t i s t i c a lp a t t e r n r e c o g n i t i o n ) 和句法模式识别( s y n t a c t i cp a t t e r nr e c o g n i t i o n ) 。前者关注的 是模式的统计特性，它一般用概率的观点来表达。如果模型是由若干逻辑规则 组成，那么就可以用句法模式识别技术，它采用规则和文法来表达模式类别和 判别条件。例如，我们可能想把英文语句分类为符合语法的和有语病的两类， 则文法规则比词频统计或语词相关性等统计特性更适宜这类模式识别任务。 本文只讨论统计模式识别方法。 基于统计方法的模式识别系统主要由4 个部分组成：数据采样、数据预处 理、特征提取、训练模式识别机器，如图1 2 1 所示。 参堙一一甲 缸岖豳 图1 2 1 模式识别系统的组成 第一章模式识别导论 数据预处理的目的是去除噪音，加强有用的信息。特征提取器输入模式，而 输出特征值。特征的数目几乎总是少于用于描述完整的感兴趣的目标所需的数 据量，因而在这个过程中产生信息损失。特征提取器通常要提取具有如下性质 的特征，即来自同一类别的不同样本的特征应该非常相近，而来自不同类别的 样本的特征应该具有很大的差异。这让我们产生了提取有鉴别能力的特征的想 法，这些特征对与类别信息不相干的变换具有不变性。例如在手写体识别中， 特征对于平移，旋转，尺度变换应该是不敏感的。而在语音识别中，我们期望 特征描述对时间平移和整体振幅的改变是不变的，我们可能还希望跟单词的持 续时间无关，也就是说，和一个模式发出的速率无关。特征提取依赖于具体问 题和具体领域，因此相应领域的知识是必须的。训练模式识别机器就是在特征 空间中用统计方法把被识别对象归为某个类别，这就需要确定个代价函数， 使得按照这种代价函数对被识别对象进行分类所造成的误识率达到最小。 按照不同的模式识别情景，模式识别大体分为模式分类，聚类和回归分析。 本文我们只讨论分类和聚类。分类也称为有监督学习，在有监督学习中，存在 一个教师信号，对训练样本集中的每个输入样本提供类别标记和分类代价，并 寻找能降低总体代价的方向。在无监督学习或聚类学习中，并没有明显的教师 信号。系统对输入样本自动形成聚类或自然的组织。所谓自然与否是由聚类系 统所采用的显式或隐式的准则确定的。 经验表明，特征提取对于学习机器的优劣是至关重要的，下面我们简要回 顾特征提取的经典方法。 1 3 特征提取 在实际应用中，遇到包含多达上千个特征的问题是很寻常的。通常认为其中 的任何一个特征对于模式识别任务都有其自己的贡献。但是，有理由认为这些 特征之间是否存在相关性，即是否存在某种信息的冗余。 通过特征提取可以降低维数，这有利于降低计算复杂度。在输入维数高时， 样本量问题会突出出来。设输入为n 维，样本量为n ，样本在空间的密度正比于 “，因此若n = l o o 对一维空间样本密度较大，而n = 1 0 时，1 0 ”个样本才能达 到同样的密度，或者说在多维空间中点间距离会变得很大，因为多维空间的体 积正比于幂次。满足一定统计指标的模型，为了使模型达到相当的精度，需要 的样本数目随着维数的增加将呈现指数增长趋势，如此多的数据对于计算是否 可行提出了严峻的挑战。这就是所谓的“维数灾难”问题“1 。 模式识别中核方法若干问题研究 通过特征提取技术抽取最有代表性的特征，可以在一定程度上缓解维数灾 难的影响。下面我们对典型的特征提取方法作简单回顾。 需要强调的是，我们这里介绍的特征提取算法都可以利用再生核技术扩展 到高维数据空间执行，同时却没有受到维数灾难的影响，从中我们可以看到核 方法对于扩展线性学习机器学习的作用。 1 3 1 主成分分析 假设原始数据为d 维，主成分分析( 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 ) 也称为k l 变换啪，它搜索c 个最能代表数据的d 维正交向量，这里c d 。这 样，原来的数据投影到一个较小的空间，导致数据压缩。p c a 背后的主要思想如 下： 对输入数据规范化，使得每个属性都落入相同的区间，它确保具有较大 定义域的属性不会主宰具有较小定义域的属性 p c a 计算c 个规范正交向量，作为规范化输入数据的基。这些向量两两 正交，被称为，主成分”。输入数据是主成分的线性组合。 。1 对主成分按照意义或强度降序排列。主成分基本上充当数据的一组新的 坐标轴，提供重要的方差信息。即，对轴进行排序，使得第一个轴显示 的数据方差最大，第二个轴的方差次之，以此类推。 既然主成分根据意义降序排列，就可以通过剔除较弱的成分( 即方差较 小的那部分) 来压缩数据。使用最强的主成分，应改可能重构原数据的 很好的近似 问题的求解引入了所谓的散布矩阵( s c a t t e rm a t r i x ) s = ：( - m ) ( 矗一m ) 其中m 是样本均值，事实上它s 是样本协方差矩阵的n l 倍，p c a 选取散布矩阵 最大的特征值对应的特征向量作为投影直线p 的方向。 从几何角度看，样本点工”，x 。在d 维空间形成了一个d 维椭球形状的云 团。则散布矩阵的特征向量就是这个云团的主轴。主成分分析通过提取云团散 步最大的方向，达到了对特征空间进行降维的目的，以上分析见文献。 上面讨论的p c a 形式涉及到在输入空间上的计算。现在考虑另一种形式的 p c a ，计算在核函数特征空间上进行，它和输入空间是非线性的关系。这里使用 的特征空间是根据节1 4 4 介绍的m e r c e r 定理的内积核定义的。基于核的主成 4 第一章模式识别导论 份分析思想归功于s c h o l k o p f 等人嘲，我们把这类工作统称为核主成分分析 ( k 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 ) 6 ”。 由于输入空间和特征空间的非线性关系，k p c a 是非线性的。令p “) 表示向 量置在非线性映射 d ：j _ f 下的像，可以定义在空间f 中相关矩阵 天= 寺拟咖) = 吉扭，_ ) 接着，如同在p c a 方法中一样，需要解特征值问题 爱g ； q 注意到特征向量q 落在由集合 驴( _ ) ) ；张成的空间中，即 g = ：。口，妒( 工，) 则上述特征值问题可以写为 k 球= 口 五为k 的特征值，口为对应的特征向量。 接下来，归一化特征值，这要求 吼= ，拈卜1 p 其中以是矩阵k 的最小的非o 特征值，假设特征值是按照降序排列的。 为了抽取测试数据x 的主成份，计算投影 以= ：。世( x ，z ) 其中d 。，是特征向量的第j 个元素。 模式识别中核方法若干问题研究 1 3 2 多维尺度分析 多维尺度分析( m u l t i d i m e n s i o n a ls c a l a ra n a l y s i s ，m d s ) 有多种类型，所以 这些类型都提出了一个基本问题：给定n 个数据点的”玎相异程度矩阵z 和距 离测度( 通常为欧氏距离) ，在空间彤中找到n 个点一，的构型，使得它们 点对之间的距离接近于相异程度，即尽力保持原有的数据结构，所有的方法都要 找到点的坐标和空间的维度e 。多维尺度分析的两个基本类型是度量m d s 和非度 量m d s 。前者假定是数据定量的，而且认为点对之间的距离与其相异度存在某种 含函数关系；非度量m d s 假定数据是定性的，或者具有次序关系，它产生的结 构试图保持相异度的排列次序。 这里只介绍度量m d s ，由于后面的章节需要应用m d s ，所以这里给出了比较 详细的介绍，关于多维尺度分析的详尽的介绍见文献 9 。 ( 1 ) 经典多维尺度分析( c l a s s i c a l 如s ，c 如s ) 给定一组p 维空间中的n 个点一，吒，计算它们之间的距离是很直接的。 c m d s 则要解决这个问题的反问题：给定距离矩阵d = 以) ，假定是欧氏距离， 如何在p 维空间中确定一组点的坐标。可以通过分解一个矩阵t 得到： t = x x t 这里x = _ ，卜点，之间的距离为 d ；= l + 乃一2 乃 ( 1 3 1 ) 如果限制，的质心位于原点，则由式( 1 3 1 ) 可以得到 乃= 一 d ；一d ? 一d ；+ d2 】 ( 1 3 2 ) 其中 d1 2 ：。d ： dj 2 n l ，d ： 吩古莓，零，d ： 式( 1 3 2 ) 允许我们从距离矩阵d 构造矩阵t 。需要做的就是将其分解为 第一章模式识别导论 丁= 。蹦的形式。因为t 是实对称矩阵，所以可以得到 丁= u 人u 7 其中u 的列示t 的特征向量，a = 拙g ，矗 是对角阵， 为t 的特征值a 因此，可以取 ! 爿= u a 2 如果要在降维空间中表示数据，则仅使用那些与最大特征值对应的特征向量。 简单的说，选择r 个特征值，使得 ：4 j ：。a 模型的训练问题如何为特定的模式识别任务选择合适的网络拓扑与 结构一直是一个没有很好的理论指引的难题，它依赖于专家的经验。另 外，网络的参数的调整也是一个棘手的问题； 模型难以解释虽然神经网络在诸多应用领域获得了成功，但是也存 l o 第一章模式识别导论 在学习到的知识难以解释，难以用解析的方式表达，启发式成分较多等 弊病。 模式识别中另一个比较重要的方法是b a y e s 网络，它建筑在b a y e s 决策理论 之上。1 9 8 2 年，p e a r l 正式提出了具有父母和一个孩子的三条弧树状结构的简单 b a y e s 网络学习方法3 ”；之后在1 9 8 7 年，l a u r i t z e n 等人在简单b a y e s 网络中引入 g i b b s 能量函数，提出了因果概率推理系统。”。1 9 9 0 年，v o v k 发展了通用的b a y e s 算法。”。但是b a y e s 网络的进一步发展同样受到了一个关键问题的困扰，即“网 络规模爆炸或者规则爆炸问题”，它同样是由系统中起作用的因素众多，相互 间又关系复杂，从而造成了网络规模和规则数的急剧膨胀引起的。 在v a p n i k 的关于统计学习理论的著作统计学习理论的本质以及统计 学习。”之中，作者痛数了神经网络的不足之处。下面是其中的一段话： “这些人工智能学者对于处理学习问题有着丰富的经验，善于对一些理论上 非常复杂的问题构造简单的算法。2 0 世纪6 0 年代末，人们认为在几年之内就 可以完成计算机自然语言翻译器，但时至今日我们离解决这个及其复杂的问题 依然路途遥远。在此之后的一个计划是构造通用问题求解器：再之后又是建立 大系统自动控制机的计划等等，所有这些科研计划都没有取得成功。” “这些学者首先做的就是改变了所用的术语，特别的，感知器被叫做神经 网络。然后这些研究被称作是与生理学家共同进行的。对学习问题的研究减少 了一般性，增加了主管色彩。在6 0 和7 0 年代学习问题的主要目标是寻找从小数 量样本出发进行归纳推理的最好途径，而到了8 0 年代，目标变成了构造利用大 脑来推广的模型” 作者并不完全同意v a p n i c k 的观点。但是，虽然v a p n i k 讨论的只是多层感知机 模型，未涉及到其他神经网络模型如自组织映射，反馈网络等，至少也说明了 神经网络在理论基础上的不足之处。 与神经网络相比，统计学习理论有着较为完备的理论基础和严格的理论体 系。传统的统计学所研究的主要是渐近理论，即样本数目趋于无穷时的统计性 质。但是现实的问题中样本数量经常是有限的，但是基本上仍然以样本数目无 穷为假设了来构造学习机器，这不能说不是一个缺陷。而以结构风险最小化为理 论基础的统计学习理论，其出发点就是有限样本数量的假设，并且提出了用有 限数量信息解决问题的一个基本原则：在解决一个给定的机器学习问题的时候， 要设法避免把解决一个更为一般的问题作为中介步骤。要试图得到所需要的答 案，而不是更一般的答案。例如，当解决模式识别或者回归估计问题时，我们应 模式识别中核方法若干问题研究 该设法去直接寻求待求解的函数，而不是首先估计概率密度函数，再来解决模 式识别任务。因为估计密度一般来说是一个不适定问题，因此需要大量的观测 才能较好的解决问题。与之相比，实际要解决的问题是很特殊的，通常只是需 要一个合理数量的样本观测即可解决。 神经网络中的所谓的过学习问题，实际上是