（计算机应用技术专业论文）基于支持向量机的多领域自适应分类方法研究.pdf

摘要 支持向量机是在统计学习理论基础上发展出的一种性能优良的学习机器， 其基本的思想是，在线性情况下，在原空间寻找两类样本的最优分类超平面， 而在非线性情况下，首先将原始模式空间映射到高维的特征空间，并在该特征 空间中寻找最优分类超平面。支持向量机利用一些具有特殊性质的核函数，将 低维空间中的非线性运算实现为特征空间中的内积运算，从而巧妙地避免了计 算高维特征空间。s v m 根据有限的样本信息在模型的复杂性和学习能力之间寻 求最佳折衷，以期获得最好的推广能力。s v m 将机器学习中的最大间隔超平面、 m e r c e r 核、凸二次优化、稀疏解和松弛变量等技术集成在一起，在许多挑战性 的问题中获得目前为止最好的性能。 核函数是支持向量机的重要组成部分之一，也是目前支持向量机的研究热 点之一。不同的核函数产生不一样的支持向量机。基于此，本文对支持向量机 的核函数进行了深入研究，主要工作如下： 1 ) 介绍了v c 维理论和结构风险最小化原则，通过支持向量机引入核函数。 讨论支持向量机参数选择的重要性，并以高斯核函数为例对高斯核半径和惩罚 参数c 进行讨论。 2 ) 通过将核函数分为局部性核函数和全局性核函数，在保持原有核函数基 本特性的基础上，并通过对其进行组合，引入了自适应组合核函数。 3 ) 将构造了的自适应核函数应用于多领域的试验中，并将实验效果与传统 的核函数试验效果进行比较。大量实验数据证明，该核函数较高斯核函数有更 好的学习能力和分类性能。 4 ) 根据试验采集的数据，建立基于支持向量机的多领域的自适应模型库。 关键词：支持向量机，高斯核函数，组合核函数，自适应 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 ei sag o o dl e a r n i n gm a c h i n eb 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 y i nl i n e a rc l a s s i f i c a t i o n ，i tf i n dt h e s u p e rh y p e r p l a n eb e t w e e nw i t ht w o c l a s s s a m p l e si nt h ei n p u ts p a c e i nn o n l i n e a rc l a s s i f i c a t i o n ，i tm a pt h ei n p u td a t ai n t oa h i g h d i m e n s i o n a lf e a t u r es p a c e ，a n dt h e nf i n dt h es u p e rh y p e r p l a n ei nf e a t u r es p a c e a g o o dp r o p e r t yo fs v m i st h a tw en e e dn o tc o m p u t et h em a p p e dp a t t e r n se x p l i c i t l y ， a n di n s t e a dw e o n l yn e e dt h ed o tp r o d u c t sb e t w e e nm a p p e dp a t t e r s ，w h i c ha r ed i r e c t l y a v a i l a b l ef r o mt h ek e r n e lf u n c t i o n i tc o m b i n eh y p e r p l a n eo fm a x i m i z i n gm a r g i n ， m e r c e rk e r n e lw i t hf l a b b yv a r i a b l ea n dt h es p a r s es o l u t i o n ，s oh a v eg o o dp e r f o r m a n c e i nm a n yd e f i a n tp r o b l e ma b o u tm a c h i n el e a r n i n g i no r d e rt o g a i nt h e b e s t g e n e r a l i z a t i o na b i l i t y ， s v mf i n dt h eb e s tc o m p r o m i s eb e t w e e nw i t hc o m p l e x i t yo f m o d e la n dl e a r n i n ga b i l i t yb yu s i n gt h ei n f o r m a t i o no ff i n i t es a m p l e s t h ek e r n e lf u n c t i o ni sa ni m p o r t a n tp a r to fs u p p o i r tv e c t o rm a c h i n e ，a n di ti s o k e yp r o b l e mo fs v m r e s e a r c h d i f f e r e n tk e r n e lf u n c t i o nc a l lp r o d u c ed i f f e r e n ts v m b a s e do nt h i s ，t h ek e r n e lf u n c t i o no fs v mi ss t u d i e di nt h i st h e s i s t h em a i n r e s e a r c hw o r k so ft h i st h e s i sa r e1 i s t e da sb e l o w ： f i m t ，t h i sp a p e ri n t r o d u c e sv 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 k m i n i m i z a t i o np r i n c i p l e i n t r o d u c ek e r n e lf u n c t i o nt h r o u g hs v ma n dd i s c u s st h e i 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 r si nk e m e lf u n c t i o n a sg a u s sk e m e lf u n c t i o nf o r a ne x a m p l e ，w ed i s c u s st h ei n f l u e n c e so fg a u s sk e r n e l r a d i u sa n dp u n i s h m e n t p a r a m e t e rc i ns v m s e c o n d ，t h e r ea r et w ok i n d so f k e r n e lf u n c t i o n ：l o c a lk e r n e lf u n c t i o na n dg l o b a l k e r n e lf u n c t i o n w ep r o p o s ean o v e la d a p t i v ec o m p o u n dk e r n e lf u n c t i o nb yt a k i n g a d v a n t a g eo fl o c a lk e r n e lf u n c t i o na n dg l o b a lk e r n e lf u n c t i o n n e x t ，t h ea d a p t i v ec o m p o u n dk e r n e lf u n c t i o ni sa p p l i e di ns v ma n dc o m p a r e d w i t ho t h e rk e r n e l si nd i f f e r e n tf i e l d se x p e r i m e n t s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t t h en o v e lk e r n e lc a l la c h i e v eb e t t e rp e r f o r m a n c et h a no t h e rk e r n e l s l a s t ，o nt h eb a s i so fe x p e r i m e n td a t a ，w eb u i l dam u l t i - f i l e da d a p t i v em o d e l l i b r a r yb a s e do ns v m i i k e yw o r d s ：s u p p o r t v 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 ，a d a p t i v ek e r n e l c o m p o u n dk e r n e lf u n c t i o n i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 工立蠢e t 期：蝉蚯! ! 吕 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以：痔本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：了专朱 导师( 签名) ：趸r 唯 曰期 岬口f q 武汉理工大学硕士学位论文 第1 章绪论 1 1 人工智能机器学习及其发展 人类的智慧中一个很重要的方面表现在从过去的数据和以往的知识中学习 的能力。通过归纳学习，得到对客观世界的认识和规律。这些规律可以帮助人 类认识现有的世界，同时帮助人类对未知的现象做出正确的预测和判断。人们 把从过去的数据和以往的知识中学习并获取规律的能力称为学习能力。用获得 的规律不仅可以解释已知的实例，而且能够对未知的现象做出正确的预测和判 断，这种能力称为泛化能力【lj 。 在人工智能的研究中，人们用计算机来模拟这种学习能力的问题常常被称 为基于数据的机器学习问题。基于数据的机器学习的任务就是设计某种方法和 模型，通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数 据进行预测或进行判断，其目的最终是使机器具有良好的泛化能力。 1 1 1 机器学习问题 学习是人类具有的一种重要的智能行为，目前对学习的认识，主要来自人 工智能专家西蒙的观剧2 1 。 定义1 1 ：学习就是系统获取知识，使其本身能力增强或者改进的自我完善 过程，使得其在下次执行同样的任务或类似的任务时，能做得更好、效率更高、 适应性更强。 定义1 2 ：机器学习就是用机器来模拟人类学习活动，使机器能够自动获取 新的知识和技能，不断完善其性能，并识别现有的知识。 机器学习是人工智能中一个重要的研究领域，也是人工智能研究的核心课 题之一。任何人工智能系统，在它拥有功能较强的自动知识获取能力之前，都 不会成为名副其实、强有力的智能系统，机器学习技术是解决这一问题的有效 途径。机器学习的研究工作主要围绕着三个基本方面： 1 ) 学习机理的研究。研究人类自身学习机制，即人类获取知识、技能和抽象 概念的能力，从根本上解决机器学习中存在的种种问题。 武汉理工大学硕士学位论文 2 ) 学习方法的研究。探索各种可能的学习方法，建立起独立于应用领域的学 习算法。 3 ) 面向任务的研究。根据特定任务的要求，建立相应的学习系统。机器学习 是从数据中发现知识的一种很有发展前景的技术，机器的自学习功能拓展了人 类处理数据的能力，是解决海量数据问题的希望。 1 1 2 机器学习的发展 基于数据的机器学习是现代智能技术中的一个重要方面，主要研究从观测 数据( 样本) 出发寻找规律，并利用这些规律对未来数据或无法观测的数据进 行预测。2 0 世纪5 0 年代，当时人们就从仿生学的角度开展了研究，希望搞清楚 人类大脑及神经系统的学习机理。1 9 5 7 年f r o s e n b l a r t t ( 罗森勃拉特) 提出了第 一个学习机器的模型，称作感知器，这标志着人们对学习过程进行数学研究的 真正开始。1 9 6 2 年，n o v i k o f f 证明了关于感知器的第一个重要定理，这个定理 是学习理论的开始。 在感知器被提出来之后，人们提出了其他类型的学习机器，如自适应学习 机、隐马尔可夫模型等，但很快发现这些机器只是解决实际问题的工具，并非 学习问题的一般模型。在1 9 8 6 年，研究者提出了同时构造感知器所有神经元的 向量系数的方法，即后向传播方法。这一方法的思想是很简单的，在修改的模 型中，新的神经元的合成是一个连续函数。利用计算神经元系数的梯度，人们 可以应用任何基于梯度的方法来构造对期望函数的逼近。后向传播技术的发现 是感知器的一次飞跃，它标志构造一般性学习机器完成，感知器也被称为神经 网络。 在这期间，统计学习理论获得大发展的时期，产生了经验风险最小化原则 的理论、解决不适定问题的理论、算法复杂度的思想。到九十年代中期，随着 其理论的不断发展和成熟，人们研究的重点转移到对神经网络的这种替代方法 的研究上。统计学习理论是一种专门研究小样本情况下机器学习规律的理论， 与传统统计学相比，该理论针对小样本统计问题建立了一套新的理论体系。在 这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有 限信息的条件下得到最优结果。现在，结构化最小风险原则成了人们研究的热 点，统计学习理论开始受到越来越广泛的重视，并且在完成了学习过程的一般 分析后，开始了最优实现算法的研究。 2 武汉理工大学硕士学位论文 1 1 3 机器学习的实现方法 到目前为止机器学习就其实现方法大致以下三种： 第一种是经典的( 参数) 统计方、法【3 1 。包括模式识别等在内，现有机器学习方 法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这 种方法中，参数的相关形式是己知的，训练样本用来估计参数的值。这种方法 有很大的局限性。首先，它需要己知样本分布形式，这需要花费很大的代价。 还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法 也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上 很优秀的学习方法在实际中表现却可能不尽人意。 第二种是经验非线性方法，如人工神经网络( 姗m 】。这种方法利用已知样 本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一 种统一的数学理论基础。容易陷入局部极小，网络的泛化能力不强，结构的设 计( 例如隐结点的数目的选择) 依赖于设计者的先验知识和经验，缺乏一种有理论 依据的严格设计程序。尽管存在上述问题，这些网络在原有的框架内仍然取得 了许多成功的应用，原因在于这些应用的设计者在设计过程中利用了自己的经 验和先验知识。 第三种是统计学习理论【5 ，6 l ( 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 ) 。与传统统计 学相比，统计学习理论是一种专f - j 究小样本情况下机器学习规律的理论。该 理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理 规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最 优结果。v a p n i k 等人从六、七十年代开始致力于此方面研究，到九十年代中期， 随着其理论的不断发展和成熟，也由于神经网络等方法在理论上缺乏实质性进 展，统计学习理论开始受到越来越广泛的重视。 统计学习理论最突出的优点是其具有良好的推广能力，即对未知样本的正 确判别能力，不会出现人工神经网络学习所出现的过学习现象( o v e rf i t t i n g p h e n o m e n o n ) 。支持向量机是建立在统计学习理论基础上有限样本下的机器学习 的理论框架和通用方法，既有严格的理论基础，又能较好地解决小样本、非线 性、高维数和局部极小点等实际问题，因此成为九十年代末发展最快的研究方 向之一，其核心思想就是学习机器要与有限的训练样本相适应，得到现有信息 下的最优解而不仅仅是样本数趋于无穷大时的最优值，并且由于算法最终将转 3 武汉理工大学硕士学位论文 化成为在线性条件限制下的二次优化问题，从理论上讲，得到的是全局最优解。 对于线性不可分问题，算法将实际问题通过非线性变换转换到高维的特征空间 ( f e a t u r es p a c e ) ，在高维空间中构造线性判别函数来实现原空间中的非线性判别 函数，同时巧妙地解决了维数问题，其算法复杂度与特征空间的维数无关。 1 2 基于支持向量机的自适应相关研究 支持向量机是上世纪9 0 年代以后逐步发展起来的一种新型机器学习方法， 由于具有基于统计学习理论的坚实基础并且在多个方面具有突出的性能优势， 它已经在许多实际工程领域中初步展示了良好的应用潜力。通过对现有研究成 果和相关文献的归纳，可以得到如下结论，即目前国内外对支持向量机理论与 应用的研究主要集中在以下几个方面： 1 ) 现有支持向量机算法的改进与完善。 2 ) 针对大规模数据集的有效学习算法的研究。 3 ) 核函数的选择和构造。 支持向量机算法的潜在应用价值吸引了国际上众多的研究学者的目光。近 年来，研究学者们提出了一些改进的支持向量机算法，并对核函数进行了研究。 同时，支持向量机也成功地应用于模式识别的众多领域，如手写字体与数字识 别、人脸识别和人脸检测、文本分类、信号处理、语音识别、图像分类与识别 等众多研究领域【_ 7 1 。尽管支持向量机在众多研究学者的努力下，在上述三方面都 取得不少成果，但也存在着很多问题和困难。一方面，支持向量机理论和算法 中还存在大量继续研究的问题，如实际问题中对于核函数的选择和构造缺乏理 论指导；另一方面，实际问题中的数据往往是海量的，样本是多类别的，学习 问题对训练速度要求较高，现有算法必须加以改进才能应用。 现有的对支持向量机的应用中大都是通过试验多个核函数及其相应参数的 方法来确定最终所使用的核函数和它们的参数的值。因此核函数及其相应的参 数值的选择就很依赖于个人的经验，并且所得到的核函数及其参数值只对当前 研究的领域有比较好的效果，对于其它应用领域，若果选择它们就很可能得不 到好的结果。因此根据不同的领域自动地选择甚至构造相应的核函数并且自动 地获得相应的参数值就具有一定的研究价值了。目前，国内外也有一些研究学 者在做这方面的工作。胡正平等人【8 】提出了分解子空间自适应核函数综合支持向 4 武汉理工大学硕士学位论文 量机解决思路，较好地改进高维模式识别的性能；朱家元等人【9 】提出了构造和训 练径向基函数网络的自适应参数学习算法，从而提供了生成径向基函数网络的 一个简单和有效的方法；白治江等人【1 0 】提出了自适应递归支持向量机算法，提 高了大型数据集的计算效率；邵壮丰等人【】提出了自适应模糊支持向量机算法， 该模型能有效地提高自适应支持向量机的抗噪能力和预测精度；刘爽等人【l2 j 提 出了一种自动选择参数的加权支持向量机算法，有效地解决类别不均衡和重复 样本问题，且训练模型具有良好的推广性能。 1 3 论文的研究内容及组织结构 本文主要针对基于支持向量机多领域自适应分类方法的研究。着重对支持 向量机中核函数及其参数的选择作了讨论分析。根据全局核函数和局部核函数 的各自优点，构造了一种自适应组合核函数，通过实验表明该核函数具有较高 的推广能力和分类性能。最后基于s v m 算法，实现了基于组合核函数的系统， 该系统具有较好的分类和预测效果。本文共分六章，文章结构及各章主要内容 组织如下： 第1 章序论，介绍了支持向量机多领域自适应分类方法的研究的背景，分 析了国内外文本分类以及支持向量机的研究现状。 第2 章支持向量机理论，介绍了支持向量机理论所蕴含的统计学习思想、 理论模型以及一些经典的实现算法。 第3 章介绍支持向量机中核函数的概念和性质。并以高斯核函数为例初步 讨论了核函数中的参数对支持向量机分类结果的影响。 第4 章介绍全局核函数和局部核函数的特点，并利用全局核函数和局部核 函数的优点，构造了一个自适应组合核函数。 第5 章基于组合核函数分类系统的设计与实现，设计并实现了一个基于组 合核函数的分类系统，对系统结构和主要功能进行了说明。 第6 章总结与展望。对全文的研究工作做出了简要总结，并展望了今后的 研究工作。 5 武汉理工大学硕士学位论文 第2 章统计学习理论及支持向量机 2 1 机器学习的基本问题 2 1 1 问题的表示 机器学习的目的是根据给定的训练样本求对某系统输入、输出之间依赖关 系的估计，使它能够对未知输出做出尽可能准确的预测，可以一般地表示为变 量y 与x 存在一定的未知依赖关系。即遵循某一未知的联合概率f ( x ，y ) ( x 与y 之间的确定性关系可以看作是其特例) ，机器学习问题就是根据刀个独立同分布 观测样本： ( 工1 ，y 1 ) ，( x 2 y 2 ) ，( x 。，y 。) 公式( 2 1 ) 在一组函数 厂( x ，彩) ) 中求一个最优的函数f ( x ，) 对依赖关系进行估计，使期望 风险最小： r ( c o ) = ll ( y ，f ( x ，o g ) ) d f ( x ，y ) 公式( 2 2 ) 其中 f ( x ，c o ) ) 称作预测函数集， 国为函数的广义参数， f ( x ，c o ) 可以表示 任何函数集，l ( y ，f ( x ，c o ) ) 为由于用 f ( x ，c o ) ) 对y 进行预测而造成的损失，不同 类型的学习问题有不同的损失函数，预测函数也称作学习函数、学习模型或学 习机器。有三类基本的机器学习问题：模式识别、函数逼近和概率密度估计。 对模式识别问题，输出y 可分别表示为：y = 0 ，1 或y = 1 ，1 ) 。预测函数 称作指示函数，损失函数可以定义为： 弘( 弘厂( 五们) = 矿i f ( ( y y = 厂f ( ( 毛x , w ) w ) ； 公式( 2 3 ) 使风险最小也就是b a y e s 决策中错误率最小。在函数逼近问题中，y 是连续 变量，损失函数可定义为 l ( y ，厂( x ，w ) ) 2 ( y f ( x ，w ) ) 二 公式( 2 _ 4 ) 即采用最小平方误差准则。对于概率密度估计问题，学习的目的是根据训 练样本确定x 的概率密度，记估计的密度函数为p ( x ，w 1 ，则损失函数可以定义 为 6 武汉理工大学硕士学位论文 弘( y ，厂( x ，国) ) = 一1 。g ( p ( x ，w ) ) 2 1 2 经验风险最小化 公式( 2 5 ) 在上面的问题表述中，学习的目的在于使期望风险最小。但是，我们可以 利用的信息只有公式( 2 1 ) ，公式( 2 2 ) 的期望风险无法计算，因此传统的学习方法 采用了所谓的经验风险最小化原理( e r m ) ，假设概率分布是均匀的，即用样本定 义经验风险：在决策函数集中寻求函数厶，最小化期望风险 r ( a ) = i i 厶( 工) 一y i p ( x ，y ) d x d y 公式( 2 6 ) 这里的厶：r _ 一1 ，1 ) 称为假设函数，集合h = 厶o ) ：a 人) 称为假设空间。 所谓经验风险是指 1 ， ( 允) = l 厶( 葺一m ) l 公式( 2 7 ) i = 1 由于分布p ( x ，y ) 未知，实际上r ( 力) 无法计算，因而也就无法最小化期望风 险。但由于已知p ( x ，) ，) 的一些样本点，且当样本点的个数，趋于无穷大时，经验 风险趋于期望风险。很多函数逼近算法，如神经网络的学习算法和最小二乘法 j 下是基于所谓经验风险最小化原理，即最小化经验风险可使期望风险最小化。 2 1 3 复杂性和泛化性能 在早期神经网络研究中人们总是把注意力集中在如何使屯。( 见) 更小，但很 快便发现，一味追求训练误差小并不是总能达到好的预测效果。人们将学习机 器对未来输出进行正确预测的能力称作泛化性。某些情况下，当训练误差过小 反而会导致泛化能力的下降，这就是几乎所有神经网络研究者都曾遇到的所谓 过学 - - j ( o v e r f i t t i n g ) 问题。从理论上看，模式识别【i3 】中也存在同样的问题，但因 为通常使用的分类器模型都是相对比较简单( 比如线性分类器) ，因此过学习问题 并不像神经网络中那样突出。之所以出现过学习现象，一是因为学习样本不充 分，二是学习机器设计不合理，这两个问题是互相关联的。出现这种现象的原 因，就是试图用一个复杂的模型去拟合有限的样本，结果导致丧失了泛化能力。 在神经网络中，如果对于有限的训练样本来说网络的学习能力过强，足以记住 每一个训练样本，此时经验风险很快就可以收敛到很小甚至零，但学习机器却 根本无法保证它对未来新的样本能够得到好的预测。这就是有限样本下学习机 器的复杂性与推广性之间的矛盾。在很多情况下，即使己知问题中的样本来自 7 武汉理工大学硕士学位论文 某个比较复杂的模型，但由于训练样本有限，用复杂的预测函数去学习对样本 进行学习的效果通常也不如用相对简单的预测函数，当有噪声存在时就更是如 此。事实上，关于学习机器复杂性和泛化能力，有以下的结论： 1 ) 经验风险最小并不一定意味着期望风险最小； 2 ) 学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样本 相适应，我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方 法的理论。 2 2 统计学习理论 统计方法是从观测自然现象或者专门安排的实验所得到的数据去推断该事 务可能的规律性。统计学习理论是在研究小样本统计估计和预测的过程中发展 起来的一种新兴理论。这里所说的“小样本是相对于无穷样本而言的，故只 要样本数不是无穷，都可称为小样本，更严格地说，应该称为“有限样本 。 n o v i k o f f ( 1 9 6 2 ) 证明了关于感知器的第一个定理标志统计学习理论的开始， t i k h o n o v ( 1 9 6 3 ) ，i v a n o v ( 1 9 6 2 ) ，p h i l l i p s ( 1 9 6 2 ) 解决不适定问题的正则化原则的发 现，v a p n i k 和c h e r v o n e n k i s ( 1 9 6 8 ) 提出了v c 熵和v c 维的概念，提出了统计学 习理论的核心概念，并得到了关于收敛速度的非渐进界的主要结论。v a p n i k 和 c h e r v o n e n k i s ( 1 9 7 4 ) 提出了结构风险最小化( s r m ) 归纳原则。v a p n i k 和 c h e r v o n e n k i s ( 1 9 8 9 ) 发现了经验风险最小化归纳原则和最大似然方法一致性的充 分必要条件，完成了对经验风险最小化归纳推理的分析。9 0 年代中期，有限样 本情况下的机器学习理论研究逐渐成熟起来，形成了较完善的理论体系一统计 学习理论( 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 ) 1 4 ，1 5 , 16 1 。s l t 被认为是目前针对 有限样本统计估计和预测学习的最佳理论，它从理论上较为系统地研究了经验 风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利 用这些理论找到新的学习原则和方法等问题。它主要内容包括以下四个方面： 1 ) 基于经验风险原则的统计学习过程的一致性理论； 2 ) 学习过程收敛速度的非渐进理论； 3 ) 控制学习过程的推广能力的理论； 4 ) 构造学习算法的理论。 8 武汉理工大学硕士学位论文 2 2 1v c 维( 函数的多样性) 为了研究经验风险最小化函数集的学习一致收敛速度和推广性，s l t 定义了 一些指标来衡量函数集的性能，其中最重要的就是v c 维( v a p n i k c h e r v o n e n k i s d i m e n s i o n ) 。v c 维：对于一个指示函数( 即只有0 和l 两种取值的函数) 集， 如果存在h 个样本能够被函数集里的函数按照所有可能的2 6 种形式分开，则称函 数集能够把h 个样本打散，函数集的v c 维就是能够打散的最大样本数目。如果 对任意的样本数，总有函数能打散它们，则函数集的v c 维就是无穷大。图2 1 为三个样本的v c 维表示。 o 。 - y 以 o o 图2 - 1 三样本的v c 维图 o o 一 i 一般而言，v c 维越大，学习能力就越强，但学习机器也越复杂。目前还没 有通用的关于计算任意函数集的v c 维的理论，只有对一些特殊函数集的v c 维 可以准确知道。n 维实数空间中线性分类器和线性实函数的v c 维是刀+ 1 。s i n ( a x ) 的v c 维为无穷大。对于给定的学习函数集，如何用理论或实验的方法计算其 v c 维是当前统计学习理论研究中有待解决的一个难点问题。 2 2 2 泛化性的界 s l t 系统地研究了经验风险和实际风险之间的关系，也即泛化性的界l l7 。 根据s l t 中关于函数集泛化性界的理论，对于指示函数集中所有的函数，经验 风险如。( 五) 和实际风险r ( a ) 之间至少以概率l 一刁满足如下关系： 9 武汉理工大学硕士学位论文 r ( a ) 墨唧( 见) + 其中，h 是函数集的v c 维， 1 ) 动l l 练样本的经验风险； 公式( 2 8 ) 刀是样本数。学习机器的实际风险由两部分组成： 2 ) 置信范围( 同置信水平1 一r 有关，而且同学习机器的v c 维和训练样本数 有关) 。 r ( 旯) 8 唧( 允) + 缈( 公式( 2 9 ) f l 在训练样本有限的情况下，学习机器的v c 维越高，则置信范围就越大，导 致实际风险与经验风险之间可能的差就越大。在设计分类器时，不但要使经验 风险最小化，还要使v c 维尽量小，从而缩小置信范围，使期望风险最小【1 8 】。 寻找反映学习机器的能力的更好参数，从而得到更好的界是s l t 今后的重要研 究方向之一。 2 2 3 结构风险最小化 从前面的讨论可以看到，传统机器学习方法中普遍采用的经验风险最小化 原则在样本数目有限时是不合理的，而是需要同时最小化经验风险和置信范围。 事实上，在传统方法中，选择学习模型和算法的过程就是优化置信范围的过程， 如果选择的模型比较适合现有的训练样本，则可以取得比较好的效果。对于模 式识别问题，虽然很多问题并不是线性的，但当样本数有限时，人们用线性分 类器往往能得到不错的结果，其原因就是线性分类器的v c 维比较低，有利于 在样本较少的情况下得到小的置信范围。 有了式公式( 2 9 ) 的理论依据，就可以用另一种策略来解决这个问题。首先 把函数集分解为一个函数子集序列( 或叫子集结构) ：s 。( 2 2s ：c cs nc ； 使各个子集能够按照中的大小排列，也就是按照v c 维的大小排列，即 危j j l 。这样，在同一个子集中置信范围就相同；在每一个子集中寻 找最小经验风险，通常它随着子集复杂度的增加而减小。选择最小经验风险与 置信范围之和最小的子集，就可以达到期望风验的最小，这个子集中使经验风 险最小的函数就是要求的最优函数。这种思想称作有序风险最小化或者结构风 险最小化( 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 原则【l 引。 图2 2 表示了在给定了训练样本的情况下，经验风险、置信范围和风险上界 1 0 武汉理工大学硕士学位论文 随v c 维的变化趋势。图中& 和分别表示最佳函数集和对应的v c 维。图2 2 表达了以下统计学习理论的内容： 1 ) 风险上界是由经验风险和置信范围共同决定的； 2 ) 经验风险和鼍信范围之间是此消彼长的关系，经验风险随v c 维的增大而 减小，置信范围随v c 维的增大而增大； 3 ) 最优函数集对应着风险上界的最低点。 风 险 界 h 图2 - 2 结构化风险最小化 在结构风险最小化原则下，一个分类器的设计过程包括以下两方面任务： 1 ) 选择一个适当的函数子集( 使之对问题来说有最优的分类能力) ； 2 ) 从这个子集中选择一个判别函数使经验风险最小。 第一步相当子模型选择，而第二步则相当于在确定了函数形式后的参数估 计。与传统方法不同的是，在这里，模型的选择是通过对它的推广性的界的估 计进行的。结构风险最小化原则提供了种不同于经验风险最小化的更科学的 武汉理工大学硕士学位论文 学习机器设计原则，但是，由于其最终目的在于在公式( 2 9 ) 的两个求和项之间进 行折衷，实际上实施这一原则并不容易。如果能够找到一种子集划分方法，使 得不必逐一计算就可以知道每个子集中所可能取得的最小经验风险( 比如使所有 子集都能把训练样本集完全正确分类，即最小经验风险都为o ) ，则上面的两步 任务就可以分开进行，即先选择使置信范围最小的子集，然后在其中选择最优 函数。可见这里的关键是如何构造函数子集结构。遗憾的是，目前尚没有关于 如何构造预测函数子集结构的一般性理论。支持向量机是一种比较好地实现了 结构风险最小化思想的方法。 2 3 支持向量机 1 9 6 3 年，v a p n i k 在解决模式识别问题时提出了支持向量方法，这种方法从 训练集中选择一组特征子集，使得对特征子集的划分等价于对整个数据集的划 分，这组特征子集就被称为支持向量( s v ) 。1 9 7 1 年，k i m e l d o r f 提出使用线性不 等约束重新构造s v 的核空间，解决了一部分线性不可分问题。1 9 9 0 年，g r a c e ， b o s e r 和v a p n i k 等人开始对s v m 进行研究。1 9 9 5 年，v a p n i k 正式提出统计学习 理论。 统计学习理论( s t l ) 研究有限样本情况下的机器学习问题，s v m 的理论 基础就是统计学习理论。传统的统计模式识别方法在进行机器学习时，强调经 验风险最小化。而单纯的经验风险最小化会产生“过学习问题”，其泛化能力较 差。根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部 分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险 最小误差，没有最小化置信范围值，因此其泛化能力较差。 v a p n i k 提出的支持向量机( s u p p o r t v e c t o r m a c h i n e ， s v m ) 以训练误差作 为优化问题的约束条件，以置信范围值最小化作为优化目标，即s v m 是一种基 于结构风险最小化准则的学习方法，其泛化能力明显优于一些传统的学习方法。 由于s v m 的求解最后转化成二次规划问题的求解，因此s v m 的解是全局 唯一的最优解s v m 在解决小样本、非线性及高维模式识别问题中表现出许多特 有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 1 2 武汉理工大学硕士学位论文 2 3 1 线性可分的s v m 所谓线性可分的分类问题是指对刀维空间的m 个数据样本 ( x 。，y 。) ，( x ：y ：) ，( ，y 。) 其中鼍为”维空间的数据样本；乃 - 1 ，1 ) 为数据样 本的类别。取值为一1 属于i 类，为1 则为类。存在并求解n 维空间内超平面的 分类面 f ( x ) = 矿z b = 0 使得如下关系成立 一c 班 - ：1 嚣善淼 公式( 2 - 1 0 ) 公式( 2 - 1 1 ) 对线性分类问题，模式识别领域已有充分研究，得到了许多有效的算法。 但在实际中，传统的线性分类算法，如模式识别的分类学习方法、多层感知器、 b p 网、r b f 网等，还存在一些问题问题： 1 ) 分类面仅考虑了对现有样本的分类面的存在与求解，未考虑其泛化能力， 因此泛化能力较弱分类面部不唯一，到底何为最优的分类面； 2 ) 何为最优的分类，最优指标的意义，对有污染的或近似线性分类的数据 样本，可能严格线性分类意义下的分类面不存在，因此鲁棒性较差； 3 ) 对海量数据，求解分类面的时间代价大。因此发展泛化能力强，鲁棒性 佳，求解的代价小的新的分类算法得到重视； 基于s l t ，针对传统分类算法中存在的分类面的问题发展了s v m 。 2 3 2 线性最优分类面的s v m s v m 对于线性分类的问题描述对刀维空间的m 个数据样本 ( x 1y 。) ，( x ：y ：) ，o 。，y 。) 存在并求解聆维空间内满足经验风险最小( 错分最少) 且泛化能力最大( 空白最大) 的最优分类面。所谓的泛化能力最大，即所找到的分 类面，应使得它能够尽可能多的将两类数据点正确的分开，同时使分开的两类 数据点距离分类面最远。 1 3 武汉理工大学硕士学位论文 7 x + b = 1 r x + 6 = 0 图2 - 3 最有分类面 如图2 3 所示，任一样本与分界面的距离为 ，= ( w r x + b ) l l w l l 2 公式( 2 1 2 ) 因此，当选择分类的开关函数为( 2 一1 1 ) n 分界面与最近邻的样本的距离为 ，= 1 l l w l l 公式( 2 - 1 3 ) 因此，s v m 所求的最优分界面可表示为如下目标函数的优化问题 吧警志芝蝥m 。i n l1 w i l 2 蛐2 舶) 雩丽营 。pz w 0 公瓦【2 - 1 4 相应的约束条件为 y i g ( x i ) = m ( t - b ) 1 i = 1 ，2 ，咒公式( 2 1 5 ) s v m 的最优分界面的优化函数为二次型约束条件是线性的，因此是典型的 二次规划问题可由拉格朗日乘子法求解。 2 3 3 线性广义最优分类面的s v m 对于许多实际问题，前面讨论的最优分类面的条件( 2 1 5 ) 过于严格。对存在 数据污染、近似线性分类的情况，可能并不存在一个最优的线性分类面。此外， 对于海量数据，求解最优分类面的时间代价大。因此，需要发展允许有一定范 围内的“错分 ，又有较大分晁区域的最优分类面。实际上，广义最优分类面是 在分类准确性与泛化特性上寻求一个平衡点，分类问题可以找到如图2 4 所示的 广义最优分类面。 1 4 武汉理工大学硕士学位论文 。- ，t ， w ox 十b = 一1 图2 4 广义最有分类面 允许有一定的错分的分类问题通过引入松弛变量磊，可表示为如下优化问题 璁善参 公式( 2 - 1 6 ) 相应的约束条件为 乃g ( 西) = y i ( w 1 t - b ) 1 一缶 i = 1 ，2 ，n 因此，s v m 的广义最优分类问题可表示为如下优化问题 m 础i 观n t _ _ 1 2 + c 善缶 c 0 约束条件 公式( 2 - 1 7 ) 公式( 2 - 1 8 ) 乃g ( 而) = m ( 矿毛- b ) 1 一毒 磊0 i = 1 ，2 ，甩 公式( 2 1 9 ) c 越大，表示分类越严格，允许错分的样本受到的限制越大，错分的样本数 少，越过拟合。我们用基于拉格朗同松弛法来求解广义最优分类面。首先引入 拉格朗日乘子 三= 丢。形0 2 + c 善z + 羔i = 1 a t 1 - 缶- y i ( w r x i - b ) 一兰i = 1 乃磊 公式( 2 乏。， 其中q 与乃为拉格朗日乘子，满足 q ，乃0公式( 2 2 1 ) 根据拉格朗日松弛法的k u h n t u c k e r 条件，有 v 。= w 一嘶m 鼍= 0 a l a b = 嘶乃= p 刎a 缶= c 一一乃= 0公式( 2 2 2 ) 1 5 武汉理工大学硕士学位论文 吒0 【1 一参- y , ( w x , 一6 ) 】= o 乃0乃缶= 0 1 一 w 2 乙q j y t x j a i y i = o 0 - 三= 一丢吩乃乃 矽r ) 矽( 乃) li ， 公式( 2 - 2 9 ) 公式( 2 3 0 ) 相应的函数优化的约束条件仍然为( 2 2 6 ) 。由上式可以看出，分类函数与优化 函数中只是涉及样本x 的特征向量( x ) 之间的内积，而未直接需要求解出特征 向量( x ) 。因此，实际上，在高维的特征空间h 中只需进行特征向量( x ) 内积 运算，而这种内积运算是可以用原空间中的函数实现的，我们甚至不需要知道 变换( x ) 的形式。 根据泛函理论，只要一种核函数k ( 五，而) = r ( 五) 矽( 恐) 满足m e r c e r 条件，它 就对应某一空间中的内积。因此，在最优分类中采用适当的内积函数就可以实 现某一非线性变换后的线性分类，而计算的复杂度没有增加。正是这一思路产 生了现在非常有效的非线性分类的s v m 。 s v m 的这一特点提供了解决算法可能导致的“