（应用数学专业论文）支持向量回归的算法分析.pdf

中文摘要 摘要 支持向量机是数据挖掘中的新方法它是建立在统计学习理论基础之上的通 用学习方法，并且已表现出很多优于已有方法的性能，目前在理论研究和实际应 用两方面支持向量机正处于飞速发展的阶段 支持向量机主要用于处理分类问题和回归问题，分别称为支持向量分 类( s v c ) 和支持向量回归( s v r ) 本文主要研究了支持向量回归的算法与误差估 计。并得到了较为满意的结果内容安排如下： 第一部分，阐述了回归问题的研究背景及现状，介绍了支持向量回归的基本 思想 第二部分，较为系统地介绍了支持向量回归的几个主要模型，详细讨论了它 们的性质以及相互关系 第三部分，通过改进一个广义支持向量回归模型的目标函数，得到了一个广 义支持向量回归新模型，该模型与广义支持向量回归模型相似，也含有一个可灵 活选取的函数，并且该广义模型不要求核函数具有正定性；简要介绍了把支持向 量回归中的原始凸二次规划问题转化为光滑的无约束问题 第四部分，研究了支持向量回归的误差问题特别的，利用采样算子理论和积 分算子理论，研究了非标准情形支持向量回归的误差分析 最后，在第五部分中，分析了前面得到的主要结果，并对未来进一步的研究方 向进行了展望 关键词：支持向量回归：核函数；采样算子；积分算子 湖北大学硕士学位论文 a b s 仃a c t s u p p o r tv e c t o rm a c h i n e s ( s v m s ) a r en e w d a t am i n i n gm e t h o d s d e v e l o p e di n 一 c e n ty e a r sb a s e do i ls t a t i s t i c a ll e a r n i n gt h e o r y , a n dt h e yh a v eb e e np r o v e nt ob em o f e p o w e r f u la n dr o b u s tt h a ne x i s t i n gm e t h o d si nm o s ta s p e 6 - ：t s t h e r ea r em a i n l yt w of o c u s e so fs v m si n c l u d i n gs u p p o r tv e c t o rc l a s s i f i c a t i o n ( s v c ) a n ds u p p o r tv e c t o rr e g r e s s i o n ( s v r ) t h i sp a p e rf o c u s e s0 1 1s v ri ns e v e r a l a s p c c l g ，i n c l u d i n ga l g o r i t h ma n d e 1 1 o ra n a l y s i s ( 1 ) an e wg e n e r a l i z e dm o d e lo fs v r i sp r o p o s e d ，a c c o r d i n gt or e v i s i n gt h eo b j e t f u n c t i o ni nt h eo p t i m i z a t i o np r o b l e m t h en e wg e n e r a l i z e dm o d e lo fs v rw i l ld e r i v e s o m ek i n d so f e x i s t i n ga l g o r i t h mo fs v l lt h em o d e li sm o r ee f f e c t i v ei nt h es e l e c t i o n o f t h ek e m e lf u n c t i o n ( 2 ) o u ra p p r o a c hd e v e l o p st h ee r r o ra n a l y s i so fs v l ls p c c i a l l y w i t ht h e o r yo f s a m p f i n go p e r a t o ra n di n t e g r a lo p e r a t o r , w eg i v et h ee r r o ra n a l y s i so fs u p p o r tv e c t o r r e g r e s s i o np r o b l e mi nn o n s t a n d a r ds i m a t i o m k e yw o r d s ： s u p p o r tv e c t o rr e g r e s s i o n ； i n t e g r a lo p e r a t o r 一 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 论文作者签名：甲卜呻 签名日期：加7 年f 月，日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： o 按照学校要求提交学位论文的印刷本和电子版本：学校有权保存并向国家 有关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学 校可以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢 利为目的的前提下，学校可以公开学位论文的部分或全部内容。( 保密论文在 解密后遵守此规定) 论文作者签名：髓磅 签名日期：刎铽月f 日 导师躲彩隧 签名日期：砂7 年蝴圬日 第一章 引言 第一章引言 1 1 支持向量回归的研究背景 广义上讲，学习问题研究的是如何从先验的不完整信息中构建模型来尽可能 精确地描述某种未知的依赖关系使之能较好地对未知数据进行预测或对其性质 进行判断【1 2 一从统计学角度来看，学习问题可以形式化地表述为：已知变量与 输入向量z j p 之间存在未知依赖关系，即服从某种未知但确定的联合概率分 布f ( z ，! ，) ，如何依据1 个独立同分布( i i d ) 观测样本 扛1 ，y 1 ) ，( z 2 ，抛) ，0 l ，鼽) ，( 1 1 1 ) 从给定的函数集 ，( z ，a ) ，q6 - a ) 中选取使预测期望风险泛函 脚) = 地，m ，a ) 舻( 刎) ( 1 1 2 ) 最小化的最优函数f ( x ，q ) 来作为对未知依赖关系的近似? 其中， ，( z ，口) ，o a 称为指示函数集，n a 为广义参数；最优函数，( z ，o ) 称为学习机器，学习函数 或学习模型；l ( y ，f ( x ，q ) ) 称为损失函数，即当使用，( z ，口) 对笋进行预测时造成的 损失 v a p n l k 在【1 冲提出学习问题的研究历史可以分为四个阶段，i i p r o s e n b l a t t 的 感知器阶段( 2 0 世纪6 0 年代) ，学习理论基础的创立阶段( 2 0 世纪6 0 到7 0 年代) ，神经 网络阶段( 2 0 世纪8 0 年代) ，神经网络的替代方法的创立阶段( 2 0 世纪9 0 年代) 1 1 4 1 1 1 1 回归问题的描述及难点 学习问题主要包括三类：模式识别( 分类问题) ，回归函数估计( 回归问题) 和概 率密度估计 在函数回归估计问题中，可是连续变量，损失函数定义为 l ( y ，f ( x ，口) ) = 0 一，( z ，口) ) 2( 1 1 3 ) 湖北大学硕士学位论文 在该损失函数下，使( 1 1 2 ) 式最小的函数为 m ) = 舻( 出) 其中f ( 可l z ) 为条件概率测度，通常称该函数为回归函数这样，回归估计问题就成 了在概率测度未知，但训练样本集己知的情况下。寻找回归函数的逼近问题 解决回归问题的一个直观的想法是：把y = f ( x ，q + ) 限制在一个不太复杂的 函数类中，在这类函数中，寻找尽可能满足 玑= f ( x t ，口) ，i = 1 ，f ( 1 1 4 ) 的，( z ，o f f ) 实际上经常使用的线性回归方法，就是限定，( z ) 为线性函数，扛) = 凹+ b ，从中找出尽可能满足式( 1 1 4 ) l j 匀f ( z ) = a * x + b 通常用 ( y i 一，( 承) ) 2 = ( 弘一簖i 一6 ) 2( 1 1 5 ) 来度量y = ，( z ) = 吡+ 6 偏离挑= f ( x t ) 的程度这个量越小，表明满足的程度越 高所以我们要尽可能满足式( 1 1 4 ) 自然考虑用下列最优化问题 的解( n + ，6 i ) 来确定，( z ) = n + z + 6 显然上面的回归问题和求解方法可以推广首先上面限定y = ，( z ) 所 在的线性函数类可以推广为某个实函数的集合f 其次度量y = ，( o ) 偏离 骆= ，妊) 程度的方式并不是唯一的， 上面采用的量( 1 1 5 ) 称为平方损失函数也可以采用其它的损失函数若记 损失函数为l ( y ，( z ，q ) ) ，则优化问题( 1 1 6 ) 变为经验风险的最小化 由此便可得到我们推断的依赖关系y = 广( z ) 2 ( l 1 7 ) 回0 砷 一凹一 鼽 。嘲 毋 z “玑“ ；甜 磐 第一章引言 以上求解回归问题的方法可以总结如下： 首先给定训练集并选定损失函数；其次限定假设f ( ：r ) f l l 成的集合，；再次定 义经验风险 = l ( v i ，m t ，q ) ) ( 1 1 8 ) 在，中找出一个使经验风险达到最小值的函数广( g ) ；最后以，( z ) 作为决策函数 这一途径最本质的困难在于假设集合，的选择对于给定的一般训练集，我 们一方面没有理由一定把，限定为非常狭小的函数类，例如线性函数类；另一方 面也不能把，取得过大做为一个极端的例子，当，是所有实函数的集合时，对于 训练集我们会得到 州2 ： 菇 ( 1 1 9 ) 显然这个决策函数是很不合理的总之，对假设集合，的选择，体现了回归问题的 一个实质性的困难 1 1 2 解决回归问题的传统模式 回归分析是统计学中最重要的学科分支之一它的方法乃至回归这个名称的 起源，统计史上一般把它归功于英国生物学家兼统计学家eg a l t o n ( 1 8 2 2 1 9 1 1 ) 传统理论体系中的回归分析是建立在所谓的度量含有加性噪声的函数的模型基 础上的设某个未知函数有下面的参数化形式 ，o ( z ) = ，0 ，i x 0 ) ( 1 1 1 0 ) 其中q o a 是未知的参数，另外设在任意点黝这个函数都有带有噪声的取值 弘= ，( 翰，o r 0 ) + 6 ( 1 1 1 1 ) 其中噪声6 独立于而且其分布服从一个已知的密度函数p ( f ) 回归的问题就是利 用这些观测到的数据对 ( z 1 ，掣1 ) ，( 丑，挑) ，( 1 1 1 2 ) 从集合，( z ，d ) ，q a 中估计函数，( z ，咖) 一3 湖北大学硕士学位论文 最大似然法是传统体系下的一个归纳引擎。函数估计的所有模型都基于它 在上述模型中，人们利用最大似然法估计参数0 0 方法是最大化泛函 f l ( 口) = l n p ( y _ i ，( 毛，a ) ) ( 1 1 1 3 ) = 1 如果采用具有零均值和某个固定方差的正态分布作为噪声模型就得到最小二乘 法。即最小化泛函 l m ( a ) = ：( 珧一，( 毛，口) ) 2 ( 1 1 1 4 ) i = 1 针对线性关系下的回归方程的最小二乘法是g a u s s 在1 8 0 9 年前后最早提出的，选 择其它形式的噪声模型p ( ) 可以得到参数估计的其它方法，eh u b e r t - 1 9 6 4 年扩 展了传统的回归估计的模型，提出了所谓鲁棒性回归估计模型根据这个模型人 们不需要准确的噪声模型，而是给出一个包含这个函数的密度函数集但是最大 似然方法只能适用于非常有限的密度函数集 在2 0 世纪6 0 年代初，学者们提出了回归估计的一些新方法，称为非参数方法 这些方法是从一个范围较宽的函数集中估计密度，而不限于参数化的函数集 在2 0 世纪7 0 年代，对p a r z e n 类型的非参数密度估计，建立了一套完整的渐近理论 从而得出对于传统的回归估计模型，如果观测数目足够多，用非参数方法替代参 数方法可以得到一个好的逼近1 9 7 8 年v a p n i k 和s t e f a n y u k 发现了一个构造和分 析各种非参数算法的一般性原则，得到两个结论：( 1 ) 一般而言，估计一个密度是 一个不适定的计算问题；( 2 ) 为较好地解决这个问题；须采用正则化技术 回归估计作为学习问题具有学习问题的两个主要要求：一是从一个宽的函 数集合中估计待求的函数，上面讨论的参数和非参数估计正是解决这个要求的方 法第二个要求是在有限数量的观测例子的基础上估计待求的函数用有限数量 信息解决回归估计问题的基本原则是：必须设法去直接寻求待求的函数，而不是 首先估计密度，然后用估计的密度来构造待求的函数为了在未知的联合分布函 数f ( x ，f ) 下最小化风险泛函( 1 1 8 ) 一般采用经验风险最小化( e r m ) 归纳原则最 小二乘法就是这一原则的直接体现在学习理论中，e r m 原则扮演着一个决定性 的角色在2 0 世纪5 0 年代，r o b b i n s 和m o u r o c 提出了另一种一般的归纳原则，即随 机逼近原则吵1 9 7 1 年，学者们创立了两种不同的一般性学习理论：( 1 ) 对随机逼近 归纳推理的一般性渐近学习理论；( 2 ) 对e r m 归纳推理的一般性非渐近模式识别 4 第一章引言 理论，后来这一理论被v a p n i k 推广到任意基于经验数据的风险最小化问题【6 j 但 在某种方式下，随机逼近方法可以解释成为e r m 方法的一种特殊做法与其他原 则相比，e r m 归纳原则能更好地利用经验数据，不依赖先验信息，并且存在很清 晰的实现方法，因此在分析学习过程时，核心问题变成了对e r m 原则的探索 1 2 支持向量回归的基本思想 支持向量机方法是在统计学习理论框架下产生出来的一种新的通用机器学 习方法2 0 世纪6 0 年代v a p i l i l 【等人开始研究有限样本情况下的机器学习问题 7 1 1 9 6 8 年和1 9 7 1 年，v a p n 帅c h e r v o n e n k i s 提出了建立在经验风险最小化原则基础 之上的v c 维理论，建立了基本理论体系一统计学习理论i s v a p n i k 于1 9 8 2 年进一 步提出了具有划时代意义的结构风险最小化( s r m ) 原则，为解决有限样本学习 问题提供了一个统一的框架【6 j 它能将很多现有方法纳入其中。有望帮助解决 许多原来难以解决的问题( 比如神经网络结构选择问题，局部极小点问题等) ； v a p n i 埔c o r t e s 于9 0 年代在此基础上提出了通用的学习算法支持向量机方法【。j 该方法表现出的优良特性及其许多成功的应用，使得学者们开始迅速重视这一学 术方向，并在理论研究和算法实现方面都取得了很大的进展【1 0 1 1 1 支持向量机方法的基本思想可以总结为： ( 1 ) 它是专门针对有限样本情况的学习机器，实现的是结构风险最小化：在 对给定的数据逼近的精度与逼近函数的复杂性之间寻求折衷，以期获得最好的推 广能力： ( 2 ) 它最终解决的是一个凸二次规划问题，从理论上说，得到的将是全局最优 解，解决了在神经网络方法中无法避免的局部极值问题： ( 3 ) 它将实际问题通过非线性变换转换到高维的特征空间，在高维空间中构 造线性决策函数来实现原空间中的非线性决策函数，巧妙地解决了维数灾难问 题，并保证了有较好的推广能力，而且算法复杂度与样本维数无关 目前，s v m 算法在模式识别，回归估计，概率密度函数估计等方面都有应用 例如，在模式识别方面。对于手写数字识别，图像识别，文本分类等问题，s v m 算法 在效率与精度上已经超过传统的学习算法或与之不相上下 从回归问题的数学提法可以看出，为建立算法，需要选择适当的损失函数， s v r 常选择的损失函数为e 不敏感损失函数： 5 一 湖北大学硕士学位论文 其中。令 订( ! ，f ( x ，o ) ) = l ( i ! ，一f ( x ，q ) i 。) 州训。= 他h ，搿舭g 这些损失函数描述了e 不敏感模型：如果预测值与观测值之间的偏差小于e 则损 失等于零 如果，( z ) 为单变量线性函数 ，( z ) = z ) + b ( 1 2 1 ) 当样本点位于两条虚线之间的带子里时，则认为在该点没有损失，我们称两条虚 线构成的带子为e 带【1 ，- 只有当样本点位于e - 带之外时，才有损失出现 争不敏感损失函数有一个特点：对样本点来说，存在着一个不为目标函数提 供任何损失值的区域。即e 带这个特点是其它许多损失函数( 例如平方损失函 数) 并不具备的可以期望，在e 一带内的样本点，不会出现在决策函数中 假设我们己知观测数据 0 1 ，讥) ，( 现，y i ) 下面简单说明支持向量回归的基本思想我们利用上述e 不敏感损失函数，并限 定在线性函数集合 f ( x ) = z ) + b ( 1 2 2 ) 其中。u z 表示u 尉与。剜的内积，b r 基于结构风险最小化原则，就得到 了对回归的线性支持向量机算法它要解决一个原始最优化问题， 曲扣n c 妻( g 倒 s t 弘一( ( u 霸) + b ) e + & ， ( ( u 戤) + b ) 一玑s + ， 6 第一章引言 6 ，等20 ， i = 1 ，2 ，l 其中，目标函数包含两项，i f , j l l 2 表示置信范围，体现了函数集的表达能力， ：= 1 ( g + 黝体现了经验风险g 是对经验风险与置信范围如何匹配的一个 裁决最小化这两项的加权之和体现了结构风险最小化的思想约束条件中的 p 为松弛变量，体现了e 一不敏感损失函数的应用支持向量回归与支持向量分类 类似，通常不直接求解问题( 1 2 3 ) ，而是首先引入它的对偶问题 约束条件为 m a x w ( a ，o ) = 一s ( 口：+ a d + 挑( 越一啦) t = 1t = 1 1 f 一；( 西一啦) ( 剪一哟) 巧) ， ( 1 2 4 ) i ( 田一啦) = 0 ， = 1 0 田g0 啦c i = 1 ，2 ，z ， 此为约束条件下的二次规划问题 通过求解该对偶问题得到最优解矿，并根据k k t 刍f e 件计算得到5 ，构造线性 回归函数 l ，( z ) = ( 函一嘭) 慨z ) + 5 ( 1 2 6 ) 任1 对于非线性函数的回归，支持向量回归首先通过映射把样本向量z 映射到一 个高维特征空间然后在这个特征空间中对映射后的样本进行线性回归利用核 函数( z ，z 7 ) 来代替对偶问题目标函数( 1 2 4 ) 中的内积 ( 甄) 圣( 巧) ) 可以得到 非线性回归函数 fl ，( z ) = ( 西一筋) 伸( 盈) 由( z ) ) + 5 = 一霹) k ( z ) + 5 ( 1 2 7 ) i = l i = 1 7 湖北大学硕士学位论文 1 3 支持向量回归的研究现状 由于支持向量机的完善的理论基础和良好的特性，人们对其进行了广泛的研 究和应用对支持向量机的研究涉及到分类，回归，聚类，时间序列分析，异常点检 测等诸多方面具体的研究内容包括统计学习理论基础，各种模型的建立，相应优 化算法的改进。以及实际应用支持向量回归也在这些研究中得到了发展和逐步 完善，已有了许多富有成果的研究工作 1 3 1 支持向量回归的各种模型 不敏感损失函数是v a p n i k 提的，在此基础上才建立了e 支持向量回归1 1 1 此后在诸多文献中进一步对其进行了研究【x o a 2 由于e 支持向量回归需要选择参 数e 。而在实际应用中很难选择合适的值因此文献 1 3 1 提出了p 一支持向量回归， 它可以自动计算e 文献 1 2 1 进一步研究了该算法在下一章我们将对这两种算法 给出详细的描述，并给出争支持向量回归和支持向量回归的关系 在文献 1 0 ，1 2 ，1 3 1 中，对支持向量回归和矿支持向量回归的讨论，其中关于 原始问题的解的集合表述以及原始问题和对偶问题解的关系的结果，都存在着不 足之处 对于线性规划形式的支持向量回归以及采用不同损失函数的支持向量回归 文献 1 4 1 给出了综述性的讨论m a n g a s a r i a n 和m u s i c a n t 提l b 了一种新的支持向量 回归线性规划模型，与 1 4 1 中讨论的线性规划模型相比，它具有更少的变量【1 5 1 同 时他们也给出了解决该线性规划的分解算法，它可以处理非常大规模的回归问 题 把参数e 取为零，并且考虑应用二次损失函数以及形如，( z ) = z ) 的回归 函数，支持向量回归就转化为核岭回归f 1 6 1 它是一种特殊形式的正则化神经网 络模型不少学者讨论了正则化神经网络与支持向量机的关系【1 7 , 1 8 而在岭回归中取形如f ( z ) = z ) + 6 的回归函数，就得到了线性最b - - 乘支持向量回归( is s v r ) 它是通过求解线性方程组得到回归函数的该算法 的缺点是丧失了支持向量机的稀疏性通过求解一系列线性方程组，每次对 l o + 一口i 的分量进行排序，将对应较小值的训练点逐步去掉，从而将稀疏性赋予了 算法l s s v r w e s t o n 针对岭回归给出了推理型支持向量回归的模型，推理型支持向量回归 一8 第一章引言 与归纳原则的支持向量回归不同之处在于，它不再通过求解一个决策函数来对未 来的点进行预测，而是直接对未知点预测 2 1 理论证明，推理型的支持向量机具有 更好的推广能力 4 1 m aj t m s h u i 等人将c a u w e n b e r g h s 和p o g g i o 处理增量支持向量分类的方法应 用到回归问题，得到在线支持向量回归较好地解决了在线时间序列预测或利 用l c x 3 谜取模型参数时的计算量问题【1 9 | 文献【1 3 】考虑了当噪声依赖于输入z 时的加支持向量回归，对每个输入都给 予不同的厶从而最后得到的带不再具有固定的宽度 因为可以把分类问题看成特殊的回归问题，所以可用支持向量回归方法求解 分类问题文献【2 0 】讨论了支持向量分类和回归之间的关系他们证明了对一个 给定的支持向量分类的解，通过选定特定的参数，存在一个相同的支持向量回归 的解而把回归问题转化为分类问题并用支持向量分类进行求解得到回归函数。 从而建立求解回归问题的新算法 1 3 2 解决支持向量回归中优化问题的算法 支持向量机最终要解决的问题是一个凸二次规划问题。当训练点数目不是很 多时，一些传统的优化算法，比如内点法，共轭梯度法，最速下降法等原则上都可 以直接应用于求解但实际上在处理具体问题时，由于存储和计算量两方面的要 求，这些算法往往会失效这样就迫使人们设计专门针对支持向量机的新算法由 于支持向量机中的最优化问题，是一类特殊的最优化问题，它们具有一些非常好 的特性，例如解的稀疏性和最优化问题的凸性等，这些性质使得构造使用较少存 储的快速专用算法成为可能，专用算法的一个共同特点是：将大规模的原问题分 解成若干小规模的子问题，按照某种迭代策略，反复求解子问题，构造出原问题的 近似解，并使该近似解逐渐收敛到原问题的最优解事实上，由于子问题的选取和 迭代策略的不同，可以有不同的算法这些算法最初是针对支持向量分类而言的。 由于支持向量回归与之有相同的最优化问题形式，所以同样可以应用这些算法 最简单的启发式方法是选块算法该方法于1 9 9 5 年由c o r t e s 和v a p n i k 提出【9 】 它的基本思想是，去掉对应于非支持向量的那些训练点，而只留支持向量计算相 应的l a g r a n g e 乘子由于实际上支持向量是未知的，选块算法需要通过某种迭代 方式逐步排除非支持向量，选出支持向量所对应的块这种方法的优点是当支持 向量的数目远远小于训练样本数目时，能够大大提高运算速度然而。如果支持向 一9 一 湖北大学硕士学位论文 量个数本身就比较多，随着算法迭代次数的增多，所选的块也会越来越大，算法就 变得十分缓慢了 分解算法( d e c o m p o s i n g )o s u n a 等人于1 9 9 7 年提出，j o a c h i m s 对其进行了改 进，得到了s y m 的舭算法【2 1 , 2 2 分解算法与选块算法的不同之处在于它每次只更 新若干个( 一定数量的) l a g r a n g e 乘子，而其他的乘子保持不变所以，每次一个新 样本点加到工作集中去，就必须舍去另外一个样本点迭代过程中只是将工作 集之外的样本点中的一部分情况最糟的样本点与工作集中的一部分样本点进 行等量交换既使支持向量的个数超过工作集的大小，也不改变工作集的规模 该算法的目的不是找出所有的支持向量，从而在相应的约束上解决问题，而是 每次只针对很小的训练子集来求解c o l l o b e r t 和b e n g i o 提出了针对支持向量回 归的s v m t o r c h 方法可以处理规模多达2 0 0 0 0 个训练点的问题，并证明了其收敛 性 p l a t t 于1 9 9 8 年提出了序列最小最优化( s m o ) 算法俐它是分解算法中选 取最小的工作集的特殊情形，即每次迭代过程中只调整相应于两个样本 点，弘) 和( 巧，协) 的l a g r a n g e 乘子它只求解一个具有两个变量的最优化问 题这时工作集的规模已经减到最小，s m o 算法的优点在于：两个变量的最优化 问题可以解析求解，因而在算法中不需要迭代地求解二次规划问题与通常的分 解算法比较，尽管它可能需要更多的迭代步，但是由于每步只需要很少的计算量， 该算法常表现出整体的快速收敛性质另外，该算法还具有其它的一些重要性质 例如不需要把核矩阵储存在内存中，没有矩阵运算，容易实现等 d a v i d 与a l e x a n d e r 于2 0 0 4 年提出了针对支持向量回归的新的工作集方法【衢j 它是通过解有限个高维线性方程组来得到最优解然后利用s h e r m a n - m o r r i s o n - w o o d b u r y 公式可以将高维线性方程组转化为低维的线性方程组，从而为解决大 型回归问题提供了一个快速。简单的高效算法 1 4 论文的研究内容和组织结构 本文针对以下几个方面对支持向量回归的问题进行了研究和探讨： ( 1 ) 本文给出了一个具有广泛意义的支持向量回归模型该模型的最优化问 题里面含有一个可灵活选取的函数，通过该函数的不同选取，使其能够包含若干 种已有的支持向量回归模型，并且该广义模型不再要求核函数具有正定性，从而 拓广了核函数的选择范围由于求解约束问题的途径之一是把它转化为个或一 一1 0 第一章引言 系列无约束问题，因此本文把支持向量回归中的原始凸二次规划问题转化为光滑 的无约束问题，建立了无约束的支持向量回归，从而能够应用某些成熟高效的无 约束算法求解； ( 2 ) 由于以往对支持向量回归的误差分析大多是针对标准情形研究的，因此 本文研究了非标准情形下回归估计的误差分析，从而完善了这一理论特别地，本 文运用了采样算子和积分算子来对这一理论进行研究 论文的结构如下： 第一章对支持向量回归的研究背景，历史及现状进行概述包括：解决回归 问题的传统模式，支持向量机的基本思想，支持向量回归的各种模型，以及求解支 持向量回归的各种算法等，并指出本文将要研究的内容和所做的主要工作 第二章给出支持向量回归的几个主要模型包括e s v r , - s v p , 线性规划形 式的s v r ，以及应用不同损失函数的s v r ，详细讨论它们的一些性质另外还给出 了h i l b e r t 空间中e s v r , v s v r 原始问题与对偶问题的关系，完善了支持向量回归 算法的优化理论基础 第三章建立了两种支持向量回归新模型第一种是广义的支持向量回归它 是从决策函数的形式出发考虑建立的新模型，它的原始问题是一个具有更广泛意 义的优化问题形式，通过对该优化问题中的某一个函数的选取。使得该形式可以 包含支持向量回归中已有的若干模型另外该模型不再要求核函数一定是正定 的，使得其适用范围更广第二种模型是无约束的支持向量回归，针对利用二次 e 不敏感损失函数的支持向量回归，将其转化为无约束的问题，并光滑化，从而可 以利用传统的无约束算法求解， 第四章给出了非标准情形下支持向量回归的误差分析首先系统介绍了 h i l b e r t 空间，然后利用采样算子和积分算子，给出了非标准情形下回归估计的误 差分析 第五章是对论文工作的总结以及展望 湖北大学硕士学位论文 第二章支持向量回归模型 这一章给出支持向量回归的几个主要模型包括争s v r , s v r ，线性规划形 式的s v r , 以及应用不同损失函数的s v r , 并详细讨论它们的一些性质 2 1e 一支持向量回归模型 本节我们讨论基于e 不敏感损失函数的两个支持向量机模型 2 1 1 基于二次不敏感损失函数的e - s v r 定义二次不敏感损失函数 鹾( z ，可，) = l 掣一，( z ) i ；= ( m a x ( 0 ，i 一，( 卫) i 一) ) 2 ，( 2 1 1 ) 二次e 不敏感损失的原问题描述如下： l r a i n 1 1 u 1 1 2 + g ( 等+ 磊2 ) i = 1 8 t ( ( u 毛) + b ) 一雏+ 靠， 挑一( ( u 鼢) + b ) e + 6 ， 靠，6 0 ，i = 1 ，2 ，1 ，( 2 1 2 ) 这里引入了两个松弛变量一个是在目标值之上超出所设，另一个是在目标值 之下超出所设考虑为变化的c 值求解这个方程，然后使用验证的方法选择参 数的最优值可以导出眦对偶问题，考虑6 基= 0 和啦反= 0 ，对下面的拉格 朗日乘子成立： 一；壹( 面一啦) ( 嘞一哟) ( 慨巧) + 刍幻) 。i d = l 。 s t 他一m ) = 0 ， 一1 2 啦+ ；：i e q 一 啦玑 。础 缸m 第二章支持向量回归模型 其中 面0 ，啦20 ，i = 1 ，2 ，f ，( 2 1 3 ) 奶= 蓁； 通过求解该对偶问题得到原始问题的解，从而构造决策函数若引入核函数 k ( z ，一) 代替目标函数( 2 1 3 ) 中的内积( 甄巧) ，则得到基于二次e - 不敏感损失函 数的e 支持向量回归算法： 算法2 1g 一支持向量回归) ( 1 ) 设已知训练集 ( z 1 ，y 1 ) ，矶) ) ，其中戤j 矿，挑r ，i = 1 ，z ； ( 2 ) 选择适当的正数和c ，选择适当的核k ( z ，一) ； ( 3 ) 构造并求解最优化问题 一1 2 塞( 画一啦) ( 嘞一) ( k ( 毛，巧) + 昙妨) j = 1 v 8 t 他一q t ) = o ， 画0 ，啦0 ， = 1 ，2 ，f ， 得剑最优解丘= ( 西，面，面，面) 1 ； ( 4 ) 构造决策函数 m ) = 妻( 画刊( 矧+ 扣“ 其中5 按下列方式计算：选择不为零的岛或五若选到的是嘞，则 5 = 协一妻( 画吲( 咖扣怕 ( 2 1 4 ) ( 2 1 5 ) q+ 啦 。甜 e一 啦 一 喀挑 。谢 缸m 湖北大学硕士学位论文 若选到的是五，则 5 = 挑一塞( 五一皿) ( k ，巧) + 专幻) 一e ( 2 1 6 ) t = 1 2 1 2 基于线性e 一不敏感损失函数的e - s v r 若用到的损失函数是线性的e 不敏感损失函数 ( 为y ，) = iy 一，p ) i 。= m a x ( o ，iy 一，( z ) i 一) ， ( 2 1 7 ) 则我们在选择决策函数时，应极小化下面的表达式 扣n c 妻蚶( 训， ) 于是得到原始最优化问题为 相应的w o l f e 对偶问题为 血扣n g 萎l ( 6 + 自 s t ( ( u x i ) + b ) 一y i + 6 ， y i 一( ( u x i ) + b ) e + 6 ， 6 0 ，6 0 ，i = 1 ，2 ，1 ，( 2 1 9 ) m a x 鼽( 画一啦) 一e ( 画+ 啦) i = li = 1 1 一；( 画一啦) ( 岛一) ( 毛巧) 。i d = l f s t 一啦) = 0 ， i = 1 0 a ，画gi = 1 ，2 ，f ，( 2 1 1 0 ) 1 4 - - 第二章支持向量回归模型 通过求解该对偶问题得到原始问题的解，从而构造决策函数若引入核函数 k ( x ，一) 代替目标函数( 2 1 1 0 ) 中的内积巧) ，则得到我们常用的e 支持向量回 归算法： 算法2 2 ( e 支持向量回归) ( 1 ) 设已知训练集 ( z l ，讥) ，一，( 而，肌) ) ，其中毛彤，玑r ，i = 1 ，z ； ( 2 ) 选择适当的正数和c ，选择适当的核k ( x ，一) ； ( 3 ) 构造并求解最优化问题 m a x y i ( & i 一啦) 一e + 啦) i = li - - = l 1 l 一；( 画一儡) ( 国一a j ) k ( = i ，巧) 一i , j = l l 8 t 一啦) = 0 ， i = 1 0 啦，画gi = 1 ，2 ，1 ， 得到最优解丘= ( 西，面，画，面) t ； ( 4 ) 构造决策函数 l ，( z ) = ( 五一画) k ( 黾，z ) + 5 ， ( 2 1 1 1 ) i = l 其中5 按下列方式计算：选择开区间( o ，c ) 中的国或五若选到的是而，则 若选到的是五，则 l 5 = 珊一( 五一面) k ( 丑，巧) + e ； ( 2 1 1 2 ) i = 1 l 5 = 挑一( 画一画) k ( 黾，巧) 一e ( 2 1 1 3 ) i = l 1 5 一 湖北大学硕士学位论文 2 1 3e o 支持向量回归中的稀疏性 首先介绍支持向量的概念，这里以基于线性不敏感损失函数的s v r 算 法2 2 讨论 定义2 1 称训练集中的输入黾为支持向量，如果算法2 1 计算出的啦o 或 画0 下面给出最优化问题( 2 1 1 0 ) 的解a 的分量啦和d i 的取值情况以及它们与样 本点，玑) 的关系： 定理2 1 设丘= ( n 1 ，面，啦，画) t 是最优化问题( 2 1 1 0 ) 的解，则每一对 啦和画中最多只能有一个不为零，即蛳匮t = 0 ，i = 1 ，f 定理2 2 设丘= ( 口1 ，血，啦，d f ) r 是最优化问题( 2 1 1 0 ) 的解，则 ( 1 ) 若啦= 画= o ，则相应的样本点( 戤，鼽) 一定在e 一带的内部或边界上 ( 2 ) 若啦( o ，回，画= o 或啦= o ，哦( 0 ，c ) ，则相应的样本点( 黾，玑) 一定在 争带的边界上 ( 3 ) 若o t = g 画= o 或啦= o ，画= g 则相应的样本点( x i ，挑) 一定在 带的 外部或边界上 推论2 1 ( 1 ) 若样本点溆，雏) 在 带内部，则啦= 国= 0 ( 2 ) 若样本点( 毛，鼽) 在e 一带的边界上，则啦【0 ，q ，碗= o 或啦= 0 ，反 【o ，c 】 ( 3 ) 若样本点慨，挑) 在e 一带外部，则啦= g d i = 0 或啦= 0 ，也= d ( 4 ) 对任意样本点慨，玑) 有6 6 = 0 由推论2 1 的结论( 1 ) 可见，所有在- 带内部的样本点( 戤，弘) 都对应啦= d = o ，即它们都不是支持向量只有那些对应于啦o 或画o 的样本点，玑) ，才 会影响决策函数这一稀疏性将简化计算显然这个优点与所采用的不敏感损 失函数密切相关 2 2 支持向量回归模型 在e 支持向量回归中，需要事先确定e 不敏感损失函数中的参数然而在 某些情况下选择合适的e 并不是一件容易的事情本节讨论能够自动计算的 - 1 6 第二章支持向量回归模型 肛支持向量回归( v - s v r ) ，它是e s v r 的一种变形 2 2 1 原始问题与对偶问题 仍先考虑构造线性回归函数，0 ) = - z ) + 6 在g 一支持向量回归( s s v r ) 中， 出发点是选定e 和c ，求解最优化问题( 2 1 9 ) 与此不同，这里的出发点是选定另 外一个参数扩和c ，即把最优化问题修改为： m i n 巾，己e ) = 扣1 1 2 + g + ；壹( 矗+ 6 ) ) i = l s t ( ( u 翱) + b ) 一觚e + 6 ， 玑一( ( u ) + b ) e + 6 ， 6 0 ，& 20 ，e 20 ， = 1 ，2 ，z ， 其中f = ( 1 ，6 ，6 ，6 ) t 注意与问题( 2 1 9 ) 不同，这里的e 是作为优化问 题的变量出现的其值将作为解的一部分给出 同样根据w o l f e 对偶定义可知原始问题( 2 2 1 ) 的对偶问题是 l m a x w ( 丘) = 玑他一啦) i = 1 一石1 壹( 面一啦) ( 嘞一哟) 似巧) ，r i j = 1 z 8 t ( 魂一啦) = 0 ， n 0 面，0 t ；，i = 1 ，2 ，f ， ( 哦+ 啦) s c 以 ( 2 2 2 ) 其中0 ，c o 是常数 通过引进核函数k ( ，一) 代替目标函数中的内积k 巧) ，则建立了如下的算 法： 算法2 3 ( v - 支持向量回归) 1 7 湖北大学硕士学位论文 ( 1 ) 设已知训练集 ( z 1 ，雏) ，鼽) ) ，其中毛j 矿，鼽r ，i = 1 ，z ； ( 2 ) 选择适当的正数和c ，选择适当的核k ( z ，一) ； ( 3 ) 构造并求解最优化问题 s t 池一q ) = 0 ， o 缄口孚，2 ，f ( 画10 t ) c ( 2 2 3 ) 得到最优解丘= ( 西，面，西，面) r ； ( 4 ) 构造决策函数 l ，( z ) = ( 面一画) k ( 毛，z ) + 5 ， ( 2 2 4 ) i = 1 其中5 按下列方式计算：选择开区间( o ，孚) 中的两个分量吗和五令 5 = ；协+ y k 一( ( 五- c r d k ( z t ，x j ) + ( 五一5 t t ) k ( x t ，巩) ) 】， ( 2 2 5 ) = 1i = j 如果还需计算云可以使用于上式对应的公式 f 手= ( 五一画) ( 而，巧) + 5 一骋， ( 2 2 6 ) i = 1 或 l 手= y k 一( 画一匾) k ( 毛，z k ) 一5 ， = 1 1 8 ， 吩 啦 一 一 町 口 施 训。d：i旷 = 、，一d 沪；蚪 叭 一 o 缸 第二章支持向量回归模型 下一节我们给出v 支持向量回归的性质 2 _ 2 2 一支持向量回归的性质 本节首先给出参数的定义，然后我们通过一个定理，可以证明出沙支持向 量回归要优于s 支持向量回归 定义2 2 设( u ，b ，e ，) 为原始问题( 2 2 1 ) 的解称训练集t 中的样本点( 而，佻) 为 错误样本点，如果= 慨，6 ，6 ，最) t 满足6 o 或基0 定理2 3 设已知训练集 ( z 1 ，玑) ，( 锄，鼽) ) ，其中盈p ，玑r ，i = 1 ，f ，并用沙支持向量回归进行回归若所得到的瞄非零，则 ( 1 ) 若记支持向量的个数为p ，则p z ，即是支持向量的个数所占总样本 点数的份额的下界 ( 2 ) 若记支持向量的个数为q ，则v2q l ，即是错误样本的个数所占总样本 点数的份额的上界 另外，在一定条件下，还可以证明，当训练集t 中的样本点个数z 一。o 时， i ，以l 的概率渐近于支持向量个数与样本点个数之比，也渐近于错误样本点个数与 样本点个数之比 由此可见大体上可以用l