（管理科学与工程专业论文）支持向量回归机及其应用研究.pdf

摘要 支持向量机是数据挖掘中的新方法它是建立在统计学习理论基础之上的通用学习方法，并 且已表现出很多优于已有方法的性能目前在理论研究和实际应用两方面支持向量机正处于飞速 发展的阶段， 处理分类问题和回归问题的支持向量机分别称为支持向量分类机( s v c ) 和支持向量回归机 ( s v r ) ，支持向量回归机无论在理论还是应用研究方面都没有支持向量分类机的研究工作深入和 广泛，本文针对以下几个方面对支持向量回归机的理论和应用进行了研究和探讨： 1 模型选择问题决定了支持向量机实际应用的成功与否对支持向量分类机，已经有了一些 文献探讨如何选择最优参数，其晶常用的评价标准是l 0 0 误差界对支持向量回归机目前还没有相 应的结果本文推导出三个支持向量回归机算法的l 0 0 误差界，并在此基础上给出了一个新的支持 向量回归机算法一l 0 0 支持向量回归机： 2 本文给出了一个广义支持向量回归机模型，该模型的优化问题中含有一个可灵活选取盼 函数，通过该函数的不同选取，使其能够包含若干种已有的支持向量回归机模型，并且该广义模 型不再要求核函数具有正定性，从而拓广了核函数的选择范围：把支持向量回归机中的原始凸- 二 次规划问题转化为光滑的无约束问题，构建了无约束支持向量回归机，使得许多成熟有效的无约 束最优化算法能够应用聋4 支持向量回归杌中去； 3 对标准的e s v r ，我们给出了其两个导山途径：一是把回归问题转化为分类问题，利用s v c 求解，推导出e s v r 的原始最优化问题；二是对回归问题给出了相应于分类问题的间隔概念，利甩 最人问隔的思想推导出e s y r 的原始问题： 4 目前支持向量回归机的研究都是基于有限维空问的优化理论，而对于无穷维空问则没有 讨论本文对无穷维空间中支持同量回归机的原始最优化问题和对偶问题的解的关系给出了严 谨的理论证明，完善了支持向量回归机的优化理论基础； 5 对小流域土壤侵蚀的预报问韪，本文荦j 用研究的理论结果建立小流域土壤侵蚀s v r 预报模 型，并根据最小化l 0 0 误差界选择最优参数与传统预报模型的比较结果表明了s v r 预报模型的可 行性和有效性，从而为支持向量回归机在新领域的应用做了有意义的尝试 关键词：支持向量机，分类问题，回归问题，模型选择，l 0 0 误差界 a b s t r 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 sd e v e l o p e di nr e c e n ty e a mb a s e do n t h ef o u n d a t i o n so fs 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 ) ，a n dt h e yh a v e b e e np r o v e nt ob em o r ep o w e r f u l a 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 c t s s v m sa r ed e v e l o p i n gp r o m i s i n g l ye i t h e ri nt h e o r yo r a p p l i c a t i o n s s u p p o av e c t o rm a c h i n e sf o rc l a s s i f i c a t i o np r o b l e ma r ec a l l e ds 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 ) ， w h i l ef o rr e g r e s s i o np r o b l e ma r es 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 so ns v ri ns e v e r a l a s p e c t s ，i n c l u d i n gt h e o r yf o u n d a t i o na n da p p l i c a t i o n 1 t h es u c c e s so fs v m sd e p e n d sh e a v i l yo nt h em o d e ls e l e c t i o n o n eo ft h em o s tp o p u l a r a p p r o a c h e si st os e l e c tt h ek e r n e la n dt h ep a r a m e t e r sb ym i n i m i z i n gt h eb o u n do fl e a v e - o n e - o u t ( t o o ) e r r o r f o rs v cs o m ef a m o u sb o u n d sh a v eb e e np r o p o s e d ，w ed e r i v et h r e el o ob o u n d sf o rt h r e e a l g o r i t h m so fs v r ，a n d an e ws v r a l g o r i t h m ( l o o - - s v r ) i sp r o p o s e d 2 ag e n e r a l i z e dm o d e lo fs v ri sp r o p o s e d ，i nt h eo p t i m i z a t i o np r o b l e mo fw h i c has e l e c t a b l e f u n c t i o ni si n c l u d e d d i f f e r e n ts e l e c t i o n so ft h i sf u n c t i o nw i l ld e r i v es o m ek i n d so fe x i s t i n ga l g o r i t h m s o fs v r ，a n dt h ek e r n e lf u n c t i o ni nt h i sm o d e lm a yn o tb en e c e s s a r i l yd e f i n i t e ；u n c o n s t r a i n e ds v ri s c o n s t r u c t e da f t e rt r a n s f o r m i n gt h ep r i m a lc o n v e xq u a d r a t i cp r o g r a m m i n gi n t ou n c o n s t r a i n e dp r o b ! e m ， s ot h a ts o m ee f f i c i e n tu n c o n s t r a i n e do p t i m i z a t i o nm e t h o d sc a nb ea p p l i e dt os v r 3 f o rs t a n d a r de - s v r ，w ep r o p o s et w ow a y st od e r i v ei t o n ei st h a ta f t e rt r a n s f o r m i n gr e g r e s s i o n p r o b l e mt oc l a s s i f i c a t i o np r o b l e ma n da p p l y i n gs v c t ot h i sp r o b l e m ，w ed e d u c et h ep r i m a lp r o b l e mo f s t a n d a r de - s v r t h eo t h e ri st h a t a f t e rg i v i n go u tt h ec o n c e p to fm a r g i ni nr e g r e s s i o np r o b l e m ，t h e p r i m a lp r o b l e mo f e - s v r c a na l s ob ed e r i v e db yi m p l y i n gt h ei d e ao f m a x i m i z i n gn a r g i n 4 e x i s t i n gr e s e a r c h e so fs v p a r eb a s e do no p t i m i z a t i o nt h e o r yo ff i n i t ed i m e n s i o ns p a c e t h i s p a p e rp r o v e st h er e l a t i o nb e “v e e nt h es o l u t i o n so fp r i m a lp r o b l e ma n dd u a lp r o b l e mi nh i l b e r ts p a c e ， w h i c hm a y b ei n f i n i t ed i m e n s i o n ，t h e r e f o r em a k e su pt h eo p t i m i z a t i o nt h e o r yf o u n d a t i o n 5 f o rt h ep r o b l e mo fs o i le r o s i o np r e d i c t i o n ，w ec o n s t r u c ts u p p o r tv e c t o rr e g r e s s i o np r e d i c tm o d e l ， a n dc h o o s eo p t i m a lp a r a m e t e r sb ym i n i m i z i n gt h eb o u n do fl o oe l l o rw ep r o p o s e d t h ec o m p a r i s o n r e s u l t sw i t ht r a d i t i o n a lm o d e ls h o wt h ep r i o r i t yo fo u rn e wm o d e l t h i sa p p l i c a t i o ni san e wa n d m e a n i n g f u ld i r e c t i o no fs u p p o r tv e c t o rr e g r e s s i o ni nt h ef u t u r e k e yw o r d s ：s u p p o r tv e c t o rm a c h i n e s ，c l a s s i f i c a t i o np r o b l e m ，r e g r e s s i o np r o b l e m ，m o d e l s e l e c t i o n ，b o u n do fl o o e l r o r 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得中国农业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 印募点、 时间： 减年f 肌泪 关于论文使用授权的说明 本人完全了解中国农业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：蠓多l 、 时间：吧 年6 月矾朋 导师签名召乍佬仞 时间：瑚年占月姗 第一章绪论 数据挖掘源于数据库技术引发的海量数据和人们利用这些数据的愿望数据的迅速增加与数 据分析方法的滞后之间的矛盾越来越突出，人们也希望能够在对已有的大培数据分析的基础i ：进 行科学研究、商业决策或者企业管理，但是有些数据分析工具很难对数据进行深层次的处理，使 得人们只能望”数”兴叹用数据管理系统存储数据，用机器学习的方法分析数据、挖掘海量数 据背后的知识，便促成了数据挖掘( d a t am i n i n gj 柏产生，概括地讲，数据挖掘的任务是从大型 数据库或数据仓库中提取人们感兴趣、事先未知的、有用的或潜在有用的信息 数据挖掘涉及的学科领域和方法很多，经典的是统计估计方法，比如回归分析( 多元回归、r i 回归等) 、判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类 等) 、探索性分析( 主元分析法、相关分析法等) 等它们共同的重要理论基础之一足统计学，在这 些方法中，参数的相关形式是已知的，洲练样本用来估计参数的值这些方法需要事先知道样本 的分布，而且传统统计学研究的是样本数目趋二f ：无穷大时的渐近理论，现有学习方法也多是基于 此假设但在实际问题中，样本数却是有限的，因此一些理论上很优秀的学习方法实际中表现却 可能不尽人意 机器学习也是数据挖掘的主要方法之一，它研究从观测数据( 样本) 出发寻找规律，利用这些 规律对未来数据或无法观测的数据进行预测比如人工神经网络( a n n ) ，它利用已知样本建立 非线性模型，克服了传统参数估计方法的困难但这种方法缺乏一种统一的数学理论 支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m s ) 是数据挖掘中的新方法它是建立在统计学 习理论( 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 ) 基础之上的通用学习方法统计学习理论是一种专门 研究小样本情况下机器学习规律的理论，最初r2 0 世纪9 0 年代由v a p n i k 1 1 提出该理论针对小 样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的 要求，而且追求在现有有限信息的条件下得到最优结果支持向量机已表现出很多优于已有方法 的性能它能非常成功地处理回归问题( 时间序列分析) 和模式识别( 分类问题、判别分析) 等诸 多问题，并可推广于预测和综合评价等领域支持向量机借助于最优化方法解决机器学习m 题， 它开始成为克服”维数灾难”和”过学习”等传统困难的有力手段虽然目前它在理论研究和实 际应用两方面还处于飞速发展的阶段，但是它的理论基础和实现途径的基本框架已经形成 1 1 研究背景 1 1 1 学习问题的提出 这里我们把学习m 题看作足利用有限数城的观测来寻找待求的依赖关系的m 题，可以川罔 来描述其一般模型： 图1 1 学习问题的一般模型 其中g 为产生器，t 为洲练器，两者联合产生训练集 t = ( z l ，1 ) ，( 。f ，f f ) ，( 11 ) 该训练集由从固定但未知的联合分布函数f ( z ，y ) = f ( z ) f ( 口抽取的f 个独立的观测组成其 中随机向量z 。er ”弥为输入，它们是从r ( x ) 中独立抽取的，玑称为输出，它们是根据条件分 布f ( y l x ) 产生的；l m 为学习机器，它能够实现一定的函数集合，( z ，口) ，o a ，其中a 足参数集 合学习的问题就是从给定的函数集中选择出能够“最好地”逼近训练器响应的函数 为了衡量“最好”，需要度量逼近程度考虑在给定输入z 下输出y 与学习机器给出的响应 ，( z ，n ) 之间的损失c ( y ，( z ，n ) ) 的期望 ， 2 似) = c ( ，( z ，c t ) ) d f ( ：r ，) ，( 卜2 ) j 我们称它为风险泛函学习的目标就是在给定训练集( 1 - 1 ) 的情况下，寻找使得风险泛函五陋) 最 小的，( z ，q ) v a p n i k 在【1 】中提出学习问韪的研究历电可以分为四个阶段，即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 2 回归问题的描述 学习问题主要包括：模式汉别( 分类问题) ，回归函数估计( 回归问题) 和概率密度估计同 归问题的训练集可表示为 t = “x l ，y 1 ) ，- ，( x l ，y 1 ) ) ( zx y )( 13 其中2 1 7 i 爿= r “是输入指标向量，或称输入，或称为模式，y 。y = r 是输出指标，或称输 z = 1 ，1 与分类m 蹈不同，这里的y 。并不限定取一1 或1 ，而可取任意实数回归问题的目的 是，给定的一个新的模式z ，根据训练集t 推断它所对应的输出y 足多少这个输j i y 也应该足一 个宴数 按照图i - 1 所示，令训练器的输f j ：y 为实数，并令，( z ，n ) ，c r a 为实函数集合，回归m 题就 足在分市函数f ( z ，y ) 未知但数据( 13 ) 已知的情况下，对采用某一个损失函数( j ( ，( z ，r t ) ) 的m 险泛函f 1 2 ) 求饭小 1 1 3回归问题的难点 首先讨论一个最简单的回归问题( 即n = l 的情况) 考虑两个增2 7 和的关系没已测得符 f 个z 值和其相对应的y 值 t = ( xl ，y 1 ) ，( 觑，y t ) ( 爿y ) 其中 = r ，y 。y = r ，i = l ，f 试根据这f 对值，推断y 对z 的依赖关系y = 几何图像上看，把这2 个点标在( z ，y ) t - 面上，参看图1 - 2 问题就变为寻求一条曲线y 图1 - 2 回归问题 ( 14 ) ，+ ( 。) 从 = ，h ) 解决这个问题的一个直观的想法是，把y = 广( z ) 限制在一个不太复杂的函数类中，在这类函 数中，寻找尽可能满足 y i = ，+ ( 雹) ，i = 】，2 ，一，f( 15 ) 的，+ ( z ) 实际上经常使用的线性回归方法，就是限定，( z ) 为线性函数，( z ) = a 2 ：+ b ，从中找m 尽 可能满足式( 1 5 ) 的厂( z ) = + z + b + 通常用 ( y l f ( x d ) 2 = ( y 。一a x l 一6 ) 2 f l6 ) 来度量y = ，( z ) = n z + b 偏离y ：= ，( z 。) 的程度这个量越小，表明满足的程度越高所以我”】 要尽町能满足式( 15 ) ，自然考虑用下列最优化问题 t i l i l l 三国t q “) 2 “7 ) 的解( n + ，b + ) 来确定，+ ( z ) = n + $ + b + 显然上面的回归m 题和求解方法可以推广首先已知的对应值( 14 ) 可以推广为训练粲 t = “z 1 ，y 1 ) ，( 2 7 f ，y 1 ) ( 爿y ) ， ( i 其中r ，a = 门“，y ，y = 、 = i ，- ，f 其次上面限定= ，+ ( z ) 所n ；的甬数类( 线性龋数j 啦 w r 以推广为某个实函数的集合，最后度址一，( - 1 偏离y 。= ，( “) 程度的方式弗1 i 址唯的 上面采用的蜡( 16 ) 称为甲方损失函数也可以采用其它的损失函数，若记损失函数为，1 ( ny f ! j l l j 优化问题( 17 ) 变为经验风险的极小化 m 肘i n c ( 7 3 i , y i ，) ) ，( 1 - 。1 由此便可得到我们推断的依赖关系y = ，( z ) 以上求解回归问题的方法可以总结如下： 酋先给定训练集( 1 - 8 ) 并选定损失函数；其次限定假设f ( x ) 组成的集合，；再次定义经验风 险 r ，】= c ( y t ，f ( x d ) ， ( 11 0 ) 在，中找出一个使经验风险达到最小值的函数广( 砷；最后以，+ ( 。) 作为决策函数 这一途径最本质的困难在于假设集合，的选择对于给定的一般训练集( 1 - 8 ) ，我们一方面没 有理由一定把，限定为非常狭小的函数类，例如线性函数类；另一方面也不能把，取得过丈做 为一个极端的例子，当，是所有实函数的集合时，对于训练集( 18 ) ，我们会得到 川牡矗乳砘嚣，。毗 显然这个决策函数是很不合理的总之，对假设集合，的选择，体现了回归m 题的一个实质性的 困难 综合以上讨论，我们给出回归问题的数学提法 回归问题的数学提法：没给定训练集 t = 扛l ，y 1 ) ，一，( x l ，肌) ) ( z y ) ，( 11 2 ) 其中q z = r “，y 。y = r ，i = 1 ，z 假定训练集是按工xy 上的某个概率分嘶i 1 ) ( z ，y ) 选 取的独立同分布的样本点，又设给定损失函数c ( z ，y ，f ) 试寻求一个函数，( z ) ，使i _ 导期望风险 r n f = c ( z ，y ，f ) d p ( x ，y ) ( 1 1 3 】 j 达到极小 注意，在这里概率分布p ( z ，y ) 是未知的，已知的仅仅是洲练集( 11 2 ) 1 1 4 解决回归问题的传统模式 回归分析是统计学中最重要的学科分支之一 2 _ 它的方法乃至“回归”这个名称的起源，统汁t 史l 二一般把它归功f 英国生物学家兼统计学家f g a l t o n ( 1 8 2 2 1 9 1 1 ) 传统理i 仑体系中的f n l 分i 足建立在所谓的度撼龠有加性噪声的函数的模型基础上的没某个未知1 函数有卜i 町的参数化形 些鳖当堑些些尘窒二，一，型：! 尘篁 其中咖a 足未知的参数，另外设在任意点z 。这个函数都有带有噪声的取值 其中噪声矗独立于q 且其分布服从一个已知的密度函数p ( f ) 数据对 ( z 1 ，1 ) ，- ，( 研，叭) ， 从集合( x ，。) ，d a 中估计函数( z ，o o ) ( 11 5 ) 回归的问题就是利用这些观测到的 最大似然方法是传统体系下的一个归纳引擎，函数估计的所有模型都基于它 人们利用最大似然法估计参数d o ，方法是最大化泛函 i l ( n ) = l n p ( y i f ( x i ，a ) ) ， i = 1 ( 11 6 ) 在上述模型中 f l1 7 1 如果采用具有零均值和某个固定方差的正态分布作为噪声模型就得到最小二乘法，即最小化泛函 z m ( n ) = ：( 玑一，( z i ，o ) ) 2 ( 11 8 ) - - l 针对线性关系下的回归方程的最小二乘法是c f g a u s s 在1 8 0 9 年前后最早提f h 的选择其它形式 的噪声模型p ( ) 可以得到参数估计的其它方法p h u b e r 于1 9 6 4 年扩展了传统的回归估计的模 型，提出了所谓鲁棒性回归估计模型根据这个模型人们不需要准确的噪声模型，而是给出一个 包含这个函数的密度函数集但是最大似然方法只能适用于非常有限的密度函数集 在2 0 世纪6 0 年代初，学者们提出了回归估计的一些新方法，称为非参数方法这些方法是 从一个范围较宽的函数集中估计密度，而不限于参数化的函数集 3 】【4 】 5 】在2 0 世纪7 0 年代，对 p a r z e n 类型的非参数密度估计，建立了一套完整的渐近理论 6 】，从而得出对于传统的回归估计模 型，如果观测数日足够多，用非参数方法替代参数方法可以得到一个好的逼近1 9 7 8 年v a p n i k 祁s t e f a n y u k 7 发现了一个构造和分析各种非参数算法的一般性原则，得到两个结论：( 1 ) 一般而 言，估计一个密度是一个不适定的计算问题；( 2 ) 为较好地解决这个问题，须采用正则化技术 凹归估计作为学习问题，具有学习问题的两个主要要求：一是从一个宽的函数集合中估 t 待 求的函数，上面讨论的参数和非参数估计正是解决这个要求的方法第二个要求是在有限数啭的 观测例子的基础上估计待求的函数用有限数量信息解决回归估计问题的基本原则足：必须泄法 去“直接”寻求待求的函数，而不是首先估计密度，然后用估计的密度来构造待求的函数为了柜 未知的联合分布函数f ( x ，) 下最小化风险泛函( 1 - 1 3 ) ，一般采用经验风险最小化( e m p h i f a lr i s k m i n i m i z a t i o n ) 归纳原则，简称e r m 原则最小二乘法就是这一原则的胄接体现在学) j 理论- h e r m 原则扮演着一个决定性的角色在2 0 世纪5 0 年代，r o b b i n s 和m o n r o e 8 】提了耐一种。 般的归纳原则，即随机逼近原则1 9 7 1 年，学者们创立了两种不同的一般性学习理论： ( 1 ) 对 随机逼近归纳推理的一般性渐近学习理论【9 】 10 1 【1 l 】；( 2 ) 对e r m 归纳推理的一般性f 渐近模式班 g u 理论，后来这一理论被v a l m i k l l 2 】推广到任意琏：经验数据的风险最小化问题似柏：某种，j 。代 下，随机逼近方法可以解释成为e r 、i 方法的一种特殊做法j 其他原则棚比，f , r m 门纳i j ；r , i j , i f i g 更好地利用经验数据，不依赖先验信息，并且存在很清晰的实现方法，因此在分析学爿过程时，核 一t i f f 题变成f x 十e r m 原则的探索 1 2支持向量回归机的基本思想 支持向量机方法是在统计学习理论框架下产生出来的一种新的通用机器学习方法2 0 世纪 6 0 年代v a p n i k 等人开始研究有限样本情况下的机器学习问题【1 3 1 ，1 9 6 8 年和1 9 7 1 年，v a p n i k 和 c l e r v o n e n k 碰1 4 1 5 】提出了建立在经验风险最小化原则基础之上的v c 维理论，建立了基本理论 体系一统计学习理论v a p n i k 于1 9 8 2 年【1 6 】进一步提出了具有划时代意义的结构风险最小化 ( 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 r m 原则，为解决有限样本学习问题提供了一个统一 的框架自能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题( 比如神经网络 结构选择问题、局部极小点问题等) ；v a p n i k 和c o r t e s 于9 0 年代在此基础上提出了通用的学习 算法 支持向量机方法1 7 1 该方法表现出的优良特性及其许多成功的应用，使得学者们开始迅 速重视这一学术方向。并在理论研究和算法实现方面都取得了很大的进展f 1 8 】| 9 j 支持向量机方法的基本思想可以总结为： 1 它是专fj 针对有限样本情况的学习机器，实现的是结构风险最小化；在对给定的数据逼近 的精度与逼近函数的复杂性之间寻求折衷，以期获得最好的推广能力； 2 它最终解决的足一个凸二次规划问题，从理论上说，得到的将是全局最优解，解决了在神 经网络方法中无法避免的局部极值问题； 3 它将实际问题通过非线性变换转换到高维的特征空间，在高维空间中构造线性决策函数来 实现原空闯中的非线性央策函数，巧妙地解决了维数问题，并保证了有较好的推广能力，而且算 法复杂度与样本维数无关 目前，s v m 算法在模式识别、回归估计、概率密度函数估计等方面都有应用例如，在模式 识别方面，对于手写数字识别、图像识别、文本分类等问题 a 0 1 3 3 1 ，s v m 算法在效率与精度上已 经超过传统的学习算法或与之不相上下 1 2 1 支持向量分类机 支持向量机方法最初是以解决分类问题为出发点的f 1 】，【3 4 卜 3 6 】 考虑对应图1 - 3 所示的2 维空间上的分类问题这h 十有许多直线能将两类点( “+ ”和“0 ” 两类) 正确分开假定分划直线的法方向w 已经给定例如图1 - 3 中的方向”直线1 就妊一条 以i i ) 为法方向且能够正确分划两类点的直线，显然这样的直线并不唯，我们还可以甲行地向 i 上方或左下方推移直线z l ，赢到碰到某类洲练点这样就得到了两条极端的饩线如，f l l 札在，? b 1 2 l 之间的甲i 行直线都能正确分划两类点，部可作为候j 戋分划直线显然在这些候选分划“线巾， 以i 2 和b “中间”的邡条直线为最好以上分析给儿；- r 在已知法方向w 的情况1 7 构造分划，f 线的 方法这样就把m 题归结为寻求法方向m 的m 题 j _ 、j 二芝 图1 - 3 线性可分问题 应如何选取分划直线的法方向”呢? 如上所述，对于适当给定的法方向，会有两条极端的直 线，我们称这两条直线之间的距离为与该法方向相应的“间隔”可以想象，我们应该选取使“间 隔”达到最大的那个法方向，如图1 4 所示 图1 4 最大间隔法 令这两条极端的直线方程为 ( 叫) - i - b = 1 莉1 ( 鲫z ) + 6 = 一1( 11 9 ) 与此相应的分划直线的表达式为 ( ? u o ) + b = 0 ，( i2 0 ) 此时相应的“间隔”为i 研2 极大化“间隔”的思想导致求解下列对变量“，和b 的最优化fr j 题 ，瓣i l l w l l2 ， ( i2 】) s t 叭( ( - x i ) + b ) 1 ，i = 1 ，2 f i2 2 ) 对r 可以用线性划分但存在错分点的分类n 题，对第i ，i = 1 ，f 个训练点( n 册) 引进协弛 变量矗三0 ，导致下面的最优化问题： ；i i , l ；t 1 2 + c 圭卜 。( ( t z ) + b ) + 己兰l ，i = 1 ，f 620 ，i = i ， 2 3 1 2 1 ) 2 5 1 巾旧农业大学悱士学位仑文筇 唯缔【f ： 其中c 为惩罚参数，做为调节两个目标；i i , , , l i 。和圭6 的权重 。 一1 但足支持向量机不足直接求解最优化问题( 61 4 ) ( 6i 5 ) ，而是通过求解它的对偶m 题 唑n ：妻妻螂伸州即功一妾。， c ，z s t y i o r i = 0 ， ( 12 7 ) o 曼n 。sc ，i = l ，i ， 【12 8 ) 得到最优解n = 陋：，n f ) 7 后，并据此计算b + ，从而构造决策函数 f ( x ) s g n ( ：n * y i ( x i z ) + 6 ) ( 12 9 ) 对不能采用线性分划的问题，支持向量机通过某个映射把训练集变换到一个高维的h i l b e r t 空 间中，然后在这个空间中用线性分划构造分类超平面，从而得到决策函数它主要是通过引入桉 函数k ( x ，z ) 来实现这一过程的( 可参看 3 4 ) 在支持向量分类机中，一般来说，可以用少量的支持向量来表示决策函数，即具有稀疏性 这一性质是与支持向量分类机选用的损失函数密切相关的其选用的损失函数是软间隔损失函数 c ( 跏，y i ，f ( x 1 ) ) = m a x o ，1 一玑( ( x i ) + 6 j ) ( i3 0 ) 当把支持向量机推广到回归问题建立新的回归算法一支持向量回归机( s u p p o r tv e c t o rr e g r e s s i o n s v r ) 时，则需要引入合适的损失函数来保持这个重要性质 1 2 2 不敏感损失函数 从回归问题的数学提法可以看出，为建立算法，需要选择适当的损失函数s v r 常选择的损 失函数为s 一不敏感损失函数 c ( x ，”，( z ) ) = l ，( z ) l ：、 ( 13 1 ) 其中 i y 一，( z ) l 。= m a x o ，i y 一，( z ) i f ) ， ( 13 2 ) 这里是事先取定的一个正数e 一不敏感抒i 失函数的禽义是，! r 点的观察值。j 筋测仇，l ，1 之差不超过事先给定的e 时，则认为在该点的预测值f ( x ) 是无损失的，尽管预测值，( 。) 柿f 观洲 值y 可能并不完全相等图1 - 5 中，面f f 了损失函数的图像 如果，( z ) 为单变地线性涵数 ，( t ) = ( f ) + b ， ( i 3 3 1 洋本点位j ：两条虚线之间的带子q 拍t ，则认为在泼点没有损失，参开罔i 一( j 哉州称两条虚线钩 8 一+ 图i - 5e 一不敏感损失函数 图i - 6e 带 成的带子为g 一带只有当样本点位于一带之外时，才有损失出现例如图i - 6 中的( i ，口) 处的 损失为= 口一，( i ) 一e 一不敏感损失函数有一个特点：对样本点来说，存在着一个不为目标函数提供任何损失值的 区域，即一带这个特点是其它许多损失函数( 例如本章最开始使用的平方损失函数) 并不其备 的可以期望，在e 一带内的样本点，不会出现在决策函数中 1 2 3 一支持向量回归机 我们以图i - 6 中的观测点( 训练集) 为例，说明支持向量回归机的基本思想利用上述不敏感损失函数，并限定住线性卤数柴弁 f _ i 估汁回归函数基j 结构风险最小化原则，就得到了对回归的线惟芷持向址机钟法7 匕喽钾央 托 ， c )r-1 一 、 。， 。 。 ， 一 t 一 一个原始最优化问题，形式为 一m p i n 。扣2 蚤幢一 ， s t ( ( 1 - z 。) + b ) 一玑曼+ 6 ，i 二l ，2 ，l 叭一( ( 圳z 。) + b ) 茎e + ；，i = l ，2 ，一，l 拳1 0 ，i = 1 ，2 ，1 ， ( 13 6 ) ( 13 7 ) f l3 8 1 ( 13 9 ) 这里( + ) 表示向量有+ 号和无+ 号两种情况的简单记号例如”0 意味着f ：0 和g 0 ，而 【) 则表示向量( 轧酊，6 ，靠) 7 ， 其中，目标函数( 1 3 6 ) 包含两项，i | w l l 。表示置信范围，体现了函数集的表达能力，f ( 矗+ f j ) j = l 体现了经验风险g 是对经验风险与置信范围如何匹配的一个裁决最小化这两项的加权之和体 现了结构风险最小化的思想约束条件中的( + ) 为松弛变量，体现了e 一不敏感损失函数的应用 支持向量回归机与支持向量分类机类似，通常不直接求解问题( 1 - 3 6 ) 一( 1 - 3 9 ) ，而是首先引入它的对 偶问题 通过求解该对偶问题得到最优解丘( + ) 性回归函数 f ( x ) ( 1 4 1 ) ( 14 2 ) ( d 1 ，矗j ，函，回) 7 ，并根据k k t 条件计算得到6 ，构造线 九4 3 ) 而对于图1 - 2 中的观测点，显然不能用线性函数进行回归，支持向量回归机首先通过映射把训 练点( ，叭) ，i = 1 ，- ，l 变换到一个高维h i n ) e r t 空间中的洲练点( 币( 。) ，。) ，i = 1 ，f ，然后在这 个空间中对映射后的圳练集进行线性回归利用核函数k ( x ，z ) 来代替对偶问题目标函数( i ) 中的内积( 币( q ) 圣( ) ) ，可以得到非线性回归函数 f f ，( z ) = ( 研d 。) ( 壬( “) 由( z ) ) + i = ( d i d ，) 砷洲) + 6 ( 1 ) i - - i! = l 1 3 支持向量回归机研究现状 由f 支持向城机的完善的理论基础和良好的特性，人们对其进行了广泛的研究干应刚对 持向世机的研究涉及到分类，回归、聚类、时间序列分析、异常点检测等渚多方| 面f l 体的研究i 容包括统计学习理论基础，各种模型的建立，相应优化算法的改进，蹦及蛮际应用支持n hu 机也在这些研究中得到了发展和逐步完善，l 三有r 许多富有成果的研究l ：作 ：j 孔 l i l n 玎 。 一o+ 嵋 ， er 叶 zq oo n ；捌 l 一2 ， 唿 2l | | 0 ， l 】 g “ 0 ，有 z l 。i r a 。p ( r i i 。 l i mp ( r e m p ，。 则称经验风险最小化归纳原则对假设集，和概率分布p ( z ，p ) 是一致的 一致性概念的示意同如图2 十1 所示，它表示r ，f 】和r e m p f 1 都依概率收敛下冀n ，f 冗f ， 岷舳j 州伐、 r ( 。i ) 圉2 一l 一致性 下面的定理表明什幺条件可以侏证经验风险址小f 二i j 纳原则楚。致的 定理2 1 6 ( 关键定理) 若对任意的f u 鄙柏 ( 2 5 ) ( 2 - 6 ) 0 0 = = 时以 啪姗 * 咎 一 一 m ，卜 坠坠些堑尘墼丝二一，! ，! ，! ，! 一垒二丝塑苎型些坚垒些 ! ! | j 经- 舱风险最小化岫纳原则对j - 和，( j = ，) 足一敛的 2 1 2学习机器推广能力的界 为了描述建立在经验风险最小化归纳原则基础上的学习机器的推广能力，即衡量经验风险i 期望风险的接近程度，导出了推广能力的界对回归估计要引入实函数集v c 维的概念，而它足建 立在指示函数集的v c 维的概念上的 定义2 1 7 指示函数集的v c 维设假设集，是一个由爿上取值为1 或+ l 的函数值组成的 集合定义，的v c 维为 v c d i m ( t ) = n l a x m ：j 厂( ，m ) = 2 m ) ( 2 - 8 ) 当 m ：( ，n ) = 2 ”) 是一个无限集合时，定义v c d i m ( j 1 = 。o 其中 厂( ，m ) 为增长函数，它 表示能用该指示函数集打散的点的个数 3 4 从定义2 1 7 可以看出，的v c 维就是它能打散的爿中的点的最大个数 定义2 1 8 实函数集的v c 维设假设集7 - = ，( 为n ) ，d a ) 是一个以常数a 和b 为界的 实函数集合定义 ，( 2 ，o ，卢) = o ( f ( z ，“) 一d ) “a ，卢( a ，曰) ，( 2 9 ) 其中目( 。) 为 口( z ) ： 。“o ；( 2 - 1 0 ) 【1 z 0 定义，的v c 维为相应的指示函数集合工= i ( z ，n ，口) a a ，口( a ，b ) 的v c 维 例2 1 9 n 维空间中的线性函数集合 ，( z ，n ) = ，+ n o l = 1 n o ，d l ，一，o 。( 一，o 。)( 21 1 ) 的v c 维是h = n + 1 利用v c 维概念，我们可以得到下面的一致性定理 定理2 1 1 0 若，的v c 维h 是有限值，则经验风险最小化归纳原则对7 - 和，陋，y ) 是一 致的 即当假没集，的v c 维有限时，经验风险最小化归纳原则足一致的显然这是当样本点数f 趋1 二无穷大时的性质然而，我们通常考虑的是样本点个数有限的情况，此时仅仅用经验风险来 近似期望风险足行不通的 定理2 1 1 1 ( 推广能力的界) 【5 0 】记，。为，的v c 维给定f 个独立同分m i 慨率分柑j 1 ( n ，1 米知) 的点 ( l ，1 ) ，( o i y t ) ，( 2 1 2 ) 经验风险以如下方式汁算 圩州，】= ；由川，儿，) ) ( 2 1 3 ) 些堑i 竖堑堡垡! 鲨耋! ，。一，。，一，二些皇尘型尘尘型 则对任意的慨率分布p ( e ”) 和6 ( f 1 1 】，j r 中的任意假没，都可使得下列不等式至少以1 一r 、的 概率成立 其中扛卜l i l ( 袅) 2 1 3 结构风险最小化归纳原则 。4 r e m v 】1 + 赢? 广 f ，il 如何控制学习机器的推广能力，即如何实现在上节给出的机器学习推广能力的界，导致构造一 种利用小样本洲练实例来最小化风险泛函的归纳腻理一结构风险最小化原则我们称式( 21 - 1 中 右端的第：项为置信区间，而将右端的两项之和称为结构风险，它是期望风险矗，1 的一个h 界 我们知道经验风险依赖于，的选择，而置信区间则是，的v c 维h 的增函数粗略地说，当集合 ，比较大时，可蹦选到适当的，使得邱m d ，】比较小而此时由于，的v c 维比较人，也会使 置信区间比较大反