（应用数学专业论文）多输出函数回归的svm算法研究.pdf

摘要 摘要 支持向量机( s v m ， s u p p o r tv e c t o rm a c h i n e ) 是近年发展起来的、一种性 能优越的统计学习方法。它是依据v a p n i k 统计学习理论发展起来的，以结构风 险最小化( s r m ， s t r u c t u r er i s km i n i m i z a t i o n ) 为原则的学习方法系统。支持 向量机最初用于解决模式识别问题，但近些年来它在回归算法的研究方面也表现 出了极好的性能，其回归算法被成功地应用于时间序列的预测、非线性建模与预 测、优化控制等方面。 目前，s v m 回归算法都是建立在单输出函数模型基础之上的，对多输出函 数回归算法的讨论很少。但在实际生产和生活中，往往需要同时对多个变量或指 标进行估计和预测。传统的解决多输出回归的方法( 如：多元统计方法和神经网 络等) 都对数据模型有比较苛刻的要求，而实际数据往往不能满足这些要求，因 此它们在实际应用中效果并不理想。而如果把多维问题转化为多个一维问题，即 对每一分量都构造一个s v m 来实现对各自的回归，在目前还没有很好地解决 s v m 训练速度问题的情况下，这种方法在训练上是不现实的，而且在理论分析 时也存在一定的问题和缺陷。 为了解决多输出函数的回归问题，本文提出了一种新的m s v r ( m u l t i s v r ) 算法。首先是改进了损失函数，将对于多维来说定义在超立方体上的损失函数改 为定义在超球上的损失函数。再将训练s v m 的问题转化为一个迭代解线性方程 的问题，而不是传统的求解二次规划问题。在求解过程中还采用了一边计算一边 使矩阵降阶的办法，使得在求解问题的同时找到了支持向量( s v ，s u p p o r t v e c t o r ) 。最后，将m s v r 算法应用到多个仿真数据集上，并将其训练结果与对 输出各分量分丌建模的s - s v r 算法( s i n g l e s v r ) 的训练结果进行了比较。结 果表明：m s v r 算法在速度上大大超过了用s m o 算法实现的s - s v r ，而与用 l s s v m 算法实现的s - s v r 相比，支持向量明显减少，并且具有更好的整体预 测精度和抗噪性能。 关键词多输出；函数回归：支持向量机；s v r 华南理工大学硕士学位论文 a b s t r a c t t h es u p p o r tv e c t o rm a c h i n e ( s v m ) i san e ws t a t i s t i c a lm e t h o dw h i c hi s e x c e l l e n to np e r f o r m a n c ei nr e c e n ty e a r s i ti sb a s e do i lt h es t a t i s t i c a ll e a r n i n gt h e o r y o fv a p n i ka n di t sd e c i s i o n m a k i n gp r i n c i p l ei ss t r u c t u r er i s km i n i m i z a t i o n ( s r m ) s v mh a so r i g i n a l l yb e e nu s e dt os o l v i n gp a t t e r nr e c o g n i t i o np r o b l e m s ，a n dn o wi t a l s oh a sg o o dp e r f o r m a n c eo nf u n c t i o na p p r o x i m a t i o na n dr e g r e s s i o ne s t i m a t i o ni n t h e s ey e a r s i t sr e g r e s s i o na l g o r i t h mi ss u c c e s s f u l l ya p p l i e dt ot i m es e r i a le s t i m a t i o n ， n o n l i n e a rm o d e l i n ga n do p t i m i z a t i o nc o n t r o l l i n g p r e s e n t l yt h er e s e a r c h e sa b o u ts v m f o rr e g r e s s i o n ( s v r ) a r ea l m o s tb a s e do n s i n g l e o u t p u tf u n c t i o n s t h em u l t i d i m e n s i o n a lr e g r e s s i o ne s t i m a t i o np r o b l e ma r i s e s w h e nt h ed e p e n d e n tv a r i a b l ei sav e c t o ri n s t e a do fas c a l a rq u a n t i t y t h i sp r o b l e m a p p e a r si nm a n yp r a c t i c a ls i t u a t i o n si nw h i c ht h eo u t p u tv a r i a b l e sa r ec o u p l e d ，t h e r e s u l t so ft r a d i t i o n a ls o l u t i o n so ft h i sp r o b l e m s u c ha sm u l t i v a r i a t es t a t i s t i c a l a n a l y s i sa n dn e u r a ln e t w o r k ，a r en o tg o o df o rt h e i rs t e r nr e s t r i c t i o n i ti su n f e a s i b l e t h a tw ed i v i d e dt h em u l t i - d i m e n s i o n a lr e g r e s s i o ni n t ok1d p r o b l e m sw h i l ew eh a v e n ow a yt or a i s et h et r a i n i n gs p e e dn o w i na d d i t i o nt h em e t h o dh a si t st h e o r e t i c l i m i t a t i o n i nt h i sp a p e rw ep r o p o s ean e wa p p r o a c hf o rs v mm u l t i d i m e n s i o n a lr e g r e s s i o n i nw h i c hah y p e r s p h e r i c a li n s e n s i t i v ef u n c t i o ni sd e f i n e da r o u n dt h ee s t i m a t e i n s t e a do ft h eh y p e r c u b i c a li n s e n s i t i v ef u n c t i o n a n dw eu s ea ni t e r a t i v ep r o c e d u r e t oo b t a i nt h ed e s i r e ds o l u t i o nw h i l et h er e g u l a rs v ra c h i e v e si tb ys o l v i n ga q u a d r a t i cp r o g r a m m i n g d u r i n gt h eo p e r a t i o np r o c e s sw e c a ng e ts v ( s u p p o r tv e c t o r ) d i r e c t l ya n dn o th a v et of i n dt h es p a r s em a t r i x s o m ee x p e r i m e n t so nd i f f e r e n td a t a s e t sa r ei m p l e m e n t e dt oi l l u s t r a t et h es u p e r i o r i t yo ft h en e wa p p r o a c h ( m u l t i - s v r ) w ec o m p a r e dt ot h er e s u l t sb e t w e e nm s v ra n dt h em e t h o dt h a td i v i d i n gk d i m e n s i o ni n t ok1dw h i c hw ec a l la ss - s v r ( s i n g l e s v r ) f r o mt h er e s u l t sw ec a n c o n c l u d et h a to u rn e wa l g o r i t h mm s v rc a ng e tn o to n l yh i g h e rw h o l ep r e c i s i o na n d t h ec a p a b i l i t yo fa n t i - n o i s eb u ta l s om u c hf a s t e rs p e e dt h a ns - s v rw h i c hi sc a r r i e d o u tb ys m oa n dl s s v m k e y w o r d sm u l t i o u t p u t ；f u n c t i o nr e g r e s s i o n a n de s t i m a t i o n ；s u p p o r tv e c t o r m a c h i n e ：s v r i i 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进 行研究所取得的研究成果。除了文中特别加以标注引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方 式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：日期：年 月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权华南理工大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 日期： 日期： 年月日 年月日 第一章绪论 1 1 研究背景 第一章绪论 让机器具有像人类一样的思维能力是人类一直以来的梦想。计算机的诞生和 发展使得实现这种梦想成为了可能，特别是人工智能技术的发现，标志着人们又 向思维机器的研究方向迈进了一大步。 人工智能自1 9 5 6 年问世以来已经取得了引人瞩目的成就，形成了专家系统、 机器学习、智能决策支持系统、人工神经网络等诸多研究和应用领域。其中基于 数据的机器学习是现代智能技术中的重要方面，它主要是研究从观测数据( 训练 样本) 出发寻找统计规律，利用这些规律对未来数据或无法观测的数据进行预测。 模式识别、函数拟合以及概率密度估计等问题都属于这类问题。事实上这些问题 也是统计推断的研究范畴，在统计学研究中称为预知性学习问题，即根据观测数 据推断一个未知系统的输入一输出依赖关系【l 2 3 】。这个问题有极大的理论意义和 实践意义，但由于系统的未知性和观测数据的有限性，因此它也是一个十分困难 的问题。 统计方法是人们在面对数据而又缺乏理论模型时最基本的( 同时也是唯一 的) 分析处理手段1 4 1 。而解决这些问题的现有方法的重要理论基础之一是传统的 统计学，其研究的基础是样本数目趋于无穷大时的渐进理论【5 】。统计学中关于估 计的一致性、无偏性、方差的界以及关于分类的错误率等诸多理论，都依赖于这 种渐进特性，所提出的各种方法只有在样本数为无穷大时其性能才有理论上的保 证。现有的学习方法，如贝叶斯决策理论、人工神经网络等也是基于此假设。可 是，在实际问题中，样本数目往往是有限的，因此人们以样本数目无穷多为假设 来推导的各种算法，有时在实际应用中效果往往不好，如神经网络方法出现的“过 学习”与“欠学习”问题等，当问题处在高维空间时尤其如此，这也是许多传统 方法所面临的困难。因此许多理论上很优秀的学习方法在实际中表现却可能不尽 如人意。这实际上是现有机器学习理论和方法中的一个根本问题。因此能够专门 用于小样本统计分析的统计学习理论日益受到重视。v a p n i k 等人从2 0 世纪6 0 年 代开始就致力于有限样本统计理论的研究，并将其称为统计学习理论( s l t ， s t a t i s t i c a ll e a r n i n g t h e o r y ) 6 1 。到9 0 年代中期，这一理论己经逐步发展成形， 开始受到越来越广泛的关注，它为研究有限样本下的统计模式识别与更广泛的机 器学习问题建立了一个较好的理论框架。支持向量机( s v m ) 方法就是在统计 学习理论的基础上发展起来的一种通用学习方法，它从最优分类面的思想出发， 华南理工大学硕士学位论文 基于结构风险最小化( s r m ) 归纳原则和v c 维理论，根据有限的样本信息在模 型的复杂性( 即对特定训练样本的学习精度) 和学习能力( 即无错误地识别任意 样本的能力) 之间寻求最佳折衷，以期获得最好的推广能力【6 1 。支持向量机在解 决小样本机器学习问题中表现出许多特有的优势，开始成为克服“维数灾难”和 “过学习”等传统困难豹有力手段。 1 2 支持向量机理论的研究内容 作为一种针对分类和回归问题的新型机器学习方法，支持向量机以其出色的 学习性能，成为机器学习界的研究热点。自从v a p n i k1 9 9 5 年首次提出s v m 算 法以来，关于支持向量机的理论研究和应用研究便开始受到关注，到目前为止已 经出现了很多有意义的成果，并在很多领域得到了成功的应用，包括模式识别、 阿归估计、概率密度函数估计等。但是支持向量机理论的发展历史毕竟时间不长， 还有很多关于s v m 和v c 的理论和应用问题亟待研究。一方面，这种基于统计 学习原理的理论思路对新的学习算法的提出很有启发，另一方面，由于s v m 出 现不久，其理论依据和算法是尚有大量问题有待于发展和完善。以下几个问题是 近几年来支持向量机算法研究的热点： ( 1 )把v c 理论和结构风险最小原理等理论框架进一步推广，产生新的学 习算法或改进算法。 ( 2 )完善s v m 方法。支持向量( s v ) 的确定可转化为约束的优化问题， 但当训练集的规模很大时，传统的优化方法难以满足实时性要求，如 何设计快速有效算法是s v m 中的重要问题之一。 ( 3 ) 基于s v m 算法的多类别分类方法。 ( 4 )对非线性分类问题，s v m 的核方法仍有待进一步研究。 ( 5 )在s v m 的应用研究方面，由于s v m 算法是对神经网络学习算法、最 小二乘法的改良，尚需要大量应用到实际问题中去，如建模、参数辨 识和自适应控制等问题，并将它与己有的处理结果进行比较和分析， 以便进一步深入研究。 可见，目前对支持向量机理论进行研究的主要内容在统计学习理论基础的研 究、各种改进的支持向量机新算法、针对大型问题的有效算法、提高在各种应用 领域的推广能力的模型选择方法以及多类别分类方法等方面。 1 3 支持向量机训练算法的研究 支持向量机算法出现不久，其成功的应用立即吸引了国际上众多的知名学者 2 第一章绪论 对它进行了广泛的研究，在理论研究和算法实现方面都取得了很大的进展。近几 年许多关于s v m 方法的研究，包括算法本身的改进和算法的实际应用，都陆续 提了出来，出现了许多发展和改进的支持向量机算法和有关非线性s v m 中核的 研究方法。 1 3 1 各种支持向量机方法简介 人们通过增加函数项、变量或修改系数等方法使标准的支持向量机中的最优 化问题变形，产生出能解决某一类问题或在某方面有优势的算法。另一方面，最 初支持向量机是用于解决分类问题的，后来推广到回归问题，多类问题等，针对 不同问题产生了各种变形算法。这里分别加以介绍。 1 分类问题 ( 1 ) c 一支持向量分类机系列方法 为了区别，将v a p n i k 在1 9 9 5 年最早提出的标准的支持向量机方法称为 c s v c ( s v mf o rc l a s s i f i c a t i o n ) 方法。这一方法是基于支持向量机的基本思想建 立的。由于最优化问题有一个参数c ，称为c s v c 算法。标准的c s v c 算法需 要求解一个凸二次规划问题。为了提高收敛速度和扩展推广能力，文献【7 和 8 】 中采用了改变原始最优化问题中的松弛变量形式的方法，文献【9 】和【1 0 目j j 修改了 原始问题的目标函数，将其对偶问题转化为边界约束问题。 如果问题的规模太大，需要建立专门的算法。由于线性规划问题的研究已十 分成熟，并有了十分有效的求解大型问题的算法，所有人们也建立了线性规划形 式的支持向量分类方法j 。 ( 2 ) 矿一支持向量分类机系列方法 c s v c 方法首先需要选取合适的参数c ，但在实际应用中有时很难做到。 s c h 6 1 k o p f 在 1 2 】中提出了y 支持向量分类机( y s v c ) 方法，用参数v 代替c ， 这里r 【0 , 1 】，而且v 是有明确含义的，易于选择。文献【1 3 中，详细地讨论了 ，一s v c 和c s v c 两种算法之间地关系。这两类算法是目前常用的算法。 ( 3 ) 加权支持向量分类机方法 在标准的支持向量分类算法中，不能够区别每个样本点的重要性。在实际应 用中，为了弥补这一缺陷，文献 】4 引入了加权支持向量机。对每个点或不同类 的点加上不同的系数，以示区别。【15 提出了模糊支持向量机方法，为每个样本 点都赋予一个模糊隶属度。在此基础上，【1 6 】，【1 7 对不确定的分类问题，提出 不确定支持向量机算法，对模糊支持向量机方法作了推广。 ( 4 ) 广义支持向量分类机 华南理工大学硕士学位论文 在标准的支持向量机方法中，要求核函数必须是正定核，m a n g a s a r i a n 提出 了广义支持向量机方法( g s v m ) f i 引，可以处理核函数非j 下定的情况。此外， m a n g a s a r i a n 还提出恶劣光滑支持向量机方法【l ”，将凸二次规划问题转化成无约 束问题，引入无约束问题的算法来求解。 2 回归问题 文献 2 0 】首次将支持向量机方法应用于回归问题，提出占s v r ( s v mf o r r e g r e s s i o n ) ，它也需要求解一个二次规划问题。在一s v r 算法中，需要事先给 定参数占的值，在实际应用中，有时很难选择合适的s ，因此，【1 2 】提出能够自 动计算占的v s v r 。 1 3 给出了s s v r 和y s v r 算法的关系。 和分类问题类似，支持向量回归机也有线性规划的形式。【2 1 】给出采用不同 损失函数的支持向量回归机算法。 3 多类问题 支持向量机方法虽然是针对两类问题提出的，但如何将两类分类方法推广到 多类问题的分类也是支持向量机理论研究的重要内容之一。目前，将支持向量机 的思想应用于解决多类问题的方法，主要有一对一，一对多以及确定多目标函数 的方法等，见文献【2 2 ， 2 3 】，【2 4 ， 2 5 。 1 3 2 解决大型问题的算法 支持向量机方法需要求解凸二次规划问题。传统的优化方法( 如内点法等) 可以直接用来求解。m a n g a s a n r i a n 在 1 9 中将支持向量机中的凸二次规划问题转 化为无约束问题，因此求解无约束问题的方法也可以作为支持向量机的算法。牛 顿( n e w t o n ) 法是求解无约束问题的基本算法，基于不精确n e w t o n 法的思想， 有许多改进n e w t o n 法的方案，特别是用共轭梯度法和条件预优共轭梯度法求解 n e w t o n 方程的算法，如文献 2 6 、【2 7 1 ，虽然其中很多算法在实际应用中十分有 效，但对其有效性缺乏理论上的证明。对此，文献【2 8 】、【2 9 】从理论上严格证明 了使用条件预优共轭梯度的n e w t o n ( n e w t o n p c g ) 法比n e w t o n 法更有效，并 对其有效性给出数量上的估计。 目前，专门针对支持向量机中的优化问题，还提出了一些有效的算法。支持 向量机中的最优化问题是一类特殊的问题，具有一些非常好的特性，例如解的稀 疏性和最优化问题的凸性等，这些性质使得构造使用较少存储的快速专用算法成 为可能。专用算法的一个共同特定是：将大规模的原问题分解成若干小规模的子 问题，按照某种迭代策略，反复求解子问题，构造出原问题的近似解，并使该近 似解逐渐收敛到原问题的最优解。事实上，由于子问题的选取和迭代策略的不同， 4 第一章绪论 可以有不同的算法。例如：选块算法( c h u n k i n g ) 、分解算法( d e c o m p o s i n g ) 和 序列最小化算法( s m o ，s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 等。 选块算法的思想最早是在1 9 9 5 年，由c o r t e s 和v a p n i k 【3 0 】提出的。由支持向 量机方法得到的决策函数只与支持向量有关，与其他样本点无关，即如果只取支 持向量作训练样本，得到的决策函数与原有的所有训练点作训练样本得到的决策 函数是一致的，对于大量样本数据的问题，往往支持向量不多。基于这种思想， 选块法将大规模的训练集分成若干小规模的i ) i i 练子集，按顺序逐个对各个子集进 行线性处理。在对每个子集线性处理时，只需根据上个子集得到的支持向量以及 当前的子集进行计算。后来提出的增量线性方法( i n c r e m e n t a ll e a r n i n g ) 3 1 , 3 2 ， 本质上就是选块算法。 o s u n a l 9 9 7 年提出了分解算法i ”1 。后来j o a c h i m s ”1 改进了它。分解算法将 一个二次规划问题的求解转化为求解一系列规模较小的二次规划问题。这些小规 模的二次规划问题只涉及到训练集中的一部分样本点。分解算法的关键在于选择 一种适当的对样本点的换入换出策略。j o a c h i m s 提出的一些启发式的迭代策略有 助于提高算法的收敛速度。他在此基础上建立了一个求解大型支持向量机中优化 问题的算法，称为s v m h s 6 , 。其基本思想是：如果存在不满足k k t 条件的样本点， 则以某种方式选择一个由口个样本点组成的工作集。在这个工作集上求解二次规 划问题，而与其他样本点相应的信息保持不变，重复这一过程直到所有样本都满 足k k t 条件，序列最小化( s m o ) 是p l a t t 于】9 9 8 年提出的1 3 5 ，是在由两个样本 点组成的工作集上用解析法求解二次规划，而不需要采用数值优化算法。k e e r t h i i 和g i l b e r t 证明了s m o 算法的收敛性 3 6 1 。 目前，建立高效的求解支持向量机中的最优化问题算法，是支持向量机理论 的研究中一个很有意义且急需解决的问题。 1 4 支持向量机的应用研究 尽管s v m 方法在理论研究上有很大的进展，但同理论研究相比，它的应用 研究相对落后，目前只有有限的试验研究报道，且大多属于仿真试验和对比试验。 因此s v m 的应用研究是很有前途的研究方面。目前大多数s v m 的应用研究集 中于模式识别领域，主要有人脸检测、手写数字识别、语音识别、图像分析和文 本分类等方面。 s v m 的一个突出的应用研究成果是由贝尔实验室对美国邮政手写数字库进 行识别分类的试验1 7j ，这个试验充分说明了s v m 较之传统的方法具有明显的优 势。在贝尔实验室的初次尝试后，c h e nd a t o n g ”1 、b a s u 3 引、h uj u n 3 9 1 等分别 讨论了将s v m 应用于图像和文本识别的问题。b e n n e t t l 4 0 i 提出了在决策树中使用 5 华南理工大学硕士学位论文 s v m 进行决策的方法。y o n g m i n l i 4 们、g o r d a n 4 1 1 、c h a k r a b a r t t y 1 4 2 1 、b l a n z l 4 3 】 p o n t i l l 4 4 i 提出了将s v m 用于图像监测和语音识别系统的方法。m a s o n f 4 ”、 s o u h e i l 4 6 1 、g u t s c h o v e n 4 。7 】贝9 将s v m 应用到数据融合问题上。 随着研究的不断深化，研究者们开始在新的应用领域进行尝试，如在蛋白质 的分类、d n a 分析等生物信息领域48 1 ，以及时间序列分析 4 9 , 5 0 、回归分析 5 1 , 5 2 , 5 3 1 、聚类分析等领域都取得了较好的结果。f l t f f g e s t e l f 5 4 1 、t r a f a l i s l 5 5 1t a y 5 6 j 等将s v m 应用到时间序列分析以及股票价格预估等实例中。d r e z e t 【5 ”、 s u y k e n s 5 ”、b r o w n l 5 9 1 将s v m 应用于线性和非线性系统辨识中。o r e t t o n 5 9 1 将s v m 应用于机器人手臂建模。 此外，m i t ，b e l ll a b 核微软研究所等已成功地将s v m 算法应用于动态图像 的人脸跟踪、信号处理、语音识别、图像分类和控制系统等诸多领域 8 , 2 0 , 3 0 , 5 4 1 。 虽然s v m 的应用研究也取得了一些成果，但上述的应用主要是面对模式识 别和分类的，非线性函数回归估计的应用成果不多，时间序列分析，回归，聚类 等方面的研究，还有待进一步的完善。另外，在实际应用中，出现的算法参数选 择，特征选择问题等，也需要进一步的研究。 综合上述的关于s v m 应用研究的工作，可以看出，虽然s v m 在模式识别 领域，已经有不少成功的尝试，但s v m 在工程中的应用还只是刚刚开始。如何 使这一理论在实践中发挥效用，是一个具有重大意义的课题。 1 5 支持向量机研究的局限性和难题 s v m 训练算法虽然已经取得了很多有意义的成果，对s v m 的实用也起到了 很大地推动作用，但仍然存在一些局限性和难题，如： ( 1 ) 最大的局限性就在于核函数的选择。由于在核确定之后，用户只能对其 参数c 进行调整。因此，核的选择对于s v m 的性能非常重要。目前已 有一些研究者对利用先验知识限制核的选择进行了研究，但如何针对特 定问题选择最佳的核仍是一个难以解决的问题。 ( 2 ) 训练s v m 的绝大部分算法都是针对分类问题，只有少部分算法考虑了 回归函数的估计问题。即便是考虑了回归函数估计问题的s m o 算法也 只能应用于静态问题的处理。 ( 3 ) 上面讲述的基于分解的c h u n k i n g 算法和s m o 算法在训练样本的支持向 量很多时，对计算机的内存依然时。个严峻的考验。 ( 4 ) 寻求多类问题的s v m 算法同样只考虑了分类问题，没有考虑到函数估 计问题。 ( 5 ) 目前应用到回归函数估计问题的s v m 都只是一个多输入单输出系统， 6 第一章绪论 虽然可以构造多个s v m 组成多输出系统，但在目前还没有很好地解决 s v m 训练速度问题的情况下，这样的做法在训练上是不现实的。 随着支持向量机在若干实际问题中的成功应用，统计学习理论正日益受到国 际主流学术界的重视，认为它有可能成为将包括神经网络在内的预知性学习方法 统一在一个理论框架内的理论基础。从理论上来说，支持向量机能够克服神经网 络的一些固有问题，获得较好的泛化能力。但目前对它的研究还存在着一些难点， 随着这些难点的解决，相信s v m 将会有更好的应用前景。 1 6 本文的研究和组织 s v m 目前的应用领域主要集中于模式识别领域，因此，训练s v m 的绝大部 分算法都是针对分类问题，只有少部分算法考虑了回归函数的估计问题。而目前 对回归问题的研究也仅仅是在单输出函数的基础上进行的，对多输出函数回归估 计的讨论很少。然而现实生活和生产中，人们又希望能够同时对多个变量或指标 进行估计，因此，对多输出函数回归估计算法的研究和探讨是很必要的。 本文的研究内容主要就是针对目前s v m 回归算法仅对单输出函数有效的问 题，讨论了实现多输出函数回归的s v m 算法。首先，指出了对输出的每一个分 量都构造一个s v m 的方法( s - s v r ) 存在一定的缺陷，主要原因是损失函数设 计不合理、忽略了输出各分量之间的相关性等。针对这些问题，我们提出了改进 的损失函数，在此基础上设计了实现多输出函数回归估计的m s v m 方法，给出 了数值仿真结果，并将其与s - s v r 进行了比较。 本文的主要内容如下： 第一章，简要介绍了支持向量机的研究背景、研究内容和研究现状，并对目 前支持向量机研究的局限性和难题进行了总结。 第二章，对统计学习理论进行了回顾，概述了统计学习理论研究的基本问题 及主要内容。为了更好地说明统计学习理论在实际中的实现问题，简单介绍了 s v m 的基本概念和基本理论。在总结了支持向量机的特点之后，将它与人工神 经网络进行了简要的比较。 第三章，主要介绍了s v m 的回归算法( s v r ) 的基本模型和原理，并分别 用理论数据和实际数据的仿真结果对其性能进行了说明。 第四章，着重介绍了s v m 算法中的s m o 算法和l s s v m 算法，详细阐述 了两种算法的求解原理和步骤，给出了它们应用于函数回归的表达式，并分析了 它们各自的局限性。 第五章，详细介绍了提出的多输出系统s v m 回归算法( m s v r ) 。我们采 用了定义在超球上的二次损失函数，考虑的是输出各分量的整体误差而不是分开 7 华南理工大学硕十学位论文 考虑每一维的误差，目标函数的设计是使整体误差最小。另外，我们还改进了求 解算法，用求解线性方程组的形式代替求解二次规划问题，并实现了边求解边使 矩阵降阶，达到同时找到支持向量的目的。通过数据仿真试验表明：本文提出的 多输出函数回归算法( m s v r ) 在训练时间和精度以及抗噪性能上均优于单独 对各分量进行回归的方法( s - s v r ) 。 8 第一章统计学习理论和支持向虽机 第二章统计学习理论和支持向量机 s v m 的理论基础是v a p n i k 等人提出的统计学习理论( s l t ) ，它是建立在一 套较坚实的理论基础上的，为解决有限样本学习问题提供了一个统一的框架，它 能将很多现有方法纳入其中，有望解决许多原来难以解决的问题( 如神经网络结 构选择问题、局部极小点问题等) 【5 l 。 v a p n i k 等人早在六、七十年代就开始致力于小样本情况下机器学习理论的研 究，因此发展成为统计学习理论，并在此基础上于1 9 9 5 年提出了s v m 理论。统 计学习理论指出经验风险最小并不能保证期望风险最小；提出了结构风险最小化 原理( s r m ) ：给出了核心概念v c 维。支持向量机是统计学习理论中最新的内容 也是最实用的部分。正因为支持向量机的提出，才促进了统计学习理论的推广与 发展【7 ，55 1 。 2 1 统计学习理论的发展概述 2 1 1 统计学习理论的发展历史 学习问题的研究历史可以分为4 个阶段1 7 1 ：一、第一个学习机器的创立；二、 学习理论的基础创立；三、神经网络的创立；四、神经网络替代方法的创立。 r o s e n b l a t t 在1 9 6 2 年提出了第一个学习机器的模型，称作感知器，这标志着 人们对学习机器进行数学研究的真正开始。接着，n o v i k o 盱1 9 6 2 年证明了学 习机器具有推广能力的原因跟最小化训练集上的错误分类数有一定联系。这导致 了对学习过程的研究分化为两个分支：学习过程的应用分支和学习过程的理论分 析分支。应用分支认为，要得到好的推广性的学习机器只要选择能使训练误差最 小的学习器就可以了。而理论分析分支认为，最小化训练误差的原则是需要证明 的。学习过程的理论分析的主要目的就是找到能够达到最好推广能力的归纳原 则，并构造算法实现这一原则，这种想法可视为统计学习理论的起源。接着 t i k h o n o v f 56 1 、i v a n o v 5 7 】和p h i l l i p s 5 8 1 发现了能够解决不适定问题的正则化原则， 这种思想及其正则化技术在统计学引发了深远的影响。在2 0 世纪6 0 年代， r o s e n b l a t t 59 1 、p a r z e n 60 1 、c h e n t s o v 6 1 】提出了几种此类算法。而v a p n i k 和s t e f a n y u k 发现了创建此类算法的一般方法，从而一举奠定了非参数统计学的基础。 s o l o m o n o f f l 6 ”、k o l m o g o r o v 6 3 1 和c h a i t i n 6 4 i 在6 0 年代，提出了算法复杂度的思 想，这种思想可被视为信息论和统计学中最伟大的思想之一，开创了推理问题的 9 华南理工大学硕士学位论文 信息论方法。同时在这一思想的基础上，r i s s a n e n t ”i 提出了对于学习问题的最小 描述长度( m d l ，m i n i m a ld e s c r i p t i o nl e n g t h ) 的归纳原则。另外，早在1 9 6 8 年， v a p n i k 和c h e r v o n e n k i s 便针对于指示函数集，提出了v c 熵和v c 维的概念，这是 统计学习理论的核心理念。利用这些概念，泛函空间的大数定理被发现，v a p n i k 等人也研究了这一定理与学习过程的联系，并得到了关于收敛速度的非渐进界的 主要结论。在1 9 7 1 年，v a p n i k 和c h e r v o n e n k i s 发表了这些工作的完全证明。所得 到的这些界使得他们在19 7 4 年提出了结构风险最小化归纳原则，从而完成了模 式识别学习理论。 在1 9 8 6 年，由l e c u n 、r u n e l h a r t 、h i n t o n 和w i l l i a m s 分别独立地提出了同 时构造感知器所有神经元的向量系数的反向传播算法，也常称为b p ( b a c k p r o p a g a t i o n ) 算法。反向传播技术的发现可以视为神经网络的第二次诞生，但是 在此后的10 年的神经网络研究中，并没有从本质上推进对学习过程本质的认识。 近几年，对神经网络替代方法的研究吸引了人们更多的注意力，尤其是关于 结构风险最小化原则和最小描述长度原则成为分折研究的热点之一。跟传统的统 计分析中的渐进理论形成相比，关于小样本数理论的讨论研究广泛地开展起来。 2 1 2 统计学习理论的基本问题 1 学习问题的表示 按照人工智能大师西蒙的观点，学习就是系统在不断重复的工作中对本身能 力的增强或改进，使得系统在执行下一次相同任务或相类似的任务时，会比现在 做得更好或效率更高。那么什么叫做机器学习呢? 至今仍没有统一的定义。有些 人称，机器学习是研究如何使用机器来模拟人类学习活动的一门学科。更严格的 提法是：机器学习是门研究机器获取新知识和新技能，并识别现有知识的学问 6 6 1 。 机器学习问题的基本模型可以用图2 1 来表示。其中系统是所要研究与分析 的对象，其在一定的输入xf 得到一定的输出y ，学习机是得到的规律的总和表示， 预测输出为多。机器学习的目的便是由给定的训练样本求取对系统输入输出之间 依赖关系的估计，使学习机可以对未知的输入做出准确的预测 5 1 。 这样上述机器学习问题可以表述为：已知变量y 与输入x 之间存在一定的未 知依赖关系，即存在一个未知的联合概率，y ) ，机器学习就是根据，个独立同 分布观测样本( 工，y 1 ) ，( x 2 ，y ：) ，( x ，y ，) ，在一个函数集合 f ( x ，口) ) ( 口a ，a 是 参数集合) 中，找到一个最优的函数f ( x ，口。) ，使预测的期望风险： r ( a ) = i l ( y ，f ( x ，a ) ) d f ( x ，y )( 2 一1 ) 1 0 笫二章统计学习理论和支持向量机 最小。其中l ( y ，f ( x ，口) ) 为由于采用f ( x ，口) 对y 进行预测而造成的损失。对于不 同类型的学习问题，可以引入不同形式的损失函数，这样便提出了以下三种典型 的机器学习问题。 图2 1 机器学习的基本模型 f i g 2 1b a s i cm o d e lo fm a c h i n el e a r n i n g 2 三种主要的学习问题 上述的学习问题是一般性的表述，利用不同的损失函数形式，可以得到如下 的三类基本问题：模式识别、回归函数估计和概率密度估计”。 对于模式识别问题，系统输出的是类别标号。这里仅讨论二分类问题，在这 种情况下y = ( o ，1 或y = 一1 ，l 是二值函数，这时的预测函数也称为示性函数 ( i n d i c a t o r f u n c t i o n s ) 或判别函数。采用的损失函数可以是以下形式： 坳以删= 苷篆嬲( 2 - 2 ，坳，似) 卜1 1 孑；歹i i 这时，由式( 2 一1 ) 计算的期望风险就是分类误差的概率。因此当概率分布f ( x ，y ) 未知时，对于训练样本的模式识别问题便是寻找一个能够最小化分类误差的函 数。 对于回归函数估计问题，这时y 是一个连续变量( 这里仅讨论单值函数的问 题) ，它是输入工的函数。而f ( x ，口) ，a a 是包含回归函数 f ( x ，口o ) = l y d f ( x ，_ y )( 2 - 3 ) 的实值函数集合。如果f ( x ，o r ) l ：，那么定义损失函数 l ( y ，f ( x ，“) ) = ( y f ( x ，盯) ) 2 ( 2 4 ) 当概率分布f ，y ) 未知时，回归函数估计问题就是最小化式( 2 - 1 ) 中风险函数的 问题。 对于概率密度估计问题，学习的目的根据训练样本确定工的概率分布。记待 估计的密度函数为p ( x ，口) ，则损失函数可以定义为 华南理工大学硕士学位论文 l ( p ( x ，口) ) = 一l o g p ( x ，口)( 2 5 ) 3 经验风险最小化原则 由于未知概率密度分布f ( x ，y ) ，因此要最小化风险函数( 2 1 ) 的话，只能依 靠训练样本集提供的信息。但是这样的做法，便无法直接计算和最小化( 2 1 ) 式定 义的期望风险。而传统的学习方法采用的是所谓的经验风险最小化( e r m ) 原 则，即用样本集来定义经验风险 1 上 r 。( c e ) = ( y ，f ( x ，口) ) ( 2 _ 6 ) 1 = 1 来逼近式( 2 1 ) 定义的期望风险。对于分类问题的损失函数( 2 2 ) ，经验风险就是 训练样本的错误分类率；对于回归估计问题的损失函数( 2 4 ) ，经验风险最小化准 则就是最小二乘方法；针对密度估计问题中采用的损失函数( 2 5 ) ，经验风险最小 化原则便是等价于极大似然估计方法。 但是从期望风险最小化原则到经验风险最小化原则并没有可靠的理论依据， 只是直观上的想当然做法。于是便存在一个学习过程一致性问题 7 1 ： 首先，r e r a p ( c g ) 和r ( a ) 都是口的函数，概率论中的大数定理只是说明，当样 本趋于无穷多时，r 。( a ) 将以一定的概率趋近于r ( a ) ，并没有保证使r e i n p ( o r ) 最 小的口+ 也同样可以使r ( 瑾) 达到最小值。 其次，即使有办法使上述条件在样本趋于无穷的时候得到保证，也无法认定 在这些前提下得到的经验风险最小化方法在样本数目有限时仍能得到类似好的 结果。 然而，长期以来用经验风险最小化替代期望风险最小化来解决学习问题的思 想几乎统治了这一领域的所有研究。 4 复杂性与泛化能力 在早期的神经网络研究中，人们总是将注意力集中于如何使月一缸) 更小， 但是很快人们就发现，训练误差小的学习机器并不总能取得好的预测效果。人们 将学习机器对未来输出进行正确预测的能力称为泛化能力( g e n e r a l i t ya b i l i t y ) ， 或称为推广性。相反，在某些情况下，过小的训练误差反而导致泛化能力大幅下 降，这就是在训练神经网络过程中经常会碰到的过学习( o v e r f i t t i n