（运筹学与控制论专业论文）支持向量机中高斯核函数的研究.pdf

论文摘要 支持向量机是二十世纪九十年代发展起来的统计学习理论的核心内容，核函 数是它的重要组成部分。在众多核函数中，高斯核函数由于其特殊的性质以及广 泛的应用，得到了广大研究者的重视。 本文主要讨论了高斯核函数的以下几方面内容： 首先，通过支持向量机引入高斯核函数，并讨论其可分性和局部性。根据高 斯核的局部性，选择全局核函数与高斯核组成组合核函数以提高分类器性能。 其次，通过v c 维理论和结构风险最小化原则，对支持向量机参数选择的重 要性作了说明，并对高斯核半径和惩罚参数c 进行选择。 对于核半径的选择，已知的方法之一是以留一误差的j o a c h i m s 上界作为核 半径选择的准则。文章提出了以最大化新空间中样本的类间和类内距离之比作为 核半径的选择准则，并通过仿真实验与己知方法进行比较，说明了本文提出的这 种方法的有效性。 最后，文章对比了高斯核函数在支持向量机和径向基网络中的应用，并基于 仿真实验说明了基于高斯核的核f i s h e r 判别在非线性可分样本分类中的优越性。 关键词：支持向量机高斯核函数高斯径向基网络核f i s h e r 判别 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 v m ) i st h em a i nc o n t e n to fs t a t i s t i c sl e a r n i n gt h e o r y d e v e l o p e df r o m1 9 9 0 s t h ek e m e lf u n c t i o ni st h ec r u c i a li n g r e d i e n to fs v m i na g r e a to fk e r n e lf u n c t i o n s m a n yr e s e a r c h e r sa t t a c hi m p o r t a n c et og a u s sk e m e l f u n c t i o nb e c a u s eo f i t sp e c u l i a rp r o p e r t ya n db r o a da p p l i c a t i o n t h i sp a d e rm a i n l yd i s c u s s e ss o m ea s p e c t so f g a u s sk e r n e lf u n c t i o n f i r s t ，t h i sp a p e l i n t r o d u c e sg a u s sk e r n e lf u n c t i o nt h r o u g l ls v ma n dd i s c u s s e si t s s e p a r a b i l i t ya n dt h ep r o p e r t yo fl o c a l i z a t i o n b a s e dt h ep r o p e r t yo fl o c a l i z a t i o no f g a u s sk e r n e lf u n c t i o n , w es e l e c tg l o b a lk e r n e lf u n c t i o nt oc o m p o u n dw i t hg a u s s k e r n c lf u n c t i o na n dc o n s t i t u t ec o m b i n a t i o nk e r n e lt oi m p r o v et h ep e r f o r l n a n c eo f c l a s s i f i e r n e x t ，t h r o u 吐v cd i m e n s i o nt h e o r ya n ds t r u c t u r a lr i s km i n i m i z a t i o np r i n c i p l e ，w e e x p l a i nt h ei m p o r t a n c eo fs e l e c t i n gp a r a m e t e ri ns v m a n ds e l e c tg a u s sk e r n e lr a d i u s a n d p u n i s h p a r a m e t e rc f o rt h es e l e c t i n go fk e m e lr a d i u s o n eo ft h ek n o w nm e t h o d si st h er u l eo f j o a c h i m s l 0 0e r r o ru pb o u n d t l l i sp a p e rs u g g e s t st h er u l eo fm a x i m i z i n gt h er a t i o o fw i t h i n c l a s st ob e t w e e n c l a s sd i s t a n c e 1 1 1 r o u 吐le m u l a t o r , w ec o m p a r ei tw i t ht h e k n o w nm e t h o da n df i n dt h i st e c h n i q u ei se f f e c t i v e l a s t t h i s p a p e rc o m p a r e st h ea p p l i c a t i o no fg a u s sk e r n e l i ns v ma n dr b f n e t w o r ka n di n t r o d u c e st h es u p e r i o r i t yo fk e m e if i s h e rd i s c r i m i n a n tb a s e dg a u s s k e m e lu s i n gi nn o n l i n e a rs e p a r a t e dd a t a 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 ，g a u s sk e r n e lf u n c t i o n ，g a u s sr a d i a l b a s i sf u n c t i o nn e t w o r k k e r n e lf i s h e rd i s c r i m i n a n t i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成 果据我所知，除文中已经注明引用的内容外，本论文不包含其他个人巳经发表或撰 写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说 明并表示谢意 作者签名：叁垒 日期： 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索：有权将学位论文的标题和摘要汇编出版保密的学位论文在 解密后适用本规定 哆彤枉 第一章引言 支持向量机是统计学习理论的核心内容 1 】 2 】，它在解决小样本和非线性的 模式识别问题中表现出许多特有的优势 3 】。核函数足支持向量机的重要组成部 分。在常用的核函数中，高斯核常常由于它特殊的性质及良好的分类性能，得到 了研究者的广泛使用。基于此，文章主要讨论了高斯核的性质、核半径的选择以 及高斯核的应用。 支持向量机的最大特点就是使用了核技巧。要解释核技巧，首先从线性可分 支持向量机开始。 对线性可分样本的分类问题，设样本集 ( ，咒) 亡r ” 一1 ，1 ，f = l ，2 ， 寻找最佳分类超平面9 0 ) = ( w 石) + 6 = 0 ，使得对于线性可分样本集，满足 髋篡! ：一y j = 1 1 1 ，i 1 2 ，1 ， l ( w 五) + 6 一，只= 一， = ， 、 超平面( x ) + b = i 和( w x ) + b = 一l 之间不存在任何样本，它们之间的距离高称 l 叫l 为( 几何) j 日j 隔。支持向量机要求最大化问隔，这样得到的分类面称为最优分类 面，它使得分类器青较强的泛化能力。 对于近似线性可分问题，即两类数据可能有少量的融合、交叉，不存在严格 满足( 1 1 ) 的最优分类超平面，但可以引入松弛变量毒，i = 1 ，2 ，使最大间隔分 类问题归结为如下二次规划问题： 噢1 2 w r w + c 善磊 s 只( ( ，t ) + 6 ) 1 一点( 1 2 ) 毒0 ，f = 1 ，2 ， 其中，c 0 是惩罚参数，用来综合间隔与错分之间的权重。 利用l a g r a n g e 优化理论，把上述优化问题转化为它的对偶问题 1 】： m i n 去”只q 0 。( 王一) 一a ， 口 i = 1j = i ，；1 s j 0 蔓qs c( 1 3 ) q 只= 0 ，i = 1 ，2 ， 其中口。，i = l ，2 ，是每个样本对应的l a g r a n g e 乘子。若口= ( 口1 一，a 是上述 最优化问题的解，则决策函数 第一章引言 华东师范大学颂士论文 ， ( x ) = s g n ( g ( 工) ) = s g n ( 芝：q 只( 工) + 6 ) ( 1 4 ) j = 】 ， 选取口的一个小于c 的正分量口，i , t 算b = y j 一只q ( x j ) 。这样，我们求得 l i 了近似线性可分情况下的最优分类面，称为广义最优分类面。 可以注意到，对于线性可分问题，我们在求分类面厂o ) 时只需计算样本之 i 日j 的内积( t x ，) 。而对于线性不可分样本，一般没有( 1 3 ) 和( 1 4 ) 的形式，整个过 程将失败。支持向量机理论的贡献在于：可以通过选择一个适当的映射矽，将样 本从原空间映射到一个高维空间，使对应的样本在新的高维空间中线性可分。于 是，与线性可分情况类似，此时的决策函数为 ， ，( x ) = s g n ( g ( x ) ) = s g n ( q 一( ( 砂妒( ) ) + 6 ) ( 1 5 ) l = i f 选取口的一个小于c 的正分量口，计算6 = y 一一q ( ( ) ( ，) ) 。此时，我们 j l l 同样只需计算新空间中样本闻的内积( 妒( 五) - ( 一) ) a 而事实上，通过讨论我们可 以知道，新空间中的样本内积( 妒( ) 矽( z ，) ) 可以表示成原空间中对应样本的函数 七( 葺，工，) ，这个函数& d 为核函数，它是一个满足一定条件的连续实值对称函数。 进一步讨论还可以知道，我们甚至不必明确映射的具体形式，而只要定义核函数， 就可以完成分类任务。 常用的核函数有多项式核、s i g m o i d 核、和高斯径向基核等。而高斯核常常 因为它的优越性能引起人们的注意，它的形式如下：足( 五工) = e x p 一j i 三；二些 ， 其中x ，x r ”是样本点，盯 0 是核半径。核半径越小，越能反映局部小领域内 样本的差异。而对于任意的训练样本，只要核半径充分小，就能使训练样本在新 空f a j 中线性可分 4 1 1 1 2 。 通过v c 维理论和结构风险最小化原则 1 】 3 】可以知道，参数选择对于支持 向量机而言是一个十分重要的过程。本文的主要成果在于高斯核半径的选择。己 知的方法之一是用留一误差的j o a c h i m s 上界作为核半径选择的准则，而作者在 高斯核的前提下，以最大化新空间中样本的类间与类内距离之比作为核半径的选 择准则。通过仿真实验对两种方法进行比较，说明了本文提出的这种方法的有效 性。它的最大优点在于无需计算支持向量，而只要根据核函数计算g r a m 矩阵， 因此大大减少了计算量。另外，文章结合对惩罚参数c 的选择，给出了u c i 数 2 第一牵引占华东岬范大学顾l 论文 据库中几个分类问题的优化参数。 高斯核在除支持向量 几以外的其他各种机器学习算法中也有着广泛的应用。 径向基网络 7 8 】的输出形式与使用高斯核的支持向量机的输出非常相似，但分 类性能却往往略逊一筹。核f i s h e r 判别 9 】在空问变换方面与支持向量机有着几 乎相同的想法，因此，基于高斯核的核f i s h e r 判别在非线性可分样本分类中有着 比f i s h e r 判别更大的优越性。 本文采用的研究方法是论文阅读和计算机仿真研究相结合。在论文的阅读中 积累知识、发现问题、接受启发，并提出自己的想法。然后通过计算机仿真实验 验证与改进想法，最后得到一些较为理想的结果。 第二章支持向量机中的核函数 传统机器学习主要的理论基础足统计学，而传统统计学研究的是样本趋于无 穷多时的渐进理论，但实际上训练样本的数目总是有限的，因而许多理论上很优 秀的算法在实际应用中表现较差。2 0 世纪7 0 年代，v - v a p n i k 等人提出的统计学 习理论( s t a f f s t i cl e a r n i n g t h e o r y ，s l t ) 是专门研究有限样本情况下机器学习规 律的理论。其中占重要位置的支持向量机理论，较好地解决了小样本情况下的机 器学习问题 3 。 与现有的各种学习机器相比，支持向量机建立在坚实的理论基础上，有较好 的推广能力和非线性处理能力。尤其在处理高维数据时，有效地解决了“维数灾 难”问题，在人脸识别、文本识别、手写体识别等应用中均表现出优于传统学习 机器的性能，成为近年来机器学习领域研究的一个热点【1 】。 第一节支持向量机 支持向量机( s u p p o r t v e c t o r m a c h i n e ，s v m ) 是v v a p n i k 于1 9 9 5 年提出的一种 新的分类技术。该方法是建立在统计学习理论的v c 维理论和结构风险最小化基 础上，根掘有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期 获得最好的推广能力 3 】。 从方法上讲，支持向量机一般先将数据映射到某个高维空间，以增加数据的 可分性，使得原本线性不可分的样本在高维空间中线性可分，再利用线性可分时 构造最优超平面的方法，并通过核技巧简单地用新空间的一个超平面完成分类。 在引言中曾经提到，对于线性和非线性可分问题，支持向量机算法只需兮别 计算样本在原空间和新空间中的内积，而新空间中的内积又可以用核函数 k ( x j ，x ) 表示。并且我们甚至不必明确空间映射的具体形式，而只要定义核函数， 就可以完成分类任务。那么，怎样的函数能够作为核函数使用呢? 本章的第二节 会说明，只要函数j i ( 五，x ，) 满足m e r c e r 条件【2 】，它就对应某一变换空间中的内积。 因此，在最优分类面中采用适当的函数j j ( ，工，) 就可以实现某一非线性变换后的 线性分类，而计算复杂度却没有增加，此时对偶问题( 1 3 ) 变为 1， m i n 只乃q q 后“，) 一q 口 - lj i ，t l s j 0 a ，c( 2 1 ) 二 c t , y , = 0 ，i = l ，2 ， 1 1 1 对应的决策函数为： ， 厂( x ) = s 鲈( g ( x ) ) = s g n ( 口。y , k ( x ，而) + 6 ) ，选取口的个小于c 的正分量口，计 4 第一窜支持向量机中的榜函数 华东师范大学硕士论文 ， 翼b = y j - zy a j 酞x j ，x 、。 l ；l 在对偶问题( 2 1 ) 中，令 日= ( 只y ，k ( x j ，_ ) ) ，p = 0 , - - - , 1 ) 7 ，口= ( 口，q ) 7 ，y = ( m ，”) 7 ，问题可表 示为紧凑形式： 1 r a i n 圭a 7 h a p 7 口 s t y 。口= 0( 2 2 ) 0 口c e 引入l a g r a n g e 函数： ，b ，j ，孝) = 妄口7 日口一p 7 0 t + 砂7 口一s r a , + 善7 似一) ，其中 z 6 ，s ，毒是l a g r a n g e 乘子。则口是( 2 2 ) 的解的k k t 条件 1 】为：存在l a g r a n g e 乘子 b ，s 和f 。，满足 0 a c e a ”y = 0 h a - e + b y s + 舌= 0 ，s 0 ，掌+ 0( 2 3 ) 善”( 口一c e ) = 0 ，s * r o e = 0 通过以上k k t 条件( 2 3 ) ，我们经简单推导可得下面结论：设口是( 2 2 ) i 构i n ，则 ， 口j = 0 时，只( 巧乃七( ，x j ) + b ) 1 ，即咒占( ) - 1 ， 0 a 7 c 时，咒( 口： 七( ，x i ) + b ) = l ，即m g ( ) = 1 ； j = l f 口? = c 时，只( 口j ”七( ，x s ) + b ) 1 ，即m g ( ) - 1 。 ，= 】 n - - n 龇了不同数值的l a g r a n g e 乘子够所对应的样本与决策面之问的 ， 位置关系。由于决策面g ( x ) = a i y , k ( x ，五) + 6 = o 由非零西及其对应的样本确 i _ l 定，因此我们把西0 对应的样本称为支持向量。其中，0 0 和对应的特征函数”：( x ) ( 渺，忆= 1 ) 进行展开，即 6 第一二章支持向量机中的核函数华东师范大学硼上论文 女( 工，j ) = - ( x ) o ) 。这时，k ( x ，x 9 = o ( x ) o ) r 其中 ，= f 矿( 工) = ( 妒( 工) ，五妒：( x ) ，) 7 ，2 ， 而( ) 是h i l b e r t 空间厶上的内积。 另外再引入正定核的定义，首先定义g r a m 矩阵： 定义2 4 ( g r a m 矩阵) ：对于给定的函数k ：x x x r 和五，葺x ，称第 f 行第列元素为女( ，x j ) 的，z 矩阵k 为函数t 的关于，再的g r a m 矩阵。 定义2 5 ( 正定核) ：设x 是r ”的子集，称定义在x x 上的对称函数k ( x ，i t ) 为一个正定核，如果对任意的玉，而x ，七( ，) 相对于五，而的g r a m 矩阵都 是半j 下定的。 若k ( x ，x ) 是m e r c e r 核，则对任意的f r ”，有 善q 。t c ，_ ，= 莓q 州妒c ，坝一，= 0 莩q 妒c ，i i 。，i ，f 因此| | 一定是正定核。其中( ) 是h i l b e r t 空间乞上的内积。 在支持向量机中，采用不同的函数作为核函数k ( x ，石) ，我们可以构造实现 输入空间中不同类型的非线性决策面的学 - - j 机器。目前常用的核函数有： 多项式核k ( x ，石) = ( z j ) + d r ，其中d 0 ，q 是正整数： 高斯径向基核t c 五工，= e 坤 一业衰笋 ，盯 。是核半径，它们都是正定核： s i g m o i d 核k ( x ，x ) = t a n h ( v ( x x 。) + c ) ，其中v 0 ，c o 是核半径。 1 可分性 所谓核函数的可分性，是指对给定训练样本，核函数导出的特征变换能否将 这些样本在特征空间中线性分开的能力。大部分情况下，我们在使用核函数之前， 并不知道样本是否真的在核函数的作用下在特征空间中变得线性可分。但是，经 常使用核函数的人可能会有这样一个经验：当选择高斯核时，只要选择合适的参 数，训练样本几乎总能在特征空间中被线性分开。这是由高斯核函数本身的性质 保证的 4 、1 2 。 参考文献【1 2 中利用二次规划解的k k t 条件详细解释了这一问题。以下给 出简单说明： 对于一般的分类问题，首先把二次规划( 1 2 ) 中的五替换成妒( 葺) ， m i n ，l ，w r w 十c 最 j 只( ( w 妒( ) ) + 6 ) 1 一磊 ( 3 1 ) 盏0 ， i = l ，2 ，z 再引入l a g r a n g e 函数： ， l ( w , b ，善，口，) = 妻w r w + c 毒一q 【咒( w ，妒( _ ) + 6 ) 一( 1 一专) 卜“专 t = 1i = l2 2 l 其中a ，是l a g r a n g e 乘子。因此二次规划( 3 1 ) f g 的k k t 等价条件是：存在 l a g r a n g e 乘子口，使 ， w = 只妒( 一) ，z 儿= o c 一西一= o f l l1 2 1 只 w 7 矿( ) + 6 卜1 + 毒o ，缶0 口：0 ，u ：0 专= o ，c e j m ( w 7 ( t ) + 6 ) 一l + 舌】= o ，i = l ，f 定理3 1 【1 2 】：若高斯核半径仃一0 ，则所有训练样本葺，i = 1 ，都是支持向量， 且它们全部被正确分类，即l a g r a n g e 乘子q 和松弛变量最满足 鹑三奄商斯核函数的参数和性质华东师范大学硕士论文 口。 o ，毒= o ，f - l ，。 证明：对于任意i = l ，设誊= 0 ，且当y l = l 时，设口。= 吼，当片= 一l 时，设 e = 照。再设正负两类样本的个数分别为+ 和，+ + n = n ，下面只要证 明所设的口和专在高斯核半径盯斗0 时满足k k t 条件，则说明所有训练样本都 是支持向量，且由( 3 1 ) 求得的最优解能把所有样本正确分类。 首先由k k t 条件的等式约束求出a 和a 一： ， q 只= 0 j n + a + 一- 口一= o ( 3 2 ) j = l a ， 只( w 7 ( ) + 6 ) 一1 = o ：只( 口，”妒7 ( _ 渺( ) + 6 ) 一l = o j t l ， j ( a ，y ，( ，_ ) + 6 ) 一只= 0 ，= l ， j 口，y j k ( ，x j ) + b = 只 ，= l 当高斯核半径盯一0 时， 代入上式得：q 卫+ 6 = y l ，即： a + 6 = 1 或一口一+ 6 = - 1 ( 3 3 ) i z l ：1 ( 3 2 州3 3 ) 可以求得饵= 等一= 等，6 = 半。 所以当常数c m a x a + ，口一 = m a x n _ ，+ 时，a 。满足不等式约束 0 0 和磊= 0 ，i = 1 ，满足k k t 条件，定理得证。 另外，文献 4 】中也详细解释了当高斯核半径充分小时，训练样本全部能被 正确分类这一问题。文中使用高等代数的方法得出了一个更一般性的结论： 定理3 2 1 4 1 ：当r a n k ( k ) = m 时，其中k = ( 七( 五，x m 是g r a m 矩阵，则训练 样本在特征空间中线性可分。 对于高斯核函数，当盯一0 时，g r a m 矩阵k 将成为强对角阵，因而满秩， 因此由以上定理可知训练样本在特征空间中线性可分。 学 第二章高斯掺函敛的参数和忡质 华东师范，：学硕上论文 有了定理3 2 ，就很容易解释为什么把任意核函数k ( x ，y ) 与高斯核函数 e x p ( 一监二业) 组合时，都能组成一个对任意训练样本都线性可分的新的核函数 盯。 讯川卅叫懈w m - 学) 其愀删。 那是因为任意核函数k ( x ，少) 的g r a m 矩阵k 对称且半正定，因此存在正交矩 阵【，使得髟= u 等于 ( 1 一c ) k + c i = u = u ( 1 一c ) ( 1 一c ) - 五 o u - 1 + 【， ( 1 一f ) 五+ c c u 。 c 因此露满秩，所以由定理3 2 可知，训练样本线性可分。在这种情况下，即使。的 值非常小，也能使矩阵满秩，从而达到样本线性可分的目的【4 】。 以上讨论了高斯核半径盯_ 0 时高斯核的可分性，那么，高斯核半径仃_ 。 时的情况又会怎样呢? 从实验中的得来的经验告诉我们，当盯逐渐增大时， l a g r a n g e 乘子q = c 的训练样本逐渐增多。由于通过e = c 可得出 只( 口；y ，七( ，一) + 6 ) - 1 ，即只g ( ) 丑 中其 一 u 、，j o 以 五 第二三章赢斯棱函数的参数和性质华东师范大学硕士论文 性可分，但容易产生过拟合，使超平面的泛化性变得较差。原因是当盯的值很小 时，从高斯核的表达式后( 工，j ) ：唧 一哮 中可以看出，它只对样本距离 l 二盯j 与盯相当的小领域内的样本产生影响，当样本之间距离远大于仃时，它的值逐渐 趋于零。因此，高斯核函数的插值能力较强，比较善于提取样本的局部性质。所 以我们把高斯核称为局部核函数。相对而言，多项式核虽然插值能力相对较弱， 但比较善于提取样本的全局特性 1 4 】。于是，我们结合两者各自的优势，构造新 的核函数( 1 - t ) ( ( j 。) + 1 ) 。+ f e x p 一竖寿 监 ，其中o f - h , hl n i 2 1 + 1 ) + 1 1 1 吾i 1 ， 则对于任意概率分布e ( x ，y ) 和任意艿( 0 ，1 】，f 中的任意假设厂都可使下列不等 式至少以1 一占的概率成立： r f 】k 【厂】+ ( 3 4 ) ( 3 4 ) 式可以简写为以下形式： 】们+ 。( 孚) ( 3 5 ) ( 3 5 ) 式右侧第二项称作置信范围，它随h 的增加而增加。右侧两项之和称为 结构风险。从( 3 5 ) 式可以看出，在v c 维较大时，学习机器较复杂，即使经验 风险很小，也无法保证期望风险r f 】较小，即无法保证系统有较好的推广性； 只有当v c 维与训练集的规模的比值较小时，期望风险r f 】才能够比较小。 可见，学习机器的推广能力不但与经验风险有关，而且和学习机器的复杂性有关。 要得到一个推广性能较好的学习系统，需要在v c 维和训练集的规模间达成一 定的均衡。基于此，我们引入结构风险最小化原则( s t r u c t u r a lr i s km i n i m i z a t i o n 。 第三章= ：i 斯核函数的参数功 ! 赝华东师范大学硕士论文 s r m ) 1 】 3 】。我们必须在一个给定的函数集中使风险最小化，这要通过控制经 验风险和置信范围的值来完成。 有两种最小化不等式( 3 5 ) 右边的构造性方法 3 】：一种足先确定一个v c 维为 某个h 的容许函数集，在学习过程中使机器最小化经验风险。神经网络( 指b p 学习算法的前馈型网络) 首先确定网络结构，这相当于确定了学习机器的置信范 围，然后按经验j x l 险最小化原则训练，这就实现了第一种方法。第二种是保持经 验风险固定并最小化置信范围支持向量机实现了第二种方法。统计学习理论中 的以下定理说明了支持向量机最小化了v c 维的上界，即最小化了鼍信范围的上 界。 定理3 7 1 8 ：在d 维空间中，设所有样本分布在一个半径为r 的超球范围内，则 满足条件0w 2s c 的规范化超平面形成的分类面函数集厂( 工，嵋6 ) = s 印 ( w x ) 4 - b ) 的v c 维满足下面的界 h s m i n ( r 2 f 】，d ) + l( 3 6 ) 由定理3 7 可知，使| 1w i l 2 最小就是使v c 维的上界最小。而分类间隔等于 2 | fw 使| 日j 隔最大等价于使i jw i l 2 最小，实际上就是对置信范围的控制。因此 最优分类面和广义最优分类面实际就是把分类函数集s = ( w 工+ b ) 按照其权值 的模( 线性可分情况下就是按照分类间隔) 分成了若干规范化子集，每个子集为 s = ( w 工+ 6 ) ：j l 卅r q ) 。对于线性可分的情况，最优分类面就是在固定经验风 险为0 的前提下寻求置信范围最小的规范化子集；而在线性不可分情况下，广义 最优分类面则是在控制错分样本的情况下使置信范围最小。因此，支持向量机算 法得到的( 广义) 最优分类面在期望风险的界的意义上是最优的，是结构风险最 小化原则的具体体现。 2 支持向量机的核参数选择与结构风险最小原则 支持向量机的决策函数是特征空间中的一个线性函数，尽管特征空间的维数 可能很大，如本文讨沦的高斯核对应的特征空间的维数为无穷【3 】，但是，通过 ， w = a ，儿驴( ) 可得f ( x ) = s g n ( w 妒( 工) + 6 ) = s g n ( ( a i ，口2 ，q ) l = l 这时的决策函数f ( x ) 可看作由 y , k ( x ，五) y 2 k ( x ，t ) y l k ( x ，而) y l 七( 工，) y 2 k ( x ，屯) y ，k ( x ，x t ) + 扪， 构成的，维空间r 上的线性指示函数。 另一方面由于约束条件( 1 2 ) 中第二式的存在，而且我们已知n 维空间上线性指示 1 4 第二章商斯恢函数的参致和性质 华东师范大学砸十论文 函数集合的v c 维是月+ l ，因此，支持向量机的决策函数的v c 维往往小于，+ 1 。 因此，支持向量机的v c 维和特征空间的维数并没有必然的关系，而是与空间r 的维数存在密切的关系。 由于核函数到特征空间的映射是一对应的，因此，不同的核参数就相当于 决定了映射之后的不同的空间r 。通过上面讨论，我们知道，空间r 的维数决定 了能在此空阳j 构造的线性分类面的最大v c 维，也就决定了线性分类面能达到的 最小经验误差。同时，每一个空间7 1 对应唯一的推广能力最好的分类超平面，如 果空问，的维数很高，则得到的分类面就可能比较复杂，经验风险小但置信范围 大，反之经验风险大但置信范围小。由( 3 5 ) 可知，这两种情况下得到的支持向量 机都不会有好的推广能力。因此，需要选择合适的核函数和核参数，使得映射后 的空问t 有合适的维数。 综上所述支持向量机的核参数决定空间r ，而空间丁的维数与支持向量机 的v c 维密切相关，因此核参数的选择与v c 维密切相关，同时也影响着支持向 量机的结构风险。 另外，惩罚参数c 的作用是在确定的特征空间中调节学习机器置信范围和 经验风险的比例以使学习机器的推广能力最好，不同特征空间中最优的c 不同。 在确定的特征空间中，c 的取值小表示对经验误差的惩罚小，学习机器的复杂度 小f 丽经验眦险值较大。称为“欠学习”；反之称为“过学习”。每个特征空间至少 存在一个合适的c 使得支持向量机推广能力最好 5 】，当c 超过一定值时， 1 幸 向量机的复杂度达到了上文提到的空间丁上允许的最大值，此时的经验风巨。推 广能力几乎不再改变。另外，惩罚参数没有出现在对偶形式( 2 1 ) 的第一式中，而 只是改变了l a g r a n g e 系数的取值范围，因此，对于一个支持向量机，如果无限 制增大惩罚因子，当支持向量机中没有边界支持向量时，c 的改变不会影响分类 性能 1 0 】。 以上讨论都告诉我们，对支持向量机的核参数和惩罚参数c 进行选择，是 寻找性能良好的支持向量分类机的重要步骤。下面分别对高斯核半径和惩罚参数 进行选择。 3 高斯核半径的选择 在第三章的第一节中，文章大致说明了当高斯核半径仃_ 0 和盯- - - ) o o 时，高 斯核支持向量机学习和泛化能力总体上的变化情况，但这只是对变化方向上的掌 控，下面通过具体的评估准则来确定高斯核半径。 要对高斯核半径进行选择，首先要制定合理的模型评估准则。经典的支持向 量机利用两类样本问的| 日j 隔( m a r g i n ) 作为泛化性能的指标。但是，不同的核以 及不同的核参数导致不同的特征空间，致使它们之间的间隔不具可比性。 另外，目前普遍使用的是k 折交叉确认法 1 】。具体方法是：把，个样本点随 机分成k 个互不相交的子集，即k 一折s ，最，墨。每个折的大小大致相等。共进 行k 次训练与测试，即对s ，扛1 ，2 ，k 进行k 次迭代，第f 次迭代的做法是， 选择s 为测试集，其余s ，5 。，墨。，最的和集为训练集，算法根据训练集 求出决策函数后，即可对测试集s 进行测试。记其中错误分类的样本点个数为，。， k 次迭代完成后，即得到了，。所有k 次迭代中错误分类数罗和总样本数 第三章高斯核函数的参数和性质 华东师范大学预卜论文 ，之比墨一作为算法错误率的一个估计，该值称为k 折交叉确认误差。 1 在实际中，七常有两种取法。第一种是取k = ，此时，每次迭代留下一个样 本点作为测试点，因此又称为留一法( 1 e a v e - o n e o u t ，简称l 0 0 ) 。由它计算的 误差也称为l 0 0 误差。l o o 误差是期望风险的一个几乎无偏估计【1 】，是对支持 向量机推广能力的估计。第二种是取k = 1 0 ，这样就得到1 0 折交叉确认误差。 虽然1 0 折交叉确认与留一法相比，计算量已减少了很多，但对数据量较大 的样本集而言，仍旧需要很大的计算量。因此，人们致力于寻找l 0 0 误差的一 个尽可能小的上界。其中，支持向量计数法就是l o o 误差上界的评估方法之一 【1 0 】。顾名思义，它是对支持向量机中支持向量的个数进行计数。根据支持向量 机和l o o 的原理，只有在所有样本上训练得到的支持向量才可能在留一法测试 时产生错误。因为如果该样本不足支持向量，那么它所对应的a ，= 0 ，在训练时 并未用它来构造分类面，当去掉该样本进行留一法训练时，分类面不会改变，用 该样本进行测试时，它仍订三确地在分类间隔外，不会产生错分。所以，若令，是 r 训练样本总数，足支持向量的总数，那么l o o 误差满足r ，。( 7 ) ；。 。 1 另外，j o a c h i m s 给出了c 支持向量分类机的l o o 误差的另一个上界。 定理3 8 1 6 b 若口；( 口? ，a j ) 7 和( w ，6 ，善) 分别是对偶问题【2 1 ) 和原始问 题的解则该算法的l 0 0 误差满足r 。d ( r ) s ，其中d 是集合 i ：2 z r 2 + f 1 f 中元素的个数，尺2 为核函数的一个上界：r 2 = m a x k ( x ，x ，) l f ，j = l ， 。 以上介绍的两种对留一误差上界进行估计的方法都是基于对错误率的估计， 它们可以作为评价支持向量机性能的准则，它们只需对包含，个样本点的训练集 使用一次支持向量机算法，而不需要像留一法那样对包含，一1 个样本点的训练集 使用，次算法。但相对于本文即将给出的一种基于高斯核半径的选择方法，它们 的计算量还是比较大。 核函数的选择，其目的在于让分类错误率尽可能小。换句话说，通过核函数 的作用，我们希望把同类样本映射得更紧凑，而不同类样本映射得更疏远。这样 就更易于找到分类面，使分类错误率尽可能小。于是，通过计算及比较映射后特 征空间的样本类间和类内距离，我们就能得到一种新的核参数选择方法： 对于训练样本 ( t ，只) c r ”x 一l ，1 ，i = l ，2 ，在原空间中两点间的距离 可以表示为忙一工l i = 舨石= i 两= i i j 二i i 了再丽；同样，在特征 空间中两点间的距离可以类似地表示为 ( x ) 一( j ) 恃0 不j f j i i 了忑两。由于我们采用的是高斯核函数，所以 上式可以简化为慨工) 一妒( x ) l i = t i 石丽。另外，不妨设前f 个样本属于1 类， 而后，一1 个样本属于+ 1 类，于是，我们定义s w = 瓯。+ s w ：为特征空间中同类样本 第三章高斯核函数的参数和性质华东师范大学预。 论文 的类内距离，其中 南= 慨_ ) 一矿( 洲= 4 2 - 2 k ( x , , x ) t = l - ，。l + 1 fj = 1 ，- a + 】， & ：= 愀) 一旭) l = 4 2 - 2 k ( x , , x j ) t i t + l - ，j 5 l + i 。，t = t + 1 ，j 。p i ， 定义s = 忪( ) 一( 一) 0 = = i 忑乏两为特征空间中异类 样本的类间距离。然后我们猜测，只要最大化类间与类内距离之比s = 卫，就可 5 w 以得到比较合适的核半径。下面通过实验来计算s ，并由实验结果来证实和改进 猜测。 以下采用了u c i 数据库中的b a l a n c e s c a l e 、b r e a s t c a n c e r - w i s c o n s i n 、i r i s 、 l e t t e r - r e c o g n i t i o n 、t i c t a c t o e 和w a v e f o 彻六个标准数据集作为确定高斯核半径的 实验对象，其中的多类问题都选取两类作为实验对象。数据集的简单说明如下表： 数据集问题类 样本总数 训练样本测试样本变量个 别数 数( + )数( 一) 数 b a l a r l c e s c a l e36 2 51 0 0 1 0 01 8 8 1 8 84 b r e a s t - c a n c e r - w i s c o n s i n26 9 91 0 0 1 1 0 0 3 4 4 1 3 91 0 1 n s31 5 01 7 1 73 3 3 34 l e t t e r - r e c o g n i t i o n 2 62 0 0 0 01 0 0 1 1 0 0 7 1 3 6 6 41 6 t i c t a c - t o e29 5 81 0 0 1 0 05 2 6 2 3 29 w a v e f o i t n2 5 0 0 01 0 0 1 1 0 0 15 5 7 1 5 4 72 1 由于计算类间与类内距离之比s 时不涉及到惩罚系数c ，因此，为了在不同 的数据集上取得一致，实验中的惩罚参数都取+ * 。高斯核半径仃= 1 0 9 ，口的取 值范围以o 2 5 为间隔，在一l 到2 之间，对数据集l e t t e r - r e c o g n i t i o n ，卢的取值范 围在1 到3 之间。在下图中，横轴表示口，纵轴表示错误率，带星号的实线表示 在测试集上的错误率，带三角的实线表示支持向量计数法给出的留一误差上界 ；。为了对比方便，把类间与类内距离之比s 也同时画在图上，当然，对于这条 l 呈s 型的实线而言，纵轴仅仅表示一个比值。 从图中可以看出，当类问与类内平方距离之比s 通过一个向上的跳跃即将趋 ， 于稳定时，即：比值的增幅突然趋缓时( 见图中箭头处) ，留一法的上界；几乎 f 是最小的，而且测试错误率也都保持在一个让人满意的值。因此，我们希望找到 箭头所指处对应的盯值。 1 7 第三章高斯_ 蠹函数的参数和性质华东师范大学硕士论文 b a l a n c e s c a l eb r e a s t c a n c e r - w i s c o n s i n j 户? 一 ，。 k 、 6 。 一一、 、，、* ，j ：rm 5oo 11 2：45口 口s t，5 2 1 n s l e t t e r - r e c o g n i t i o n 。 一- 。 7 一。 h 一、f 一一 一- 0 5oo512 t l c t a c t o ew a v e f o f i l l f 一；r 一一一 ? 一 一，、i_ i 、 i ：j n 、o ， ，、 、 一 ，?、。 “一+ h 、_ 一一一 - 1o 1 2 箭头所指处可以用差分的方法计算，在这篇文章中，取了箭头附近一阶差分 的相对值( 即：磊蠢丢晋摹) 等于。5 时对应的卢，由此得到高斯 核半径仃= 1 0 ，。具体数值见下表( 由于实验数据都是离散点，所以下列数值都 是近似的离散值) ： 数据集b a l a n cb r e a s t c a r l c em sl e t t e r -t i c t a c tw a v e f o f i l l e - s c a l