（概率论与数理统计专业论文）统计学习算法：多分类及非独立同分布抽样下的回归.pdf

摘要 摘要 随着现代科学技术的发展，人们每天都要面对大量无法直接理解的数据。 如何利用计算机来帮助我们理解和处理数据信息成了当今科学技术界的一个 重要研究课题。机器学习是计算机得到广泛应用后逐渐发展起来的一门学科。 它是人工智能的一个子领域，主要研究如何利用已有的经验数据设计一些算 法使计算机具有从数据中学习出规律的能力。机器学习跟统计学有着重要的 关系，因为这两个领域都是研究数据分析，但是又不像统计学，机器学习关注 的是计算实现的算法复杂度。很多推论问题属于无程序可循难度，所以部分 的机器学习研究是开发容易处理的近似算法。 学习理论是机器学习的一个分支。它是一个跨学科的研究领域，涉及应用 数学、统计、计算机科学、计算生物学和数据挖掘等学科。它的目的是通过数 据学习函数的特征( 例如函数值和变量) 或数据结构。主要研究课题包括设计 一些更有效的算法和为机器学习中已有的算法提供理论支持。 在此论文中，我们研究了两个问题。首先是提出了一种新的多分类算法。 我们通过p a r z e n 窗设计了一种多分类算法，并对该算法进行了理论分析。这 种p a r z e n 窗多分类器优于通常的通过结合二分类器来构造多分类器的各种方 法。因为通过结合二分类器得到多分类器的方法往往很复杂，而且对于某些 区域，分类的结果往往不一致。在抽样的条件概率分布的某些正则条件和边 际分布靠近边界的某些衰减性条件假设下，我们给出了额外分类误差的收敛 阶。 在文献中，当附z e n 窗用于密度估计和回归时，逼近误差一般是在离开边 界的输入空间x 的内点上估计。我们的主要贡献是在数学上证明了当边界附 近抽样的边际分布满足一定的衰减条件时，我们能在全输入空间上得到满意 的额外分类误差的l 1 范数或者c ( x ) 范数的阶。 其次，我们研究了非独立同分布抽样下的学习算法。该类算法包括最小 二乘正则化回归和二分类问题。在过去的几年里，学术界对独立同分布下的 正则化回归算法的理论分析有了重大进展。但是，无论独立或同分布都是一 个相当严格的假设。在现实的数据分析中，如s h a i l n o n 抽样，啪d o l t l i z e d 抽样或 者弱相依抽样都不满足这样的条件。我们的设置不要求独立或者同分布条件。 在抽样的边际分布序列满足在h 6 l d e r 空间的对偶空间中指数收敛的条件，和抽 样序列满足多项式弱相依条件下，我们得到了和假设空间容量无关的逼近阶。 而且当弱相依抽样的条件弱到接近独立抽样的时候，我们的逼近阶和独立同 i 摘要 分布抽样下的逼近阶是一致的。对于非同分布下的二分类算法，我们也得出 了满意的额外分类误差的与假设空间容量有关的逼近阶。 关键词：学习理论，误差分解，再生核希尔伯特空间，多分类算法，回归算法， 逼近，非独立同分布抽样，黎曼流形 a b s l l r a c t a b s t r a c t l e 锄i n gt h e o r yi s a i li n t e r - d i s c i p l i n a 巧r e s e a r c hf i e l di n v o l v i n ga p p l i e dm a t h e m a t i c s ，s t a t i s t i c s ，c o i i l p u t e rs c i e n c e ，c o m p u t a t i o n a lb i 0 1 0 9 ya i l dd a t a 面n i n g i ta i m s a tl e 锄i n gf u n c t i o nf e a t u r e s ( s u c ha sf u n c t i o nv a l u ea n dv 撕a _ b l e s ) o rd a t as t m c t u r e s f r o ms a m p l e sb yl e a r m n ga 1 9 0 r i t l l m s m a i nr e s e a r c ht o p i c si n c l u d ed e s i g n i n ge f j i i c i e n t a l g o r i t h m sf b rv a i i o u sp 珈o s e sa n d 血e o r e t i c a la i l a l y s i so fl e 枷n gm e m o d s i i lt h i st h e s i s ，w ec o n s i d e rt w or e s e a r c hp r o b l e m s 。t h e6 r s ti st op r 叩o s ean e w l e a r n j n ga l g 嘶t h mf o rm u l t i c l a s sc l a s s i f i c a t i o nb yp a r z e nw i n d o w sa n dt oc o n d u c t b o t ht h e o r e t i c a l u n d e r s t a n d i n g a i l da p p l i c a t i o nf b rt t l i sa l g o r i t h m t t l i sp a r z e nw i n d o w s c l a s s m e ri sb e t t e rt h a l lm eu s u a lw a yo f d e s i g n i n gm u l t i c l a s sc l a s s i n e r sb yc o m b i n i n g b i n a r yc l a s s i f i e r si nv 缸o u sw a y s ，w h i c hi so 舭nc o l p l e xa n dh a st h ep r o b l e m so f o v e r l a p p i n g w eg i v em ec o m r e 曙e n c er a t e so ft i l ee x c e s sm i s c l a l s s 讯c a t i o ne r r o r u n d e r s o m er e g u l a r i 哆c o n d i t i o n so nt h ec o n d i t i o n a lp r o b a b i l i t ) rd i s t r i b u t i o n sa n ds o m ed e c a y c o n d i t i o n s 锄t h em 蝣i n a ld i s t r i b u t i o nn e a fm eb o u n d a r yo ft h ei n p u ts p a c e 1 1 1m el i t e r a t u r eo fp a r z e nw i n d o w sf o rd e n s i t ye s t i m a t i o na n dr e g r e s s i o n ，t h ea p p r o x i m a t i o ne r r o ri se s t i m a t e dl o c a l l ya tp o i n t sw h i c ha r ei nt h ei n t e r i o ro ft h ei n p u t s p a c exa w a yf 幻mm eb o u n d 哪lo u rk e yc o n t r i b u t i o nf o rm em a t h e m a t i c a la n a l y s i s i st os h o wh o wt t l ed e c a yo fm 鹕i n a ld i s t r i b u t i o n sn e a u rm eb o u n d a d ，y i e l d ss a t i s f a c - t o r ) rb o u n d sf b r 咖i nt e m so fl 10 rc ( x ) n o n n st a k e n9 1 0 b a l l yo nm ew h o l ei 印u t s p a c e i h es e c o n dr e s e a r c hp r o b l e mc o n s i d e r e di nm i st i l e s i si s 血es t u d yo fl e a n l i n g a l g o r i t h m sw i t l ln o n - i i d s a m p l i n g t h ea l g 嘶t h m si n c l u d el e a s ts q u a r er e g u l 撕z e d r e g r e s s i o na n db i n a 巧c l a s s i 靠c a t i o n 1 1 1t h el a s tf e wy e a r s ，m e f eh a v eb ns i g m f i c a i i t d e v e l o p m e n t si i lm e o r e t i c a lu n d e r s t a i l d i n go fl e a n l i n ga l g o r i t t l m sw i t t li i d s a i n p l i n g b u te i t h e ri n d e p e n d e n c e0 ri d e r n i c a ls a n 叩h n gi sar a t h e rr e s t r i c t i v ea s s u m p t i o ni nr e a l d a t aa n a l y s i s ，s u c ha ss h a n n o ns 锄p l i n g ，r a n d o i i l i z e ds 锄p l i n ga n dw e a yd e p e n d e n t s a n l p l i n g 0 u rs e t t i n gd o e sn o tr e q u “ei n d e p e n d e n c eo ri d e n t i t y u n d e rt h ec o n d i t i o n s m a tm es e q u e n c eo fm a 玛i n a ld i s t r i b u t i o n sf o rs a i n p n n gc o n v e r g e se x p o n e n t i a l l yf a s t i nt l l ed u a lo fah 6 l d e rs p a c ea i l dt h es 锄p l i n gp r o c e s ss a l i s f i e sap o l y n o 而a 1s t r o n g i i l i ) 【i n gc o n d i t i o n ，w ed 甜v ec a p a c i 够m d e p e d e n tl e a n ：l i n gr a t e s o u rc o n v e 略e n c er a t e i sc o n s i s t e n tt ot 1 1 a to ft 1 1 ei i d s e t t i n gw h e nt h e1 1 1 i x i n gc o n d i t i o np a r 锄e t e rt e n d st o z e r 0 f o rab i n a d rc l a s s i f i c a t i o nl e 删n ga l g o r i t h mw i t t ln o n - i d e n t i c a ls a m p l i n g ，w ea l s o d e r i v es a t i s f a c t o 】哆c a p a c 时d e p e n d e n te s t i m a t e sf o rm ee x c e s si i l i s c l a s s i f i c a t i o ne 仃o r k e y w o r d s ：l e 锄崦m e o e 啪rd e c o m p o s i t i o n ，r e p r o d u c i n gt l i l b e r ts p a c e ，m u t i - c l a s sc l a s s i f i c a t i o na k o r i t h m ，r e g r e s s i o na l g o r i t l l m ，a p p r 0 虹i r l a t i o n ，n o n - i i d s 锄- p l i n g ，慰e m a i l i l i a l lm 砌f o l d s 斟 插图 插图 1 1 点z 到超平面伽z = 6 的距离 1 2 样本点完全可分情况下的线性分隔超平面 3 1 结合二分类器构造多分类器的两种方法：左图显示了把一类和 其他所有类分开的方法，右图显示了把类两两分开的方法。标 记问号的区域是分类结果不一致的区域 v 7 7 1 9 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志 对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 保密的学位论文在解密后也遵守此规定。 作者签名：蝉 。哆年( 月7 日 第l 章绪论 第1 章绪论 机器学习是一门在过去4 0 年里迅速发展的交叉学科，涉及统计、应用数 学、计算机科学、数据挖掘、计算生物学、信息论和其他领域。其主要目的是 利用经验数据设计有效的算法，使计算机拥有学习的能力。学习理论是机器 学习的一个分支，着重于为机器学习算法提供理论分析，并设计一些更有效 的算法。 本文研究的问题都属于监督学习。它主要是从一组给定样本点 ( 甄，玑) 】罂1 中学习函数或分类器。如果一个算法的目标是学习回归函数，我们称此算法 为回归算法。若目标是学习分类器，则称该算法为分类算法。 本文首先简要介绍经典的统计学习理论和支持向量机。 1 1 二分类问题 分类问题是科学与工程领域的一个经典问题。它在实际应用中有许多不 同的形式，比如文字识别、图形分类、网页分类和基因鉴定等。分类问题也是 学习理论研究的一个基本问题。它的主要目标是根据一些已知的样本或观测 值，构建一些分类器来预测样本的属性。出现一个新的观测值，我们就通过 该分类器来预测该观测值所属的类别。通常一个观测值是由一组反映该观测 值特性的数值组成。这一组数值在数学上可以表达成黔的一个子集( 即通常 的n 维欧氏空间) 。分类的数目可以由一组符号来表示，比如y = 1 ，2 ，尼) 。 学习算法的目标就是找到这样的分类器，它们是渺到y 的映射。 当后= 2 时，我们称该分类算法为二分类算法。对于二分类算法，文献中 已经有大量的算法设计和理论分析。当南 2 时，该分类问题称为多分类问题。 多分类问题将在3 中研究。在本章中我们只考虑二分类问题。 我们现在介绍二分类问题的设置。假设输入空间x 是一个紧的度量空 间，y 1 ，一1 代表两类。一个二分类器c ：x y 对于每一个x 中的点z 做 一个预测。因此分类问题的关键是学习两分类器。 为了度量一个分类算法的预测能力，一个恰当的误差概念很重要。对 于z x ，如果分类器分类错误的话我们称该分类算法产生了误差，也就 是，c ) y 。分类器c 的预测能力由在所有可能的( z ，可) 上产生的总的误差来 衡量。该误差称为分类误差( c l a s s i f i c a t i o ne r r o r ) 。 1 第l 章绪论 许多实际问题如金融工程、生物工程等的输入数据既是随机的，或者是 根据一个概率分布产生。在学习理论中，我们通常假设数据( z ，可) 是根据定义 在z = x y 上的一个b o r e l 联合概率分布p 选取的。因此分类器c 的分类误差 为误判概率，即事件彤( z ) 秒) 的概率： 冗( c ) = p r i d b 如，| ) z c ( 。) 可 = 尸( 可c ( z ) i z ) 却x ( 1 1 ) 在本文中，腿是分布p 在x 上的边际分布，尸( - i z ) 是条件概率测度。 显然，一个好的分类器应该产生小的分类误差。最小化分类误差( 1 1 ) 的分 类器称为贝叶斯分类器( b a y e sm l e ) ： ，c = a r g m i n 冗( c ) ( 1 2 ) 相应的最小分类误差冗( 丘) 称为贝叶斯风险( b a y e s r i s k ) 。 注意到当p ( y = 1 i z ) = 尸( y = 一1 l z ) 时，分类器的分类不影响分类误差。 因此贝叶斯分类器可能不唯一。为了简单起见，我们总是假设这些z 的分类属 于正的那一类。所以厶的表达式为： 丘( z ) ： 三1 ，薹；三：譬；三；三二；譬；： 如果p 是已知的，我们可以很容易直接计算贝叶斯分类器。但是在几乎所 有的实际问题中，概率测度p 是未知的。我们知道的只是一组样本 z = ( 戤，玑) ) 罂1 z m ( 1 3 ) z = t 【z t ，玑j ，i 兰1 么 l l - j j 因此贝叶斯分类器厶不能由直接计算得出。它必须通过算法从这些样本中学 习出来。 定义1 1 一个分类算法就是一个从样本空间u 袅1z m 到一组分类器空间的映 射，对于每个z 都产生一个分类器c ( z ) 一个分类算法的效率由一致性来衡量。一致性描述了一个算法能否产生 分类误差小的分类器。在此论文中，我们主要关注贝叶斯误差一致性，通过比 较得到的分类器的分类误差和贝叶斯风险。这两者之差冗 ( z ) ) 一冗( 厶) 称为 额外分类误差( e x c e s sr i l i s c l a s s i f i c a t i o ne n o r ) 。 定义1 2 如果对于一个分类算法c ，冗( c ( z ) ) 以概率收敛到冗( 丘) ，即对任意 的5 0 ，有 l i mp r o b z z m ：冗( c ( z ) ) 一冗( ，c ) g ) = o ， ( 1 4 ) m 我们称该分类算法c 是贝叶斯风险一致的。 第l 章绪论 贝叶斯风险一致不仅依赖于算法，分类器空间的逼近能力，而且依 赖于具体的概率测度p 。在文献中关注的比较多的是普遍一致性( u i l i v e r s a l c o n s i s t e n c y ) 。它表示贝叶斯风险一致对于所有的b o r e l 概率测度都成立。 一个分类算法只有在具有一致性的情况下才有效。如果一个算法不满足 一致性，随着经验数据的增多，该算法并不能得出更可靠的学习性能。不过， 要使一个算法在实际应用中有效，仅仅该算法产生的分类误差收敛到贝叶斯 风险是不够的，我们还需要分类误差收敛到贝叶斯风险的收敛速率。因此，对 于具体的学习算法，收敛阶的分析是学习理论的一个主要研究课题。 1 2 经验风险最小化原则 学习理论不同于经典的回归分类问题。它们的差别在于学习理论可以处 理高维空间的大量数据问题。学习理论的研究起源于b o s e r ，g u y o n 和v r a p n i k 【1 5 1 ， c o n e s 和v a p i l i k f 2 3 】，v a p n i k 【9 1 1 等提出的统计学习理论和支持向量机。经典统计 学习理论的核心思想是经验风险最小化原则( e m p i r i c a lr i s km i n i i l l i z a t i o n p r i n c i p l e ) 。 。 在学习理论中，如果用一个函数厂来做预测，则我们用一个r 2 一酞+ 的损 失函数来度量由此引起的局部误差( 秒，( z ) ) 。学习的目的就是找到期望风险 ( e x p e c t e dr i s k ) 的最小化子： ， ( ，) = e ( ，( z ) ，秒) = ( ，( z ) ，秒) 却 ( 1 5 ) ，x x y 最小化期望风险的函数称为目标函数( t 鹕e tf u n c t i o n ) ： = a r g ，翼导( ，) ( 1 6 ) 由于我们只是知道一组样本z = ( 耽，弘) ) 罂1 ，而不是概率测度p 本身，最小化 期望风险的函数不能够直接计算。但是根据大数定律，对于任意给定的函数， 经验风险( e r n p i r i c a lr i s k ) 1 m ( ”= 去m t ) ) ( 1 7 ) 随着样本数量m 的增加，会以概率收敛到期望风险( ，) 。一个直观的想法就是 如果( ，) 收敛到e ( ，) ，巴( ，) 的最小化子 砑= a r g ，妥s ( ，) ( 1 8 ) 可能也收敛到( ，) 的最小化子。这称为经验风险最小化原则的一致性。否则， 如果经验风险最小化原则不是一致的，随着经验数据的增加我们并不能得到 3 第1 章绪论 更可靠的预测结果。因此，在统计学习理论中，关于经验风险最小化原则一致 性的研究是一个重要的课题。 不同于最小化占( ，) ，当最小化巴( ，) 在整个可测函数空间上进行时，经验 风险最小化原则( 1 8 ) 会由于过拟合( o v e m t t i n g ) 而失效。也就是说，我们可以 找到这样的函数，对于样本( 1 3 ) 满足对t = 1 ，2 ，m ，( 既) = 扰，但是这样 的函数厂对于未来样本的预测能力却非常差。 一般有两种方法来解决过拟合问题：一是寻找一个合适的假设空间，在此 空间上实行经验风险最小化原则。二是正则化。正则化的方法将在1 5 节讨论。 这里我们主要研究为经验风险最小化原则选取一个合适的假设空间。 显然，该假设空问不能太大，我们需要一些量来控制它。设咒为x 上的一 个假设空间。我们求邑( ，) 在咒上的最小化子 缘= a r g 嘶( n ( 1 9 ) 希望在某种意义上收敛于( ，) 在假设空间h 上的最小化子： a = 盯g 咖( n ( 1 l o ) 经典统计学习理论的主要问题是估计样本误差( s a m p l ee 0 r ) ( 么) 一 ( a ) 。我们通过分解误差成三部分来估计样本误差： ( 磊) 一巴( 盘) ) + ( 缘) 一( 凡) ) + 0 ，有 3 i ms u p p r c i b z z m s u p s u pl 乏( ，) 一( ，) i e = o ， 。o 。p lm ，氕j 其中s 叩在z 上所有的b o r e l 概率测度上取得。 4 第1 章绪论 一个自然的问题是要找出这样满足一致g l i v e i 岫c a i l t e u i 集的函数集。在 学习理论中，一个函数集通常用覆盖数( c o v e m gn u i n b e r ) 1 1 4 1 1 5 1 ，熵数( e n 咖p y n u m b e r ) 【3 5 4 8 1 ，r a d e n l a c h e r 平均数( r a d e m a c h e ra v e r a g e s ) 【7 】组合数( c o m b i n a t o r i a l q u a i l t i t i e s ) 如y c 维【9 l 】和k 维舢( v c 维的推广) 度量。由v a p n 墩和c h e r v o n e n l 【i s 等人【1 4 蚴，a l o n 等人【2 】作出的先驱性工作，一致g l i v e n k 0 c a n t e l l i 集可以由v c 维或嵋维( 在此我们省略定义) 来描述。 定理1 1 设咒为从x 到 1 ，一1 ) 的一个函数集，则咒是一致g z f l ，已，z 勋一q 咒纪肼集 的充分必要条件是咒的粥维是有限的 定理1 2 设“为从x 到y 的一个函数集，其中y 是r 上的一个闭区问。则冗是一 致g f f v e ，l 幻一国n 把f f f 集的充分必要条件是对于任意的，y 0 ，咒的k 维都是有限 的。 我们已经发现( 力) 是期望风险占的最小值，它只依赖于测度p 和损失函 数。期望风险( 盘) 依赖于p ，咒，经验数据z ，还有定义舷的经验风险最 小化算法( 1 9 ) 。 ( 兹) 一( 彤) 称为额外期望风险( e x c e s se x p e c t e dr i s k ) 。学习理论的一个 目标就是证明，在一定关于p ，膨和咒的假设下，随着经验数据增加到无穷，这 个额外期望风险会逐渐趋近于o 。我们分解额外期望风险成两部分： ( z ) 一( ) + ( 觑) 一( 彤) ( 1 1 3 ) 第一项就是我们上面提到过的样本误差。我们称第二项为逼近误差 ( a p p r o x i m a t i o ne r r o r ) 。逼近误差依赖于假设空间咒的选择，函数臂的属性等，但 与经验数据无关。在过去的统计学习理论中，这一项没有被考虑过。再回过头 来考虑假设空间的选择，大的假设空间会产生小的逼近误差但是同时又产生 大的样本误差。因此我们要选取合适的假设空间来平衡样本误差和逼近误差。 这称为误差方差权衡( b i a s v 撕a n c e 仃a d e o f ! f ) 。 作为例子，我们对二分类问题应用经验风险最小化原则。利用损失函数： 如一。( c ( z ) ，秒) = 呈：；i 三 ：； c ，4 ， 则期望风险就正是分类误差： 冗( ，) = e 一1 ( 秒，( z ) ) ， ( 1 1 5 ) 而目标函数就正是贝叶斯分类器。经验风险最小化原则求解 巴= a r g 嘶亿( ，) ( 1 1 6 ) 5 第1 章绪论 其中 1 三 7 屯( ，) = 二 ：咖。一1 ( 玑，( z t ) ) ( 1 1 7 ) 吾 这个算法在v c 理论【9 1 1 的框架下已经得到了很好的理解。事实上，定 理1 1 告诉我们冗忆) 一i n f c 咒冗( c ) 一。的充分必要条件就是函数空间冗的v c 维 是有限的。对于逼近误差i n f c 饨冗( c ) 一冗( ，c ) 的估计，文献f 5 8 1 研究了最小二乘 损失函数的逼近误差，文献【2 2 】研究了分类损失函数的逼近误差。 尽管对于0 1 损失函数经验风险最小化原则在理论上发展得比较完善，但 是该算法的求解是一个n p - h 砌问题。因为o 1 损失函数既不连续也不具有凸 性。它在算法设计和实际应用中有很大的难度。 直到2 0 世纪9 0 年代中期，f i s h 【柏】，r o s e n b l a 仕【6 4 1 ，和v r a p n m 【9 0 】等人提出了支 持向量机( s u p p o nv e c t o rm a c l l i n e ) 算法，学习理论才在应用上取得了巨大的成 功。支持向量机体现了结构风险最小化原则，同时利用了内点法等有效的优 化算法，可以快速地处理大量高维的数据。支持向量机在现实世界中有广泛 的应用，如手写文字识别、图形分类、生物信息学、网页分类等。 1 3 样本点严格可分的情况 支持向量机由一族有效的分类算法组成：样本点完全可分情况下的硬 问隔( h 砌m a r g i n ) 支持向量机分类器( 1 2 1 ) ，样本点不完全可分情况下的软 间隔( s o f tm 鹕i n ) 支持向量机分类器( 1 2 2 ) ，还有一般形式的支持向量机算 法( 1 2 5 ) ，即在损失函数为砌曙p 肠s s 九和一般的m e r c e r 核k ( 将在下文中定义) 下的分类算法。前两种支持向量机分类器可以由线性核k ( z ，秒) = z 可+ 1 来 表示。一般形式的支持向量机分类器可以由一般形式的m e r c e r 核来表示，如 多项式核( z 影+ 1 ) 七，其中庇n 【1 5 1 ，或者高斯核e x p 一崆笋) ，其中盯 o 【2 3 1 。 所有的支持向量机算法有一个共同的特点，就是损失函数是l l i n g el o s s 饥= ( 1 一亡) + = m a x 1 一亡，o ) 。 尽管为什么损失函数取l l i n g el o s s 就能得到好的分类器不是一眼就看得出 原因，我们可以从几何角度来尝试解释为什么会这样。接下来我们就从几何 角度来研究这个问题。 从最简单的情况开始：样本点可由线性分类器完全可分的情况( 接下来 我们会看到，对于一般形式一一样本点由非线性分类器不完全可分的情况 一一也会得到非常相似的二次规划问题) 。同样样本表示为 ( 兢，仇) ) 罂l ，犰 1 ，一1 ) ，兢舯。假设存在这样的超平面，使得两类的样本点可以完全分开。 位于超平面上的点z 满足叫z = 6 ，这里叫是一个和超平面正交的单位向量。于 6 第l 章绪论 是从一点z 到超平面叫z = o 的距离就是忙”l c d s 引= 怕i l i i z i i i c d s 引= i 如z l 。 由于超平面训z = 6 和超平面叫z = 0 平行，因此从点z 到超平面叫z = 6 的距 离就是i 叫z 一6 i o 图1 1 点z 到超平面硼茁= b 的距离 w - 工= 6 + 吱 j = 西 w ，= 6 一t 图1 2 样本点完全可分情况下的线性分隔超平面 令d + ( d 一) 为从分隔超平面叫z = 0 到两类样本的最近距离。我们定义一个 分隔超平面的间隔( m a r g i n ) 为4 + d 一： 4 2 嚣碧 叫戤一耐2 爨璺叫。鼢一玩l “= ll “2 1 7 第1 章绪论 d 一= 一m a 薯 叫瓤一6 = 6 一m a 墨伽戤 选择截距6 使得d + = d 一，也就是 6 = c ( 伽) = 三 ( 1 1 9 ) d + = d 一= ( t u ) = 专 4 + d 一) = 吉 爨碧叫戤一暑当伽戤 ( 1 1 9 ) 对于样本点由线性分类器完全可分的情况，支持向量机算法就是寻找能最大 化间隔的分隔超平面： r、 i m 筒( 叫) 2 稆筒 器璺训。z t 一嚣兰至训。既 ( l 2 0 ) 0 伽i i = 1 、 l l 叫0 = 1i 肌= 1 玑= 一1 j 如果叫是当( 伽) o 时( 1 2 0 ) 的最大值，则叫z = c ( 叫) 被称为最优超平面 ( o p t i m a lh y p e 叩l a n e ) ，而( 训) 被称为样本的最大间隔( m a x i m a lm 哗i no fm e s a r n p l e ) 。 v a p n 墩( 并参见c u c k e r 和z h o u 【矧) 证明了在样本完全可分，而且任何一 个类都非空的情况下，最优化问题( 1 2 0 ) 存在唯一的解叫，而且( 训) o 。进 一步这个问题可以表达如下：如果西是 酬2 s t 轨( 叫兢一6 ) 1 ，i = 1 ，2 ，m ( 1 2 1 ) 的解，则叫= 尚，而且分隔超平面的间隔为( 伽) = 南。 因此，在样本完全可分的情况下，我们可以通过求解最优化问题( 1 2 1 ) 来 解决( 1 2 0 ) 。得到的分类器z s g n ( 伽z 一6 ) 称为硬间隔分类器( h a r dm a r g i n c l a s s i f i e r ) ，其中 s s n ：袭受 使得( 1 2 1 ) 中等号成立的向量玩称为支持向量( s u p p 叫v e c t o r s ) 。在支持向量机 的应用中，支持向量的个数一般都远远小于样本的个数m 。这一特性使得最优 化问题( 1 2 1 ) 的求解具有很快的速度。 对于样本不是完全可分的情况，不存在这样的叫瞅和6 r ，使得样本 点可以被超平面叫z = 6 分隔成两类犰= 1 和犰= 一1 。在这种情况下，我们通 过引入松弛变量( s l a c kv a r i a b l e ) 来得到软间隔分类器( s o f tm a r g i nc l a s s i f l e r ) 。可 以表示成如下的优化问题： 哪恕泄州1 2 + 忐& s t 犰( 叫z i 一6 ) 1 一已( 1 2 2 ) 、 已0 ，吾= 1 ，2 ，m 第1 章绪论 这里a 0 是正则化参数。如果( 叫，6 ，f ) 是( 1 2 2 ) 的解，则软间隔分类器定义 为zhs g n ( 伽z 一6 ) 。样本完全可分情况下的硬间隔分类器( 1 2 1 ) 可以看做样 本不完全可分情况下软间隔分类器( 1 2 2 ) 的一个特例，通过取圭= ，并且所 有的解满足= 0 。 我们在本节的开始就提出损失函数为l l i n g el o s s 的正则化分类器和如上讨 论的间隔，分隔超平面等概念有关。回顾h i n g el o s s 的定义是 ( 亡) = ( 1 一亡) + = m a x 1 一t ，o ) 如果( 叫，6 ，f ) 是( 1 2 2 ) 的解，则必然有 已= ( 1 一玑( 叫戤一矿) ) + = ( 犰( 叫兢一矿) ) 因此最优化问题( 1 2 2 ) 可以表达如下： 1 m 梨熹九( 弘( 叫嘞一6 ) ) + 入2 ( 1 2 3 ) 1 4 经典的支持向量机和核 核方法已经成为学习理论中的一类重要算法，这里我们以支持向量机为 例来说明其应用和理论内涵。 更一般的，如果我们通过超曲面，( z ) = 0 而不仅仅是超平面来分隔样本， 而同时又希望算法是有效的优化算法，这就要求函数，在再生核希尔伯特空间 中【4 1 。 定义1 4 一个函数k ：x x _ g 称为胁胱r 核，如果它是连续的，对称的并 且是半正定的f 即对于任何有限点集 z 1 ，视) cx ，矩阵( k ( 观，巧) ) ：，j ：1 都是 半正定的j 。利用该讹彤已厂核k ，我们可以在线性空间印口n ：= k ( o ，) ：万 x ) 中定义内积( ，) k ：( ，) k = ( z ，秒) 。由线性空间印口，z 恐：= k ( z ，) ： z x 按内积( ，) k 完备化得到的希尔伯特空间称为由k 生成的再生核希尔伯 特空问f ，即r d d “c f 馏妇m p z 日f 场8 玎印n c g ) ，记为冗k 。 再生核希尔伯特空间包括一些s o b l e v 空间【9 3 1 ，实解析函数【2 6 1 和它们的一 些推广【7 3 1 。其再生性是该空问的一个十分重要的性质，它在学习理论中有着 广泛的应用。 如果我们考虑r r 上的线性m e r c e r 核k ：k ( z ，可) = z 可，则相应的冗k = 伽z i z r ) ，i i 玩怯= i i 叫l | 2 并且最优化问题( 1 2 2 ) 可以写成： 1 m ，艘r 去讹( m t ) 一6 ) ) + 删艮 ( 1 - 2 4 ) 9 第l 章绪论 当支持向量机软间隔算法( 1 2 4 ) 包含偏移项( o 凰e t ) 6 时，该算法更加灵活而且 可以分隔更一般的样本。相应的，误差分析也更复杂。所以一般情况下，我们 只考虑没有偏移项的设置 墩= 弼艘 熹喜州鼽m + 刈州凳) ( 1 2 5 ) 从( 1 2 5 ) 得到的支持向量机分类器s g n ( 髭2 ) 具有如下很多优良的性质。该算法 不仅有效，而且实际应用中经常具有小的分类误差。 首先，支持向量机不同于经验风险最小化原则和神经网络。支持向量机本 质上就是一个正则化算法。正则化算法在1 9 6 3 年由t i k h o n o v 提出，目的是为了 解决i 1 1 p o s e d 问题或逆问题。正则化参数a 的作用是防止上述算法出现过拟合。 在核的选择方面，除了再生核希尔伯特空间外，文献【1 ，8 8 ，8 9 】中使用了s o b o l e v 空 间来处理高维数据。 其次，h i n g el o s s 九具有减少秒，( z ) 1 时的局部误差的良好性质。对于二 分类问题，我们只关心，( z ) 的符号，而不是它具体的数值。所以在判断，( z ) 的 符号和是否相同时，损失函数用的变量是可，( z ) ，而不是回归估计中常用 的可一，( z ) 。另外，机不仅连续而且是关于芒是凸的，这是支持向量机为什么是 有效算法的一个原因。 最后，再生核希尔伯特空间的特殊性质保证了最优化问题( 1 2 5 ) 的最小值 能在 i ) 銎1 张成的子空间冗k ，。内取得。由再生核希尔伯特空间的再生性产 生的这一特性称为表示定理( r e p r e s e n t e rt h e o r e m ) ( 参见文献) 。 定理+ 1 3 若入 o ，则求解墩的优化问题f j 2 5 ) 可以简化为求解一个凸的二次 规划问题墩= 銎。货；，这里 噼眭九 薹悱) + 吾撇驯2 6 ， 这个定理表明叠5 ：可以用优化定理( 参见文献【6 1 7 1 ) 有效求解。这是支持向量 机为什么是有效算法的另一个原因。支持向量机算法可以快速地处理大量高 维的数据。计算快速是支持向量机算法区别于经验风险最小化原则和神经网 络等方法的最显著特征。 尽管支持向量机由v a p n 伙等人根据一些几何直观所提出来，并有经典统计 学习理论的结果做保障，但他们及其后的一些理论工作如【2 4 1 所得到的推广性 的界都跟数据点有关，因此不令人满意。一个根本性的理论问题是：支持向量 机是否对任意的分类问题都有效，即支持向量机分类器是否对任意的分布都 是贝叶斯风险一致的? 直到2 0 0 2 年s t e i n w a r t 在文献【7 6 】中第一次给出了一个初 1 0 第1 章绪论 步解答。他指出，只要m e r c e r 核生成的再生核希尔伯特空间在连续函数空间中 稠密，则支持向量机算法对任意的分布都有效。但要想得到一致的收敛阶，我 们必须对分布作出一定的限制【7 7 ，7 9 1 。2 0 0 4 年，z l l a i l g 在文献【l ”】中给出了支持 向量机的比较定理，即用期望风险来控制分类误差，从而利用期望风险的一 些推广性界的估计就可以得到分类误差的一致性上界。但那时的学习理论中 关于误差估计的分析都没有考虑到逼近误差，因此得到的推广性的界还是不 完善的。w h 和z h o u ，c h e n 等人在文献【9 8 】，【2 2 】中给出了更完善的分析，他们给 出了支持向量机的逼近误差。同时结合前人所得到的样本误差得到最终满意 的推广性的界。 1 5 再生核希尔伯特空间中的正则化算法 学习理论的研究中，解决经验风险最小化原则( 1 8 ) 过拟合问题的另一方 法是引入再生核希尔伯特空间中的正则化算法。文献【9 3 】研究了样条核函数， 文献【“，9 0 9 l 】研究了一般的m e r c e r 核函数下的正则化算法。对于不同的再生核希 尔伯特空间，支持向量机算法有不同的形式。 令q ：咒一r + 为假设空间咒上的损失函数。经验风险最小化原则下 的t i k h o n o v 正则化算法可以表示如下： ，、 ，z ，a = 射g l 观 邑( ，) + a q ( ，) ( 1 2 7 ) jco 、 7 函数q ( ，) 称为正则化子( r e g u l 撕z e r ) 。正则化参数a 0 控制着经验风险和惩罚 值之间的权衡。正则化的基本思想是，当入一。时，厶，入在某种意义上是，z 的一 个良好的逼近。 文献中正则化子有很多中不同的形式。如果我们考虑线性函数，正则 化子经常取权向量的某种意义下的范数【5 3 ，6 2 6 7 1 ( 包括最常用的欧氏距离) 。如 果咒是b a n a c h 空间，正则化子则取为b a n a c h