（电路与系统专业论文）用于回归估计的支持向量机的学习算法及应用[电路与系统专业优秀论文].pdf

摘 要 用于回归估计的支持向量机的 学习算法及应用 摘要 支持向量机( s v m ) 是由v a p n i k 及其研究小组于1 9 9 5 年在统计学习理 论的基础上提出来的一类新型的机器学习方法，由于其出色的学习性能，恢技 术已成为当前国际机器学习界的研究热点。用于回归估计的支持向量机方法 ( s v r ) 以可控制的精度逼近非线性函数，具有全局最优、良好的泛化能力等 优越性能，得到了广泛研究。但是其理论体系和学习算法的实现仍然有大量问 题有待发展和完善，如何设计快速有效的算法是s v r 实际应用中的瓶颈问题， 而且其在应用方面的研究也相当缺乏。 本文首先介绍了几种s v r 算法，通过理论推导及改造s v r 优化式，提出 了一种毅的用于回归估计的支持向量机的优化算法l s v m r 。而后围绕应用问 题展丌了一些研究，针对医学上三类血浆脂蛋白( v l d l 、l d l 、h d l ) 样本 中胆固醇含量测定的问题，提出了利用s v r 和l s v m r 进行回归估计的方法， 并与b p 网络方法进行了比较；针对物理上光的衍射和干涉实验提出了利用 s v r 对实验数据进行曲线拟合的方法，并与最小二乘法的方法进行了比较。 实验表明上述所提出的方法在整体性能上优于b p 网络方法和最小二乘法的方 法。 关镅! 词： s 、，r ， 学习算法， l s v m r ， 胆固醇， 物理实验 圳r 同门估计的支持向域机的算法及应州 l e a r n i n ga l g o r i t h m sa n da p p l i c a t i o n s o f t h es v mf o rr e g r e s s i o n a b s t r a c t s u p p o nv e c t o rm a c h i n e ( s v m ) b a s e do nt h es t a t i s t i c a ll e a m i n gt h e o r yi sa n e wm a c h i n el e a r n i n gm e t h o d ，w h i c hw a sd e v e l o p e db yv 巾n i ka n dh i st e a mi n 19 9 5 t h es v mh a sb e c o m et h eh o t s p o ti nt h ef i e l do fm a c h i n e1 e a r n i n gb e c a u s eo f i t se x c e l l e n tl e a m i n gp e r f o r m a n c e s u p p o nv e c t o rm a c h i n ef o rr e g r e s s i o n ( s v r ) h a sr e c e n t l ya t t r a c t e dg r o 、v i n gr e s e a r c hi n t e r e s td u et oi t so b v i o u sa d v a n t a g e ss u c h a sn o n l i n e a rm n c t i o n 印p r o x i m a t i o n w i t h a r b i t r a r ya c c u r a cy a n d g o o d g e n e r a l i z a t i o na b i l i t y ，u n i q u ea n dg l o b a l l yo p t i m a ls 0 1 u t i o n s b u ti t st h e o r e t i c a l s y s t e mh a sm u c hr o o mf o ri m p r o v e m e ma n dt h er e a l i z a t i o no ft h ei e a m i n g a l g o r i t h mh a sm a n yp r o b l e m sf o rs 0 1 u t i o n h o wt od e s i g ns v r1 e a m i n ga l g o r i t h m s w h i c ha r eb o mf a s ta n dv a l i dh a sb e c o m et h eb o t l l e n e c ki np r a c t i c a l 印p l i c a t i o n so f s v r m o r e o v e r j t sr e s e a r c hi na p p l j c a t i o n sn e e d st ob ee n h a l l c e d i n t h i sd i s s e n a t i o n ，s o m ee x i s t i n gs v r1 e a m i n ga l g o r i t h m sa r en r s t l y i n t r o d u c e d b yi n f e r e n c ea i l dv i ai m p r o v e dm a t h e m a t i c a lf o m u l a s ，an e ws v r l e a r n i n ga l g o r i t h m l a g r a n g i a ns u p p o r tv e c t o rm a c h i n ef o rr e g r e s s i o n ( l s v m r ) i sp r e s e n t e d t h e ns o m ea p p l i c a t i o n sa r es t u d i e d t h es v ra n dl s v m rb a s e d m e t h o d sa r e p r e s e n t e dt od e t e m “n es e r u mc h 0 1 e s t e r 0 1l e v e l sf r o mt h e m e a s u r e m e n t so fs p e c t r a lc o n t e n to fab l o o ds a m p l ei nm e d i c a ls c i e n c e ，w h i c ha r e c o m p a r e dw i t ht h eb p - n e t w o r k - b a s e dm e t h o d i na d d i t i o n ，t h es v r - b a s e dm e t h o d i sp r e s e n t e dt oc u r v e n tt 1 1 ee x p e r i m e n td a t ao ft h ei n t e r f e r e n c ea n dd i f r r a c t i o no f 1 i 曲t i n p h y s i c se x p e r i m e n t s ， w h i c hi s c o m p a r e dw i t ht h e l e a s t s q u a r e a l g o r i t _ b a s e dm e t h o d t h ee x p e r i m e n t a lr e s u l t ss h o wm a tt h e 摘要 p r o p o s e dm e t h o d s a r eb e n e r t h a nt | l eo t h e rt w om e t h o d si nw h o l ep r o p e r t i e s k e vw o r d s ： s u p p o nv e c t o rm a c h i n e sf o rr e g r e s s i o n ( s v r ) ，l e a r n i n ga l g o “t h m s ，l a g r a n g i a n s u p p o r t v e c t o rm a c h i n ef o r r e g r e s s i o n( l s v m - r ) ，c h o l e s t e r o l ，p h y s i c s “p e r i m e m s 独创性声明 本人严明所呈交的学位论又是本人在导师指导f 进行的研究工作及取得的 研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获绳泓其他教育机构 的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意 学位论文作者签名：一弋靠 签字日期：砂一 年 碉智日 学位论文版权使用授权书 本学位论文作者完全了解审璃奠欠秀角关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权) 圣；f j = 编将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：j 蕊 导师签名： 偶存 签字日期：乙驴 年h 秀日签字日期：力柙r 年厂月p 日 举位诒女作者毕业去由： 工作单位： 通讯地址： 电话： 邮编： 第一辛绪言 第一章绪言 1 1 统计学习理论与支持向量机 基于数据的机器学习是继专家系统之后人工智能应用的又一重要研究领 域，也是人工智能和神经计算核心研究课题之一。研究从观测数据出发寻找规 律，利用这些规律对未来数据或无法观测的数据进行预测。现有的机器学习方 法的共同理论基础之一就是统计学。 传统的统计学是在样本数足够多的前提下进行研究的，所提出的各种方法 都只有在样本数目趋于无穷大时才能有理论上的保证。但是在实际问题中，样 本数往往是有限的，这时很多方法都难以取得理想的效果。在传统的统计学研 究中，我们都是将经验风险r 。最小化作为解决问题的基本思想的，称之为经 验风险最小化准则( e m p 谢c a lr i s km i n i m i z a t i o n ，e r m ) 。但是这样一来存在 两个方面的问题，一方面，经验风险r 。只有在大数定理的保证下彳能与期望 风险r 在概率上保持一致；另一方面，即使我们得到在样本数目无穷大时趋 近r 的r 也不能保证在有限样本情况下仍然得到好的效果。2 1 近年来，有限样本情况下的机器学习理论逐渐成熟起来，形成一个较完善 的理论体系统计学习理论( s t a t i s t i c a ll e a r n i n gt h e o r y ，s l t ) 4 7 1 。 为了解决传统统计学研究中的上述两个问题，我们先介绍一下v c 维的概念。 假如存在h 个样本能够被函数集中的函数按所有可能的2 “种形式分成两 类，则称函数集能够把h 个样本打散；函数集的v c 维就是它能打散的最大样 本数h 。 由统计学习理论，经验风险最小化准则下机器学习的实际风险是由两部分 组成的： r r + 巾 其中中称作置信范围，m 与样本数n 和v c 维h 的比值成反比a 这样当较 川丁同 估计的支持向繁机的算法及席_ 【 j 小时，置信范围较大，用经验i x l 险近似真实风险就会有较大的误差；当样本数 增多，形变大，置信范围变小，经验风险就会近似真实风险。因此在有限样 ，l 本情况下，机器学习过程不但要使经验风险最小，还要尽量缩小置信范围，这 样才能取得较小的实际风险，对未来的样本有较好的推广性，即具有较好的泛 化能力。为此统计学习理论提出了结构风险最小化准则( s t m c t u r a lr i s k m i n i m i z a t i o n ，s r m ) ，即在最小化实际风险时必须同时最小化经验风险和置 信范围。换句话说，如果数掘服从某个固定但未知的分布，要使机器的实际输 出与理想输出之间的偏差尽可能小，则机器应该遵循结构j x l 险最小化准则，而 不是经验风险最小化准则。 我们知道传统的神经网络的学习算法和最小二乘法都是基于经验风险最 小化准则提出来的，即最小化经验风险( 训练误差) 从而试图使期望风险最小 化。而支持向量机( s u p p o nv e c t o r m a c h i n e s v m ) 是由a t t 贝尔实验室 的v a 口n i k 及其研究小组于1 9 9 5 年在统计学习理论的基础上提出来的一类新型 的机器学习方法。它是结构风险最小化准则基本思想的具体实现。为了最小化 期望风险，做到同时最小化经验风险和置信范围，即以训练误差作为优化问题 的约束条件，而以置信范围值最小化作为优化问题的目标来实现。所以支持向 量机的泛化能力要明显优于神经网络等传统的学习方法。 支持向量机的主要思想可以概括为两点：1 ) 它丌始是针对线性可分情况 进行分析的，后来对于线性不可分的情况，通过使用非线性映射算法将低维输 入空剐线性不可分的样本映射到高维属性空间使其线性可分，使得在高维属性 空间采用线性算法对样本的非线性特性进行分析成为可能；2 ) 它通过使用结 构风险最小化准则在属性空间构造最优分割超平面，使得机器学习得到全局最 优化，解决了过学习问题，对样本具有较好的泛化能力。 8 l 另外，由于支持向 量机的训练问题本质上是一个经典的二次规划问题，避免了局部最优解，有效 地克服了维数灾难，而且可以利用最优化理论中许多成熟的算法。 币是基于支持向量机的上述优势，无论在理论基础上还是在应用前景上， s v m 都具有其它机器学习方法难以比拟的优越性，它已经在模式识别和回归 估计方面取得越来越多的进展。下面分别从这两个方面对支持向量机的训练算 法作一简要的介绍。 第一章绪言 1 2 用于分类的支持向量机算法 s v m 方法最早是针对模式识别问题提出来的，而且大部分算法的研究都 是针对两类问题展开的。 在标准算法【2j 中，v a p n i k 先就两类线性可分的情况构造了最优分类面， 即使两类无错误地分丌并且两类的分类间隙最大，从而将分类问题归结为一个 二次型方程的求解问题。而后v a p n i k 又考虑到两类线性不可分的情况，通过 构造核函数的方法将输入样本空间非线性变换到另外一个特征空| 日j ，再在这个 新空间中求取样本的最优线性分类面。但是随着训练样本数的增多，标准s v m 算法会出现训练速度过慢，由于面临维数灾难或内存限制而导致无法训练的问 题。所以如何训练大训练集的s v m 成为s v m 实际应用中的瓶颈问题。 目前用于训练s v m 的算法都是在经典s v m 算法基础上提出来的一些优 化算法1 0 】。它们主要从两个方面对标准算法进行改造的。一方面从分解策 略出发，通过处理一系列小规模的子q p 问题来一步步解决原大规模问题，只 是分解的规模大小和工作集的选择策略不同；另一方面对标准算法中的目标函 数和优化条件式进行一些改造和替代。 1 2 1 从分解策略出发的s 优化算法 我们先从第一个方面对s v m 的优化算法加以展开并作简要的介绍： 1 9 9 5 年，c o r t e s 和v a p n i k 提出了块处理c h l m k i n g 算法”j 。其出发点是删 除矩阵中对应l a g r a n g e 乘子为零的行和列将不会影响最后的结果，从而将一 个大型二次规划( q u a d r a d i cp r o g r 锄m i n g ，q p ) 问题分解为一系列较小规模 的q p 问题。在算法的每步中c h u n k i n g 都解决一个q p 问题，其样本为上一步 所剩的具有非零l a g r a n g e 乘子的样本以及m 个不满足k t t 条件的最差样本。 每个q p 子问题都采用上个q p 子问题的结果作为初始值。在最后一步时， 所有非零l a g r a n g e 乘子都被找到，解决了初始的大型q p 问题。它将矩阵规 模从训练样本数的平方减少到具有非零l a g r 趴鲈乘子的样本数的平方。然而 _ l j 川n i 门估计的支持向姑机的算法及席川 当训练集的支持向量数很大时，仍然无法将矩阵放入内存中。 1 9 9 7 年，o s u n a 针对s v m 训练速度慢及时间空间复杂度大的问题，提出 了一种固定工作集的分解算法【1 3 j ，其主要思想是将训练样本集分为工作集b 和非工作集n ，且保持工作集b 的大小不变。在解决每个q p 子问题时，先从 工作集中移走一个样本，并加入个不满足k t t 条件的样本，再进行优化。 陔算法存在效率问题，因为每一步中，进行一次q p 问题的最优化只能使一个 样本符合k t t 条件。 1 9 9 8 年，j o a c h i m s 提出一种解决大型问题的学习算法，称为s v m “曲。 它实际上是o s u n a 方法的推广。其基本思想是如果存在不满足k t t 条件的样 本，则以某种方式选择q 个样本作为工作集，其它样本保持不变，在这个工作 集一卜解决o p 问题，直至所有样本都满足k t t 条件。 1 9 9 8 年，p l a t t 又提出了一种名为s m o 的学习算法来解决大训练样本 的问题。浚算法也可以看作是0 s u n a 分解算法的一个特例，工作集b 中只有 两个样本。其优点是针对两个样本的二次规划问题可以有解析解的形式，避免 了多样本情形下的数值解不稳定及耗时问题，也不需要大的存储空i 剐。s m o 算法主要耗时在最优条件的判断上，所以应该寻找最合理的最优条件判别式。 1 9 9 9 年，s s k e e r t “”1 又对p l a t t 的s m o 算法作出重大改进，即在判 别最优条件时用两个闽值代替一个闽值，使算法更合理更快。 1 2 2 从改造优化式出发的s v m 优化算法 下面我们再从第二方面对s v m 的优化算法作一个简要的介绍： s s k e e r c h i 提出了n p a 最近点算法1 18 1 。其基本思想是将s v m 原问题 的惩罚项由线性累加改为二次累加，从而将优化问题转化为两个凸集问的最大 问隔。 张学工提出c s v m 算法，将每类训练样本集进行聚类分成若干子集， 用子集中心组成新的训练样本集训练s v m 。根据每个子集的每个样本的系数 的改变对目标函数的影响对训练样本集进一步划分，直到没有新的拆分点为 止。这样就提高了算法的速度，也减少了训练数据中的野值对分类结果的影响。 第一苹绪言 s c h o 】k o p f 提出了v s v m 算法【2 0 【2 1 ，它的优点体现在1 ) 参数v 表示支 持向量的卜| 界和f 日j 隙误差的上界，使用它来控制支持向量的个数及误差。2 ) 没有参数c 避免了数值计算的麻烦。 j a k s u y k e n s 提出了最小二乘法支持向量机算法l s s v m 【2 3 j 【2 4 】【2 5 ， 将二次规划问题的不等式约束转化为等式约束，从而将问题转化成了线性方程 的求解问题。 o l v i lm 提出了s o r 算法【2 6 】，通过在原目标函数中加一项b 2 ，使对偶 问题多了一项，但约束条件少了一项等式约束，变为边界约束条件下的二次规 划问题，适合迭代求解。 m a n g a s a r i a n 提出了l s v m 算法【2 7 】，通过将松弛变量项改为二次范数的形 式，使约束条件少了一项不等式约束，从而减少了计算的复杂性，提高了学习 速度。 1 2 3 多类支持向量机算法 至于多类问题，我们必须将其转化为两类问题来解决。一般都是通过某种 方式构造一系列的两类分类器并将它们组合在一起实现多类分类。f 2 8 i 1 一v r ( o n e v e r s u s r e s t ) s v m s 算法 2 9 l 依次用一个两类s v m 分类器 将每一类与其他所有类别区分开来，得到k 个分类函数，分类时将未知样本分 到函数值最大的那一类中。 1 v l ( o n e v e r s u s - 一o n e ) s v m s 口0 1 算法每两类问训练一个分类器，对 于k 类问题将有( 一1 个分类函数。对未知样本分类时，每个分类器都对 其类别进行判断，并为相应类别投上一票，最后得票最多的即为该未知样本类 别。 有向无坏图多类s v m s 分类法川也是构造每两类间的分类面，该方法将所 有分类器构造成有向无环图，图中包括女( 一1 z 个节点和k 个叶，其中每个 节点为一个分类器，叶是类别数。对未知样本分类时，首先从顶部的根节点开 始，根据根节点的分类结果用下层中的左节点或右节点继续分类，直到达到 j 4 j 丁同门估计的支持向量机的算法及虑川 某个叶为止，浚叶表示的类别即为该未知样本类别。 层次s v m s 分类法首先将所有类别分成两个子类，再将子类进一步划分成 两个次级子类，如此循环下去，直到得到一个单独的类别为止。 这些用于分类的支持向量机方法在字符识别嘲，文本自动分类吲1 3 4 】，人 脸识别【3 5 】等领域都得到了很好的应用。今后的研究方向主要是寻找大规 模训练样本下的实用算法，进一步提高在线训i 练的速度。 1 3 用于回归估计的支持向量机算法 我们在前面已经提到s v m 方法最早是针对模式识别问题提出来的， v a p n i k 通过引入8 不敏感损失函数，将其推广应用到非线性回归估计中，并表 现出了很好的学习能力。下面我们就简要地描述用于回归估计的一些s v r ( s u p p o r tv e c t o r m a c h i n e f o r r e g r e s s i o n ) 基本学习算法 3 7 】。 在用于回归估计的标准s v r 学习算法中，学习的目的在于构造一个回归 估计函数厂o ) ，使它与目标值的距离小于，同时函数的v c 维最小，从而将 线性或非线性函数( x ) 的回归估计问题转化为一个具有线性等式约束和线性 不等式约束的二次规划问题，可以得到唯一的，全局最优解。但它同样存在两 个方面的问题，一方面，c 和8 的选择问题。c 取得过小，训练误差变大，系 统的泛化能力变差，c 取得过大，也会导致系统的泛化能力变差；取得小， 回归估计精度高，但支持向量数增多，取得大，回归估计精度降低，但支持 向量数少。另一方面，在求解大规模问题时也同样存在学习速度过慢的问题， 因此，如何减少计算时间和存储空间同样是用于回归估计的s v r 学习算法的 研究热点。 1 3 1 从改造优化式出发的s v r 优化算法 我们先从第一个方面对s v r 的优化算法加以展开并作简要的介绍： 在s c h o l k o p f 和s m o l a 提出的v s v m 算法【2 0 】中，引入反映超出s 管道之外 第一章绪言 的样本数据点，即边乔支持向量数量，和支持向量数的新参数v ，简化了s v m 的参数调节。而且在优化求解过程中不需要s 的值，因此不需要预先规定取 多少值。 在j a k ，s u y k e n s 提出的最小二乘法支持向量机算法l s s v m 【2 3 j 中， 优化指标采用平方项，将不等式约束转变为等式约束，从而将二次规划问题转 变成线性方程组的求解问题。另外，与标准s v r 算法相比，减少了个调整 参数，减少了多个优化变量，因此简化了计算的复杂性。 在加权支持向量机w s v m 算法【3 8 1 【3 9 】中，对每个样本点采用不同的惩罚系 数c ，或对每个样本数据点采用大小不同的s 管道，以得到更准确的回归估计。 加权支持向量机可以通过对惩罚系数c 加权实现，也可以通过对加权实现。 k e c m a n 和h a d z i c 提出将优化目标用一次范数替代二次范数，将最优化 问题转化成线性规划问题来求解。但是这样做的突出问题是线性规划的约束数 与，维数有关，对于非线性样本集实际上无法求解。 1 3 2 从分解策略出发的s v r 优化算法 我们接着考虑大训练样本问题从第二个方面对s v r 的优化算法作个简要 的介绍，在这方面基本上是s v m 优化算法的类推： 分解算法的主要思想是将大训练样本集分为大小固定为q 的工作集b 和非 工作集n ，由于分解法中工作集b 的大小固定不变，o p 子问题的求解不会随 样本数的增加而增加。 s c h o l k o p f 和s m 0 1 a 针对回归估计提出了s m o 算法，s m o 算法是分解法 的一个特例，它将工作集b 的大小限定为两个样本。在进行0 p 子问题的求解 时直接用解析法计算最优值，而不需要采用数值优化算法进行计算。 这些用于回归估计的支持向量机方法在非线性系统辨识，预测预报4 2 1 ， 函数逼近等领域都有潜在的广泛应用。但是目前用于回归估计的支持向量 机方法仍然存在许多尚未解决的问题，尤其在应用方面的研究相当缺乏。 h jr 同门f 占计的支持向鼙机的算法及应h j 1 4 本文主要研究内容 通过自口面对支持向量机的介绍，我认为有两个问题值得进行研究： 1 由于s v m 出现不久，其理论体系和学习算法的实现仍然有大量问题 有待发展和完善，我们前面也提到如何训练大训练集的s v m 是s v m 实际应 用中的瓶颈问题，因此如何设计快速有效的算法是s v m 研究的一大热点。 2s v m 算法是对传统的神经网络的学习算法和最小二乘法的改良，丌展 s v m 方法的应用研究，推广s v m 的应用，对解决很多实际疑难问题，如对 字符识别，人脸识别，预测预报，建模与控制等问题的解决，具有非常重要的 意义。 我的毕业论文主要是从用于回归估计的支持向量机的学习算法及其应用 这两个方面展丌的。 一方面在对现有的这些支持向量机算法进行理论分析的基础上，通过理论 推导和计算提出了一种用于回归的支持向量机的优化算法。本文将 m a n g a s a r i a n 提出的用于分类的l s v m ( l a g r a n g i a ns u p p o nv e c t o rm a c h i n c l s v m ) 设计方法推广到回归估计问题中，对用于回归估计的标准s v m 算法 加以改造，得到了改进的用于回归估计的支持向量机l s v m r ( l a g f a n g i a n s u p p o nv e c t o r m a c h i n ef o r r e g r e s s i o n l s v m _ r ) 。实验比较结果表明，改进 的用于回归估计的s v m 学习算法在保持了与用于回归估计的标准s v m 学习 算法同样的精度下，学习速度得到了显著提高。 另一方面做了一些有关支持向量机在回归估计上的应用。 应用一：应用s v r 和l s v m r 对3 种不同类别血浆脂蛋白样本与其血浆 胆固醇的含量进行回归估计，并与b p 网络的方法进行了比较，实验表明其在 稳定- | 生上优于b p 网络，而且在对v l d l 类血浆脂蛋白样本中血浆胆固醇的含 量回归估计的精度上比b p 网络方法要好；并且l s v m r 方法在训练时间上也 毫不逊色于b p 网络方法。 应用二：应用s v r 对光的双缝干涉和单缝衍射的条纹分靠情况进行曲线 拟合，并与物理实验上通常采用的最小二乘法的方法进行了比较，实验表明其 第一章绪言 在精度上优于最小二乘法的方法，尤其在对复杂曲线进行拟合时效果极其明 显。我们知道在实际实验中，遇到的都不是现成的函数关系而往往是一批实验 数据，再通过数据拟合束推断函数关系，因此s v r 方法是一种较最小二乘法 更为理想的曲线拟合方案，有利于物理实验数据的处理与分析，而且可以将其 推广到工程技术领域。 1 5 本文内容安排 本文第二章分别从线性可分，广义线性可分和线性不可分三种情况入手介 绍用于分类的支持向量机的标准算法：第三章从不敏感损失函数的引入介 绍了用于回归估计的支持向量机的标准算法以及四种在标准算法基础上改造 的支持向量机的优化设计算法；第四章先介绍了用于分类的支持向量机的一种 优化算法l s v m ，并在此基础上将这种优化算法推广到用于凹归估计的支持向 量机中，形成了一种新的改进算法l s v m r ；第五章主要做了一些支持向量机 在回归估计上的应用，包括在胆固醇测定中的应用，在物理实验曲线拟合上的 应用；第六章全文总结，提出今后的研究方向。 9 川丁同门估计的支持向昔机的算法及府 第二章用于分类的支持向量机 的标准算法 支持向量机( s u p p o r tv e c t o rm a c h i n e ，简称s v m ) 是针对模式识别问题 提出来的，它的理论最初来自于对数据分类问题的处理。对于数据分类问题， 如果采用传统的神经网络方法来实现，其机理可以简单地描述为：系统随机产 生一个超平面并移动它，直到训练集中属于不同分类的点t f 好位于平面的不同 侧面。【8 】这就决定了用神经网络方法进行数据分类最终获得的分割平面将相当 靠近训练集中的点，从而出现过学习问题，造成神经网络方法的泛化性能较差。 因此在s v m 方法中引入了最优超平面，寻找一个满足分类要求的分割平面， 并使训练集中的点距离该分割平面尽可能远，也就是使分割平面两侧的空白区 域最大。 由于s v m 方法中的大部分算法都是针对两类问题展开的，因此在本章讨 论的是两类问题的标准支持向量机算法。【m 】【3 5 】 设学习( 训练) 样本集为 x ，y ， ：，x ，是第f 个学习样本的输入模式，且是 一d 维列向量，即x ，e ，x ，= x ? x 0 x ? 】7 ，另外，m + 1 ，一1 ) 是其类别标 记( 或称为目标输出) 。如果x 。属于第一类，则标记1 ；如果工，属于第二类， 则标汜1 。支持向量机的目标就是根据结构风险最小化原理，构造一个目标函 数，将两类模式尽量正确地区分丌来。下面就分三种情况分别进行讨论。 2 1 线性可分模式下的最优分类面 假设学习样本集 一， ) 墨是两类线性可分的，这种情况下的判别函数为 g ( x ) = ( 坩，工) + 6 = ，1 x + 6 ( 2 1 ) 式中x 是一样本向量，w 是权向量，6 为分类阈值，( w ，x ) 表示两向量的内积。 第一章用丁分类的支持向鼙机的标准筇法 如果存在决策面 能够分丌两类样本，使得 g ( x ) = i ，x 十6 = o 对于y ，= l ，有g ( x ) = w t x ，+ 6 0 对于r = 一1 ，有g ( 工) = 1 x + 6 o ( a 罡 o ) 且其类别标记为儿+ = + 1 ( y 女一2 一1 ) 的支持向量，则可求出6 。为 扫0 p = 一委 ，印7 ( x 。+ + x + 一) ：一三喜。，y ，r x ，工。+ ，+ c x ，x 。一， 2 2 。 最后得到的最优分类函数为 4 乜 一工x ( y ， o 盯 i i d ，。脚叫 。d。r厶 l 一2 n 峙 n o 2 一 i i n ， 这若 第二章_ l j 丁分类的支持向昔机的标准算法 ，( x ) = s i g n g ( x ) j = s i g n ( 1 ，。工+ 6 。)( 2 2 】) 厂x、 = s i g n f “j ”y j ” 0 ，f ，= o 时问题变为线性可分模式 下的情形。 与线性可分模式最优分类面问题求解相类似，广义线性可分模式下最优分 类面问题可转化为求解下列函数的极小值问题： n 抄w + c c 塾， s t y ，( w 7 工，+ 6 ) 一1 + 喜，o ( 2 2 4 ) 毒o f = 1 ，2 ， 式中c 为正的惩罚系数，它实际上起控制对错分样本惩罚程度的作用，实现 控制样本偏差与学习机器泛化能力之问的平衡。c 是可调参数，不难看出，c 越大，对错分样本的惩罚越重；当c 呻啪时，( 2 2 4 ) 式的优化问题等同于( 2 1 1 ) 式，因此线性可分模式下最优分类面问题是广义线性可分模式下最优分类面问 些! i ! i 塑笪兰塑奎堡望兰! ! 竺竺苎墨壁型 题的一个特殊情况。 ( 2 2 4 ) 式优化问题的解是由下面l a g r a n g e 函数的鞍点给出： l ( ，6 ，孝，晓，) ：当 ，t ，+ c f 兰f 。 一壹a ，【y ，( t 工。+ 6 ) 一l + 亡j 一圭，f ， ( 2 2 5 ) z ，= i 忙ff = l 这单a ，o ，卢，o 为l a g r 柚g e 系数，= 胁i ! 卢 7 。根据最优化理论， f 2 2 4 ) 式优化问题的解必须满足下列条件： 塑避鱼生盟：ojw ：兰刚 ( 2 “) 塑唑粤型：oj 兰坍：o ( 2 ) 塑骘磐型：oj 肛，：c ( 22 8 ) a - 将( 2 2 6 ) 式、( 2 2 7 ) 式和( 2 2 8 ) 式代入( 2 2 5 ) 式，就可得到( 2 2 4 ) 式优化问题的对 偶问题： 啷n 睦喜喜口，m y ，c x ，一喜引 s 【 d ，= o ( 2 2 9 ) o n c f = 1 ，2 ， 注意，虽然广义线性可分模式下的对偶问题( 2 2 9 ) 式与线性可分模式下的对偶 问题( 2 1 6 ) 式在约束条件中略有不同，但最后求出的分类闽值6 0 p 表达式以及最 优分类函数表达式却是完全一样的。 根据k n 1 1 1 t u c k e r 条件，( 2 2 9 ) 式的优化问题的解。必须满足下列条件： a 严【y ，( ，。7 x + 6 ) 一l + 善】= 0 瞒3 0 ( 2 3o ) a j ? 七l l j = c f = l ，2 ， 由( 2 3 0 ) 式，我们不难分析： 若a 严= 0 ，则必有“= c ，鲁= o ，那么 y ，( 缈。x + 6 ) 一1 0 ( 23 1 ) 第一蕈川 分类的支持向草d 【的标准算法 若o “f ” c ，则必有o ，f ， c ，f ，= o 那么 y ，( w o d l x + 6 ) 一l = o( 2 3 2 ) 若“? 9 = c ，则必有m = o ，专o 那么 y ，( w 1 工+ 6 ) 一1 o( 2 3 3 ) 由( 2 3 1 ) ，( 2 3 2 ) ，( 2 3 3 ) 式，我们可以得出 4 4 中的结论： 对样本集进行训练得到s v m 分类器，d o 为l a g r a n g e 系数。d = o 对应的样 本分布在分类器分类i 、日j 隔之外，o 、 若用+ ( 一) 表示满足n 芒 o ( 口罂 0 ) 且其类别标记为儿+ = + 1 ( y i 一= 一1 ) 的支持向量，则可求出6 。为： 6 。p = 去w 叩1 ( x k + + x i 一) ：。 ( 2 3 5 ) = 一去吐，j ，( ( x ，x 。+ ) + ( 工，x 。一) ) 最后得到的最优分类函数为 厂、 厂( x ) = s i g n d 严y ，( x ，工，) 十6 。l ( 2 3 6 ) o eo 鲥 其中，。为样本集 置，m 兰中支持向量的下标集，也就是 a 。= 陋p d 罗6 【妒 中不为0 的元素的下标集。 2 3 线性不可分模式下的最优分类面 上面所讨论的都是线性最优分类函数及其求解过程中的对偶优化问题。对 于非线性分类问题，我们首先使用非线性映射。将数据从输入样本空间非 h 】。同门估计的支持向营机的拜法及虑h j 线性变换到另一个高维特征空间( h i l b e r t 空阳j ) ，然后在这个新的空间中求 取样本的最优线性分类面。高维特征空问的维数可能是非常高的，支持向量机 理论巧妙地解决了这个问题。观察到在线性情况时仅涉及输入样本之问的内积 运算( x ，x 。 ，因此在非线性情况中也只需考虑在高维特征空间中的内积运算即 可，而不必明确知道非线性映射。是什么，从而避免了复杂的运算。因此内积 函数( 或称为核函数) 是构造支持向量机的关键。 设 妒，q ) 健；为输入样本空幛j 到特征空 、日j 的非线性变换，并在特征空间中 定义超平面为 w ，妒肛) + 6 = o ( 2 3 7 ) 这里 w ， 翟，为一组权值，6 为分类阈值。 令特征空阳j 中超平面的权向量为w = 【比w 。 ，特征空间中特征向 量为 妒= 【p ，( x ) p 2 ( x ) ( x ) 】1 ( 2 3 8 ) 类似于在输入样本空i l 日j 求解最优分类面，仿照( 2 1 7 ) 式和( 2 1 9 ) 式，我们可以求 出特征空间中最优分类面或最优超平面，其权向量，。和分类阈值6 。p 分别为 w 。= af 。p y ，尹( x ，) ( 2 3 9 ) 6 0 。= 一 一? 9 y ，( 9 ( z ，) ，伊( x ) ) ( 2 4 0 ) ，= 1 将( 2 _ 3 9 ) 式代入( 2 3 7 ) 式得 a y ，( p ( 工) ，妒( x ，) ) + 6 0 。= o ( 2 4 1 ) t = l 即为线性不可分模式下的最优分类面。 由( 2 4 0 ) 式和( 2 4 1 ) 式可知，特征空间中最优分类面只与特征向量伊( x ) 之 间的内积有关。为此，定义核函数( 即内积函数) 世( x ，x ) 为： k ( j x ) = 伊( x ) t 妒( 工) ：兰妒，( 工) 妒，( 工一) f o r f ：1 ，2 ，一， ( 2 4 2 ) = 妒，( 工) 妒j ( 工+ ) f o r f = 1 ，2 ，一， 、一 = 0 第二章h j 。分类的支持向域机的标准算法 不难看出，核函数k ( x ，工) 是对称函数，即k ( x ，x ) = 芷( 一，州。 因此，利用核函数k ( j x7 ) 就可以在特征空间中构造出最优超平面，而无 需考虑从输入样本空f 日j 到特征空间的非线性变换的具体表示式。 根据h i b e n s c h m i d t 理论，核函数岸( 工，葺) 必须是满足下面m e r c e r 条件的 对称函数： m e r c e r 定理： 设芷( x ，工) 是定义在闭区间a 工b ，a 一b 内的连续对称核函数， 趸( x ，x7 ) 能以正的系数 展丌成 世( x ，x ) = 九，纪( x ) 仍( x ) ( 24 3 ) 卜o 当且仅当对满足下式的任意函数y q ) y 2 ( x ) “ + 1 ) 4( 2 4 7 ) 径向基c 高斯，核函数k c 工，x j = e x p ( 一坠专华) c ：a s ， 两层神经网络核函数 丘( 工，x ，) = t a l l l l ( x ，工，) + c )( 2 4 9 ) 如果在线性不可分模式中引入非负松弛变量f o ( f ：i ，2 ，) 和惩 罚系数c ，可以得到下面的二次规划问题： 啤n 三，t w + c ( 善钔 s t y ，( w 1 妒( 工，) + 6 ) 一1 + 者，o( 2 5 0 ) 孝，0 f = 1 ，2 ， 用丁同门估计的支持向鼙机的算法及席州 式中，= m ，! w a ，】t ，妒) = 【蛾( x ) 仍伍) 妒。q ) 】。上式的对偶问 题为 峋。唼兰窆d ，“y ，世( x ， “ 忙i ，= 1 s - t 仅y ，= o o 玉d c f = 1 ，2 ，j v a ， ，：1 设对偶问题的解为口。= 陋严a 罗仅罗 1 ，由此可求出分类闽值 ( 2 5 1 ) 6 。，：一去羔a 飘伙( b “) + 世( k ) ) ( 2 5 2 ) 以及最优分类函数为 厂、 厂( x ) = s i g n i 严y 。k ( x ，x 。) + 6 印i l + 6 v f 2 5 3 、 = s i g n 【d ? ”y ；”k ( 工，x j ”) + 6 。p 图2 3 给出了支持向量机网络图。 z 2 幽2 3 支持向簧机网络剧 第二章州丁同9 1 估计的支持向姑机的训练算法 第三章用于回归估计的支持向量机 的训练算法 支持向量机( s u p p o n v e c t o rm a c h i n e s v m ) 是由a t & t 贝尔实验室的 v a p n i k 及其研究小组于1 9 9 5 年提出来的一种新的机器学习算法。s v m 的方法 最早是针对模式识别问题提出的，随着v a p n i k 对r 不敏感损失函数的引入， 已将其推广应用到非线性回归估计和曲线拟合中，得到了用于曲线拟合的回归 型支持向量机方法( s u p p o nv e c t o rm a c h i n ef o rr e g r e s s i o n s v r ) ，并且表 现出很好的学习效果。用于回归估计的支持向量机方法在非线性系统辨识，预 测预报，建模与控制等领域都有潜在的广泛应用，使得对其进行研究显得非常 重要。 本章重点介绍了用于曲线拟合的标准s v r 学习算法以