（应用数学专业论文）度量空间中的软间隔分类问题.pdf

摘要 2 0 世纪9 0 年代中期，在统计学习理论的基础上发展起来了一种新的模 式识别方法这是由v n v a p n i k 等人提出的支持向量分类机( s v m ) 它是 解决分类问题的一种有效算法支持向量分类机在数字识别，数据挖掘和信息 处理等实际问题中有非常广泛的应用，近年来有了迅猛的发展 考虑到在许多实际问题中，构造描述目标之间关系的距离函数比构造支持 向量机中的核函数更容易更自然，且在没有度量空间的先验信息的情况下，可 以利用度量的特性构造度量空间中数据的分类算法，本文讨论度量空间中的 分类问题m h e i a 和0 b o u s q u e t 等人构造了度量空间中的最大间隔分类 算法但是，在实际问题中，样本不一定是可分的，且最优超平面也不一定都 存在因此我们在其所做工作的基础上讨论度量空间中的软间隔分类问题， 并得到了两个主要结果t 首先构造了度量空间中的软间隔分类算法，然后通过 改进分类算法中的核函数增大了支持向量分类机对训练样本的分类间隔主 要内容安排如下， 第一部分介绍分类问题和支持向量机的基本思想 第二部分。通过度量与核函数之间的转化关系构造度量空间中的最大间 隔分类算法 第三部分t 在m h e i n 和0b o u s q u e t 等人所作工作的基础上，构造了 度量空间中样本线性不可分情形下的软间隔分类算法 第四部分：讨论分类算法中核函数的选取与改进通过最小亿v c 维的 上界选择核函数的参数利用核函数在输入空间诱导的黎曼几何结构改进核 函数，增大支持向量机对样本的分类间隔 最后，在第五部分中，分析了前面部分得到的两个主要结果，并对未来研 究工作方向进行丁展望 关键词 度量空间；支持向量机；再生核希尔伯特空间；核函数；黎曼几何结构 a b s t r a c t i nt h em i d d l eo f1 9 9 0 s ，an e wp a t t e r nr e c o g n i t i o nm e t h o di sd e v e l o p e do n t h ef o u n d a t i o no fs t a t i s t i c a ll e a r n i n gt h e o r yt h i si ss u p p o r tv e c t o rm a c h i n e p r o p o s e db yvn v a p n i k i ti sa ne f f e c t i v ea l g o r i t h mt os o l v ec l a s s i f i c a t i o n p r o b l e m ss u p p o r tv e c t o rm a c h i n eh a s a ne x t r e m e l yw i d e s p r e a da p p l i c a t i o ni n d i g i t a lr e c o g n i t i o n ，i n f o r m a t i o np r o c e s s i n ga n ds oo ni ti sd e v e l o p i n gv i o l e n t l y i nr e c e n ty e a r s t h i st h e s i st a l k sa b o u tt h ec l a s s i f i c a t i o nf o rm e t r i cs p a c e si nm a n ya c t u a l p r o b l e m si ti se a s i e rt oc o n s t r u c td i s t a n c ef u n c t i o n so ft h eg o a lr e l a t i o nt h a n t oc o n s t r u c tk e r n e lf u n c t i o n s w i t h o u tt h ei n f o r m a t i o ni nt h em e t r i cs p a c e j w et e na l s ol l s et h em e t r i ct oc o n s t r u c tc l a s s i f i c a t i o na l g o r i t h m mh e i na n d0b o n s q u e th a v ec o n s t r u c t e dam a x i m a lm a r g i nc l a s s i f i - c a t i o na l g o r i t h mf o rm e t r i cs p a c e sb u ta c t u a l l y , s a m p l e sa r en o tn e c e s s a r i l y d i v i d e d a l s ot h em a x i m a lm a r g i nh y p e r p l a n e sd on o te x i s t t h e r e f o r ew e c a r r yo nap r o m o t i o no ut h e i rw o r kw ec o n s i d e rt h es o f tm a r g i nc l a s s i f i c a t i o n f o rm e t r i cs p a c e s f i r s t l yas o f tm a r g i nc l a s s i f i c a t i o na l g o r i t h mi sc o n s t r u c t e d f o rm e t r i cs p a c e s ，s e c o n d l yt h ek e r n e li sp r o g r e s s e di ns u p p o r tv e c t o rm a c h i n e t om a x i m a l i z et h em a r g i n t h em a i nc o n t e n ti sa r r a n g e da sf o l l o w i n g ： i nt h ef i r s ts e c t i o n ，w ei n t r o d u c et h ec l a s s i f i c a t i o np r o b l e ma n dt h ei d e c o fs u p p o r tv e c t o rm a c h i n e i nt h es e c o n ds e c t i o n ，am a x i m a lm a r g i nc l a s s i f i c a t i o na l g o r i t h mi sc o n s t r a c t e df o rm e t r i cs 口a c e si ti sb a s e do nt h et r a n s f o r m a t i o nb e t w e e nt h ek e r u e l a n dt h em e t r i c i nt h et h i r ds e c t i o n ，as o f tm a r g i nc l a s s i f i c a t i o na l g o r i t h mi sc o n s t r u c t e d f o rm e t r i cs p a c e s i ti sb a s e do nt h ew o r ko fmh e i na n d0b o u s q u e t i nt h ef o u r t hs e c t i o n ，w et a l ka b o u tt h ei m p r o v i n go ft h ek e r n e lf u n c t i o n i ns u p p o r tv e c t o rm a c h i n e i nt h el a s ts e c t i o n lw ea n a l y s et h et w om a i nr e s u l t sa n dd os o m ee x p e c - r a t i o no ft h ef 1 1 t u r e k e yw o r d s m e t r i cs p a c e ；s u p p o r tv e c t o rm a c h i n e ；r e p r o d u c i n gk e r n e lh i l b e r t s p a c e ； k e r n e lf u n c t i o n ；r i e m a a n i m ag e o m e t r y 湖北大学学位论文原创性声明和使用授权 说明 原创性声明 本人郑重声明。所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他 个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本声明的法律后果由本人承担。 论文作者签名t 声诌 签名日期：游，月f 日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即t 按照 学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷 本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化 或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部 分或全部内容。( 保密论文在解密后遵守此规定) 论文作者签名 差遥 签名日期：御年月f 日月栅 第一章暑l 宫 1 1 分类阐惩简介 讨论空间石中的分类问趔，就是根据所绘训练样本，构造近似袭示未知 努带f 戆学琴梳器。奉爱上，窀霹瓣表_ 承熊下；铜练嚣建涌虱嚣搦臻静事俘 并确鼹肝出现的事件属于k 娄中的哪一类；需要构造一个机器，谈机器在观 测了训练器的分类盾船够以与训练器相同的方式近似的完成分类工作 聚蘑形式纯港京，这释藏遘霹教表连为t 在令鑫摄率分毒西数f ( x ) 辑裁 画的确定环境中。搴件随机独崴的出现；训练器将每个事件分类到类之一；我 们假定训练器利用条件概率分布函数f ( u 嘞，其中u o 1 ，一l = p 搔镤练器将事停。稽派到筹p 类) 完戒分类 我们既不知道环境f ( o ) 的性质，又不知道训练器f l ( “j i 。) 的决策规则然 而，我们确实知道遽两个函数帮熄存在的因此，联合分布f ( u ，g ) = f ( w t x ) f ( x ) 氇是移在露。褒雀，给定一函数嶷，a ) ，a a ，宅廷载十蓬o ，l ，自一l ( 嶷 策规则集) 我们考虑最简单的损失函数 ， 三白，) ； 。， ”4 ( n 1 ) ll ，“母 分类问题是，在函数集( $ ，a ) ，n a 上摄小化泛阈 ， 霆每) = ；三知，簪( 茹，盘) ) 。i f ( 。，。) ( 1 i 2 ) j 其中分布函数f ( w ，) 是未知的，但给出独囊的随机样举点对 和l ，g i ) ，妇，觏) ( 1 1 3 对于损失函数( 1 。11 ) ，泛函( 1 ，1 2 ) 确定了任何给定决策规则( o ，) 的分类错 误概举选样，问题就是，在未知概率分带函数f p ，。) 但飨出数据( 1 。i 3 ) 的情 疆下，最枣拖努炎镣谩概率舞了簿萃起琵，考虑两类努嶷闯题( 帮。翅，l 的情况) ，这里我们仍采用最简单损失函数( 1 1 ，1 ) 因此，分类问题已经归结为 基于缀验数据( 1 1 3 ) 最小化风险( 1 1 ，2 ) 的l 可题 】 考虑到在许多实际问题中，构造描述目标之间关系的距离函数比构造支 持向量机中的核函数更容易更自然，且在没有度量空间的先验信息的情况下， 可以利用度量的特性构造度量空间中数据的分类算法，本文讨论度量空间中 的分类问题 1 2 机器学习问题 在人们对机器智能的研究中，希望能够用机器( 计算机) 来模拟人类的学 习能力，这就是所谓的基于数据的学习问题，或简单地称为机器学习问题这 一问题的研究目的是设计某种方法，利用学习得到的规律，较好地解释已知的 实例，并且能够具有对未来现象或无法观测的现象作出正确预测和判断的推 广能力 六十多年以前，r a f i s h e r 提出了模式识别理论中的第一个算法，判决 分析法二十世纪6 0 年代，f r e s e n b l a t t 提出了第一个学习机器的模型， 称作感知器这标志着人们对学习过程进行数学研究的真正开始 在人们对学习问题的研究过程中，从6 0 年代r o s e n b l a t t 的感知器模型， 到7 0 年代学习理论基础的创立，直到8 0 年代神经阿络的出现。统计学一直 在解决机器学习问题中起着基础性作用然而，传统的统计学所研究的主要 是基于大样本的渐近理论在实际问题中，面对的样本通常是有限的，使得针 对大样本的各种算法，条件往往难以实现，并且这些针对大样本的算法在样本 较少时未必有较好的表现，当问题处在高维时尤其如此其中，近年来常谈论 的神经网络过学习问题就是一个典型代表t 当样本有限时，本来很不错的一个 学习机器可能表现出很差的推广能力 人们对于解决此类问题的努力一直在进行vn v a p n i k 等人早在2 0 世纪6 0 年代就开始研究有限样本情况下的机器学习闻题，并于7 0 年代末建 立了有限样本的学习问题的基本体系，直到9 0 年代形成了一个较完善的理论 体系一统计学习理论( s l t ) ，它针对小样本统计问题建立了一套新的体系而 同时，神经网络等较新兴的机器学习方法的研究9 遇到一些重要的困难。比如 如何确定网络结构的问题，过学习与欠学习伺题，局部极小点问题等等在这 2 种情况下，试图及鬻本质上研究学习闯题的统计学习理论逐步得到黧棍，无论 是在学习理论中，进是在理论成用统计学中，都形成了一个前沿的研究方向 1 9 9 2 年一1 9 9 5 年，在统计学习理论鲍蕊醛上发展赶7 一种遥用的机器学 习方法一支持商擞机。较甜往方法表现出穰多理论和实践上的优势它建立 在统计学习理论的v c 维理论种结构风险最小化( s r m ) 原则基础上，根据有 限襻零售患在楱燮姆复杂性稚学霹髂力之阕寻求最佳捞襄班期获霉最好静携 广能力$ v m 鼹统计学哥理论的一种戚渤实现虽然这一新兴的学习方法 中尚肖许多问题需螟进一步研究，但很多学脊认为，它磁成为继模式识别和神 经隧绻研蹇之后枕嚣学习领域耨的研究热点，在模式识别，函数遥避，信号硬 测，信息融合等领域，s v m 敬得到了广瑟应用，它辩避一步研究必将推动机 器学习理论和技术的重大发殷 l 。2 ，1 撬嚣学习惩瑟静衰拳 机器学习问麒的基本模麴包括三个部分；样本生成嚣( g e n e r a t o r l 依照某 一来知概率势枣穗祝产生数撼$ ，赣 到我柏研究的对象监督器( s u p e r v i s o r ) 中得到一个输出轨同时学习机器( l e a r n i n gm a c h i n e ) 辩输入$ 响瘦输出，( 习 机器学习问题可以形式化的表示为z 融知输入空间爿与输出空间y 之同 存褒一定鳇来霸袋赣关系，帮存在一个来翔的联合摄察溯麦p ( o 滂) ，撬器学 习就擐根据包含m 个独立茼势布的观浏样本的集合 s = 扛l ，搬) ，+ 一，( 。；，皱) ，- 一，( z 。，# 。) ( 1 2 ，1 ) 在一十函数集( 或称假设空间) ，中寻拽个最优的函数，使它的期壤风险( e x - p e c t e dr i 3 k 1 ， 鼠疗一7 职职，( 妨) 扭擘，曲( 2 2 2 ) j 最小，其中矿表示在给定输入。下。监督器的响应，与学习机器给出的响应 ，露) 之涟静擐失。不霹类型懿学茸惩麓穗貔其毒苓霹澎式懿擐失蘸数。 在这一体系中假设空间，是一个 芝娥空间，在，中需要定义一个收敛 准则，即f 必卿 黼于拓扑结构本文始终假定其为一曲拓扑向量鸯间一般 3 说来，学习问题是一个不适定问题，通常将问题转化为下述最小化问题： 磐( 去姜v ( 帅扪瑚) 其中泛函n ( ，) 表示了，光滑性的先验信息，参数 0 是在，对样本的拟 合度与，的光滑性之间进行调节的参数，通常称为正剐化参数 而当写出损失函数时，我们已暗示了函数，在任何一点a 是已知的进 一步，如果我们能够使用学习机器对任一给定的输入。作预测，那么，0 ) 必 须对所有z 爿都存在，即我们需要的是点点有定义的函数集同时要求评 价函数是线性的，连续的，使得假设空问具有再生性在赋予函数集这些性质 后就会产生许多有意义的结果在学习机器领域最有用的结论是一个核函数 耳的存在性，个具有再生性的二元函数 v ，jo l ，i 一1 ，一，m ，m n ，s t ，o ) q c ( x ，) 因实际的原因，可能有不同的表示，主要依赖于核的选择如果函数 集是一个h i l b e r t 空间，那么，它成为一个再生核希尔伯特空间( r k h s ) 尽 管h f l b e r t 结构对于学习问题的假设空间不是必须的，但再生核希尔伯特空间 及其相应的再生核园具有良好的性质，在学习领域中被广泛应用 1 2 2 机器学习的基本问题 机器学习问题中最基本的三个问题是模式识别，回归估计和概率密度函 数估计 在模式识别( 即分类) 问题中，对于两类情形，输出空间为y = 1 ，1 ) ， 假设空间y - ：= s g n ( ，) ：f ， 考虑的损失函数为 y ( 蚶( 瑚： 帅”g n m ) l1 ，其它 对于这个损失函数，( 1 2 2 ) 式的风险泛函确定了训练集s 和学习机器响应 的函数所给的答案不同的概率我们把该函数所给的答案与训练器输出的值 不同的情况叫做分类错误这样，模式识别问题就成了在概率测度p ( x ，y ) 未 知，但训练样本集( 1 2 1 ) 已知的情况下，寻找使分类错误最小的函数 农回归估计问题中，y 量皴，为安德函数集合考虑的损失藏数为 v ( y ，( 。) ) = ( y 一，( z ) ) 2 我们知道，在该损失函数下，使( 1 2 2 ) 式最小的函数为 ，0 ( 。) = y d p ( y l g ) 其中p ( y i = ) 为条件概率铡度，通常称该函数为回归函数这样，西归估计问 题就成了在概率测度未知，但训练样本集已翔的情况下，寻找回归醋数的逼近 闻黩， 在密度函数 寄计中，考虑在概率测度p ( z ) 未知，黼绾出独立阿分布样本 情况下，利用损必函数 v 如( $ ) ) = 一l a p ( z ) 爱麓婆风陵( 1 2 2 ) 式这到最小 1 2 3 机器学鼬问题的基本方法 统诗学在瓣炎氍器学霉弱瓤懿方法孛趣着基璃蛙镩蹙，毽薄缀戆统计学 所研究的主要是渐进理论，即幽样本趋于觅穷多时的绒计性质在现实问题 中，我们所面对的样本数目通常居有限的，有时还十分宥限统计学习理论是 奎v ，n v a p n i k 簿入旱在2 0 锻纪6 0 每鼗靛嚣始翡萋予程限撵本条 孛瞬究筏 器学习问题，而捌9 0 年代中期才形成的个较为完整的理论体系 统计学习理论的核心内容包含以下四个方面： 1 ) 经验最险凝夺霓熏蘩l 下统诗学习一致瞧戆条 孛； ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论； ( 3 ) 在这些界的基础上建崴的小样本归纳推理原则t 氍) 实瑗这羲耩瓣蘸粼静蜜嚣方法( 羹法) 所谓经验风随最小化( e r m ) 原则是t 根据学习i 聊题给定的实际条件， 为了梅未知概率测度下最小化甥望风险，黼采甩最小化经验风险( e m p i r i c a l 5 r i s k ) 叫) = 熹姜州) ) 当襻本数霜m 趋予惹努时，著髑时有 e ( f ) 一器8 ( n 孟( r ) 一磐 ( 其中，+ = a r g r e l a y ，( ，) ) 成崴，则称e r m 是一致的 这漾戥是菲紫一般黪，蘩决一墼特臻擎湾阏嚣戆镶多传缝方法，鲤鹾舞 估计问题中的最小= 乘法，概率密度估计中的最大似然法簿都是e r m 原则 的具体实现统计学习理论中的关键定理把e r m 一致性的问题进行了转化 定理1 2 1 ( 2 4 j ) 对于有莽锅失海数，e r m 学习一致姓的充分必要条件是； 垤 0 ， 熙p m 磐) 一e d f ) ) 5 2 o 在e r m 原则下。关于统计学习推广性的界的理论，v a p n i k 等人提出了 函数集的v c 维概念称函数集的v c 维为h ，若h 为能够被，中的蛹散以 辑毒可籀懿2 矗释方式分成两类翡离萋盈，魏翡最大数秘，谴秘稃磁如下 形式的v c 界 定瑾1 2 。2 ( 【2 壤) 簿母考暴嚣受鸯羲囊，= ，：o ，嚣 ，v5 ( o ，1 ) 下面不等成以至少1 一占的概率威意 s ，u 。p ( 黜m ( 甥譬( 1 + f 口、 其中兰4 业生掣，h 为芦的w 维 在这一结果的蒸箍上产生了结构风险最审他( s 跚) 溅弼j 该努鳢源尉旨 在针对经验风险和置倍范围这两项最小化风险泛函它定义了在对给定数据 逼近的考囊度和遥近丞数的复杂性之间姆一种攒中。出于期搬风险的界是经验 6 风险与置信范围的和，s r m 通过选择一个恰当的容许缔构，使得随着结构元 素序学的增加，经披风险逐渐减小，丽置信范围将增加，最小期望风脸的界是 在鳍褥缒菸个适当醵元素上取攥+ 在s r m 的思想基础上产生了两类学习机器神经阕络和支持向爨机前 者是保持置信范围嘲定( 通过选择一个适当构造的机器) ，而最小化经验风险 后毒潍壤行保持经验菇验篷露悫( 毙热等予，著最枣诧嚣痿范霹这一策略。 本文主嚣考虑支持句量机这一通用的机器学习方法 l 。3 变耪商量撬囊警基本惹戆 支持向量机算法由v a p n i k 及其合作者在计算学习理论( c o l t ) 1 9 9 2 年的 会议串蓠次提出来，之嚣受到了广泛馥关注。在2 0 整鳃9 0 年婕嫠期褥弱了 全面深入的发展，现吕成为机器学习和数据挖掘领域的标准工具吏嚣原因之 一是8 v m 是机器学习领域若干标准技术的寨大成者，它集成了最大间隔超平 嚣，m e r c e r 接，热= 次侥纯，糖藏躲嚣橙魏变量等接本，在若于撼羧睦的应 用中获得了目前为止最好的性黼在美国科学杂志上，s v i v l 及核方法被认为 是“机器学习领域非常流行的方法和成功的例子，并是个令人瞩目的发展方 海”避每寒，s v m 缒理论基缝致褥了重太避嶷，萁冀法实褒蒙珞及赛蠡应 用也发展迅速，可以确信t 该技术的研究矗发展成为机器学习中个独立的领 域，在理论和实践黼方面都有糟光明的前景 l 。3 1 再生桉h i l b e r t 空嗣 一个学习机器息是在一定的函数集上实现某种算法的，函数集的类型和 性爱缀大程囊主淡定着算法实瑷戆难易程凄缭定静蘧数空瓣稚势镁谖空翅 ( 模型函数集) ，其中的每个函数均称为假设榱机器学习是现在比较流行的一 种机器学习算法窘的思想是将数据映射到嵩维的特征空闯，寻找特征空间的 装瞧学号靛器嚣逮释线睦学霹撬器在对髑童海是塔簿鬣映射海弦黪形式窭 现的。此时内积对陂着原始空悯的核函数。邋过选择核嚼数来代替内积后，就 隐式地袭录了特征映射在计算时只需要计算棱函数在成对出现的训练样本 7 上的值 s v m 属于核机器学习的范畴，不过它选撵的核为再生核，它的假设空间 是由这个碳导出静葛受援希尔偿黪宝藏，下霹将绘窭它瓣定义 定义嫡数 k ：爿七叫强 ( $ ，句- 一暂池t ) 记恐( t ) = 耳( z ，t ) 对每个固定g z ，耽( ) 是爿上的函数若( z ，t ) = k ( t ，。) 对耩毒( s ，e ) 岸x z 成嶷，豫稚嚣蔻对嚣鳃嚣蟊露时述奖予嚣 个变量遗续，剐称岸( t ，o ) 为棱醋教 下筒我们定义正定核 设爨数k ：z 鬣，超瀵楚条箨； ( 1 ) 描是对称的； ( 2 ) 对任意z l ，靠，g r a m 矩阵 k 一( 盯( 墨，) ) ；1 满足协z ”，x k 0 则称为正定棱。若此时k 逐连续，则称其为 m e r c e r 棱， 常见的m e r c e r 棱有以下两种形式： ( i ) k ( x ：) = ，( l 。一一炉) ， 辩嵩斯径自羞穰瓣靛凳缸，茹一) = 。一譬， ( 2 ) ( $ ，z ) = ，扣- ) 如多项式核函数岸( ，妁一( 1 + 。一哆 m e r c e r 挟具有下鬻两能嚣t ( 1 ) m e r c e r 核是非负的t 事实上，在定义中取n = 1 即可 2 ) ( 菇( ，”) ) 2 愆扛，回k ( # ，”) ：事实上，在定义中玻= 2 ，得到 心舭啦舞搿) ( 兰) 菲负邵 x i k ( u ，u ) 十2 z l x 2 ( u ， ) 十。；( _ ， ) 0 这说暖关于z t ，如静二次式酶粼l 式是 燕鳇，嚣诧 ( 2 k ( u ，”) ) 2 4 k ( u ，“) ( ， ) 0 出戴瑟得f 2 ) 。 定理1 3 1 ( f 2 4 j ) 设函数k ：甜z 畸r 是m e r c e r 核，则存在定义在岸 上的连续函数组成的希尔伯特空间奠k 满足下面性痿 v t 七，v 几) 7 l k ，坤) = ( ，( ) ，喝( ) ) 日 我魍把壤定遮巾茬曩鬟；毙褥垒洼，穗燕孬垒睦骛棱被稚为再垒棱。f 获这 里我们可以看到m e r c e r 核是再生核) 我们把州q 做由核导出的再生核 希尔怕特空间( 3 1 ) 下面我们米考察h 的结构 令西是并定+ r 戆m e r c e r 援，定义获势冀子 ， 丁k ，一k ，一) ，( 一) 如 j 夸太强嚷汹努菇燕! k 懿持短璧纛榜程瓣鼗。 根据m e r c e r 定理 合 嘲 考虑缀数集 k ( x ，嚣，) 一玛够毫( 。) y = 1 c j ( z ) = v 百啦， k ( x ，z ) = 幽( z ) 如( z ” ，。i 5 r _ - ( ，：m ) 一哪由 0 在，中定义内积 ，。o、 ( a j c j ( z ) ，南( z ”= a j b j k ( x ，。，) ， 、，= lj 2 l ，盯 仁i j = l 则，关于上面定义的内积是一个r k h s ，即，是由核导出的再生核 希尔伯特空间州k 不难验证再生性成立； 、 ( ，( z ) ，k ( z ，一) ) h = ( 畸咖( 。) ，如( ) 咖( 一) ) j = 1，= 1 ，日 = q 由( 一) = ，( 一) j = l 对，中的函数，( 。) = a j 由( $ ) ，若令 j = l “j = ( a l ，a 2 ，一，8 ，) ， 妒( z ) = ( ( z ) ，也( 。) ，机( z ) ，) ， 则f ( x ) 可以表为f ( m ) = ( u ，妒( 。) ) 的形式我们称定义在z 上的映射 妒：妒( 。) = ( 1 ( z ) ，也( 。) ，- ，妣( z ) ，- - ) 为特征映射，t = 仲( z ) ，。并) 为特征空间 若a j = 啦咖( 戤) ，则 i = l n ，( 。) = n 。咖( 盈) 咖扛) i = 1 i = 1 no o = “。奶( 矾) 奶( z ) = 1 j = l n = m k ( 。，吼) ；= 1 n 即，( 。) 可以写成，( z ) = 啦g ( x ，缸) 的形式，我们称，( z ) 的这种表示形 式为f ( x ) 的对偶表示基于核的学习算法的思想是将原问题转化到对偶空间 求鹪，从而将解转化为对偶表示，这为我们的计算提供了很大的方便 注意到，假设空间，中的函数，( ) 一和，p ( 。) ) 与标准的s v m 算法的 定义，( 。) = ( u ，_ p ( 。) ) + b 相差个常数b ，本文假定b 包含于r k h s 1 0 1 3 2 最大间隔分类器 s v m 中最简单也是最早的模型是最大间隔分类器，它只能适用于特征空 间( 即原始数据经过一个非线性映射后所在空间) 线性可分的情形不用说， 它是最容易理解的算法，并且是更加复杂的支持向量机算法的主要模块它 展示丁这类学习机器的关键特征1 9 6 2 年，n o v i k o f f 用对应于训练集s 的 假设，的间隔给出了线性学习器的推广误差界，并且用于分开数据的特征空 间的维数没有出现在这个界中而最大间隔分类器就是通过用分开数据的最 大间隔超平面来优化这个界，并表明这个界不依赖于空间的维数，因此这个分 类面可以在任何特征空间中搜索得到最大间隔分类器形成了第一个支持向 量机的策略，其基本思想简单介绍如下 设，d ) 表示输入空间( 原空间) ，一般为r “的紧度量子空间y 为输 出空间，对两类分类问题。y = - 1 ，1 1 ；对于回归问题，y r z = z y 称为样本空间，其上定义了未知概率测度p ：依据该分布随机独立产生包含 m 个样本的训练集s ，即 s 一( z 1 = ( z 1 ，”1 ) ，一，薯= ( 积，玑) ，南。= ( z m ，蜘；) 特征映射妒将原空间爿映射到特征空间妒( 爿) 设 ( _ p ( z ) ，可- ) ，一，( 妒( m ) ，卦m ) ) 为线性可分的集合假设空间，中的元素具有形式 ，( 。) = 帕 其中 表示n 维向量u 和妒( z ) 的内积，b 为偏置该函数定义了特征 空间的一个分类超平面 + b = 0 我们将判别函数归一化，使两类样本都满足l ，( z ) l 1 若定义分类间隔为两 类样本到超平面距离的最小值，则它即可表示为由 1 1 霉1 1 鼯就，使阍辍最大麓是等价懿爱l u 舻最小寻我最大耀疆分类器就是求 麓下面的二次优化闷蔻 s , t 。承，( 瓤) 1 i l ，t 一，m 道个瓣题可以遴过l a g r a n g e 方法转化期对偶富闻密解，即 逸些口；稚为l a g r a n g e 黎子蓑k a r m h - k u h n - t u c k e r 系数，他砖穗蔗豢辞 诎( 赞，( 鼬) 一i ) = 0 ，i = 1 ，t 一，m 遁进菏单酶计算可鞋舞得 一 敝 ，骓 盘一 m 幅i ， “ 一 l 一2 1 = l l z 氆 o o 五 警疏 矾 铲 摊 k 口 ；h 赫 与这些。：0 对应的样本点满足 y d ( 。k ) 一1 = 0 称满足上式的输入向量。 为支持向量( s v ) 通常，支持向量的个数z 远小于 样本总个数m 最后得到最大间隔分类器f 具有形式 m ) = y a i k ( x 舭) + 扩 其中 矿= 一! ! ! 生三二! ( 三竺：! 竺! 兰1 2 三! 型竺塾三! ( 三! ：! ! 苎2 三2 2 而k ( x ，z 7 ) = 称为核函数 最大间隔分类器没有试图控制支持向量的数目，但实践中通常只有很少 的支持向量，解的稀疏性也促使产生了很多实现技术来处理大的数据集( 8 ) 1 3 3 软间隔分类器 最大剐福分类器是一个重要的概念，它是分析和构造更加复杂的支持向 量机的起点但是当数据在特征空间线性不可分时，最大间隔分类器不存在 所以它只是完美的产生一个没有训练误差的一致假设，而在真实数据中，噪声 总是存在的，这会导致算法出现问题 我们对最大间隔分类器进行推广，当数据在特征空间线性不可分时，允许 有少量的的样本被错误分类。并且保证分类后有一个较大的间隔例如假设 v 岛，l ，( q ) | a ，如果我们考虑的是样本分类正确与否的数目，可以采用下面 的错分类支持向量算法解决下面优化问题( f 1 1 ) 肛”s 磐阻旷+ 等娄矗) ( 1 。t ) s t 6 = ： ，( q ) l a ， 玑，慨) 0 y i f ( z , 1 0 i = 1 一n 1 3 定义损失函数 其相应的期望风险为 经验风险为 则( 1 31 ) 式可以等价的写作 = a r g 磐( 风m p ( u ) + 匆u i l 2 ) 1 4 m m 肛 ? p =， 1 一n 瑚 i | 。 = 八 d n 地 毗 础 第置章度鲞空间中的最大间隔分类 2 1 介绍 设( 茗，d ) 戈震囊空惩，= - 1 ：l 滩练榉本扫i ，啦) ，( # 。，鍪擀) zxy 是依据省y 上的莱个来知的分布黼数f ( z ) 随机独立抽驭的讨论 空间爿中的分类问题，就是根据所给训练样本，构造近似表示未知分布f ( x ) 的学嚣魂器。本厦士，它可髓表泰如下： l 练溪强测到耩瘩理的事姊劳确定所 出现的事件属于类中的哪一嶷；需要构造一个橇器，该机器在观测了训练 器的分类后能够以姆训练器相同的方式近似的完成分类工作 蹇撩鸯量癸樊撬是解烫努类惩题懿一释毒效算法( 基罐 i 3 它i 莲蓬棱垂 数定义的某个非缝性变换，将输入向量m 映射到特征盘间z ，然后寝z 中构 造最优分类超平面，从而实现对卫中数据的分类支持向量机方法恩有很好 懿挂广薤力，虽攫蘑筷函数方涟，避免了缨数灾难l 霹爨( 1 l 饕) 当稍练襻本线 性可分时，我们可m 通过构造簸大问隔分类超平面来构旋支持向量分类机当 训练样本线性不可分时，则可构造软l 可隔分类超平面构造支持向量分类机 考虑刭在谗多窦舔瓣嚣孛，糖造接逮嚣檬之蓠关系戆踅离丞数毪_ 辫造支持 向量机中的核函数更窖易更自然，且在没有度量空间的先验信息的情况下，可 以利用度量d 的特性构造z 中数据的分类算法，本文讨论度量空间中的分类 簿疆。燕薅单趁冕，我蠡考虑努戏嚣类静悸麓( k = - - 1 ，1 ) ，首竞对亏：一类特臻 度量d ，它满足一水是条件芷惫的。则最大间隔分类嚣童i 是此类空间刀中的 分类算法由一舻是条件正定的知一铲是岸到瓞的条件正定棱函数 根据条件更定接满数与正定棱瓣数窝懿转诧荚系，遵过度量d 梅遗一个正定 核函数，由此正定榱函数定义一个非线性映射。将度量嶷河( 七，d ) 等距嵌入 到一个再生核h i l b e r t 空间，利用再生核h i l b e r t 空间的线性结梅，谯其中构 造最夫阗隔分类斑平霉然意，考虑一簸炭最空闻( 并，番中的努樊闯题，苇 同于前者的是将搿等距嵌入到一个b a a a c h 空间，利用b a n a c h 盘间中最大 化越平面的间隧与掰类集合间距离的等债性来构造最大间隔分类算法 1 5 2 2 度量与核函数问的转化 定义2 2 1 定义在z z 上的实值函数耳称为正定的 日应地条件正定j ，当 且仅当k 是对称的且v q r ，x i z ，i = l ，2 ，m ，m n 一目应地v q r ，i = 1 ，2 ，m ，7 _ - 1 q = 0 ) 有 ，nt n c j c j k ( ) 0 f = 1 j = 1 易见，正定的核函数一定是条件正定的 当度量d 满足一铲是条件正定时，一d 2 是x x x 到r 的条件正定核函 数它与正定核函数有如下转化关系： 命题2 2 2 ( 2 1 ) 爿是输入空间，是其上的条件正定核函数，则 d ( # ，y ) = x k ( x , z ) + k ( y ，y ) 一2 k ( x ，y )( 2 2 1 ) 是2 3 上的半度量，且一铲是条件正定的反之，所有z 彤一r 的条件正 定核函数可由满足一d 2 是条件正定的度量d 诱导； 1 k ( x ，y ) = 一；d 2 0 ，y ) + g 缸) + g ( )( 222 ) g 是z _ r 的函数 证明易知d ( ) 是空间z 的度量若k ( x ，y ) 是条件正定的，则k ( x ，y ) = k ( x ，y ) + g ( 。) + g ( y ) 也是条件正定的一 m m m mm m q 勺肖( 岛国) = 膏( 翰，q ) + 2 q 9 ( ) i = lj = l 1 = 1 j = l= 1 j = l m ”1 = 詹( ) 0 = l j = l 因此由( 2 21 ) 式知一铲是条件正定的另一方面，若一d 2 是条件正定的，则 根据( 22 ，2 ) 式可定义一个条件正定的核函数耳 口 命题2 2 3 ( 1 】) 若k 是条件正定而不是正定的一个核函数，则v 功z ， k = ( 。，y ) 一g ( x ，z o ) 一k ( x o ，y ) + k ( x o ，x o )( 2 23 ) 是正定的当且仅当k 是条件正定的 1 6 2 3 度量窝间中的最穴间隔分滋算法 送一部分营建分缨特殊度擞空闯中鲍最大间隔分类这里的特殊度量空 闻最措度量d 潞遐一铲是条件正定静穰掇驻上介绍静度量与核醋数阔的转 化关系。我们得到下面的定理； 定瑾2 3 。1 1 4 1 ) 设( z ，毋势度量空薅，藏度量d 满蔑一毋是条佟蒜定娉 则矗太间隔分类嚣是此类度量堂间中的最太间隔分类算法， 证弱：根据度量d 满足一扩凳条件正定静这一特性，遗过( 2 , 2 2 ) 式搬( 2 ，2 3 ) 式。可由d 构造一个正定棱磷敷霞然后利用霞定义一个非线性映射 垂：爿_ 取芹。h 巾。= 霞( ，) 将魔激空间( ，等距嵌入劐一个荐垒棱h i l b e r t 垒阔最后利掰再生棱 h i l b e r t 空间的线性结构，在萁中构造最犬间隔分类超平面即解优化问题t n 擎| | 虢a t 如，| | 釜2 y l y j c t t 唧霞敏，辱) t 2 1 o l ，。i nm一 = 雏珊卜i 萨( 戤，妁) + 9 ( t ) + 9 ( q ) l 2 l j o j - m 斑 = 一；y i y j a i a f l 2 ( 哪) ”l = l j = t s t 。虢如一o ， j = l 础一2 ， = l 趣三0 解得分类算法为 ，( 。) = 虢铷霞墨，甸+ = 喜【一孙 m 州叫 1 7 = 一鸯嘶一) 十c 丑 上述讨论仅隈鼍：满足一萨是条件正是静这类特殊淡基空间申的分类问 题讨论一般度量空间( z ，d ) 中的分类问题，介绍以下分类算法 考虑一般度量盎随浮，啦中静分类算法，可通过度攮d 定义一个非线性 浃翦将囊间z 等躐嵌入到一个b a n a c h 空瀚，利甩b a n a c h 空间中激太化超 平面的间隔与两类集合间距离的粹价性来构造最大间隔分擞算法( 1 1 6 1 7 1 ) 首先考虑如下辫个映射v x o 髫， 圣：出+ 豫并 书h 圣。：= d ( g ，) 一d ( z o ，) 田：爿_ r t $ h 皿。：= d ( + ，砷一d ( z q , # ) 令 d = s p a n e z ：o ) ， e = 婶 峨：$ 掣 ， 0 e 1 | z = i n f 庙l ：e 。忍m 。吼z ，i ，i o 。 1 l 理2 3 ，2 4 1 ) 姨耪圣甍度量蜜藏( 名，礴等距嵌凡 b a n a c h 堂麓 ，) c 幅( 省) ，) 证明圊为 l 屯茎d ( 。，勰) 。 j | 蚤* 国) 一垂。( ) | | f t d ( z ，) 一d ( x ，g ，) | l 十i d ( z o ，y ) 一d ( z o ，) 0 茎铽舀，奶， 所以 盘渊) 又 i | 4 0 一量i 。= l f ) 一d ( y ，) l 。 d ( g ，y ) 且在点z ，”取到最大僦，故垂姓鸯闯，d ) 到b a n a c h 空阐( 西，”l 。) c ( c b 彤) ，l i ， l 。) 的簿距映射 8 引理2 , 3 3 ( 【7 1 ) 1i i g 是空间e 的度量 证鞠耪翱弘妇燕室阕嚣辑举藏奄， 西势 j e e ，s t ，涮| 嚣= 0 ， 所戳 j ( 矗) ，( 臆，n ) ，。袖，s t 。e = 成。坦。， 厶 l 触l 一0 。 敌g 0 。 v # 男， 8 $ ) l = 鹰。零。( g ) 域如 s 她x o ) i 堪如 定理2 3 。4 ( 【1 4 1 ) ，| | - l 彩警豫麟铸千( 黟，| | 1 l 黟) ，蓉建嚣棼鹾恕嚣麓 f 是努娉肆蔼蜜瓣。 证明令 蚤一 秽：g ，磷一0 ，v d d 口 考虑枣滴m ( x ) d ，裰蕹f i 4 | ) 串逛理4 , 9 ，移等聪间构于 d ( 西1 定 义姨射 d ：e 4 印 是：# 盘) 弦 廿( 田。) = 如b ， l 剃空闻e 等距同构于s p a n 6 。x i d 故( 嚣， | - 吾) 等飚闶构于 ( 可，f i 伊)口 程b a n a c h 空阕牵，最大识趣乎嚣鲍越瓣等秘