（计算机科学与技术专业论文）支撑向量机的核参数选择算法.pdf

独创性声明 i i l i irllr l f l li t i t f l li t l iitii i t i i i f y 17 8 7 7 5 7 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 摘要 摘要 支撑向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 是由v a p n i k 等人于上世纪9 0 年代在多年研究统计学习理论的基础上提出的一个新的机器学习方法。由于在学 习和分类问题中出色的泛化性能，支撑向量机( s ) 很快成为了国内外学者 研究的热点并在许多智能信息获取与处理领域都取得了成功的应用。 核函数是支撑向量机( s v l ) 模型的主要元素，它将原空间中的数据映射到 特征空间，使得在输入空间中难以处理的非线性问题可在特征空间中获得线性性 能。然而仅有高性能的核函数对于构造支撑向量机( s v m ) 模型是不充分的， 还要有与之对应的高性能模型选择算法。模型选择算法通过发现最优的模型参 数，从而使支撑向量机( s v m ) 达到较好的训练效率和应用效果。 传统的基于网格的模型参数训练方法可以概括为一个关于惩罚因子c 和高 斯核参数的两层循环优化过程。该算法对于大规模样本集，时间和空间复杂度较 大，同时训练样本中存在的噪音点通常使得分类精度降低。所以减样和除噪( 或 者统称为选择候选支撑向量集) 成为影响支撑向量机( s v m ) 分类性能的重要 因素。 本论文对支撑向量机( s v m ) 核参数的选择，提取候选支撑向量集等问题进 行了学习、研究和探索。首先本文介绍了支撑向量机( s v m ) 研究的现状，以 及支撑向量机( s v m ) 的理论基础和其关键技术核函数。而后就支撑向量机 ( s v m ) 模型选择问题尤其是高斯核函数的参数选择算法进行了详细的介绍和 分析。最后通过对减样和除噪问题进行分析而提出选择候选支撑向量集的算法， 并基于此提出了基于候选支撑向量集的核参数选择方法。实验结果表明该算法在 时空复杂度和准确率上都有较为明显的提高。 关键词支撑向量机；候选支撑向量；参数选择；核函数 i l ；ii a b s t r a c t a b s t r a c t i n y e a r so fr e s e a r c ho ns 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 v m ) ，an e wm a c h i n el e a r n i n gm e t h o dw a sp r o p o s e db yv a p n i ki nt h e9 0 so ft h el a s t c e n t u r y d u et ot h ee x c e l l e n tg e n e r a l i z a t i o np e r f o r m a n c ei nl e a r n i n ga n dc l a s s i f i c a t i o n ， s u p p o r tv e c t o rm a c h i n e ( s v m ) q u i c k l yb e c o m i n gah o tr e s e a r c hs c h o l a r sa th o m e a n da b r o a da n dh a v em a d es u c c e s s f u la p p l i c a t i o n si nm a n ya r e a so fi n t e l l i g e n t i n f o r m a t i o na c q u i s i t i o na n d p r o c e s s i n g k e r n e lf u n c t i o ni st h ep r i m a r ye l e m e n ti ns u p p o r tv e c t o rm a c h i n em o d e l a n di t w i l lm a pt h ed a t ai nt h ea r i g i n a ls p a c et ot h ef e a t u r es p a c e , t h e n ，t h en o n l i n e a r p r o b l e mw h i c hi s d i f f i c u l tt ob es o l v e di nt h e i n p u ts p a c ec a na t t a i n l i n e a r p e r f o r m a n c ei nt h ef e a t u r es p a c e o n l yh i g h - p e r f o r m a n c ek e r n e lf u n c t i o ni sn o t s u f f i c i e n tf o rt h ec o n s t r u c to fs u p p o r tv e c t o rm a c h i n em o d e l ，b u ta l s oa c o r r e s p o n d i n gh i g h p e r f o r m a n c e m o d e ls e l e c t i o n a l g o r i t h m m o d e l s e l e c t i o n a l g o r i t h mw i l lf i n dt h eo p t i m a lm o d e lp a r a m e t e r s ，s ot h a ts u p p o r tv e c t o rm a c h i n e ( s v m ) a c h i e v e sab e t t e re f f i c i e n c y t h et r a d i t i o n a lg r i d - b a s e d s u p p o r tv e c t o rm a c h i n e ( s v m ) a l g o r i t h mc a nb e s u m m a r i z e da sat w o - l o o po p t i m i z a t i o np r o c e s sa b o u tt h ep e n a l t yf a c t o rca n dg a u s s k e r n e lp a r a m e t e r s f o rl a r g e - s c a l es a m p l es e t ，t h et i m ea n ds p a c ec o m p l e x i t yo ft h i s a l g o r i t h m i s l a r g e r , a n dt h en o i s e si nt h et r a i n i n gs a m p l e su s u a l l ym a k et h e c l a s s i f i c a t i o na c c u r a c yl o w e r a sar e s u l t ，e l i m i n a t i n gn o i s e sa n ds a m p l er e d u c t i o n ( m a yb ec a l l e da ss e l e c tc a n d i d a t es u p p o r tv e c t o rs e t s ) a r et h ei m p o r t a n tf a c t o r st h a t i m p a to ns u p p o r tv e c t o rm a c h i n e ( s v m ) c l a s s i f i c a t i o np e r f o r m a n c e i nt h i sp a p e rw ew i l lc o m b i n et h ec u r r e n ts t u d ya th o m ea n da b r o a df o rs u p p o r t v e c t o rm a c h i n ea n dw i l lh a v ea no v e r a l li n t r o d u c t i o no ft h ep a r a m e t e rs e l e c t i o n ， c a n d i d a t es u p p o r tv e c t o rs e l e c t i o na n ds oo ni ns u p p o r tv e c t o rm a c h i n em o d e l f i r s t l y , w ew i l li n t r o d u c et h ec u r r e n ts t u d yo fs u p p o r tv e c t o rm a c h i n ea n dt h e nt h e s u p p o r tv e c t o rm a c h i n et h e o r ya n dk e r n e lf u n c t i o nw i l lb ei n t r o d u c e di nd e t a i l ， s e c o n d l y , t h es u p p o r tv e c t o rm a c h i n em o d e ls e l e c t i o na l g o r i t h m ，s p e c i a l l y , t h e p a r a m e t e r ss e l e c t i o na l g o r i t h mo fg a u s s i a nk e r n e lf u n c t i o nw i l lb ei n t r o d u c e di n d e t a i l l a s t l y , w ew i l li n t r o d u c eh o wt os e l e c tc a n d i d a t ev e c t o r s ，a n db a s e do nt h i s u s i n gt h es e l e c t e dc a n d i d a t ev e c t o r st od e t e r m i n ek e r n e lp a r a m e t e r sw i l l a l s ob e i n t r o d u c e d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mc o m p l e x i t yo ft i m ea n d s p a c e ，t h ea c c u r a c yr a t ec a nb ei m p r o v e ds i g n i f i c a n t l y k e y w o r d ss u p p o r tv e c t o rm a c h i n e ；c a n d i d a t ev e c t o r ；p a r a m e t e rs e l e c t i o n ；k e r n e l f u n c t i o n 1 1 i i v 目录 目录 摘要i a b s t r a c t i i i 第l 章绪论1 1 1 课题研究背景及意义1 1 2 国内外研究发展现状1 1 2 1 支撑向量机理论的研究现状2 1 2 2 支撑向量机学习算法的研究现状。2 1 2 3 支撑向量机应用的研究现状5 1 4 文章的研究内容和组织结构5 第2 章支撑向量机7 2 1 支撑向量机的理论基础7 2 1 1 机器学习的主要问题一7 2 1 2 统计学习理论9 2 1 3 结构风险最小化1 1 2 2 支撑向量机模型1 2 2 2 1 支撑向量机的基本思想1 2 2 2 2 支撑向量机模型分类l3 2 2 2 1 线性支撑向量机1 3 2 2 2 2 非线性支撑向量机17 2 3 支撑向量机中的核函数1 8 2 3 1 核函数的基本性质1 8 2 3 2 核函数的分类1 9 2 3 3 高斯核函数的性质2 0 2 4 本章小结2 2 第3 章支撑向量机核参数选择方法2 3 3 1 解析法2 3 3 2 取样法2 4 3 2 1 简单验证2 4 3 2 2 剩余一交叉验证2 4 3 2 3k 倍交叉验证2 5 3 3 统计学习法2 5 3 4 迭代策略2 7 3 4 1 网格搜索算法2 7 3 4 2 模拟退火( s a ) 算法2 8 3 4 3 遗传算法( g a ) 3 0 3 5 高斯核函数的参数选择过程3 1 3 5 1 惩罚系数c 的选择3 2 v 北京t 业大学工学硕l j 学位论文 3 5 2 高斯核半径y 的选择。3 2 3 6 模型选择应注意的问题3 4 3 7 本章小结3 4 第4 章基于候选支撑向量的核参数选择3 5 4 1 提取候选支撑向量3 5 4 1 1 提取候选支撑向量的研究现状3 5 4 1 2 在原空间中提取候选支撑向量的方法3 6 4 1 3 参数占和曰选择方法3 7 4 2 核参数y 选择方法3 8 4 2 1 理论基础3 8 4 2 2 选择步骤：。4 0 4 3 实验设计及分析4 1 4 3 1 实验设计4 l 4 3 2 结果分析4 4 4 4 本章小结4 5 结论4 7 工作总结4 7 下一步工作展望4 8 参考文献4 9 攻读硕士学位期间所发表的学术论文5 5 致 射5 7 v i 第1 章绪论 第1 章绪论 1 1 课题研究背景及意义 基于数据的机器学习是现代智能技术中的重要方面，研究从观测样本数据 出发寻找规律，对未来数据或无法观测的数据通过这些规律进行预测。包括模 识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。 传统统计学研究的是当样本数目趋于无穷大时的渐近理论，现有学习方法也多 是基于此假设。但在实际问题中，样本数目往往是有限的，因此一些理论上很 优秀的学习方法在实际中的表现往往不尽人意。 v a p n i k 等人提出的统计学习理论( 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 ) 是一种在 小样本情况下研究统计学习规律的理论，该理论的核心思想是通过引入结构风 险最小化准贝i j ( s r m ) 来控制学习机器的容量，从而刻画了过度拟合与泛化能力 之间的关系。在这一理论基础上产生的支撑向量机( s v m ) 学习方法近年来受到 广泛重视，该方法不但引入了结构风险的概念，还采用了核映射的思想。与传 统方法相比，支撑向量机具有的优势体现在：对问题模块化的解决方案，即把 问题划分成核函数与分类器两个不同的模块，这样既克服了传统方法的大样本 要求，又有效地克服了维数灾难及局部极小问题，并在处理非线性问题时显示 了其卓越的优越性，但这种优势只有在核函数及其参数确定的前提下才有意义。 参数选择直接决定着支撑向量机( s v m ) 的训练效率和应用效果。c h e r k a s s h 认为：“支撑向量机模型( s u p p o r tv e c t o rm a c h i n em o d e l ，s v m m ) 的质量依赖 于参数的设置，如何选择参数是应用支撑向量机( s v m ) 的主要问题。c h a p e l l e 1 j 和v a p n i k 也指出：“学习算法决定于参数，参数控制着假设空间的规模以及假 设空间的搜索方式【2 】。因此，参数选择是支撑向量机模型( s v m m ) 选择的关 键 3 - 5 1 。 本文正是在支撑向量机( s v m ) 这一新兴的理论背景和实际分类问题这一 应用背景下，以支撑向量机( s v m ) 方法为基础，探讨了其关键技术一核函数 的几何性质及核参数选择问题的理论基础，并提出了改进的选择核参数的方法； 研究了提取候选支撑向量集( c a n d i d a t e v e c t o r s ) 过程中的关键问题一除噪和减 样，并提出了改进的提取候选支撑向量集的方法。 1 2 国内外研究发展现状 支撑向量机是上世纪9 0 年代以后发展起来的一种新型机器学习方法。由于 基于统计学习理论的坚实基础和其在多个方面突出的性能优势，它一提出，就 北京t 业人学t 学硕i ：学位论文 得到了国内外学者的高度关注并且己经在许多实际工程领域中展示出了良好的 应用潜力。目前，对支撑向量机的理论研究和实际应用两方面都正处于飞速发 展阶段，对其研究主要集中在以下三个方面。 1 2 1 支撑向量机理论的研究现状 虽然支撑向量机的发展时间不长，但是由于其产生是居于统计学习理论的， 因此具有坚实的理论基础。近几年涌现出的大量理论研究成果，使支撑向量机 的理论不断得到完善和发展，为其应用研究奠定了坚实的理论基础。主要的理 论研究成果体现在以下四个方面。 ( 1 )泛化能力的估计 对泛化能力的估计是支撑向量机理论研究的重要内容之一，简单、准确和 有效的估计方法是进行模型选择、参数优化以及核函数优化的基础。一些学者 针对泛化性能进行了研究，提出了多种估计泛化上界方法，它们包括：留一法 1 6 、k 重交叉验证方法【7 】、跨度方法【8 】、j a a k k o l a - h a u s s l e r 方法嘲以及w a h b a - l i n 方法f l o 】等。 ( 2 )核函数的研究 支撑支撑向量机的泛化能力与核函数密切相关，如何构造与实际问题相适 应的核函数一直是支撑向量机研究的重要课题【l l 】。a m a i r t l 2 提出利用实验数据 修难己有核函数，使之逐步与问题相吻合。文献【1 3 】、【1 4 分别针对文本分类、 图像处理等具体问题构造了不同类型的核函数，作为度量样本间的相似性的尺 度，获得的泛化性能优于高斯核或多项式核。 ( 3 )变形s v m 为了扩展支撑向量机的应用范围或者克服它在某些方面的局限，通过改变 其原始优化问题中的函数项、变量或系数，从而获得在某些方面具有突出优势 或者适用于特定问题的变形s v m 。 ( 4 ) 多分类问题 支撑向量机是针对两分类问题产生的，但如何有效地将其扩展到多分类问 题是当前理论研究的一个重要内容。目前，构造多分类s v m 的方法主要有以 下两种。第一种方法的基本思想是通过组合多个二值s v m 分类器来解决多分 类问题【1 5 舶】。第二种方法是直接将二值s v m 扩展成多值s v m t l 7 - 18 1 ，但目前存 在目标函数复杂、计算复杂度高等局限，有待进一步地研究。 1 2 2 支撑向量机学习算法的研究现状 我们把求解支撑向量机的算法称为“学习算法”或“训练算法”。一般来说，经 第1 章绪论 典的梯度下降方法可以用于求解支撑向量机【1 9 】，但是，用此方法的求解效率很 低并且不适用于样本规模很大的情况。可将其原因归结为如下两点：( 1 ) 求解 s v m 的对偶问题需要计算和存储整个核矩阵，空间复杂度与问题规模呈二次方 关裂2 7 】；( 2 ) 在二次型寻优过程中需要进行大量的矩阵运算，时间复杂度至少 与问题规模呈二次方关系【2 刀，随着问题规模的增长，需要的计算时间增长很快。 一些学者针对支撑向量机自身的特点提出了多种快速学习算法，尝试通过不同 途径提高支撑向量机的学习速度并且获得处理大规模数据集的能力，它们包括： 块算法【2 0 1 、分解算法【2 1 - 2 4 、s m o 学习算法等【2 5 之6 】等。同时，也有一些学者从进 一步提升支撑向量机泛化能力的角度出发，将集成技术( e n s e m b l e ) 弓i 入到支撑向 量机的学习过程，研究了支撑向量机的集成学习算法【2 8 铷】。现今，关于支撑向 量机学习算法的研究方兴未艾，它是支撑向量机的研究重点和难点内容之一。 本小节将对几种重要的支撑向量机学习算法的研究现状简要介绍、分析如 下。 ( 1 )块算法 通过块算法( c h u n k i n g ) 来求解支撑向量机是基于这样一个事实：去掉拉格朗 日乘子为零的学习样本并不会影响原问题的解，也就是说求解支撑向量机方得 到的判别函数只与支撑向量有关，而与其他样本数据无关。大多数情况下，非 支撑向量占据了学习样本的大部分，消耗了大量的计算时间和内存资源。因此， 块算法的目标就是通过某种方式迭代地排除非支撑向量。具体做法是：将样本 集分成工作样本集和测试样本集，每次对工作样本集利用二次规划求得最优解， 剔除其中的非支撑向量，用学习结果检验出剩余样本中违反k - k - t 条件的样本， 将它们与本次结果的支撑向量合并成为一个新的工作样本集，然后重新学习， 如此反复下，直到获得最优结果。快算法可以大大减少系统所占的内存。 块算法求解规模随着支撑向量数量的增加而增加，因此使用块算法能减少 时空复杂度的前提是支撑向量的数目比较少，反之，如果支撑向量的数目本身 就比较多，那么随着训练迭代次数的增加，工作样本数也越来越大，就会导致 算法无法实施。 ( 2 )分解算法， o s u n a 等( 1 9 9 7 ) 3 1 】证明了解决支撑向量机训练算法q p 二次规划问题的一个 新集合理论。该理论证明了大的q p 问题可以化解为一系列小的q p 问题，并提 出了一种分解算法。该算法能保证求解q p 问题，而不对数据集的数量做出限 制。只要至少一个违背k - k - t 条件的样本加入前一个子问题的样本中，每一步 将减少目标函数并保持满足所有约束的合理点。o s u n a 等建议对于每一个q p 子问题保持一个恒定大小矩阵，其意味着在每一步加入和删除相同数目的样本 数。利用恒定大小矩阵，允许在任意大小数据集合中进行训练。然而这个方法 仍需要一个数值q p 解法。j o a c h i m s 指出，采用启发式迭代策略会提高算法的 北京工业入学工学顾【：学位论文 收敛速度，并提出一种称为s v m l i g h t 的支撑向量机学习算法，该算法实际上是 分解算法的推广。 ( 3 )序列最小化算法 对于分割算法，需要求解一个q p 问题。众所周知，得到一个数值q p 解的 问题是复杂的，并且还有很多数值精度问题需要处理。微软研究院的j o n nc p l “2 4 】提出了训练支撑向量机的一个新方法：序列最小优化算法，即 s m o ( s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ) 算法。其基本思想是把一个大数据量的 q p 分解为一系列的最可能小的q p 子优化问题。s m o 算法采取了一种极端的 情况，即每次只对两个拉格朗日乘子进行优化。s m o 算法可以分为两个组成部 分：内环和外环。外环根据k k t 优化条件，采用启发式方法从数据集中挑选 出每次要优化的数据，内环则对拉格朗日乘子进行分析求解。s m o 算法解决了 对于大数据量的二次规划问题，其优点是针对两类样本的二次规划问题可以有 解析解的形式，从而避免了多样本情形下的数值解不稳定及耗时问题。同时在 s m o 算法中，内存的需求与训练数据的大小呈线性关系，不需要额外矩阵存储。 这样，它可对非常大的数据进行训练。由于在s m o 中没有使用矩阵算法，其 对于数值精度问题不太敏感。由于采用启发式样本选择策略，标准样本集的实 验结果表明，s m o 算法要比c h u n k 算法快很多倍。k e e r t h i 2 2 】等人对s m o 算法 提出了改进，即在判别最优条件时用两个阈值代替一个阈值，从而使算法更加 合理，收敛更快。 ( 4 )不平衡方法 在数据采集中，往往某些类中有用的数据非常有限，通常仅占全部样本数 据的- d , 部分，我们称这种某类样本数量明显少于其它类样本的数据集为不平 衡数据集。不平衡数据集的分类问题大量存在于我们的现实生活。例如，文本 自动分类【3 3 1 ，分辨恶意的骚扰电话【3 4 】等等。在提到的这些应用中，人们主要关 心的是数据集中的少数类，而且这些少数类的错分代价往往非常大。在实际应 用中，要求对少数类的判别有较高的精度。不平衡数据集的学习问题被公认为 机器学习领域的难题之一，其困难主要来自于不平衡数据集本身的特点：不平 衡数据集的少数类样本不足，此时样本的分布并不能很好的反映整个类的实际 分布。若将一般算法直接应用于不平衡数据集时，由于并未考虑数据的不平衡 性，往往偏向于多数类而把少数类的样本错分，尽管整体的分类精度比较高， 但少数类的分类精度非常低。此时这些传统的方法无法满足实际应用的要求， 为了提高不平衡数据的分类效果，目前己有大量的研究成果出现，但这些方法 都各有优缺点，仍需进一步完善。 ( 5 )减样或除噪法 目前支撑向量机技术虽然己有长足的发展，但支撑向量机本身仍有一些问 题亟待解决，例如对大规模样本集训练的代价太高( 耗时长，占用内存太大) ， 以及当支撑向量太多时，分类运算速度太慢等。为了提高支撑向量机的学习速 度，有关研究人员先后提出不少快速算法，如上面提到的块算法【2 0 1 、分解算法 【3 1 1 、序列最小化算法【2 4 】等。但这些快速学习算法仍然不能彻底解决上面提到 的问题。因为使用上述算法的前提条件是不改变训练集大小。为了有效解决大 样本分类代价高的问题，近几年大量减样方法被提出【3 5 。”】。这些减样方法各有 优缺点，有的甚至比一般算法付出更高的代价。所以，寻找好的减样方法是一 个紧迫而重要的研究课题。 另外，使用支撑向量机分类精度不高的重要原因之一是样本数据含有噪点 ( 或野点) 。为了提高识别或分类的精度，需要预先或同时考虑除噪。近几年出 现了大量的除噪方法【4 0 删，研究除噪问题是支撑向量机目前研究最重要的课题 之一。本文也就除噪和减样问题作了一些研究并且将在后面的章节中给出自己 对样本进行除噪和减样的算法。 1 2 3 支撑向量机应用的研究现状 支撑向量机由于在理论上有很突出的优势，理论研究也比较成熟，近几年 其应用研究得到了长足的发展。到目前，支撑向量机已用于数据分类、回归估 训5 0 1 、时间序列分槲48 4 9 1 、聚类分析、函数逼近等领域。应用最广也最成熟的 自然是在模式识别领域，支撑向量机通过解决手写数字识别问题【4 副第一次成功 的应用在模式识别领域，后来又应用于人脸检测【4 6 1 ，以及文本分类【47 j 等各种领 域。支撑向量机在生物信息领域，如蛋白质的分类，d n a 分析等领域也取得了 较好的效果。m i t ，b e l ll a b 和微软研究所己将s v m 算法应成功地应用于动态 图像的人脸跟踪，信号处理，语音识别，图像分析和控制系统等诸多领域【5 。 支撑向量机自出现以来，应用领域越来越广泛，但在时间序列分析，回归 估计，聚类分析等方面的研究，还有待进一步完善，在分类问题中关键的核函 数选择、核参数选择等问题，还需要进一步研究。 1 4 文章的研究内容和组织结构 本文的主要目标是要通过除噪和减样选择出合适的候选支撑向量集，并用 此数据集来选择合适的核参数。通过选择候选支撑向量集来减少选择核参数的 运算时间，通过选择核参数来减少训练支撑向量机模型的时问，同时以期得到 较好的分类精度。 本文将按照以下结构组织全文内容： 第一章是绪论部分，主要阐述了支撑向量机技术的研究背景和意义，并概 北京1 二业大学t 学硕_ 【j 学位论文 要介绍了国内外相关研究的进展与现状，以及本文研究内容。 第二章对支撑向量机的理论基础和关键技术进行详细介绍。 第三章阐述支撑向量机模型的研究现状，并介绍了几种有代表性的模型选 择方法尤其对高斯核函数的函数性质和参数选择进行了详细的研究和分析。 第四章提出了基于候选支撑向量集的核参数选择方法，并选取标准数据集 做实验，对实验结果进行了分析、对比和总结。 第2 章支撑向量机 第2 章支撑向量机 支撑向量机( ( s u p p o r tv e c t o rm a c h i n e 简称s v m ) 是一种新型通用的机器学习 方法【5 3 】。它建立在结构风险最小化原则基础之上【5 4 1 ，具有很强的学习能力，是 数据挖掘中的一项新技术，主要借助于最优化方法解决数据挖掘中的分类问题， 是数据挖掘技术中一个新的研究热点。本章首先简要介绍支撑向量机( s v m ) 的 理论基础，接着将对支撑向量机( s v m ) 的知识背景、模型的导出与求解以及一 些主要的算法给出比较详细的阐述。 2 1 支撑向量机的理论基础 基于数据的机器学习是现代智能技术中的重要方面，研究从观测样本数据 出发寻找规律，然后利用这些规律对未来数据或无法观测的数据进行预测。现 有机器学习方法包括模式识别、神经网络等在内，共同的重要理论基础之一是 统计学。传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方 法多是基于此假设。在利用实际数据样本进行建模的过程中，传统统计方法对 数据量要求较高，但在实际问题中，样本数目往往是有限的，因此传统统计方 法对一些实际应用效果不理想。 由于传统统计学方法存在上述问题，v a p n i k 等人从上世纪六、七十年代开 始致力于小样本情况下机器学习规律的研究工作，到九十年代中期，建立了一 套全新的理论体系一统计学习理论，随着其理论的不断发展和成熟，也由于神 经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广 泛的重视。 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学 习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决 许多原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ； 同时，在这一理论基础上发展了一种新通用学习方法一支撑向量机。目前支撑 向量机已表现出很多优于已有方法的性能并成为了机器学习和数据挖掘领域的 标准工具。 2 1 1 机器学习的主要问题 机器学习的目的是根据给定的训练样本数据求对某系统输入输出之间依赖 关系的估计，使它能够对未来数据或无法预测的数据进行预测。可以一般地表 北京l ：业人学t 学f 硕i j 学位论文 示为：变量y 与x 存在一定的未知依赖关系，即遵循某一未知的联合概率分布 a ( x ，y ) ( x 和y 之间的确定性关系可以看作是其特例) 。 机器学习问题就是根据一个独立同分布观测样本 ( _ ，y ) ，( 恐，y ：) ，( 而，乃) ， 其中，誓彤，咒r ，f = 1 ，在一组函数f ( x ，们中求一个最优的函数f ( x ，w o ) 对依赖关系进行估计，使期望风险【5 3 】最小。 尺( 们= i l ( y ，f ( x ，w ) d p ( x ，y ) )( 2 1 ) 其中，f ( x ，叻称作预测函数集，w 为函数的广义参数，厂( 五们可以表示任 何函数集；l ( y ，f ( x ，川) 为由于用厂k 们对y 进行预测而造成的损失，是评价 预测准确程度的一种度量，不同类型的学习问题有不同形式的损失函数。而预 测函数通常也称作学习函数、学习模型或学习机器。 对模式识别问题，输出y 是类别标号，两类情况下j ，= o ，1 或 l ，一l ，预测 函数称作指示函数。损失函数可以定义为： 坳胞w ) ) = 黔；舷器 ( 2 - 2 ) 学习的目的就是通过选择一个参数w ，使得学习系统的输出f ( x ，们与期望 输出之间的误差概率最小化，即期望风险( e x p e c t e dr i s k ) 最小化，定义如下式： 尺( 们= i 去l y 一厂( 五w ) id p ( x , y ) ( 2 3 ) 其中p ( x , y ) 为样本空间的实际概率分布。由于p ( x ，y ) 通常是未知的，因此 无法直接算r ( w ) 。但是，对给定的训练集，其经验风险( e m p i r i c a lr i s k ) 如。( w ) ： & r a p ( 1 4 1 ) = 刍喜i 咒一厂( 而，w ) l ( 2 - 4 ) 却是确定的。其中( 五，弘) 为训练样本，为训练集中样本数，即训练集规模。由 统计学习中的大数定理可知，随着训练集规模的扩大，如。( 们将逐渐收敛于 r ( 叻。通过上面表述可以看出，学习的目标在于使期望风险最小化，但是由于 我们无法利用样本信息计算期望风险，而经验风险却可以通过给定的样本信息 来计算，因此我们考虑用经验风险来作为期望风险的一个估计，通过最优化方 法使经验风险最小化。 事实上，用经验风险最小化代替期望风险最小化并没有理论上的保证，只 是直观上合理的想当然做法，但这种思想却在多年的机器学习方法研究中占据 了主要地位。多年来人们将大部分注意力集中到如何使经验风险上最小化的问 题上，而实际上，即使可以假定当璇鱼向于无穷大时( 2 4 ) 趋近于( 2 3 ) 式， 在很多实际问题中，样本数目往往有限。那么在有限样本下得到的结果能使期 望风险也较小吗? 第2 苹支撑向量机 神经网络的过学习问题就是一个反应上面所提到问题的例子。开始，很多 注意力都集中在如何使如。( w ) 更小，但很快就发现，通过经验风险最小化使训 练误差最小并不总能导致好的预测效果。某些情况下，训练误差过小反而会导 致推广能力的下降和真实风险的增加，这就是神经网络中的过学习问题。 在神经网络中，对于有限的样本来说网络学习能力过强，足以记住每个样 本，此时经验风险就可以通过不断学习收敛到很小甚至零，但此时却无法保证 它对未来样本能给出好的预测。 从文献 3 2 】中的例子我们可以看到：学习机器的复杂性与推广性之间的这种 矛盾同样可以在神经网络之外其它学习方法中看到。由此可见，在有限样本情 况下： 1 经验风险最小通常并不一定意味着期望风险最小。 2学习机器的复杂性不但应与所研究的系统有关，而且要和有限数目的样 本相适应。 由于经验风险不能指导小样本情况下建立有效学习和推广方法，于是在这 种情况下统计学习理论便应运而生。 2 1 2 统计学习理论 统计学习理论就是研究小样本统计估计和预测的理论，它被认为是目前针 对小样本统计估计和预测学习的最佳理论，它从理论上比较系统地研究了经验 风险最小化成立的条件，有限样本情况下经验风险与期望风险的关系及如何利 用这些理论找到新的学习原则和方法等问题。统计学习理论的主要内容包括以 下四个方面： 1 1 经验风险最小化准则下统计学习一致性的条件； 2 ) 在这些条件下关于统计学习方法推广性的界的结论； 3 1 在这些界的基础上建立的小样本归纳推理准则； 4 ) 实现新的准则的实际方法( 算法) 。 其中，最有指导性的理论结果是推广性的界。与此相关的一个核心概念是 v c 维。 模式识别方法中v c 维的直观定义是：对一个指示函数集，如果存在h 个样 本能够被函数集中的函数按所有可能的2 6 种形式分开，则称函数集能够把h 个 样本打散；函数集的v c 维就是它能打散的最大样本数目h 。比如规模为3 的 样本被打散是指这3 个样本能够被函数集按以下2 3 = 8 种方式分开，见图2 1 。 若对任意数目的样本都有函数能将它们打散，则函数集的v c 维是无穷大。有 界实函数的v c 维可以通过用一定的阈值将它转化成指示函数来定义。 北京t 业人学t 学硕l 学位论史 ； ， 八 ， o o r i 一 oo t 八 o 。 _ 中 番一 图2 - 1 3 个样本以2 3 = 8 种方式分开 f i g 2 1 t h et h r e es a m p l e sw a r es e p a r a t e dt h r o u g he i g h tw a y s v c 维反映了函数集的学习能力，v c 维越大则学习机器越复杂。然而，目 前尚没有通用的关于任意函数集v c 维计算的理论，只知道一些特殊函数集的 v c 维。比如在，z 维实数空间中线性分类器和线性实函数的v c 维是刀+ l ，而 f ( x ，彳) = s i n ( a x ) 的v c 维则为无穷大。对于给定的学习函数集，如何( 用理论 或实验的方法) 计算其v c 维是当前统计学习理论中亟待研究的一个问题。 统计学习理论系统地研究了各种类型的函数集，经验风险和实际风险之间 的关系，即推广性的界。关于两分类问题，结论是：对指示函数集中的所有函 数( 包括使经验风险最小的函数) ，经验风险r 。( 们叫和实际风险尺( 叻之间以至 少l 一7 7 ，0 7 7 0 3 7 时这个界肯定是松弛 ， 的，当v c 维无穷大时，这个界就不再成立) 。而且，这种推广性的界只有在对 同类学习函数进行比较时