（模式识别与智能系统专业论文）基于kernel的数据学习算法研究.pdf

摘要 学习算法的目标是寻找最小化风险泛函的最优函数及其参数集合。通常 选择最小化训练集合上的误差的经验风险最小化原则。统计学习理论给出了 另外一种学习原则：结构化风险最小化原则。支持向量机实现了结构风险最小 化原则，而其主要特点就是使用k e r n e l 技巧，本报告从以下几个方面研究了基 t - k e r n e l 的学习算法： 首先，我们研究构造正定核函数的方法及基于k e r n e l 的马氏距离判别分析。 给出了用正定核函数的已有的性质构造连续论域上的正定核函数的方法。提出 了一种基于正定核函数的马氏距离判别实现方法。通过使用k e r n e l 技巧实现存 高维的k e r n e l 特征空间中有效地计算马氏距离。对二元分类问题而言，组内方 差相等时，马氏距离确定的判别轨迹与基于k e r n e l 的费舍尔判别函数平行，并 且通过特征空间中两类均值之间的中点。大景的模拟实验显示了该方法的有效 性。 其次，提出一种新的支持向量机的更新算法并讨论其性质，给出了相应的 实验结果。该过程是使用标准的支持向量算法得到初始的概念，然后利用文中 提出的概念更新方法，即求解一个类似标准支持向虽机算法的凸二次规划问题。 更新模型具有与标准支持向量机类似的数学形式，能够得到解的稀疏表示；无 需额外的计算就可以返回上一步：还能用于估计表达问题所需的样本的数量。 然后，我们提出了基于极小极大概率机的多类别分类算法。我们利用最小 最大概率机的概率信息和样本间隔信息构造各个分类器在结果合成阶段的权 重，克服了以往绝大多数算法在合成阶段仅仅依靠投票数量来进行决策和分类 器权重均等的不足。扩展了弱分类器的概念，利用弱化的分类器来减少迭代次 数，这样在类别数量较大时可以大量减少迭代次数；而在结果合成阶段利用非 线性映射提升整体分类性能。 最后，我们研究了函数型数据的表达以及函数型主成分分析方法，然后利 用支持向量机实现了曲线的分类。 关键词：统训学习理论，支持向量机，马氏距离，概念更新，极小极大概率机 函数型数据分析 a b s t r a c t t h eg o a lf o rl e a r n i n ga l g o r i t h mi st of i n dt h ef u n c t i o na n di t sp a r a m e t e r s m l n n n l z m gt h er i s k u s u a l l yt h et r a i n i n ge r r o ri sm i n i m i z e dv i at h ee m p i r i c a l r i s km i n i m i z a t i o np r i n c i p l e a l t e r n a t i v e l y ，t h es t r u c t u r a lr i s km i n i m i z a t i o ni s p r o p o s e di ns t a t i s t i c a ll e a r n i n gt h e o r y s u p p o r tv e c t o rm a c h i n ea p p r o x i m a t e l y i m p l e m e n ts t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e t h em a i ni d e ai st h a tk e r n e l t r i c ki su s e dt op r o j e c tt h ei n p u td a t ai n t oa ni m p l i c i tf e a t u r es p a c e w ed i s c u s s k e r n e l - b a s e dl e a r n i n ga l g o r i t h ma sf o l l o w i n g ： f i r s t l y ，w ed i s c u s st h em e t h o d st oc o n s t r u c tp o s i t i v ef u n c t i o n a lk e r n e la n d p r o p o s e dk e r n e l b a s e dm a h a l a n o b i sd i s t a n c ed i s c r i m i n a n t t h em a i ni n g r e d i e n ti s t h ek e r n e lt r i c kw h i c ha l l o w st h ee f f i e i e n tc o m p u t a t i o no fm a h a l a n o b i s sd i s t a n c e i nk e r n e lf e a t u r es p a c e f o rt w og r o u pd i s c r i m i n a n t ，t h el o c u so fp o i n t ss p e c i f i e d b ym a h a l a n o b i s sm e t h o di st h es e to fa l lp o i n t sp e r p e n d i c u l a rt ok e r n e lf i s h e r 8 d i s c r i m i n a n tf l m c t i o nc o e f f i c i e n t s ，c r o s s i n gt h ed i s c r i m i n a n tf u n c t i o na x i sa tt h e m i d p o i n tb e t w e e nt h et w og r o u pm e a ns c o r e sw h e nw i t h i n g r o u pv a r i a n c e sa r e e q u a l s e c o n d l y , w ea p p l ys u p p o r tv e c t o rm a c h i n e ( s v m ) t ot h ec o n c e p tu p d a t i n g p r o c e d u r e i f i n i t i a lc o n c e p tw o u l db eb u i l tu pb yi n d u c t i v ea l g o r i t h m t h e nc o n c e p tu p d a t e di st h en o r m a ls o l u t i o nc o r r e s p o n d i n gt ot h ei n i t i a lc o n c e p tl e a r n e d i tw a ns h o w nt h a tc o n c e p tl e a r n e dw o u l dn o tc h a n g ei ft h en e wa v a i l a b l ed a t al o c a t e di ne r r o r i n s e n s i t i v ez o n e e s p e c i a l l y ，c o n c e p ti n i t i a l l yl e a r n e da n d u p d a t e d b ys v ri n d u c e sa ni n c r e m e n t a ls v ra p p r o x i m a t e l yl e a r n i n gm e t h o df o rl a r g e s c a l ed a t a t h i r d l y ，w ep r e s e n tm e t h o d sf o rm u l t i c l a s sp r o b l e mt h a tc o u l do v e r c o n l e s u c hl i m i t a t i o na n ds o l v et h ed e s i g np r o b l e me f f e c t i v e l y w ep r o p o s e dah e u r i s t i c s t r a t e g yu s i n gp r o b a b i l i t yo u t p u to fam i n i m a xm a c h i n ea n dm a r g i ni n f o r m a t i o n w ec a nv i e wa na l g o r i t h mw i t hl e s si t e r a t i v es t e p so fo p t i m i z a - t i o na sa “w e a k ”a l g o r i t h mw h i l ep r e s e r v i n gi t so t h e rc h a r a c t e r i s t i cl i k el a r g e m a r g i na n dg e o m e t r i cp r o p e r t i e sf i n a l l yw em a k eu s eo ft h ek e r n e lt r i c kf o r 堡 些鉴望垦堕里生塑塑塑堂望篁鲨堕塞 “w e a k ”a l g o r i t h m s o u t p u t ( v e c t o r ) t ow o r ki nh i g hd i m e n s i o n a ls p a c e sa n d i m p r o v et h ep e r f o r m a n c e s f i n a l l y ，w ed i s c u s st h ef u n c t i o n a ld a t aa n a l y s i sm e t h o d si n c l u d i n gf i m c t i o n a l d a t ap r e s e n t a t i o na n df l m c t i o n a lp r i n c i p l ec o m p o n e n ta n a l y s i s a n dw eu s e s u p - p o r tv e c t o rm a c h i n et oc l a s s i f yc u r v ed a t a k e y w o r d s ：s l t ，s v m ，m a h a l a n o b i sd i s t a n c e ，c o n c e p tu p d a t i n g ，m p m ，f d a 表格 2 1 常用的核函数1 8 3 1 串的特征映射3 2 3 2 m d 、r b f 、a b 、a b r 、s v m 及k f d 实验比较结果4 0 4 1 数据集及实验参数。4 9 4 2 实验参数。5 6 4 3 实验结果，5 6 4 4 独立测试集上的f 误差6 2 4 5 实验数据集描述6 3 4 6 实验结果：m s e 一均方误差，孝一算法迭代次数6 4 5 1 平均训练、测试精度和准确分类概率下界7 2 5 2 构造支持度矩阵的算法描述，8 1 5 3 构造权重矩阵的算法描述8 2 5 4 数据集的特性描述。8 3 5 5 线性算法最佳成绩与其他方法比对8 3 5 6 非线性算法最佳成绩与其他方法比对8 4 5 7 固定合成阶段核函数，二类分类器不同核的结果8 4 5 8 固定二类分类器核甬数，合成阶段不同核的结果8 4 5 9 固定二成阶段核函数的不同叠代次数的结果8 5 6 1 人工数据的1 0 折交叉检验的平均误差9 8 插图 2 1 学习的概念图示 5 2 2 学习过程的一致性，1 1 4 1 批处理和增量式支持向量机性能比较，5 1 4 2 b a n a n a ：虚线表示更新后的平均性能；实线足文【6 1 】算法 5 1 4 3 c a n c e r ：虚线表示更新后的平均性能；实线是文【6 l 】算法 5 2 4 4 d i a b e t e s ：虚线表示更新后的平均性能；实线足文 6 1 1 算法 5 2 4 5 f l a r e - s o l a r ：虚线表示更新后的平均性能；实线是文1 6 1 算法5 3 4 6 g e r m a n ：虚线表示更新后的平均性能；实线是文 6 1 】算法 5 3 4 7 h e a r t ：虚线表示更新后的平均性能；实线是文 6 1 】算法 5 4 4 8 增量式回归：第一行从左到右为1 曲步，第二行从左到右为6 _ 加步 5 7 4 9 左图为批训练结果；右图为1 0 步增量式训练结果；圈点为支持向量5 8 4 1 0 ，( ，2 1 ，( 3 1 ，( ”，( 射，( 6 ) 函数的图形， 5 9 4 1 1 加入噪音的，( 1 1 ，( ，( 3 1 ，( 4 1 ，射，( 6 ) 图形。 6 0 5 1 几何解释， 5 2b a n a n a 决策边界 5 3 训练、测试精度和准确分类概率下界 6 11 0 个女孩的身高数据，每点代表一次测量，测量时问点是不均匀的8 8 6 2 人工数据：左为实际函数图形；右为加入随机变化后图形9 7 6 3 曲线的基本统计特性：样本均值、标准差、方差、协方差与相关系数9 9 6 4 函数型主成分：上部4 个图为c l a s s o n e , 下部4 个图为c l a s s t w o 1 0 0 6 5c l a s s o n e 、c l a s s t w o 的前两个主成分上的得分散点图1 0 1 加符孔 第一章绪论 生物体包括人类每天都在进行各种情况下的对象识别活动，例如寻找食物、 迁移路线，辨别敌友、辨认配偶等，作为高级动物的人类同样每天都进行大量的 辨识对象的活动，例如辨识人脸、识别语音、阅读手写文字或根据气味判断食 物是否变质。这些活动对有生命体来说显得非常简单，但其却隐含了非常复杂 的处理机制。随着电子计算机技术的发展，建立自动的智能自动化系统的需求， 模仿各种形式的对象识别能力的得到了发展，带动了工业及其他领域的技术发 展。这些系统中，模式识别系统是一种特殊的系统，其通过某种方式获取所需要 的数据，表达为某种特定的形式，选择任务相关的特征，实现模型的建立，然后 利用学习算法构造分类器或经验的判别函数，从而实现了对对象的自动识别。 1 1 学习与适应性 设计模式识别系统的过程就是不断重复数据采集、特征选择、模型选择、训 练和评估的过程。在开发一个模式识别系统时，利用样本数据来确定分类器的 过程( gr l 练分类器) 尤其关键。在过去的几十年的反复试验和经验表明基于样本 的学习方法是设计分类器的最有效方法，因此分类器的训练过程也是一个学习 过程。 从广义上看，设计分类器所用的任何方法，只要其利用了训练样本的信息， 都可以认为运用了学习算法。在实践中遇到的问题往往相当复杂，难于事先给 出一个最佳的分类判别准则。因此主要难点在于研究学习算法问题。构造分类 器的过程包括建模和利用样本数据实现未知参数的估计。学习就是指利用某种 算法估计模型参数，实现分类器在训练数据上的分类误差逐渐变小，而且最终 输出的分类器具有推广能力。学习算法可分为：有监督学习、无监督学习和强 化学习。在有监督学习中存在一个教师信号，训练样本数据的每个样本均已标 记为不同的类别。无监督学习算法或聚类算法中训练样本数据均不带有类别标 号，聚类算法的目的就是对输入样本形成自然的类聚。而强化学习中无需指明 目标类别的教师信号，其只需教师对分类任务完成情况给出正确与否的判断。 本报告讨论基于样本学习的分类器设计的有监督方法，其中的关键问题是 2基于k e r n e l 的数据学习算法研究 学习算法和分类器的适应性问题。 1 2 研究的动机及目标 从上世纪9 0 年代，支持向量机提出以来，无论是理论上还是应用上支持向 量机得到了迅猛的发展，并成功应用到许多领域。支持向量机的优点之一就是 使用所谓的核函数( k e r n e lf u n c t i o n ) 技巧。核函数实现隐含的特征映射，把输入 空间中的有限维数据映射到高维，甚至是无限维的特征空间中。该特征空间为 希尔伯特空( h i l b e r ts p a c e ，完备的内积空间) ，具有良好的性质。该空间中的 内积( 标量积) 能够用输入空间中的元素计算。因此，具有计算上的巨大收益，而 又能够避免所谓的“维数”问题。 基于k e r n e l 的学习算法就是利用核函数在计算的优势发展起来的一系列学 习方法，许多经典的学习算法经过所谓的“核化”( k e r n e l i z a t i o n ) ，已经被推广到 高维的空间，并在实践中取得良好的效果。但仍存在许多值得研究的问题，我 们的研究动机包含两方面：其一、扩展传统的分类或判别方法，使得能够充分 利用核函数的技巧，同时扩展基于k e r n e l 的学习算法的应用领域，如类别分类 问题、曲线分类。其二，注意到模式识别系统的动态性，即系统的更新问题。 我们的研究目标就是以统计学习理论为依据，充分利用正定核函数所提供 的技巧，扩展已有的学习算法，研究支持向量机的更新问题，扩展基于核函数的 学习的应用领域包括多类别分类和曲线数据分类问题。 1 3 本报告的贡献 t 本报告主要从以下几个方面研究了有关基于k e r n e l 的学习算法： 1 提出了基于k e r n e l 的马氏距离判别方法：扩展了经典的马氏距离判别法， 实现了在核特征空间中的马氏判别分析，实验的结果表明该方法的有效 性。 2 提出了支持向量机的更新算法：其无需重新训练支持向量机，只需运行更 新算法便能够适应新的改变，并且具有良好的理论性质，试验结果进一步 证实了理论的结果。 第一章绪论 3 3 提出了基于概率机的多类别分类方法：受支持向量机的启发，我们研究了 一种新的多类别分类方法，基于概率机的多类别分类方法，并提出s w s 多 类别分类框架。 4 研究了基于支持向量机的曲线分类：曲线数据是一类特殊的数据，其具有 无限维的本质特性，我们讨论了基于滤波的支持向量分类方法。 1 4 结构安排 1 在第2 章中，我们回顾了从样本中学习的基本概念，归纳原则以及学习理 论的发展历史。同时，概述统计学习理论的基本内容，特别是支持向量机 的原理和主要的实现算法 2 在第3 章中，我们研究了核函数的构造问题以及核特征空间中的马氏距离 判别法。基于核函数的学习算法的关键之一就是如何确定核函数? 已有的 实践表明核函数的构造是任务相关的，针对不同的应用环境和任务，构造 恰当的核函数是基于核函数的学习算法的必须解决的问题，但由于从输入 空间到特征空闻的映射是隐含实现，因此我们很难理解特征空问中的信 息。在讨论了正定核函数的构造方法之后，提出了一种基于k e r n e l 的马氏 距离判别方法。 3 在第4 章中，我们提出了支持向量机的更新算法。标准的支持向鼍机隐含 假定样本数据反映了数据分布的一切信息，并且数据分布保持不变。但在 实际应用中，环境是处于动态改变中的。这就涉及到支持向量机的更新问 题。在本章中我们研究了支持向量机的更新问题，提出了一种更新算法， 4 第5 章中，我们研究了基于概率机的多类别分类问题。在实践中，多类别 分类问题是常见的。我们利用最小最大概率机的概率信息和样本间隔信息 构造各个分类器在结果合成阶段的权重，并且我们扩展了弱分类器的概 念，利用弱化的分类器来减少迭代次数，这样在类别数量较大时可以大量 减少迭代次数：而在结果合成阶段利用非线性映射提升整体分类性能。 5 在第6 章中，我们研究了函数型数据( 曲线) 分类问题。函数型数据是一种特 殊类型的数据，与常见的特征向量型数据不同的是样本对象是一个函数， 而且在实际应用中，我们并不可能得到函数的精确形式，可利用的仅为末 4 基于k e r n e l 的数据学习算法研究 知函数在有限点上的取值。困难还在于已知点上的值在曲线上的分布是不 均匀，也就是函数数据抽样是不均匀的，在某些区间具有稀疏性。冈此， 在本章中我们研究基于支持向量机的函数型数据的分类i 、h j 题。 6 第7 章，我们给出了本报告的总结以及需进一步研究的展望。 第二章统计学习理论概述 在本章中，我们回顾了从样本中学习的基本概念，归纳原则以及学习理论 的发展历史。同时，概述统计学习理论的基本内容，特别是支持向量机的原理 和主要的实现算法。 2 1 学习过程 2 1 1 从样本中学习的基本概念 概念上来说，学习就是给定一定数量的观测，构造知识模型的过程。当这 种模型构造出来后，人们可以从该模型中推断实例。可以用图2 1 表示学习和应 用的过程。下面我们给出学习问题的一种形式的定义： 假设有限的独立同分布的训练集为五= z ，z e ) ，未知分布为f ( z ) 。 在给定此训练集合的前提下，学习算法的目标是最优参数嵋，它决定了函数 集，( 忽，叫) ，w w 的函数，( 历，啦) ，该函数在测试样本集上具有最好的测试精 度。其 g w w 代表函数集合f ( z e ，叫) 的抽象参数集合，w 表示所有容许的抽象 参数集合。 为了评价预测函数的“最优”性，我们必须选择一种评价的准则。因此，引 入风险泛函： n ( w ) = fl ( z ，伽) d f ( z ) 彬w 图2 1 ：学习的概念图示 6 基于k e r n e l 的数据学习算法研究 其中l ( z ，t | ，) 为损失函数集合。学习算法的目标就是最小化该风险泛函。该风险 泛函的具体实现定义了不同的学习问题。通常可以归纳为三种学习问题：模式 识别、回归估计和密度估计。它们的损失函数的定义如下： 模式识别在模式识别中，数据由输入输出组成的数对z = ( x ，) ，x 彬。这 里y 是学习系统的的输出且可 o ，l 。函数集f ( x ， ) ，叫w 限制为指示 函数集( 函数的输出仅取值为0 或1 ) 。该问题的一种可能的损失函数是： l c 玑，c x ，叫，= ：；i ；：； 通常称上面的损失函数为肛1 损失函数。如果分类错误，那么损失函数取 值北零。因此，该学习问题转化为在概率分布f ( x ，可) 未知，仅给定训练集 的条件下寻找具有最小化分类错误概率的函数。 回归估计在回归估计中，学习系统的输出取值为实数值，并且函数集，( z ， ) ，w w 为实值函数集。该问题的一种损失函数为： 工( y ，f ( x ，叫) ) = ( y f ( x ，枷) ) 2 通常称上面损失函数为平方误损失函数。注意到在这种情况下损失函数的 取值范围是f o ，+ o o ) 。 密度估计在密度估计中，假设密度函数集合为p ( x ，t l ，) ，x r d ，坩w ，那么可 以考虑下面的损失函数： l ( x ，叫) ) = 一l o g p ( x ，) 这种情况下，损失函数的取值范围是( 一o o ，+ 。) 密度估计是学习问题的通解，也就是说，一旦估计得到了密度，那么有 关学习任务的所有方面都可以使用该密度而得到解决。但是密度估计需要最 多的训练样本，而解模式识别问题需要最少的学习样本。因为任何实际的学 习过程只有有限的样本可利用，因此显然如果能够选择，应该解最容易的问 题。v a p i l i k 7 1 】把用有限数量信息解决问题的基本原则表达为： “遗y o up o s s e s sar e s t r i c t e da m o u n to li n f o r m a t i o n | 甜s o l v i n g $ o t n e p r o b l e m ，t r yt os o l v et h ep r o b l e md w e c t l ya n dn e v e r s o l v eam o r eg e n e r a lp r o b l e m 第二章统计学习理论概述7 a 8a n ，l t e r m e d i a t es t e p i ti sp o s s i b l et h a tt h ea v a i l a b l ei n f o r m a t i o ni ss u f f i c i e n t ! 舛ad i r e c ts o l u t i o nb u ti si n s u f f i c i e n t o ts o l v i n gam o r eg e n e r a li n t e r m e d i a t e p r o b l e m ” 意思是说在解决一个给定的问题时，要设法避免把解决一个更为一般的问 题作为其中间步骤。诚然，如果需要解一个模式识别问题则直接解模式识别问 题，而不是把试图估计密度作为其中间步骤。 学习的目标是寻找最小化风险泛函的最优函数及其参数集合。通常，在 训练阶段只有训练数据可以利用的时候，人们需要最小化训练集合上的误 差。按这个原则选择最优函数称为经验风险最小化( e r m ：e m p i r i c a lr i s k m i n i m i z a t i o n ) 原则。如果使用该原则并且只使用训练集合，风险泛函可以用下 式代替： 1 三 r 唧( 硼) = ；( z ，埘) ( 2 1 ) l = l 换句话说，通过最小化经验风险用l ( z ， 3 t ) 近似最优损失函数l ( z ，矿) 当然也可假设该原则将产生一个最小的真实误差。但是通常情况并非如此。 它是计算学习中的最基本的问题之一：如何折中经验风险和真实风险? 从根本 上说，这种折中可以通过由学习算法实现的潜在的归纳原则确定。不同的学习 理论和学习算法以不同的方式说明该问题。 2 1 2归纳原则和学习算法 存在许多学习方法学习非参数的函数或模型近似。但是，基于它们使用的 归纳原则，我们可以把它们分类为： 正则化原l j ( r e g u l a r i z a t i o n ) ：径向基函数( 神经) 网络。 早停机原贝o ( e a r l ys t o p p i n g ) ；b p 神经网络，s o m 算法，c 4 5 ，等等。 最小描述长度( m i n i m u md e s c r i p t i o nl e n g t h ) ：基于m d l 的模型选择 贝叶斯原则( b a y e s i a n ) ：用于模型选择的贝叶斯推理网络。 结构风险最小化原贝i j ( 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 v m ) 。 8基于k e r n e l 的数据学习算法研究 上面提到的许多学习原则本质上都是启发式的，并且它们依赖于专家在具 体的学习算法中实现这些原则的直觉。但是这却不是一目了然的事。 因为学习的目标是从一个广泛可能模型集合中构造一个模型，张成的所 有可能的模型的参数空间可能是相当庞大的。特别地在非参数估计中。模型参 数的数量可能非常大，因此参数空间的维数相当高甚至是无限维。在高维空间 中，通常存在“维数灾难”问题。为了避免依赖于启发式，提出了不同的学习理 论。2 1 3 给出一个简短的回顾。在2 2 中，概括了v a p n i k 提出的统计学习理论。 该理论以解析的方式导出了结构风险最小化归纳学习原则。 2 1 3 学习理论的历史回顾 从学习理论发展的历史来看，可以分为三个主要的阶段： 第一阶段参数统计 第二阶段非参数统计和神经网络 第三阶段学习复杂性和推广性理论，以及学习算法( 如：支持向量机) 的构造理论。 第一个阶段是在几个世纪前随着统计学的出现而出现的。第二个阶段大约 在6 0 年代随着感知器的发现而出现。随后是第三个阶段，支持向量机则是在过 去1 0 年中构造出来的。 经典的统计学：根据f i s h e r ，经典的学习问题可以分为两部分：参数区分 和参数估计。参数区分包括确定未知的潜在分布的参数，而估计是确定刻 画具体分布的过程。传统的学习算法主要集中研究估计参数的算法，而参 数的区分完全由学习系统的设计者确定。典型的方法是密度估计的最大似 然( m l ) 方法，分类的判别分析。在这两种方法中，潜在的分布是作为一 个先验的假设，而它们的参数可以通过这些方法确定。通过一个例子说明 判别分析方法的缺点。假设我们需要从数据巾构造个二类分类器，并且 假设我们已知潜在的分布为两个多维正态分布( p 。，仃1 ) 和( p 2 ，眈) 。那么 判别分析方法规定用最大似然方法估计概率分布的参数p l ，口l ，肛2 ，0 2 。这 些密度用来构造分类器。最优决策分类器是阶数为2 的多项式。但是如果 只有有限的数据点可用，估计密度的参数是相当不可靠的，这一点已经得 到了实验说明。 第二章统计学习理论概述 9 非参数统计与神经网络：相对于参数化方法，非参数方法并不依赖于预先 设定的参数化潜在分布，而是指定潜在的分布作为该方法的一部分。因 此，执行了前述的两个步骤。最熟知的非参数学习算法包括不同的神经网 络和密度估计的直方图方法。 2 2 统计学习理论 正如前所述，学习概念的中心问题是归纳步骤以及如何正确执行这些归纳 步骤的问题。该问题在一百多年前就为哲学家所思考：如何建立正确的知识? 或 如何建立正确的模型? 伟大的哲学家i m m a n u e lk a n t 在1 8 世纪提出了更加清楚 的问题：如何区分错误与正确的知识? 换句话说，从观测数据中，何时执行正确 的归纳步骤? 哲学家k a r lp o p p e r 在1 9 3 4 年提出了种解决方法。他提出，一种 理论或模型是否科学的条件是当且仅当该理论是可证伪的，也就是说，在该理 论或模型中，存在否定该理论的观测的可能性。如果永远没有观测可以否定该 理论或模型，那么该理论或模型就不能被看成是科学的。 在统计学习中具有一个类似的原则。可证伪性相应于学习算法中的有 限学习能力：仅当学习系统具有有限的学习能力，该系统才是真正的学习系 统。v a p n i k 提出学习系统的学习能力量化为v c 维，并且对有限学习能力来说是 有限的。该理论的目标是提出一种能够自动确定学习系统的最优学习能力的过 程。 2 2 1 研究的主要问题 该理论包括以下四个主要的问题： 1 一致性：一个基于e r m 原则的学习过程具有一致性的条件是什么? 2 收敛性：这个学习过程收敛的速度如何? 3 泛化能力：如何控制该学习过程的收敛速度? 4 算法：怎样构造能够控制泛化能力的算法? 我们概括统计学习理论的有关这些问题的回答。首先考虑下面的关键量。 1 0基于k e r n e l 的数据学习算法研究 2 2 2 关键量的定义 假定q ( z ，w ) ，w w 为指示函数集合，即取值为1 和一1 的函数组成的集合。 那么定义w ( 磊) 为对数据集合历= z l ，忽) 能够被函数集合q ( z ，w ) ，w w ，例如，考虑超平面指示函数集合，实现的不同的分割数。对较小的数据 点数f ，该超平面集合将以所有可能的方式，即( 历) = 2 f ，分离这些数据点。 但是，如果增加数据点，那么存在数据点属于其中的任何一种情况并且显 然( 磊) f 】= 0 ，v e 0( 2 6 ) c + ，“ 并且作为该结果的一个推论，可以导出下面的e r m 原则的一致性的充分必要条 件： 恕譬= o ( 2 7 ) 2 2 4 学习过程的收敛速率 如果我们选择指数速率，那么对任何e 0 成立： p ( r ( w ) 一r ( w o ) e - 3 过程的一致性和收敛性之外，v a p n i k 还得到学习过程泛化性能的 界。具体地说，假定v c 维为h ，期望风险的界为： 脚胚r e m p ( 毗) + ( ；) ( 2 9 ) 该泛化性能通过不等式( 2 9 ) 右边的两项定界：经验风险项和依赖于近似函数的 复杂度的另一项。不等式( 2 9 ) 完整表达如下。至少以概率1 一叩下式成立 r c 眦，忍唧c 毗) + i ( - + + 掣) ， 其中 h ( 1 n 警) 一1 i l ( ；) e = 4 生，_ 二堑 第二章统计学习理论概述 1 3 在给定函数集上，期望风险与可实现的最优风险的距离a ( w t ) = r ( w e ) 一 兄( 咖) 为： ( ；) 完整的表达为；至少以概率l 一2 下式成立 ，知网+ 浮 其中e 与前述一样。 虽然，实验表明上式界是很宽松的。注意到它们对任何分布都是有效的。但 是，这个界是在未知分布情况下的最小的已知解析形式的界。 2 2 7 结构风险最小化原则 考察学习过程泛化性能的界的表达，为了改进泛化性能的界，一方面可 以采取减少经验风险。另一方面，可以给定某个经验风险，最小化学习过程 的v c 维。后者就是结构风险最小化原则：对给定的某个经验风险，通过选择具 有最小v c 维的函数集达到最小化该函数集的结构。 许多归纳原则依赖于控制( 最小化) 经验风险，而不控制或仅仅通过启发 式隐含控制函数集的结构。正如图2 2 显示一样，保持结构固定，可能导致非 常差的泛化能力( 当九很大的时候) 。对很小的样本数，例如 ，渊，卫 ( 2 1 4 ) 因此问题变为寻找最大化的w 。显然存在无穷多个解，它们之间只差一个常识 f 为了得到唯一的解，只考虑满足下式的正规化解： a 0w = 1 相应的超平面成为正规超平面。 第二章统计学习理论概述 因此，最大化间隔等价于最小化0wi | 。所以最有超平面是满足不等 式( 5 2 ) 并且最小化： ；1 1 w0 2 ( 2 1 5 ) 比例系数 和平方是为了下面的计算方便。该问题是是个约束优化问题。 为了解该优化问题，我们可以使用l a g r a n g e 乘子法寻找最优解。如果啦 0 是l a g r a n g e 乘子，那么前述的约束优化问题可以写为下面的无约束优化问题： 1 f l ( w ，b ，口) = ；w w ) 一n ；缸 w ) 【i + 6 】一 ( 2 1 6 ) 一t=l 为了得到最优解，我们必须寻找该泛函l ( w ，b ，a ，) 的鞍点；该泛函关于w 和b 最小 化，并且关于o e o 最大化。在鞍点上解( w + ，b + ，矿) 必须满足下面的条件： 通过解这些方程可得： 1 l a g r a n g e 乘子必须满足： 坌! ! ：! ! ：! 壁：2 ：0 o b ! ! ：! 竺! 竺：2 ：o ( 2 1 7 ) ( 2 1 8 ) f n ：玑= 0 ， o ，i = 1 ，( 2 1 9 ) t = 0 2 法向量w + 是训练数据的线形组合： w = 。：玑) ( 1 ， q ：o ，i = 1 ，( 2 2 0 ) t = - 0 k t 定理说明如果在式( 5 2 ) 的约束中等式成立，那么q ：为非零。 q ；卧( w 】【l + b ) 一1 1 = 0 ，i = 1 ，( 2 2 1 ) 称相应的l a f a n g e 乘子o l ： 0 6 勺i jj l 练数据k 为支持向量。把l a 口a n g e 函数( 2 1 6 ) l 重 写为： l ( 。，6 ，。) ：( w w ) 一壹。玑k w a 壹n 。仇+ 壹m t = l = lt = 1 ( 2 2 2 ) 1 6 基于k e r n e l 的数据学习算法研究 把式( 2 1 9 ) 暑w 式( 2 2 0 ) 代入上式可以得到只含o 。的l a 盯a n g e 函数： f l d u a l ( o ：) = 一；a ，0 j 玑协( ) ( i 均) + 啦 ( 2 2 3 ) 。1 , 3 = 1 t = l 该表达式是优化问题的对偶形式。为了解该对偶优化问题，式( 2 2 3 ) 必须关于参 数o l ，o 最大化并且约束条件为： f f q 。玑= 0 ， 啦o ，i = 1 ，一，f( 2 2 4 ) # 0 由于没有不等式约束，对偶问题比原问题更容易解。更主要的一个特点是数据 仅以内积的形式出现。因此，只要计算内积，而内积的计算可以通过核方法隐 含计算。通过核方法可以推广支持向量机到非线性的情况。 此时，决策函数可以表示为： ，( x ) = n ：玑( x ) 【1 ) + 6 ( 2 2 5 ) s = l 线形不可分情况 线形可分的假设在大多数情况下是不能满足的。另外，即使数据时线形可 分的，当只有一些数据位于间隔内时候，我们也希望获得更大的间隔，这意味着 更低的结构风险。 为了泛化位于间隔中的数据或位于决策边界错误一侧的数据，引入正的松 弛变量1 一，放宽约束条件( 5 2 ) 为： 玑w x ，+ 6 】21 一矗，6 0 ，i = 1 ，( 2 2 6 ) 为了寻找具有最大问隔的超平面，同样最小化泛函( 2 1 5 ) ，但是增加一项松弛变 量的总和作为附加的代价： h 譬妻矗 ( 2 2 7 ) 约束条件为( 2 2 6 ) 式。参数e 量化函数复杂性和允许不可分数据比例之间的一种 折中。 第二章统计学习理论概述1 7 同样希望把该优化问题转化为对偶问题。对偶的l a g r a n g e 函数为： 工删( 。) = 一i 弘现( 】【l 为) + 啦 ( 2 2 8 ) l j = j t = l 2 3 2 基于核的支持向量机 核方法的主要思想是把数据隐含映射到高维空间中，只要把内积用核函数 来代替。假设数据x 映射到高维空间爿中： rh 爿 x ( x ) 高维空间咒是一h i l b e r t 空间并且可能是无限维的。在有限维的情况下，可以把 空间咒为欧氏空间。 假设存在一个核函数满足： k ( x ，y ) = 庐( x ) 毋( y ) 如果需要计算( ( x ) ( y ) ) ，仅在高维空间爿中内积相关，那么只需要计 算g ( x ，y ) 而不要直接计算内积。而只要在低维空间中计算核函数。根据h i l b e r t - s c h m i d t 里论，k ( x ，y ) 可以是满足下面一般条件的任意对称函数。 定理2 1 f 先聊砂妥保证l 2 下的对称函数k ( 札，u ) 能以正的系数a o 展开成 g ( u ，口) = a k c k ( u ) 妒k ( v ) ( 2 3 0 ) f 即( “，口) 描述了某个特征空间中的一个内积j ，充分必要条件是，对使得 9 2 ( 乱) 如 。 2 q l = c f 一 吼 一 口0 = 玑 o 。m 为件条柬约 0 = 玑 a 。耐 第二章统计学习理论概述 2 3 3 支持向量机回归算法 支持向量机同样能够用来解决回归问题：在输入空间或特征空间中学习线 性的或非线性的函数。 在输入空间或特征中，用参数化的线性函数近似回归函数： ，( x ，w ) = 毗也( x ) 此处虽然没有考虑偏置项b ，但可以用常函数( x ) = 1 作为及函数来表达。使 v a p n i k 提出的e - 损失函数： w 炉 i ：一五l “墨型三。 使用结构风险最小化原则，最小化近似函数集的结构。而每一个结构& 定 义为： 鼠= 娄毗也c x ，：c w x ，魄) 假设我们通过最小化下式表示的经验风险寻找函数参数w ： c w ，= ；塾0 ，喜啡，) 约束条件为： w w c k( 2 3 5 ) 等价于寻找参数叫，其最小化由松弛变量，g ，i = 1 ，f 的泛函： 约束条件为( 2 3 5 ) 及 玑一w 。破( x ) e + g z = l t 以破( x ) 一玑e + z = 1 g 0 毛0 ( 2 3 6 ) ( 2 3 7 ) ( 2 3 8 ) ( 2 3 9 ) g 一 。商 + ，甜 生堇王鉴堡呈丛堡垦堕墼塑堂- f 翌篁鎏堕塞 二o o “口y q 异阱咒 可以重写为下面的二次规划问题的形式：最小化 詈(