（管理科学与工程专业论文）支持向量机中最优化问题的研究.pdf

摘要 支持向精机是挂于统计学习理论，借助最优化疗法束解决机器学习题的新i 县它将机 器学习问题转化为求解最优化叫题，j 麻_ l 最优化理论构造算法束解决题本文上要是从最 优化理论f 抖法的角度对支持向毓机中的最优化问题进行研究 在理论上，本文河先详细地论述了支持向撤机的基本思想和备种常 h 的支持向节机片法， 然 ；通过深入分析，指出现宵力法q 仔在的1 4 题针对这些闷题，戍_ l l j 最优化理论进行深入研 究，上要丁作如r ： 1 在作为支持向昔机基础的原始问题解和对偶问题解的关系上，当时研究存在逻辑缺陷 本文发现j 弥补了这。缺陷，第次在完整严密的逻辑基础上完善了各种支持向督机中最优化 “题的理论体系 2 在部分情况f ，支持向憬机无法利州现有的公式计算决策函数的闽值本文给出了所有 可能情况f ，支持向量机中决策函数阂值的求解公式 3 m a n g a s a r i a n 提出广义支持向罱机，但不包含标准的支持向荒机：静者研究股帕严格 凸舰划问题，而后者针对的是特定的凸规划问题本文推广了i l a n g a s a r i a n 提出的广义支持向最 机，使之适用于标准的支持向量机，从而完善了广义支持向量机的理论体系 4 支持向量机中有一类重要的变形方法，虽然很有效但缺乏相府的统计学爿理论基础 本文从统计学习理论出发，对其进行深入研究 在算法方面，本文在将支持向芾机中的最优化问题转化为无约束问题的前提f ，研究了 n e w t o n p c g 算法n e w t o n p c 6 算法是解决无约柬问题的有效方法在该算法中需要求解一个一 维整数最优化问题，并且算法的效率也依赖于它的最优值本文建立了简单有效的剪法来求解 该【l j 题， 通过估计它的晟优值，对n e w t o n p c g 算法的有效性给出数量上的估计 【j 前，对支持向最机的研究土要是针对统计学习理论以及各种应用领域的研究而从最优 化理论的角度出发的研究t 作共少因此本文的研究无论对支持向量机的理论还是实践应_ 【 j ， 部具宵报重要的意义 关键词：支持向量机w o l f e 对偶，k k t 条件，n e w t o n p c g 算法 a b s t r a c t i nr e c e n ty e a r s ，s u p p o r tv e c t o rm a c h i n e s ( s v m s ) h a v eb e c o m ei n c r e a s i n g l yp o p u l a rt e c h n i q u e si n m a c h i n el e a r n i n g b a s e do nt h es t a t i s t i c a l l e a r n i n gt h e o r ya n do p t i m i z a t i o nt h e o r y ，s v m sh a v eb e e n s u c c e s s f u l l ya p p l i e dt om a n yf i e l d ss u c ha sp a t t e r nr e c o g n i t i o n ，r e g r e s s i o na n d e t c t r a i n i n ga ns v m a m o u n t st os o l v i n gac o n v e xq u a d r a t i cp r o g r a m m i n gp r o b l e m i nt h i sp a p e rw ed o s o m er e s e a r c h e so ns v m s b yt h eo p t i m i z a t i o nt h e o r ya n dm e t h o dw ep o i n to u ts o m eb a s i cd r a w b a c k s i nt h eo p t i m i z a t i o np r o b l e m so fs v m sa n dm a k es o m e i m p r o v e m e n t st ot h e mu p t on o w m o s ts t u d i e s a r ec e n t e r 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 ya n ds o m ea p p l i c a t i o n s t h er e s e a r c ho ns v m sf r o mt h e o p t i m i z a t i o np o i n to fv i e wi sa l s oa tt h eb e g i n n i n gi nt h ew o r l d t h e r e f o r e ，o u rs t u d yi sv e r yi m p o r t a n t o nt h et h e o r e t i c a la n d p r a c t i c a la s p e c t so fs v m s t h em a i nw o r k si nt h i sp a p e ra r ea sf o l l o w s ： 1 b a s e do nt h ea n a l y s i so f t h eb a s i ci d e a sa n ds o m es t a n d a r da l g o r i t h m so fs v m s ，w ef i n dt h a tt h e r e a s o n i n gt od e d v et h ee x i s t i n ga l g o r i t h m sh a v es o m eb a s i cd r a w b a c k s s o m ei m p r o v e m e n t s h a v eb e e nm a d eo nt h es t r i c tt h e o r e t i c a lf o u n d a t i o no f s v m si nt h i sp a p e n 2 i ns o m ec a s e s ，t h eu s u a lm e t h o d sf o rd e t e r m i n i n gt h et h r e s h o l d so fd e c i s i o nf u n c t i o n si ns v m s d on o tw o r k t h en e wf o r m u l at oc o m p u t et h et h r e s h o l d sa r ep r o p o s e df o ra n yc a s e s 3 t h eg e n e r a l i z e ds u p p o r tv e c t o rm a c h i n e s ( g s v m s ) w a sp r o p o s e db ym a n g a s a r i a n ，b u ti tc a n n o tb ed e g e n e r a t e dt ot h es t a n d a r ds v m s i nf a c t t h ef o r m e ro n l yc o n s i d e rt h es t r i c tc o n v e x p r o g r a m m i n g ，w h i l et h el a t t e rc o n s i d e r st h ec o n v e xp r o g r a m m i n g w ee x t e n dt h eo p t i m i z a t i o n p r o b l e m o fg s v m st ot h ec o n v e x p r o g r a m m i n g 4 t h ev a r i a t i o no f s v m si sv e r ye f f i c i e n t ，b u tl a c ko f t h ec o r r e s p o n d i n gs t a t i s t i c a ll e a r n i n gt h e o r y w em a k es o m ei m p r o v e m e n t so ni t a sa l le f f i c i e n tm e t h o dt os o l v et h eo p t i m i z a t i o np r o b l e m si ns v m s ，n e w t o n p c ga l g o r i t h m h a sb e e n i n t r o d u c e dn e w t o n p e g a l g o r i t h m i s v e r y e f f i c i e n tf o rs o l v i n gt h eu n c o n s t r a i n e d o p t i m i z a t i o n p r o b l e m s w ec o n s i d e r e da ni n t e g e ro n e d i m e n s i o n a lo p t i m i z a t i o np r o b l e ma p p e a r e di nn e w t o n - p c g m e t h o d t h ee f f i c i e n c yo f n e w t o n p c ga l g o r i t h mi sd e p e n d e do nt h eo p t i m a lv a l u eo f t h i sp r o b l e m a s i m p l ea n de f f i c i e n ta l g o r i t h mi se s t a b l i s h e dt os o l v et h i sp r o b l e ma n d i t so p t i m a lv a l u ei se s t i m a t e di n t b i sp a p e n 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 ，w o l f ed u a l ，k k tc o n d i t i o n s ，n e w t o n p c ga l g o r i t h m 独创性声明 本人卢明所呈交的论文是我个人位导| f j 指导下进行的研究t 作及取得的研 究成果。尽我所知，除了文- i t 特别加以标f 和致谢的地力+ 外，论文f | i 不包含其他 人 二经发表或撰写过的研究成果也不包含为获得中国农业大学或其它敦f f 机构 的学位或证h 而使川过的材料。与我同t 作的同志对本研究所做的任何贞献均 已往沦文i i 作厂明确的说明并表示r 谢意。 研究，f 爷名 张齐等 时问： 抄夸年月彳目 关于论文使用授权的说明 本人完全了解r p 国农业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和磁盘允许论文被查阅和借阅，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同意中国农业大学可以用不同方式在不同 媒体上发表、传播学位论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：张奈耸 时问：卯妒年月描目 导帅签名 即扔 时间：2 一心，年占月吣日 x 训 b w s 醇( ) ，( ( z ，t ) | | g ) ( “小 y t ) 符号表 实数集合 n 维欧氏空间 训练点 训练集 训练点个数 训练点所在空同 训练集所在空间 输入空间 输出空问 输入向量( 输入模式) 输出指标( 输出) 输出向量 z 与z 的内积 特征空间 特征空间中的向最 权向量 阈值 特征空间中的权向量 符号函数 接函数 2 一范数 惩罚参数 r h ) y ) “ j t “一 。川啪 叫删 咄r舌=卜。肌爿y“玳垆 中凹农业大学博士学佗论文第一章绪论 第一章绪论 支持向量机( s n p p o r tv e c t o rm a c h i n e s 简称s v m s ) 是在统计学习理论基础上发展起来的， 借助最优化方法解决机器学爿问题的新上具它最初j ：上一世纪9 ( j 年代由v a p n i k 1 l 提出，近年 来在其理论研究和算法实现力i 面都取得了突破性进展开始成为克服“维数灾难”和“过学习”荨 传统困难的有力手段 目前，已出版丁许多著作和会议文集【l 】， 2 1 ，【3 】，【4 1 ，【5 】在许多领域都获得了 成功的应用，如：模式识别 6 1 ，1 7 1 ，f 8 回归分析【9 1 ，f 1 0 】等，井推广到综合评价和经济预测【1 1 1 , 1 2 】 等领域，逐渐成为新的研究热点 1 1 研究背景 1 1 1 问题的提出 机器学习( 1 3 1 ) 主要研究如何从一些观测数据出发得出目前尚不能通过原理分析得到的规律 利用这些规律去分析客观现象，对未来数据或无法观测的数据进行预测现实世界中确实存在大 鲢人类尚无法准确认识但却可以进行观测的事物，因此机器学习在从现代科学、技术到社会、经 济等各领域都有着十分重要的应用将研究的规律抽象成分类关系时，这种机器学习问题就演变 为分类问题，或称模式识别支持向量机方法最初主要是针对分类问题而提出的 分类问题简单地说，是根据给定的两类数据组成的集合来判断一个新数据属j 二哪一类如图 111 所示，一个2 维空间上的分类问题 已知在平面( h l ，2 ) 上有一些点，它们分别属1 ：两 类 正类和负类。正类点用“+ 形点来表示，负类点用圆形点来表示现在平面上新给出一个 点z ，分类问题的日的是要推断它属r 正类还是负类即要寻找一个规则，把平面划分成两部分。 使得当该点落入其中一部分时，推断该点属r 正类；而落人另一部分时，推断它属r 负类 分类问题用数学的语言可描述为z 圉1 1 1 分类同题 7 0 f j 中国农业大学博士学伸论文第一蕈绪论 分类问题根据给定的训练集t = f ( x l ，y 1 ) ，( 乩虮) ( 爿y ) ，其中z 。z 二r ”，y l y 二 1 ：一l ，i = l 、，l ，寻找爿= _ r ”上的一个实值函数9 ( z ) ，以便用决策甬数 ，( r ) = s g n ( g ( x ) ) ， ( 11 ) 推断任一模式z 相对应的使 其中，s g n ( ) 是符号函数 酬n ) ： 1 。邳： ( 12 ) l 一1 ，o 0 ，并据此计算b = 蜥一y t ；( q ) ； z = 12 = 1 d _ 构造分划超平面( w + z ) + b = 0 ，由此求得决策函数，( z ) = s g i l ( ( 协+ f ) + 扩) 口 注2 1 3 关于名词“支持向量分类机 现在对“支持向量机”这一名词作一点说明这里的。机( m a c h i n e 机器) ”实际上是一个算 法在机器学习领域，常把一些算法看做是一个机器称分类算法为分类机 。支持向量“。是指 训练集中的某些训练点的输入耳事实上，最优化问题( 2 2 卜( 24 ) 的解o t + 的每一个分量o ：都与 一个训练点相对应，显然算法2 12 所构造的分划超平面，仅仅依赖f 那些相应- t ：o ：不为零的训 练点( y 1 ) ，而与相应于。：为零的那些训练点无关所以我们特别关心相应fo ：不为零的训练 点( 玑j ，并称这些训练点的辖入x 。为支持向量显然，h 有支持向量对最终求得的分划忍平面 的法方向+ 有影响，而与非支持向量无关，在这个意义上，称这种方法为支持向量( 分类) 机 2 1 2 近似线性可分问题 对j 二图2l2 所示的问题，用一条直线也能大体上把训练集正确分开，这类问题称为近似线性 可分问题，这时仍可以考虑使用线性分类学习机 本文第一章介绍的图1 , 2 3 所示的分类问题属f 近似线性不可分问题，因此应用前面介绍的方 法，通过求解原始问题( 11 3 ) - ( 11 5 ) 的对偶问题( 11 6 ) ( 1 1 8 ) ，来确定决策函数，具体算法步骤如 卜： 算法2 1 4 ( 线性支持j 旬i 分类机) l _ 设已知训练集t = “z 1 ，1 ) ，( x l ，帅) ) ( z x y ) ，其中孔z = r “，虮y = ( 1 ，- 1 ，i = 1f 1 2 中国农业大学博士学佗论文第二章支持向量机的理论基础 o o 囝2 1 2 近似线性可分问题 2 选择适当的惩罚参数c 0 ，构造并求解最优化问题 “ 玑d = 0 0 茎o 。c ，i = l x j )( 25 ) ( 26 ) ( 27 ) 得最优解n = ( n ：，d ”7 ； lf 3 计算叫= 肼n ：“选择矿的个分量o 。j c ，并据此计算b = 轴一y 。a ：( ”q ) ； i 2 1i = l 4 构造分划超平面( 矿x ) + 6 - = 0 ，由此求得决策函数f ( x ) = sg r i ( z ) + 扩) 2 1 3 线性不可分问题 口 对r 图2 13 所示的问题，显然这时用直线分划会产生很大的误差。这类问题称为( 实质) 线 性不可分问题这时就必须使用非线性分类学习机 o o o + j o + o 0 图2 13 线性不可分问题 1 3 一 z q玑 ” ， ， l 一2 ! 里窒些查兰堡圭兰堡堡奎量三塞塞堡堕苎墨墼堡堡兰型 对j ：这类问髯显然不能月1 超1 f 面去向 分，自然地人们希望用“超曲面”来代替对j ：超平 曲支持向量机利用4 间隔”最大的思想。来确定最优超平面，但超曲由- 没有问隔的概念这时， 通过个映射把寻找超曲面的m 题转化为寻找超平面的m 蘑下面以图2 j3 所示的分类问题来 说明 。 j 。 少一 弋 j乡0 圉2 1 4 非线性分划 记其对应的训练集为t = f ( x l ，y 1 ) ，z = l ， ，2 0 ) ，其中z 。是( s ) 平面上的点 ( k l t ，k k ) t 叭 1 ，一1 可以看出，比较合理的分划线看来是( ns ) 平面上的一个椭圆 【w 】lr 2 + w 】2 s 2 十b = 0 ， ( 28 ) 其中【w h ，( w k 和b 都是常数，参看图2 1 4 我们已经有了寻求线性分划( 直线) 的方法，自然希望 仍然使用线性分划方法，求出这个非线性分划( 椭圆) 考虑从( r ，s ) 平面上的点z = ( 【刊i ，2 ) 7 刮( “- u z ) 平面上的点x = ( x i ，f x j 2 ) 7 的映射x = 币( z ) = ( ( z 】i ，m ；) ： ：孙2 断，f 2 _ 9 1 x l 。= ； 它把( _ s ) 平面上的椭圆c w l l r 2 + h 1 2 s 2 + b = 0 映射到( “1 2 2 ) 平面上的一条直线：【w l 。u l + w 协? + b = 0 ，如图2 】，5 所示 所以只要用映射( 2 - 9 ) 把( r ，s ) 平面上的两类训练点分别映射到( u l ，u 2 ) 平面上，然后在( u - ，u 2 ) 平面上使用线性学习机求出分划直线，最后把分刘直线再映射回平面( r s ) ，就得到所寻求的非线 性分剐( 椭圆) 了 由这一简单的伪子可以看出对干( 实质) 线性不可分问题引入一个非线性函数母将输入空间 映射列一个高维特征空问， 圣：爿c r ” z 州，(210 x = 垂( z ) ， ! 里壅些奎兰壁圭兰堡堡兰堑三塞塞垫堕里堡塑堡兰矍些 o 图2 1 5 非线性映射 然后在特征空间中 勾造线性分划，此时最优化问题为 。m “i n 扣n c 窆“ sl 肌( ( wx ，) 十b ) + ，= 1 7 一l ，l 已0 ，o = l ， f 这里k = 中( 五) 类似地，引入它的对偶问题 ( 2 l l f 21 2 ( 2 1 3 21 4 1 s t 虮o 。= 0 ， ( 21 5 ) 01o l i 曼c ，i = 1 - 、? ( 21 6 1 这里 ( 甄q ) = 睁( z 。) - 垂( q ) ) ( 21 7 ) 称为核函数通过求解求偶问题来确定最终的决策函数，这样就得到标准的支持向量分类机算法 算法2 1 5 支持向量分类机( c - s v c ( s u p p o r tv e c t o rm a c h i n ef o rc l a s s i f i c a t i o n ) ) l 设已知训练集t = ( z hy 1 ) ，- ( 却玑) ( 爿y ) ，其中z 。z = 打”y y = 1 一1 ) = 1一f ： 2 选择核函数，f ( z 一) 和惩罚参数f ，构造并求解最优化问题 圳，= 0 ， 0 n ，c i = 1，f 1 5 q ) 一 j = 1 f 21 8 f 21 9 ( 22 0 q ， 一 q fkqn 玑 可 ，川 。 l 一2 t 驴 。 ； 中国农业大学瞎士学佗论文 第二章支持向量帆的理论基础 得最优解n = ( q ：，一n ? ) 7 3 选择n 的一个分昔0 o 时，说明用函数g 进行分类时样本点( “玑) 被正确分类当g 为线性函数 g = ( 叫- z ) + b 且竹( g ) 0 时，竹( 9 ) 就是“，x l 到直线g = 0 的距离的最小值这也是称 竹( 9 ) 为几何问隔的原因 根据几何问隔的定义，前面提到的规范的分划直线的几何间隔即为百三百，因此对f 规范的分 l l | | 蜘直线。它的几何间隔的大小可以用0 凹 1 来衡萤下面的定理m 1 ，就给出了基】：间隔的推广能力 的估计，这一定理为标准的支持向量分类机提供了理论基础 定理2 2 1 3 设概率分布p 确定的在爿上的分布只满足 z ：恻i 墨( = 1 若考虑线性决策函数f = 8 9 n ( ( m ，。) + b ) ，则对任给6 ( 0 ，i 】- 相对to - 1 损失函数 至少以l d 的概率满足 跗2 ( m s 。c s 郑z 州岫s t ( 堕乎业) ) ， ( 25 7 ) ，期望风险r f ，】 ( 25 8 ) l ，( 25 9 )而而 了 ! 星粪些奎兰堡皇兰堡堡兰塞三塞塞塑墼曼堡墼呈堡苎些 这个定理给出丁期望风险r 】的至少以1 6 概率成立的一个上界，即式( 25 8 ) 的右端显 然这个上界是d e 厅的单调增函数因此在选择决策函数，= s 印( ( 埘z ) + b ) 时，应使d e f r 尽可能 小现在我们说明求解原始问题( 21 1 ) 一( 21 3 ) 大体上就是寻找使d e 行达到最小的( w ，6 ) 为此考虑 原始u j 题( 2 l1 ) 一( 2 1 3 ) 的一个变形 i i t 】l 】 u - ，6 e sl ( 26 0 ) ( 26 1 ) ( 26 2 ) 其中c 0 是一个惩罚参数这个问题虽然与原始问题( 45 5 ) ，( 45 7 ) 不完全一致但其本质是相 同的，h 不过对应不同的损失函数罢了因此只需考查问题( 26 0 ) 一( 26 2 ) 和d e i f 的关系书实上 式( 25 9 ) 给出的唣盯由两项组成它们分别对应目标函数( 26 0 ) 中的第一项和第一二项中的尊 i = l f 目标雨数中的参数c 则是调节以上两个因素i l w l l 2 和g 的因子容易看出，这里的g 体现 了经验风险，i i ii l | | 则体现了表达能力所以因子g 实质上是对经验风险和表达能力如何匹配的 一个裁决 2 3 优化理论 支持向量机涉及到两个凸规划问题一原始问题和对偶问题，而且由两个问题解之间的关系建 立算法因此优化理论也是支持向量机的重要理论基础在这一部分我们给出关于凸规划问题的 优化理论如：凸规划问题解的充分必要条件，及其对偶理论( 【9 l l 【9 2 】，f 9 3 1 ) 2 3 1k k t 条件 考虑凸约束问题： m l n ，( z ) ，z 酽， s t c ( 2 7 ) s0 ，2 = 1 、p ， c ( z ) = 0 ，i = p + 1 ，- ，p + q ( 26 3 ) ( 26 4 ) ( 26 5 ) 其中目标函数，( z ) 和约束函数q ( 。) ，i = 1 ，p 都足凸函数，而q ( z ) ，i = p + 1 ，p + q 都是线 性函数 定理2 3 1 ( 凸约束问题的解) 考虑凸约束问韪( 26 3 ) ( 26 5 ) 设d 是问题的可行域 则 口= f z i q ( z ) s0 = 1 ，一，p ；c i ( x ) 二0i = p + 1 ，p + q ；z r “) ( 2 6 6 ( i ) 若问题有局部解z ，则一是问题的整体解 | i 嘻 + a 圳 一2 孙 中国农业大学博士学能论文第二章支持向量机的理论基础 ( i i ) 同题的整体解组成的集合是凸集； ( j i i ) 若问题有局部解r ，( ) 是d 上的严恪凸函数，则r 是问题的唯一整体解 定义2 , 3 2 约柬规格考虑一般约束问题( 26 3 ) ( 26 5 的i r 行域 d 二f t h ( x ) 曼o ，i = 1 ，p ；c 。( z ) = 0 i = p + 1 ，一p + q ：x r ” ，( 26 7 ) 其中p 个约策函数r ，杠) ，c ，( ) 都是可微雨数弓1 进下剪i 两种对约束的限制性条件l 约束规格) ： ( i ) 线性条件：p 个约束函数c l ( 引，c p ( z ) 都是线性函数 ( i i ) 梯度线性无关条件：梯度向憾集 ( v c 。( x ) l i a j( 26 8 ) 线性无关其中a 为i 处的有效集 定理2 3 3 ( 凸约束问题解的必要条件) 考虑凸约束问题( 26 3 ) ( 26 5 ) ，其中，：r “一r 和 c 。：r “一r “= 1 ，p ) 都是可微凸函数，且定义2 32 中的某一个约束规格成立，若z 是该问 题的解，则存在着a = ( d - - ，z 如) r p ，口= ( 岛十，1 3 p + 。) e r q ，使得k k t 条件成立，即 pp + 日 v 。( 窖，丘，口) = v m ) + 丘。v c ，( j ) 十馈v q ( 亍) = 0 ， ( 26 9 ) t = i t 2 p t q ( z ) 0 i = 1 ，p ，( 27 0 ) c 。忙) = 0 ，i = p 十1 ，p + q ( 27 1 ) n 。10 、i = l 、一，n( 27 2 ) 6 t c 。( 2 ) = 0 ，i = 1 ，一，p ( 27 3 ) 定理2 3 4 ，( 凸约束问题解的充分条件) 考虑凸约束问题( 26 3 ) ( 26 5 ) ，其中，：舻一r 和 c 。：邪一月“二1 ，p ) 都是可微凸函数，若j r ”满足k k t 条件即存在着6 = ( o lh - 一，晦) 胛，口= ( 内+ h _ ，岛+ q ) r q 、使得 pp + q v ：( z ，d ，芦) = v 珩) + q 。v c | ( 孟) + 厦审c 。( 雪) = 0 ， ( 2t 4 ) i = 1l = p + 1 c ：( i ) so ，i = 1 ，p ，( 27 5 ) c 。( i ) = 0 ，i = p + 1 ，- - ，p + q ，( 27 6 ) d 。0 ， = 1 ，p ，( 27 7 ) n ：岛( o ) - = 0 ，i = 1 ，p ，( 27 8 ) 则是问题( 2 n 6 3 ) ( 26 5 ) 的解 中国农业大学博士学位论文第二章支椅向量机的理论基础 2 3 2 w o l f e 对偶 定义2 3 5 w o l f e 对偶称州题 】i i xl ( x o ，口) ， h t 甲：l ( z n 们= 0 n 0 27 9 j 2 8 0 ) 28 1 ) 为凸最优化问题( 26 3 ) ( 26 5 ) 的v v b l f e 对偶 其中l ( x ，n ) 为拉恪朗日函数即 pp + 口 ( ”) = ，( z ) + 。q ( z ) + 屈q ( ) ( 2s 2 ) l = 1i = 1 定理2 3 6 ( 凸约束问题的强对偶定理) 考虑凸约束问题( 26 3 ) ( 26 5 ) ，其中，：r 4 一兄和 q ：r ”。r ( i = 1 ，p ) 都是町微凸函数，e l ( x ) ，l = p + l ，p + q 是线性函数，且定义2 3 2 中的某一个约束规格成立则 ( i ) 若原始问题( 26 3 ) ( 26 5 ) 有解，则它的对偶问题也有解； ( i i ) 若原始问题( 2 6 3 ) ( 26 5 ) 和对偶问题分别有可行解2 和( a ，p ) ，则这两个可行解分别为 原始问题和对偶问题的最优解的充要条件是它们相应的原始问题和对偶问题的目标函数值相等 定理2 3 7 ( 凸约束问题的w o l f e 对偶定理) 考虑凸约束问题( 2 - 6 3 ) 一( 2 - 6 5 ) ，其中，：r ”一r 和c i ：r ”一_ r ( i = i ，p ) 都是可微凸函数c 。( z ) ，l = p + 1 ， ，p + q 是线性函数，且定义2 32 中的某一个约束规格成立则 ( i ) 若原始问题( 26 3 j ( 26 5 ) 有解，则它的w o l f e 对偶问题也有解； ( i i ) 若原始问题( 26 3 ) ( 26 5 ) 和1 , v o l f c 对偶问题分别有可行解z 和( d ，卢) ，则这两个叮行解 分别为原始问题和对偶问题的最优解的充要条件是它们相应的原始问题和对偶问题的目标函数值 相等 2 4 小结 奉章详细介绍了解央分类问题的支持向量机的基本思想及其理论基础，为以后的工作做准备 主要内容包括： 1 针对不同类型的分类问题，讨论相应的支持向量分类机； 2 阐述了支持向量机方法中求解对偶问题的优势；由j ：棱函数的性质，使得对偶问题的解仅 依赖j ：馈函数的选取，这使得支持向量机具有很大的灵活性； 3 详细论述了支持向量机的理论基础之一统计学习理沦的主耍内容特别地，定理2 21 3 为支持向量分类机提供了统计学习理论基础从统计学习理论的角度讲，“间隔”最大体现了在 某种程度上推广能力最好，这使得支持向量机在应用中获得很好的效果； 2 6 中国农业大学博士学他论文第二章支持向量机的理论基础 t 作为支持向量机的男一个重受理论基础最优化理论，本章土要论述了凸规划的l , v o l f c 对偶及k k r 条件等理论 ! 里堡些查兰堡圭兰堡堡兰矍三兰童里塞垫堕里堡垒塞童垒塑堡矍 第三章常用支持向量机及其存在的问题 本章以分类同题和回归u 】题为背景，系统阐述常用的儿种支持向鲢机方法指出在现有文献 中，关j ：这几种方法的论述所存t f e 的f u j 题 3 1 支持向量分类机 3 1 1 c 一支持向量分类机 考虑分类问题设给定训练集 ( q 玑) ) ( zx y )( 3 1 ) 其中爿= r “，y i y = 1 ，一l ，i = 1 - ，f ，分类问题是要寻找函数9 ( j ) ，以便用决策函数 3 2 ) 来推断任一模式z 相对应的y 值e 一支持向量分类机是支持向量机理论中最基本的方法在第 二章已经详细的介绍了这一算法2l5 为了叙述的方便，将算法重写如下： 算法3 1 1 ( c s v c ) 1 设已知训练集t = ( ( 。1 ，y 1 ) ，( 乩虮) ) y ) ，其中z 。爿= r “，y l y ： 1 ，一1 ，i ： 1 ，f ； 2 选择核函数k ( z ，z ) 和惩踊参数g ，构造并求解最优化问题 s t 蚋，= 0 得最优解n + = ( 。；，口? ) 7 0 o 。ci = 1 ，- - ，j 3 选择o 的一个分量0 0 则相应地， y a ( w ) + b ) + 6 1 = 0 ，( 32 2 ) 进一步，由式( 3t 6 ) 得，若存在o 的分量嵋 c ，则 6 = 0( 32 3 ) 山式( 32 2 ) 和( 32 3 ) 吖得，若存在对偶问题的解n 的分量o ；满足0 n j e ，则计算b 的公 式为 b = 蜥一( w x 。) = 一叭：( 4 ，z ，) ( 32 a ) l = l 中国农业大学博士学位论文第三章常用支持向量帆及茸存在的问题 从前面推导的过程可以看出求解b 的公式仍然是通过考察原始问题的k k t 条件出发而得到 的显然和求解w 存在同样的问题更进一步，我们发现算法在求解6 的公式时，有限制条件，即 嘤求存在对偶问题的解q 的分量0 n ： c ，若找不到这佯的分量，如下面的例子31 3 所示 则算法就失效丁另一方面，这一算法h 给出b 的唯一j 拜，事实上原始问题关j ：b 的解可能不唯 一r 面举例说明 倒3 1 3 原始问题关于b 的孵不唯一的例子 考虑一维空问上的分类问题设训练集为 1 1 = “x 1 1 )，( x 6 ，如) ) j = “o ，1 ) ，( 1 ，1 ) ，( f 1 1 ) ，( 3 ，一1 ) ，( 6 ，一1 ) ，( 7 ，1 ) ，( 32 5 ) 即一维输入0 ，1 ，r i 为正类，3 6 ，7 为负类，显然这是一维线性不可分的m 题 若选取惩罚参数c = 丧，则原始最优化同题为 ( 32 6 ) ( 32 7