（计算机科学与技术专业论文）支持向量机算法的研究及在说话人识别上的应用.pdf

支持向量机算法的研究及在说话人识别上的应用摘要(j统计学习理论是一种专门研究有限样本情况下机器学习规律的理论，它不仅考虑了对推广能力的要求，而且追求在现有有限信息的条件下得到最优结果支持向量机是在统计学习理论的基础上发展而来的一种新的模式识别方法，在解决有限样本、非线性及高维模式识别问题中表现出许多特有的优势y本文的工作是以说话人识别为背景研究支持向量机的理论和方法说话人识别属于生物识别技术的一种，是一项根据语音波形中反映的说话人生理和行为特征的语音参数，自动鉴别说话人身份的技术为了达到这个目的，我们在详细研究支持向量机的最新进展乖说话人识别的主要特点的基础上，围绕三个问题对支持向量机的理论和方法进行了较为深入的研究本文的第一个工作是研究了支持向量机的多类分类算法经典的支持向量机分类算法是针对二类分类的，对于多类分类，研究者们先唐提出了一对多组合和一对一组合的方法本文从两个角度对各个分类器的综合进行优化：其一是建立全局目标函数，将所有的分类目标函数综合起来；其二是利用决策树的方法，将分类器分布在各个节点上本文的第二个工作是针对开集说话人辨认问题，提出了支持向量区域描述算法。1 支持向量区域描述算法的主要思想是建立一个超球，包含所有同类点，目标函数使球半径尽量小，并且球内包含尽量多的同类点。我们进一步将该算一法推广到多类分类问题上，建立了在开集背景下，进行说话人辨认的理论基础y本文的第三个工作是结合支持向量机和隐马尔可夫模型、高斯混合模型各自的优点，建立混合模型。性说话人识别问题上，虽然原有的马尔可夫模型和高斯混合模型具有良好的时间规整能力，但是，受极大似然准则的限制，他们的类别区分能力较弱支持向量机以结构风险最小化为准则，具有很强的类别区分能力本文将支持向量机与这两种模型相结合，并取得了较好的实验结果v关键字：说话人识别，统计学习理论，支持向量机支持向量机算法的研究及在说话人识别上的应用a b s t r a c ts u p p o r tv e c t o rm a c h i n e ( s v m ) i san e wa n dv e r yp r o m i s i n gc l a s s i f i c a t i o nt e c h n i q u e t h ea p p r o a c hi ss y s t e m a t i ca n dp r o p e r l ym o t i v a t e db ys t a t i s t i c a ll e a r n i n gt h e o r y t r a i n i n gi n v o v l a ss e p a r a t i n gt h ec l a s s e sw i t has u r f a c et h a tm a x i m i z e st h em a r g i nb e t w e e nt h e m a ni n t e r e s t i n gp r o p e r t yo ft h i sa p p r o a c hi st h a ti ti sa l la p p r o x i m a t ei m p l e m e n t a t i o no ft h es t r u c t u r a lr i s km i n i m i z a i t o n ( s r m ) i n d u c t i o np r i n c i p l e i i it h i st h e s i s t h et h e o r ya n dm e t h o do fs u p p o r tv e c t o rm a c h i n e sw e r es t u d i e di nt h eg i v e na p p l i c a t i o n ，t e x t - i n d e p e n d e n ts p e a k e rr e c o g n i t i o n s p e a k e rr e c o g n i t i o n ，w h i c hi d e n t i f i e so rv e r i f i e sp e o p l eb yt h e i rv o i c e ，i sak i n do fb i o m e t r i c s b a s e do nt h er e c e n ta d v a n c e m e n t so fs u p p o r tv e c t o rm a c h i n e sa n dm a i np o i n t so fs p e a k e rr e c o g n i t i o n 1 w ep r o p o s e dt h r e er e l a t e di s s u e sa n dd i s c u s s e dt h e mr e s p e c t i v e l y t h ef i r s ti s s u ei sm u l t i c l a s sc l a s s i f i c a t i o na l g o r i t h mo fs u p p o r tv e c t o rm a c h i n e s t h et r a d i t i o n a ls u p p o r tv e c t o rm a c h i n e so n l yd e a lw i t ht h eb i n a r yc l a s s i f i c a t i o n u n l i k et h eo n ea g a i n s to n ea n dt h eo n ea g a i n s tr e s tm e t h o d sb r o u g h tf o r w a r db yo t h e rr e s e a r c h e s ，w es o l v e dt h em u l t i - c l a s s i f i c a t i o nw i t ht w od i f f e r e n ta p p r o a c h e s ，o n ei sc o n s t r u c t i n gau n i f o r mo p t i m i z a t i o nf u n c t i o n ，t h eo t h e ri su t i l i z i n gd e c i s i o nt r e et oc o m b i n et h eb i n a r yc l a s s i f i e r s t h es e c o n di s s u ei ss u p p o r tv e c t o rd o m a i nd e s c r i p t i o nf o ro p e ns e ts p e a k e rr e c o g n i t i o n t h em e t h o d ，o r i g i n a l l ys u g g e s t e db yv a p n i li n t e r p r e t e da san o v e i t yd e t e c t o r sb yt a xa n dd u i n i nw a su s e da sac l a s s i f i e r i tc o n t a i n ss u p p o r tv e c t o r sd e s c r i b i n gt h eh y p e r s p h e r es e p a r a t i n gt h es a m p l e s w i t ham i n i m a lr a d i u sr ，t h i sc l a s s i f i e ra c h i e v eg o o dp e r f o r m a n c ei nf i n d i n ga b n o r m a ls a m p l e sw i t h i nt h eo p e ns e tt e s t t h et h i r di s s u ei sc o m b i n i n gs u p p o r tv e c t o rm a c h i n ea n dg e n e r a t i v em o d e l s g e n e r a t i vm o d e l ss u c ha sh i d d e nm a r k o vm o d e l sa n dg a u s s i a nm i x t u r em o d e l sh a v eb e e np r o v e dt ob ea ne f f i c i e n tw a yf o rs t a t i s t i c a l l ym o d e l i n gs e q u e n c es i g n a l s a n dt h es u p p o r tv e c t o rm a c h i n e ss e e mt ob eap r o m i s i n gc a n d i d a t et op e r f o r mt h ec l a s s i f i c a t i o nt a s k t od ot h ec o m b i n a t i o n ，p r o b a b i l i t yo u t p u t sw e r ee x t r a c t e df r o ms u p p o r tv e c t o rm a c h i n e s k e y w o r d s ：s p e a k e rr e c o g n i t i o n ，s t a t i s t i c a ll e a r n i n gt h e o r y , s u p p o r tv e c t o rm a c h i n e s支持向量机算法的研究及在说话人识别上的应用第1 章引言从上个世纪末开始，人们越来越频繁地接触到一个新名词一一“统计学习理论”( s t a t i s t i c a l l e a r n i n g t h e o r y ，简称s l t ) 【i - 3 。统计学习理论是一种专门研究有限样本情况下机器学习规律的理论a1 9 9 2t z - - 1 9 9 5 年，在统计学习理论的基础上发展出了一种崭新的模式识别方法一支持向量机( s u p p o r t v e c t o r m a c h i n e ，简称s v m ) 【3 5 ，1 2 1 5 1 。1 1 机器学习理论人类智慧中一个很重要的方面是从实例中学习的能力，通过对已知事实的分析总结出规律，预测出不能直接观测的事实。在这种学习中，重要的是要能举一反三，即利用学习得到的规律，不但可以较好的解释已知的实例，而且能够对未来的现象或无法观测的现象做出正确的预测与判断；我们把这种能力叫做推广能力。在人们对机器智能的研究中，希望能够用计算机来模拟这种学习能力，这就是我们所说的基于数据的机器学习，或者简单地称作机器学习 1 6 - 1 7 】。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于实现方法大致可以分为三种：第一种是经典的( 参数) 统计估计方法。现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的；在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先，它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。第二种方法是经验非线性方法，如人工神经网络。这种方法利用己知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。与传统统计学相比，统计学习理论是一种专门研究有限样本情况下机器学习规律的理论。该理论针对有限样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对推广能力的要求，而且追求在现有有限信息的条件下得到最优结果。vv a p n i k等人从六、七十年代开始致力于此方面研究，到九十年代中期，随着其理论的不断发展和成熟，统计学习理论开始受到越来越广泛的重视。1 9 9 2 年一1 9 9 5 年，在统计学习理论的基础上发展出了一种新的模式识别方法一支持向量机( s u p p o r t v e c t o r m a c h i n e ，简称s v m ) ，在解决有限样本、非线性及高维模式识别问题中表现出许多特有的优势，并能推广应用到函数拟合等其他机器学习问题中。支持向量机方法的几个主要优点 1 2 1 5 有：( 1 ) 它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值：( 2 ) 算法最终将转化成为一个二次型寻优问题，从理论上说。得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题：( 3 ) 算法将实际问题通过非线性变换转换到高维的特征空间，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。虽然统计学习理论和支持向量机方法中尚有很多问题需要进一步研究，但很多学者认为，它们正在成为继模式识别与神经网络研究之后机器学习领域新的研究热点，并将推动机器学习理论和技术取得重大的发展第1 页支持向量机算法的研究及在说话人识别上的应用1 2 说话人识别近年来t 在生物识别技术领域中，说话人识别技术( 或称声纹识别技术) 【2 8 2 9 1 以其独特的方便性、经济性和准确性等优势受到世人瞩目并日益成为人们日常生活和工作中重要且普及的安全验证方式。说话人识别属于生物识别技术的一种，是一项根据语音波形中反映说话人生理和行为特征的语音参数自动识别说话人身份的技术。与语音识别不同的是，说话人识别利用的是语音信号中的说话人信息，而不考虑语音中的字词意思它强调说话人的个性化特征；而语音识别的目的是识别出语音信号中的言语内容，并不考虑说话人是谁，它强调说话人的共性特征f 6 】。对说话人识别的研究始于2 0 世纪3 0 年代。早期的工作主要集中在人耳听辨实验和探讨听音识别的可能性方面。随着研究手段和工具的改进，研究工作逐渐脱离了单纯的人耳听辨。b e l l 实验室的l gk e s t a 目视观察语谱图进行识别，提出了“声纹( v o i c e p r i n t ) ”的概念；之后电子技术和计算机技术的发展，使通过机器自动识别人的声音成为可能。b e l l 实验室的s p r u z a n s k y 提出了基于模式匹配和概率统计方差分析的说话人识别方法。而引起信号处理领域许多学者的注意，掀起了说话人识别的一个研究高潮。其间的工作主要集中在各种识别参数的提取、选择和实验上，并将倒谱和线性预测分析等方法应用于说话人识别。从7 0 年代末至今说话人识别的研究重点转向对各种声学参数的线性或非线性处理以及新的模式匹配方法上，如动态时间规整、士成分分析、隐马尔可夫模型、神经网络和多特征组合等技术 7 - 8 】。如今说话人识别技术已逐渐走入实际应用。1 3 研究意义研究支持向量机在说话人识别技术上的应用，其意义在于：( 1 ) 一种新的可行的说话人识别方法的建立。说话人识别系统本质上是一个基丁统计的模式识别系统。其核心是分类问题。基于统计的模式识别系统一般由四部分组成：数据获墩，预处理，特征提取和选择以及分类决策。分类决策就是在特祉空问中用统计方法把被u 别对象门为某一类别，基本作法是在样本训练集基础上确定某个判决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小。支持向鹭帆就是一个有效的，具有 艮好的推广能力的分类算法。( 2 ) 对高斯混合模型和隐马尔可夫模型的补充。高斯混合模型和隐马尔可夫模型在语音识别领域已经取得了巨大的成功，在说话人识别方面也有很好的应用。从原理上看这两个模型与支持向量机的侧重点不同：第一，高斯混合模璀和隐马尔町夫模型适合处理连续信号，而支持向撼机适合于分类问题；第二，高斯混合模诅和隐马尔可夫模型受极人似然准! i ! i j 的限制类别区分能力较弱其结果反映了同类样本的相似度，而支持向量机的输出结粜则体现了异类样本间的差异具有很强的分类能力。( 3 ) 支持向量机应用于连续输入向量问题的探索。支持向量机在很多模式识别领域( 如人脸识别，印刷体识别等) 都取得了很好的效果。这些识别对象所共有的特点是提取出来的特，征向量都是独立的。而语音信息不同，人的说话音经过特征提取以后得到的一串向艟。是连续的。在这方面的尝试，有利于我们更好地理解和发挥支持向鼍机对连续的特征向- 蛀序列的分类能力。甚至可以将其联系到当前很热的生物信息( d n a ，基因序列等) 分类，日l i i f 已经有研究人员将支持向量机应用在生物信息学中6 6 1 。第2 页支持向量机算法的研究及在说话人识别上的应用i 4 全文内容安排本文内容包括：第一章引言；第二至八章，每一章都有小结和参考文献，最后是总结与展望。第二章介绍了关于统计学习理论的基本原理，其中包括一些重要的概念，包括机器学习的推广能力、v c 维以及结构风险最小化等。第三章介绍了支持向量机的具体算法，其中包括支持向量机在推广能力上的体现。支持向量机的核心部分核函数的选取以及支持向量机的应用等。第四章介绍了说话人识别的概念与方法，其中包括说话人识别的系统结构，语音特征提取以及常用的识别模型等。第五章讨论了支持向量机在多类分类领域的应用方法，其中包括全局优化分类和决策树分类这两种新的多类分类方法的建立和算法分析。第六章讨论了支持向量区域描述算法，其中包括这一支持向量机的变体算法在分类问题上的推广以及在开集的说话人识别上的应用。第七章讨论了讨论了支持向量机和高斯混合模型、隐马尔可夫模型的结合。其中包括二类支持向量机的计算结果转化为概率的方法，以及在多类问题时的修正。第八章是总结与展望。第3 页一一三茎旦苎垫兰堕塑墅塞墨垄塑重望型圭塑生旦第2 章统计学习理论2 1 机器学习问题函数估计模型我们从下面三个部分来描述从样本学习的一般模型 1 】：( 1 ) 产生器( g ) ，产生随机向量x r “，它们是从固定但未知的概率分布函数f ( x ) 中独立取得的。( 2 ) 训练器( s ) ，对每个输入向量x 返回一个输出值y ，产生输出的根据是同样固定但未知的条件分布函数f ( y i z ) ( 3 ) 学习机器( l m ) ，它能够实现一定的函数集，瓴口) ，口a ，其中a 是参数集合。机器学 - 7 的目的是根据给定的训练样本求对某系统输入输出之间依赖关系x i _ y i 的估计，使它能够对未知输出作出尽可能准确的预测x _ f ( x ，口) 。其中，函数f ( x ，口) 由参数口控制。给定一个新输入的样本x ，和一个特定的参数口，系统将给出一个唯一的输出，( x ，口) 。参数口的产生过程就是我们所说的学 - - j 1 1 练。对于固定结构的神经网络，口对应于连接权重。机器学习问题就是根据n 个独立同分布观测样本( x i ，y 1 ) ，( x 2 ，y 2 ) ，( h ，y 。)( 2 1 )在一组函数( 厂口) ) 中求一个最优的函数，口) 对依赖关系进行估计，使下式r ( c t ) = ；| y 一，( z ，口) i 卵( x ，y )( 2 - 2 )最小。其中存在密度函数p ( x ，y ) ，d t ( x ，y ) 可以写成p ( x ，y ) 出咖。主要的学习问题学习问题的这种形式化表述的面是很广的。它包括了很多特殊的问题，我们考虑其中主要的问题：模式识别，回归函数估计和概率密度估计1 ，1 2 1 4 。模式识别令训练器的输出y 只取两种值y = 1 , 0 ，并令f ( x ，口) ，口a 为指示函数集合( 指示函数即只有0 或1 两种取值的函数) 。考虑下面的损失函数：w 瓴鳓= 0 ；：；篇( 2 ，)对于这个损失函数，( 2 - 2 ) 式的泛函确定了训练器和指示函数，a ) 所给出的答案不同的感率。我们把指示函数给出的答案与训练输出不同的情况叫做分类错误。这样，学习问题九成了在概率测度函数f ( x ，y ) 未知。但是数据( 2 1 ) 已知的情况下使分类错误的概率最小的函数。回归估计令训练器的输出y 为实数值，并令f ( x ，口) ，t 7 t a 为实函数集合，其中包括着回归函数f ( x ，a o ) = f y d f ( y 功( 2 4 )我们知道，回归函数就是在损失函数第4 页塞茎塑兰墼竺堕墼塑塞墨垄塑重堡型圭塑窒墨三( 只厂( 种) = o 一，仉) 2( 2 5 )下使泛函( 2 - 2 ) 式最小化的函数。这样，回归估计的问题就是，在概率测度f ( x ，力未知但数据( 2 1 ) 式已知的情况下，对采用( 2 - 5 ) 式损失函数的风险泛函( 2 2 ) 式最小化。密度估计最后，考虑从密度函数集p ( x ，口) ，口a 中估计密度函数的问题。对这个问题，考虑下面的损失函数：l ( p ( x ，口) ) = 一l o g p ( x ，口)( 2 - 6 )我们知道，待求的密度函数在损失函数( 2 6 ) 式下使泛函( 2 - 2 ) 式最小化。因此，从数据估计密度函数的问题就是，在相应的概率测度f ( x ) 未知，但给出了独立同分布数据而，z 。的情况下，使风险泛函最小化。经验风险( 2 - 2 ) 式中r ) 的值称为期望风险，在这里我们称为真正风险。它的取值是我们最终感兴趣的。而“经验风险”则是对一个有限测试集合的平均错误，其表示为：尺唧( 咖寺f 劐1y f _ ，( a ) i( 2 7 )注意这里没有分布概率p ，也。陋) 对于一个特定的口和特定的分布“，y t ) 是一个固定值。i 】，一f ( x 。口) l 的值称为损失，它只能取值0 或1 。z用经验风险( 2 - 7 ) 逼近期望风险，这一原则称作经验风险最小化( e m p i r i c a lr i s km i n i m i z a t i o n ) 归纳原则，简称e r m 原则。对于一个归纳原则，如果对任何给定的观测数据，学习机器都依照这一原则来选择逼近，则我们说这一归纳原则定义了一个学习过程。在学习理论中，e r m 原则扮演了一个具有决定性的角色。e r m 原则是非常一般性的。解决一些特殊的学习问题的很多传统方法，比如在回归估计问题中的最d x - 乘方法，概率密度估计中的最大似然方法等，都是e r m 原则的具体实现，其中采用了前面我们讨论过的损失函数。仔细研究经验风险最小化原则和机器学习问题中的期望风险最小化要求，可以发现，从期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上颗粒的想当然做法。首先，r 。幢) 和r ( a ) 都是口的函数，概率论中的大数定理只说明了( 在一定条件下)当样本趋于无穷多时r 。缸) 将在概率意义上趋近于尉力，并没有保证使足，。和) 最小的口与使r ( a ) 最小的口是同一个点，更不能保证r 。( c o 能趋近于r ) 。其次，即使我们有办法使这些条件在样本数无穷大时得到保证，我们也无法认定在这些前提下得到的经验风险最小化方法在样本数有限时仍能得到好的结果。尽管有这些未知的问题，经验风险最小化最为解决模式识别等机器学习问题基本的思想仍统治了这一领域的几乎所有研究，人们多年来一宜将大部分主意力集中到如何更好地求取最小经验风险上，与此相反，统计学习理论则对用经验风险最小化原则解决期望风险最小化问题的前提是什么? 当这些前提不成立时经验风险最小化方法的性能如何? 以及是否可以找到更合理的原则等基本问题进行了深入的研究。第5 页支持向量机算法的研究及在说话人识别上的应用2 2 推广性的界复杂性与推广性在早期神经网络研究中，热门总是把注意力集中在如何使经验风险更小，但很快发现，一味追求训练误差小并不是总能达到很好的预测效果。人们将学习机器对味来输出进行正确预测的能力称为推广性某些情况下。当训练误差过小反而会导致推广能力的下降，这就是几乎所有神经网络研究者都曾遇到的所谓过学习( o v e r i i t t i n g ) 问题从理论上看，模式识别中也存在同样的问题，但因为通常使用的分类器模型都是相对比较简单，因此过学习问题并不像神经网络中那样突出。之所以出现过学习现象，一是因为学习样本不充分，二是学习算法设计不合理，这两个问题是互相关联的。在神经网络中如果对于有限的训练样本来说网络的学习能力过强，足以记住每一个训练样本，此时经验风险很快就可以收敛到很小甚至零，但我们却根本无法保证它对未来新的样本能够得到很好的预测。这就是有限样本下学习机器复杂性与推广性之间的矛盾。在很多情况下。即使我们已知问题中的样本来自某个比较复杂的模型但由于训练样本有限，用复杂的预测函数去学习对样本进行学习的效果通常也不如用相对简单的预测函数，当又噪声存在时就更是如此。从这些讨论中我们可以得出以下基本结论【1 】：在有限样本情况f ，( i )经验风险最小并不一定意味着期望风险最小；( 2 )学习机器的复杂性不但与所研究的系统有关而且要与有限的学习样本想适麻。有限样本情况f 的学习精度和推广性之间的矛盾似乎是不可调和的，采用复杂的学习机器容易使学习误差更小但却往往丧失推广性。因此人们研究了很多弥补方法比如在训练误差中对学习函数的复杂性进行惩罚：或者通过交叉验证的方法进行模型选择以控制复杂度，等等使原来的方法得到了该经。但是这些方法多带有经验性质。缺乏完善的理论基础。推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的荚系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数( 包括使经验风险段小的函数) 经验风险r 。幢) 和实际风险r ( 之间以至少i 一_ 的概率满足如f 关系：r ( a ) r 口心) + j ( h ( 1 n ( 2 h ) ；_ _ 1 ) - i n ( r 4 ) )( 2 - 8 )t1其中h 是函数集的v c 维，l 是样本数。这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险( 训练误差上式右边的第一部分) ，另一部分称作置信范围( 也称v c 置信。上式右边的第二部分) ，它和学习机器的v c 维及训练样本数有关。它反映了根据经验风险最小化顾则得到的学习机器的推广能力。因此称作为推广性的界。它表明。在有限训练样本下。学习机器的v c 维越高( 复杂性越高) 则置信范围越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原阅。机器学习过程不但婴使经验风险最小。还要使v c 维尽缝小以缩小置信范围，才能取得较小的籀6 页支持向量机算法的研究及在说话人识别上的应用实际风险，即对未来样本有较好的推广性。需要指出的是，推广性的界不依赖于p ( x ，y ) ，即不管是训练样本还是测试样本都是相对于某个p 力完全独立的；在通常情况下，经验风险是很难计算出来的，而如果知道了h的值，就很容易计算出置信范围。对于函数集合( x ，口) ，如果口已知，则使置信范围最小的a 取值就是风险最小的学习机器。这是机器学习的基本原理，也是结构风险的主要思想。2 3v c 维为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标，其中最重要的是v c 维( v a p n i kc h e r v o n e n k i sd i m e n s i o n ) 【2 0 】。模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2 “种形式分开，则称函数集能够把h 个样本打散；函数集的v c 维就是它能打散的最大样本数目h 若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大有界实函数的v c 维可以通过用一定的阈值将它转化成指示函数来定义r ”空间有向超平面的v c 维假设数据点所在的空间是r ”，函数集合 厂位) 包含有向直线。对某一分类线而言，一边的点都赋值以类1 ，另一边的点是类1 。图1 中的箭头表示方向，箭头所指方向是类别1 的所在。显然，在平面上，分类线总能把三个点完全区分，但是四个点却不能保证a 所以在平面上用有向直线分类的v c 维是3 。凸二一吖a。一。么fo? 图2 - 1 二维空间有向直线的三点分离现在我们考虑r ”空间有以下定理定理1 在空间里考虑m 点集合，选定一个点为原点，则这m 个点能被有向超平面分离的充分必要条件是除原点以外的其他所有点是线性无关的推论r 一空间有向超平面的v c 维是n + l 。因为总能找到n + 1 个点，选择其中一个为原点，剩余的n 个点是线性无关的。但对于n + 2 个点不行，因为n + 1 个矢量在尺”空间里线性无关第7 页杏支持向量机算法的研究及在说话人识别上的应用是不可能的。v c 维和参数数目v c 维表示了给定分类函数的分类能力。直接感觉是，参数越多的学习算法v c 维越高，参数越少的学习算法v c 维越抵然而事实不是这样的。举一个反例：一个只有一个参数的学习算法的v c 维是无限大。定义一个单步函数日( z ) ，x r ： 口“) = l v x o ；口( x ) = 一l v x s o ) 考虑只有一个参数的函数集，定义为：，( z ，口) 詈o ( s i n ( o z ) ) ，x ，口e r( 2 。9 )如果待分的点的个数为1 ，我们取如下，个点：研= 1 0 - i , i = 1 ，1对于任意的一种二值分类，y l ，y 2 ，y l ，y ie - 1 ，l 分类函数，幢) 都能正确给出分类结果，取a 值如下：a = z ( 1 + 兰，里二2 i 业，c ：_ ，。，可见v c 维是无穷大。有趣的是，尽管我们可以将任意多的点分离开来，我们也会碰到难以分离4 个点的情形。考虑如下4 个等距离排列。但是类别隶属如图所示。卜。- 幽l234图2 - 2 不可分离的4 点设。1 的相位是九= 2 n 口+ j ，要使y 1 = l 需要满足o ( 5 ( f 。那么对于。2 ，其相位m o d 2 石就是2 占，由y 2 = l 得出o d ，r 3 。而在。4 点，条件口3 j 0 为l a g r a n g e 系数。式( 3 4 ) 9 2 t j w 和b 求偏微分并令他们等于0 ，原问题可转化为简单的对偶问题：在约束条件y ，口= 01 1 1口， 0 ，i = 1 ，- n下对口，求解下列函数的最大值：q ( 口) = 口。一寺口。口j y 。y j ( x ，o )i f f i l，j 。l若口? 为最优解，则( 3 - 5 )( 3 6 )( 3 7 )w = 量口? y ，而( 3 8 )i = 1按照优化理论的k u h n t u c k e r 定理，在鞍点，对偶变量与约束的乘积为0 ，即口。( y 。( w x ，) + b ) 一1 = 0 ，f = 1 ，n( 3 - 9 )可见，非0 的。f 所对应的样本仅由最靠近超平面的样本组成，这些样本完全确定了超平面。求解上述问题的结果是：，( = s 驴 ( w z ) + 6 )( 3 1 0 )广义最优分类面最优分类面是在线性可分的前提下讨论的，在线性不可分的情况下些样本不能被超平面正确分类，因此引入松弛变量蠡0 ，( 3 2 ) 式变成y d ( w 而) + 6 】一1 + 点o , i = 1 , 2 ，芹考虑到可能存在一广义最优分类面问题可演化为在条件( 3 1 1 ) 的约束下求下列函数的极小值( w ，。= j 1 ( w ，w ) + c 耋毒c 为某个指定常数。该问题的求解与上面的求解类似。只是条件变为0 s 口c第1 3 页( 3 - 】1 )( 3 - 1 2 )支持向量机算法的研究及在说话人识别上的应用3 2 支持向量机推广能力的控制使分类间隔最大实际上就是对推广能力的控制，这是s v m 的核心思想之一。统计学习理论指出，在n 维空间中，设样本分布在一个半径为r 的超球范围内，则满足条件l i w i l s a的正则超平面构成的指示函数集f ( x ，w , b ) ；s g n ( w + 6 ) ) 的v c 维满足下面的界h m i n ( e r 2 a 2 , ) + l( 3 1 3 )因此使| 1wi i2 最小就是使v c 维的上界最小，从而实现s r m 准则中对函数复杂性的选择。最优分类面和广义最优分类面实际就是把分类函数集s = m x + 6 ) ) 按照其权值的模( 线性可分情况下就是按照分类间隔) 分成了若干规范化子集，每个子集为：& = ( _ 1 - x + b ) ：m c k )( 3 - 1 4 )对于线性可分情况，最优分类面就是在固定经验风险为0 的前提下寻求期望风险的界最小的规范化子集；而在线性不可分情况下广义最优分类面则是在控制错分样本的情况下求期望风险的界的最小。因此说，它们在期望风险的界的意义上是最优的，是结构风险最小化原则的具体实现。值得注意的是，对于n 维空间中的线性函数，其v c 维为n + l ，但根据式( 3 1 3 ) 的结论，在f fwf s a 的约束下其v c 维可能大大减小，即使在十分高维的空间中也可以得到较小v c维的函数集，以保证有较好的推广性。同时我们看到，通过把原问题转化为对偶问题，计算的复杂度不再取决于空间维数，而是取决于样本数，尤其是样本中的支持向量数。这些特点使有效地对付高维问题成为可能。非线性问题对非线性问题，可以通过非线性变换转化为某个高维空间中的线性问题，在变换空间求最优分类面。例如广义线性判别函数问题如果把一个问题在其定义的空间中不是线性可分的，这时可以考虑通过构造新的特征向量，把问题转换到一个新的空间中，这个空间一般比原空间维数增加，但却可以用线性判别函数实现原空间中的非线性判别函数。比如构造y = f ljj 2 】7 ，就可以用占o ) = 口7 y 的线性函数实现亨力= c o + q x + f 2 j 2 的二次判别函数，其中广义权向量口= c 10 2 】7 。实际上，一般来说，对于任意高次判别函数，都可以通过适当的变换转化为另一空间中的线性判别函数来处理。然而，虽然这种变换理论上可以用简单的线性判别函数来解决十分复杂的问题。但由于变换空间中的维数往往很高，容易陷入所谓维数灾难而使问题变得实际上不可实现。因此，广义线性判别函数的思想只是在一些相对不十分复杂的非线性问题中得到了解决。按照广义线性判别函数的思路，要解决一个非线性问题，我们可以设法将它通过非线性变换转化为另一个空间中的线性问题，在这个变换空间求最优或广义最优分类面。这种变换可能比较复杂，因此这种思路在一般情况下不易实现。但是注意到，在上面的对偶问题中，不论是寻优函数还是分类函数都只涉及训练样本之间的内积运算( x ，z ，) ，这样，在高维空第1 4 页兰茎塑苎垫! 堕盟翌塞墨垄塑堡望型圭塑窒旦间实际上只需进行内积运算，而这种内积运算是可以用原空间中的函数实现的，根据泛函的有关理论，只要一种核函数k ( 一，z ，) 满足m e r c e r 条件，它就对应某一变换空间中的内积。m e r c e r 条件：对于任意的对称函数足( x ，x ) ，它是某个特征空间中的内积运算的充分必要条件是，对于任意的9 ( x ) 0 且9 2 ( 砷矗 0+f 3 1 5 )这一条件并不难满足。+因此，在最优分类面中采用适当的内积函数k ( x 。，x ，) 就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加，此时目标函数( 3 7 ) 变为q ( 口) = 乏口一音q 口y f y ，k ( 而，x ，)( 3 - 1 6 )l o loj j o l而相应的分类函数也变为，( x ) = s g n 5 7 a , y 。k ( x 。，x ) + 6 + ( 3 1 7 )i = l这就是支持向量机。概括地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求( 广义) 最优分类面。s v m 分类函数形式上类似于一个神经网络，输出是中间节点的线性组合，每个中间节点对应一个支持向量，如图3 2 所示。主要核函数图3 - 2 支持向量机示意图s v m 中不同的内积核函数将形成不同的算法，目前研究最多的核函数主要有三类一是多项式核函数k ( x ，x i ) = ( z x i ) + l l q所得到的是q 阶多项式分类器；第1 5 页( 3 1 8 )支持向量机算法的研究及在说话人识别上的应用二是径向基函数( r b f ) x - x ，1 2k ( x ，x i ) = e x p - l ( 3 1 9 )盯所得分类器与传统r b f 方法的重要区别是，这里每个基函数中心对应一个支持向量，它们及输出权值都是由算法自动确定的。三是可以采用s i g m o i d 函数作为内积，即k ( x ，x i ) = t a n h o , ( x 。f ) + c )( 3 - 2 0 )这时s v m 实现的就是包含一个隐层的多层感知器，隐层节点数是由算法自动确定的，而且算法不存在类似困扰神经网络方法的局部极小点问题3 3 学习算法分类问题分类学习问题是支持向量机的经典学习算法，这在前面已经介绍过了。但是前面介绍的基于最优分类面的学习算法是基于约束条件下多元二次不等式求解的算法，需要较大的运算量。在这里，我们介绍线性学习问题。上面所述的都是使用二次方程求解。在这里，我们讨论使用一次线性求解的可能性。将目标函数改为：mmm i n c e a ，+ c y 磊】( 3 2 1 )i ii = 1约束条件my 。 口。k ( x 川x ) + b 】1 一点( 3 - 2 2 )一l这里a 。0 ，鲁0 。通过求羔口最小值，我们可以得到一个更加“稀疏”( 即所用点数更少)i = t的解。而且，线性极值问题存在着很多有效的方法可以求解。所以线性分类器是对上述的二次方程求解的有利补充。在二次求解碰到困难时，可以尝试使用线性分类器。线性求解的方法在以下要介绍的异点检测和回归分析中同样可以应用。异点检测现实中，有很多问题不是去划分类别而是检测出奇异的非正常样本。异点检测在很多领域( 例如条件控制、医学诊断等) 有较大的应用潜力。一个可行的办法是对当前已知的数据分布建立模型，得出支持点；这样，可以建立一个判断函数，对于新的样本点，如果函数计算结果为正。则是正常样本，否则，是奇异点。我们试图找到这样一个超球面，包含尽量多的正常点，而其半径尽量小。落在这个超球面以外的都是不正常的点。设该超球面的半径为r ，球心为a 。在训练学习过程中，位于球面外面的点用松弛变量蠡调节目标函数为：1m i n r 2 + 二最】( 3 - 2 3 )l约束条件：第1 6 页兰茎旦苎垫苎鎏盟堕塞墨垄亟堡堡型圭些查旦( x i 一1o f 一口) r 2 + f f( 3 - 2 4 )其中量0 ，c 为某个常数，控制两者之间的权重。目标函数为：1r t lmm一上足以。f 缶2 月2 + 嘉f ! l 缶一点岛铲fa ! i ( r 2 + 缶一( x i x i - 2 a x i + a 砌( 3 - 2 5 )其中a i 0 ，岛0 。求解并用核函数替换以后，转化为求下式的最大值：矽( 口) - a i k ( x i ，。f 卜a i a j k ( x i , 。，)( 3 2 6 )lf ，y f = m ，y f = r t l。对于口f ，y f = m 满足条件口f = l ，而且o a f 玉c 。对于新输入的一个点：，如果满足下式则判断其为异点：k ( z ，：) 一2 口j k ( z ，x ，) + 口，口j k ( x ，x ，) 一只2 0( 3 2 7 )对于r ，可以任取一个口。，0 口， c ，通过上式求得。回归分析首先考虑线性回归。设样本为1 1 维向量，某区域的k 个样本及其值表示为( 一，n ) ，( x k ，y k ) e 走”r线性函数设为：，( j ) = wx + b优化问题是最小化：尺( w 善，善+ ) = ：1w w + c k ( 毒+ 占)t=l条件为：f ( x ) 一y 。等+ s ，i = l ，kf ( x ，) 一y 。s f ? + f ，i = l ，k( 3 - 2 8 )r 3 2 9 )( 3 - 3 0 )( 3 - 3 1 )r 3 - 3 2 )等，毒0 ，i = 1 ，l( 3 - 3 3 )式( 3 3 0 ) c 9 第一项使函数更为平坦，从而提高泛化能力，第二项则为减小误差，常数c对两者做出折中。s 为一正常数，f ( x i ) 与y f 的差别小于f 时不计入误差，大于s 时误差计为i f ( x f ) - y ，f - fa这也是一个凸二次优化问题，引入拉格朗日函数上( ，嵋b ，善手，岛4 ，) = ：1w w + c 圭( 最+ 等) 一t=l圭q 噱+ s h + f ( x ，) 卜圭口一+ f + 儿一( ) 卜圭幅n + 占y ? ) ( 3 - 3 4 )i = 1i = lf l l第1 7 丽支持向量机算法的研究及在说话人识别上的应用其中a i , 口k o ，。，o ，i = 1 ，k函数l 应对w ，b ，氟最小化，对a i , a ；，r i y ；最大化。函数l 的极值应满足条件斋瑚，刍矧，砉瑚素瑚p s s ，从而得到圭( 吼一口? ) = 0( 3 3 6 )i 越w = 圭( 嘶一口：) 坼( 3 3 7 )c 一口，- y i = 0 ，i 1 ，k( 3 - 3 8 )c a ：一，：= o ，i = l - ，k( 3 - 3 9 )将以上4 式代入式( 3 - 3 2 ) ，可以得到优化问题的对偶形式，最大化函擞( 口，口) = 一了1 圭( 口j 口：) ( 口j 一) ( 托z ，) + i ( 毋一口? ) 乃一i ( q + z 批( 3 - 4 0 )0 1 = 1il i其约束为w = 童( a j 一口：) x 。( 3 - 4 1 )0 sa i , a i + s c ，i = 1 ，k( 3 - 4 2 )这也是一个二次优化问题，w 可由式( 3 3 5 ) 得到，b 的求法与分类情况相同。对于非线性回归，与非线性分类相似，首先使用一非线性映射把数据映射到一个高维特征空间，再在高维特征空间进行线性回归，其关键问题也是核函数k (