（计算机应用技术专业论文）支持向量机的若干问题的研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究所取得的成果。除文中已经注明引用的 内容外，本论文不包含任何其他个人或集体已经发表或撰写 过的科研成果。对本文的研究曾做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律责任由本人承担。 论文作者签名：二4 址 日 期：j 盟蛰组 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定， 同意学校保留或向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅；本人授权贵州大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：蛆导师签名： e l 期：至qq 酞旦 摘要 本文提出了一种改进的支持向量分类方法和一种针对支持向量机的增量 学习算法。根据支持向量机中支持向量不会出现在两类样本集间隔以外的正确 划分区的理论，通过引入类质心，类半径，类质心距等概念，从而较好地解决 快速而准确的删除非支持向量的问题；引入了类向心度的概念，解决了当两类 样本集混淆严重的时候如何更加精确地进行剔除混淆点，保证算法泛化性的问 题。实验表明，采用这种改进的算法既能快速精确地对训练样本进行删减，又 可以当两类训练样本集混淆较严重时又能较好地解决泛化性问题。通过引入相 似度上限、相似度上限，以及可靠度下限等概念，提出了一种可以快速收敛的 支持向量机增量学习算法。实验表明，采用这种改进支持向量机增量算法能使 决策函数快速地向真实的决策函数逼近。 关键词： 支持向量机类质心类半径类向心度增量学习相似度可靠度 中图分类号：t p 3 0 1 6 a b s t r a c t a ni m p r o v e ds v ma l g o r i t h mi sp r o p o s e db a s e do nt h et h e o r yt h a t s u p p o r tv e c t o r sw i11n o ta p p e a ri nt h ea r e a sw h i c ho u to ft h ei n t e r v a l b e t w e e nt w oc l a s s e s b e n e f i t i n gf r o m t h ec o n c e p t so fc l a s s - r a d i u s ， c l a s s c e n t r o i d d i s t a n c ea n dc l a s s c e n t r i d e t a lf o r c e w ec a nd e l e t e t h o s en o n s v s e f f e c t i v e l yw i t hh i g ha c c u r a c ya n dg e n e r a l i z a t i o n c a p a b i l i t ye v e nt h ed a t aw a sp r o m i s c u o u s t h ee x p e r i m e n t a lr e s u l t ss h o w t h a t ，c o m p a r i n gw i t ho t h e ra l g o r i t l l s ： o u rm e t h o da c h i e v e da s a t i s f a c t o r yr e s u l t a ni m p r o v e di n c r e m e n t a ls v ma l g o r i t h mi sa l s o p r o p o s e d ， w h i c hi sb a s e do nt h e c o n c e p t s o f c o m p a r a b i l i t y a n d d e p e n d a b i l i t y t h ee x p e r i m e n t a lr e s u l t ss h o w t h a t t h ei m p r o v e d i n c r e m e n t a ls v ma l g o r i t h mc a nm a k ed e c i s i o n f u n c t i o na p p r o a c ht h er e a l o n eq u i c k l y 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 ，c l a s s c e n t r o i d ，c l a s s r a d i u s ， c l a s s c e n t r o i d d i s t a n c e ， i n c r e m e n t a ll e a r n i n g ， c o m p a r a b i l i t y ， d e p e n d a b i l i t y ， 2 第一章绪论 本章首先阐明了本文所选课题的研究背景，简要回顾了机器学习的发展， 然后重点介绍支持向量机的研究现状，以及所选课题的研究价值，最后综述了 本文的主要研究工作和创新点。 1 1 选题的研究背景和意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以 非常方便地获取和存储大量的数据。面对大规模的海量的数据，传统的数据分 析工具( 如管理信息系统) 只能进行一些表层的处理( 如查询、添加，删除等) ， 而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫 乏”的困境，人们迫切需要一种能够智能地自动地把数据转换成有用信息和知 识的技术和工具，这种对强有力数据分析工具的迫切要求使得机器学习和数据 挖掘技术应用而生。 基于数据的机器学习是一种重要的知识发现方法，也是现代智能技术中的 重要内容。其研究从观测数据( 样本) 出发寻找规律，利用这些规律对未来数据 或无法观测的数据进行预测。迄今为止，关于机器学习还没有一种被共同接受 的理论框架，关于其实现方法大致可以分为以下三种： 第一种是经典的( 参数) 统计方法。包括模式识别等在内，现有机器学习方 法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这 种方法中，参数的相关形式是己知的，训练样本用来估计参数的值。这种方法 有很大的局限性。首先，它需要己知样本分布形式，这需要花费很大的代价， 有的时候甚至是不可能的。其次，传统统计学研究的是样本数目趋于无穷大时 的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往 是有限的，因此一些理论上很优秀的学习方法在实际中表现却可能不尽人意。 第二种方法是经验非线性方法，如人工神经网络( a n 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 l t ) “1 。与传统 统计学相比，统计学习理论是一种专门研究小样本情况下机器学习规律的理论。 该理论针对小样本统计问题建立了套新的理论体系，在这种体系下的统计推 理规则不仅考虑了对渐近性能特别是泛化性的要求，而且追求在现有有限信息 的条件下得到最优结果。y a p n i k 等人从六、七十年代开始致力于此方面研究， 到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等方法在理 论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。 统计学习理念的一个核心概念就是v c 维( v cd i m e n s i o n ) 概念，它是描述 函数集或学习机器的复杂或者说是学习能力( c a p a c i t yo ft h em a c h i n e ) 的一个 重要指标，在此概念基础上发展出了一系列关于统计学习的一致性 ( c o n s i s t e n c y ) 、收敛速度、泛化性能( g e n e r a l i z a t i o np e r f o r m a n c e ) 等的重要 结论“”。 统计学习理论是建立在一套较坚实的理念基础之上的，为解决有限样本学 习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决 许多原来难以解决的问题( 比如神经网络结构选择问题、局部极小点问题等) ， 同时，在这一理论基础上发展了一种新的通用学习方法：支持向量机( s u p p o r t v e c t o rm a c h i n e 或s v m ) “，己初步表现出很多优于已有方法的性能。 目前，国际上对这一理论的讨论和进一步研究已经有了1 0 年左右的时间， 而我国在此领域开展研究和国际也越来越接轨，因此，加强这一方面的研究工 作，使我国在这一领域的研究和应用能够尽快赶上并且具有国际先进水平具有 十分重要的意义。 1 2 支持向量机算法目前的研究现状 由于s 方法较好的理论基础和它在些领域的应用中表现出来的与众不 同的优秀的泛化性能，近年来，许多关于s v m 方法的研究，包括算法本身的改 进和算法的实际应用，都陆续提了出来。尽管s w 算法的性能在许多实际问题 的应用中得到验证，但是传统的支持向量机算法在计算上存在着一些问题，包 括训练算法速度慢、算法复杂而难以实现以及检测阶段运算量大，支持向量机 抗击噪音以及孤立点能力差，多类分类问题等等。 本文将从提高支持向量机训练速度、预处理方法、多类分类方法回归 ( s w r ) 、应用等五方面介绍支持向量机算法的研究现状。 4 1 2 1 提高支持向量机训练速度的研究 传统的利用标准二次规化技术解决对偶问题的方法是训练算法慢的主要原 因：首先，s v m 方法需要计算和存储核函数矩阵，当样本点数目较大时，需要很 大的内存，例如：，当样本点数目超过4 0 0 0 时，存储核函数的矩阵需要多达1 2 8 兆内存，其次，s v m 在二次型寻优过程中要进行大量的矩阵运算，多数情况下， 寻优算法是占用算法时问的主要部分。s v m 方法的训练运算速度是限制它的应用 的主要方面，近年来人们针对方法本身的特点提出了许多算法来解决对偶寻优 问题，大多数算法的一个共同思想就是循环迭代：将原问题分解成为若干子问 题，按照某种迭代策略，通过求解子问题，最终使结果收敛到原问题的最优解。 根据子问题的划分和迭代策略的不同，又可分为二类。 第一类是所谓的“块算法”( c h u n k i n ga l g o r i t h m ) “”，它最早在1 9 9 5 年， 由c o r t e ：和v a p n i k 提出。“块算法”基于、这样的事实，即去掉l a g r a n g e 乘子 等于零的训练样本不会影响原问题的解。对于给定的训练样本集，如果其中的 支持向量是己知的，寻优算法就可以排除非支持向量，只需要对支持向量计算 权值( 即l a g r a n g e 乘子) 即可。实际上支持向量是未知的，因此“块算法”的目 标就是通过某种迭代方式逐步排除非支持向量。具体的作法是，选择一部分样 本构成工作样本集进行训练，剔除其中的非支持向量。并用训练结果对剩余样 本进行检验，将不符合训练结果( 一般是指违反k a r u s h k u h n t u c k e r 最优化 条件) 的样本( 或其中的一部分) 与本次结果的支持向量合并成为一个新的工作 样本集，然后重新训练。如此重复下去直到获得最优结果，其收敛性得到了证 明。这种方法当支持向量的数目远远小于训练样本数目时，“块算法”显然能 够大大提高运算速度。然而，如果支持向量的数目本身就比较多，随着算法迭 代次数的增多，工作集样本也会越来越大，算法依旧会变得十分复杂。 第二类方法把问题分解成为固定样本数的子问题：- r 作样本集的大小固定 在算法速度可以容忍的限度内，迭代过程中只是将剩余样本中部分“情况最糟 的样本与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样 本集的大小，也不改变工作集的规模，而只对支持向量中的一部分进行优化。 这个思想最早由o s u n a “1 等人提出来的。在o s u n a 算法中，首先建立一个工作集， 保持其大小不变，在解决每个二次规划子问题时，先从工作集中移走一个样本， 并加入一个不满足k k t 条件的样本，再进行优化。固定工作样本集的方法和块算 法的主要区别在于：块算法的目标中仅包含当前工作样本集中的样本，而固定工 作样本集方法虽然优化变量仅包含工作样本，其目标函数却包含整个训练样本 集，即工作样本集之外的样本的l a g r a n g e 乘子固定为前一次迭代的结果，而不 是像块算法那样设为0 。而且固定工作样本集方法还涉及到一个确定换出样本 5 的问题( 因为换出的样本可能是支持向量) 。这样，这一类算法的关键就在于找 到一种合适的迭代策略使得算法最终能收敛并且较快地收敛到最优结果。1 9 9 9 年，p l a t 在中提出s m o ( s e q u e n t i a lm i n i m a io p t i m i z a t i o n ) 算法。将工作样本 集的规模减到最小( 两个样本) 。之所以需要两个样本是因为等式线性约束的存 在使得同时至少有两个l a g r a n g e 乘子发生变化。由于只有两个变量，而且应用 等式约束可以将其中一个用另一个表示出来，所以迭代过程中每一步的子问题 的最优解可以直接用解析的方法求出来。这样，算法避开了复杂的数值求解优 化问题的过程，此外，p l a t 还设计了一个两层嵌套循环分别选择进入工作样本 集的样本，这种启发式策略大大加快了算法的收敛速度。标准样本集的实验结 果证明，s m o 表现出在速度方面的良好性能。文献对s m o 方法的收敛性进行了证 明。子问题的规模和迭代的次数是一对矛盾，s m o 将工作样本集的规模减少到2 ， 一个直接的后果就是迭代次数增加。针对p l a t 的s m o 算法，k e e r t h i 等通过对s v m 算法的分析中提出了重大改进，即在判别最优条件时用两个临界值代替一个临 界值，从而使算法更合理，更快。其收敛证明通过实际数据的对比，证明确实 比传统s m o 快。同时也指出s m o 算法应用于回归等类似的问题。r o n a n “”将考虑了 上述改进的s m o 算法应用于分类和回归问题，实现了比s v ml i g h t 更强的软件包。 p a r l o r 。1 提出了速度快于s m o 方法的b o o s t - s m o 方法。为了弥补s m o 在求解线性支 持向量机当中的不足，k a i - m i nc h u n g 提出了线性支持向量机的分解算法1 。 h u s h 等人迸一步从形式上统一了算法c h u n k i n g 、s m o g s m o 工作集的生成方法， 进而将上述分解算法置于一个统一的框架之下，并给出了关于收敛性的证明。 1 2 2 支持向量机多类分类方法的研究 支持向量机最初是为两类分类问题而设计的，如何有效地将其应用到多类 分类问题，是当前支持向量机研究的一个重要方面目前，构造s v m 多值分类器 的方法主要有两类，一类是同时考虑多类的分类方法：v a p n i k ，w e s t o n “”在1 9 9 9 所提出的多值分类算法，与前面方法对等的还有c r a m m e ra n ds i n g e r 3 在2 0 0 0 年提出的多类分类算法。g u e r m e u r 。”根据多类判别函数的近似提出一种基于一 致收敛的多类分类方法，此外还有一些其它的多类方法。这种算法在经典s v m 理论的基础上，重新构造多类分类模型，通过s v m 方法对新模型的目标函数进行 优化，实现多类分类。但是，这类算法选择的目标函数十分复杂，实现困难， 计算复杂度也非常高。 另一类算法的基本思想是通过组合多个二值子分类器实现对多类分类器的 构造。卜a _ r ( 卜a g a i n s t r e s t ) 方法，对于n 类问题，构造n 个分类器，第i 个 s v m 用第1 类中的训练样本作为正的训练样本，而将其它的样本作为负的训练样 6 本。最后的输出是两类分类器输出最大的那一类( 此时，两类分类器的判别函数 不用取号函数s g n ) 。其缺点是它的泛化误差无界。卜a _ 1 ( 1 - a g a i n s t 一1 ) 方法。 它是由k e r r “”提出的，该算法在n 类训练样本中构造所有可能的两类分类器，每 类仅仅在n 类中的2 类训练样本上训练，结果共构造k = n ( n - i ) 2 个分类器。组合 这些两类分类器很自然地用到了投票法，得票最多( m a xw i n s ) 的类为新点所属 的类。u - k e r 用该方法训练多类s v m 取得了很好的结果。算法的缺点是：如果单 个两类分类器不是规范化的，则整个n 类分类器将趋向于过学习并且分类器的数 目n ( n - i ) 2 随着类数n 急剧增加，导致在决策时速度过慢。 1 2 3 支持向量机回归的研究 支持向量机最初是为分类问题而设计的，它己成功应用于o c r ( o p t i c a l c h a r a c t e rr e c o g n i t i o n ) 和目标识别任务。但近些年来，支持向量机在回归算 法的研究方面也表现了极好的性能 支持向量机回归分为线性回归和非线性回归，对于线性回归，考虑用线性 回归函数估计样本数据。对于非线性回归，其基本思想是通过一个非线性映射 小将数据x 映射到高维特征空间( h i l b e r t 空间) ，并在这个空间进行线性回归。 这样，在高维特征空间的线性回归就对应于低维输入空间的非线性回归，其具 体实现是通过核函数来实现的，这样就免去了在高维空间计算复杂的点积运算。 和支持向量机的分类算法相似，支持向量机的回归算法最终也转化为一个求解 凸二次规划问题，并且其二次规划的规模为同样样本数量下分类问题的二倍， 因此，支持向量机回归同样面临着当样本较多时计算量大，训练速度慢的缺点。 因此提高支持向量机回归问题的训练速度便成为支持向量机研究的一个重要方 面。 陶卿“”等提出一种基于支持向量机分类的回归方法，通过对样本点集的适 当变换，提出一种将回归问题转化为二分类问题的新思想，从而方便求解，一 方面这与前馈神经网络的理论体系相一致，另一方面也使得回归问题中支持向 量的几何意义更明显，为分类问题的研究成果应用于回归问题奠定了理论基础。 1 2 4 支持向量机的应用研究 s v m 方法在理论上具有突出的优势，贝尔实验室率先对美国邮政手写数字库 识别研究方面应用了s 方法，取得了较大的成功。在随后的近几年内，有关s v m 的应用研究得到了很多领域的学者的重视，在人脸检测、认证和识别、说话人 语音识别、文字手写体识别、图像处理、及其他应用研究等方面取得了大量的 7 研究成果。 人脸检测、验证和识别 o s u n a “最早将s v l l 应用于人脸检测，并取得了较好的效果。其方法是直接 训练非线性s v m 分类器完成人脸与非人脸的分类。由于s 的训练需要大量的存 储空间，并且非线性s v m 分类器需要较多的支持向量，速度很慢。为此，马勇m ， 等提出了一种层次型结构的s v m 分类器，它由一个线性s v m 组合和一个非线性s v m 组成。检测时，由前者快速排除掉图像中绝大部分背景窗口，而后者只需对少 量的候选区域做出确认；训练时，在线性s v m 组合的限定下，与“自举 ( b o o t s t r a p p i n g ) ”方法相结合可收集到训练非线性s v m 的更有效的非人脸样本， 简化s 训练的难度，大量实验结果表明这种方法不仅具有较高的检测率和较低 的误检率，而且具有较快的速度。人脸检测研究中更复杂的情况是姿态的变化。 叶航军等提出了利用支持向量机方法进行人脸姿态的判定，将人脸姿态划分成6 个类别，从一个多姿态人脸库中手工标定训练样本集和测试样本集，训练基于 支持向量机姿态分类器，分类错误率降低到1 6 7 ，明显优于在传统方法中效果 最好的人工神经元网络方法。在人脸识别中，面部特征的提取和识别可看作是 对3 d 物体的2 d 投影图像进行匹配的问题。由于许多不确定性因素的影响，特征 的选取与识别就成为一个难点。凌旭峰等及张燕昆等分别提出基于p c a 与s v m 相 结合的人脸识别算法，充分利用了p c a 在特征提取方面的有效性以及s v m 在处理 小样本问题和泛化能力强等方面的优势，通过s v m 与最近距离分类器相结合，使 得所提出的算法具有比传统最近邻分类器和b p 网络分类器更高的识别率。王宏 漫“等采用分阶段淘汰的支持向量机分类机制进行识别。对两组人脸图像库的 测试结果表明，基于s v m 的方法在识别率和识别时间等方面都取得了较好的效 果。 文字手写体识别 贝尔实验室对美国邮政手写数字库进行的实验，人工识别平均错误率是 2 5 ，专门针对该特定问题设计的5 层神经网络错误率为5 1 ( 其中利用了大量 先验知识) ，而用3 种s 方法( 采用3 种核函数) 得到的错误率分别为4 o 、4 1 和4 2 ，且是直接采用1 6 1 6 的字符点阵作为输入，表明了s w 的优越性能。手 写体数字o 9 的特征可以分为结构特征、统计特征等。柳回春等在u k 心理测试 自动分析系统中组合s v m 和其他方法成功地进行了手写数字的识别实验。另外， 在手写汉字识别方面，高学等提出了一种基于s v m 的手写汉字的识别方法，表明 了s v m 对手写汉字识别的有效性。 图像处理 ( 1 ) 图像过滤。一般的互联网色情图像过滤软件主要采用网址库的形式来封 锁色情网址或采用人工智能方法对接收到的中、英文信息进行分析甄别。支持 向量机分类和最近邻方法校验的多层次图像处理框架，达n 8 5 以上的准确率。 ( 2 ) 视频字幕提取。视频字幕蕴含了丰富语义，可用于对相应视频流进行高级语 义标注。将原始图像帧分割为n * n 的子块，提取每个子块的灰度特征；然后使用 预先训练好的s v m 分类机进行字幕子块和非字幕子块的分类；最后结合模型和后 期处理过程，实现视频图像字幕区域的自动定位提取。实验表明取得了良好的 效果。( 3 ) 图像分类和检索。由于计算机自动抽取的图像特征和人所理解的语义 问存在巨大的差距，图像检索结果难以令人满意。近年来出现了相关反馈方法， 以s v m 为分类器，在每次反馈中对用户标记的正例和反例样本进行学习，并根据 学习所得的模型进行检索，使用由9 9 1 8 幅图像组成的图像库进行实验，结果表 明，在有限训练样本情况下具有良好的泛化能力。 1 3 本文的主要内容及创新点 本文针对机器学习中的支持向量机方法进行几方面的研究，具体内容如下： 第一章为本文的绪论部分，本章首先阐明了本文所选课题的研究背景，指 出所选课题的研究意义，然后重点介绍支持向量机目前研究主要集中的几个方 面以及研究现状，最后总结了本文的主要研究工作和创新点。 第二章首先简要介绍了机器学习的基本方法，然后引出统计学习理论的基 本思想，并对统计学习理论的一些基本概念进行了介绍，最后详细介绍了支持 向量机的有关分类的基本理论知识，以此作为以后各章所研究的基础。 第三章针对支持向量机分类算法支持向量的选择提出了一种提高支持向 量机分类速度的新方法，并通过实验验证了本章所提方法的有效性。 第四章针对支持向量机分类算法在样本混淆严重情况下分类精度不高的 问题，并针对目前方法存在的缺点，提出了一种基于类向心度概念的支持向量 机分类算法，并通过了实验验证。 第五章针对以往支持向量机增量学习的处理机制的缺陷，并提出了一种新 的支持向量机增量学习算法，并进行了实验验证。 第六章是全文的总结和展望。 本文的主要创新在于： ( 1 ) 通过对支持向量训练速度慢的主要原因进行分析，针对支持向量机分类算 法支持向量的选择，提出了一种基于样本几何分布的提高支持向量机分类 速度的新方法，并通过实验验证了本章所提方法的有效性。 ( 2 ) 针对支持向量机分类算法在样本混淆严重情况下分类精度不高的问题，并 针对目前方法存在的缺点，提出了一种基于类向心度概念的的支持向量机 分类算法，并通过了实验验证。 9 ( 3 ) 针对出以往支持向量机增量学习的处理机制的缺陷，并提出了一种新的支 持向量机增量学习算法，并进行了实验验证。 l o 第二章统计学习理论以及支持向量机理论 本章首先描述了支持向量机背后的基本思想，介绍了机器学习的基本方法 及其存在的缺点，从而引出统计学习理论的基本思想，在此基础之上，讨论了 简单的线性情况下的最优超平面的构造，然后进一步将其推广到非线性情况。 其次，对基于不同核函数的支持向量机方法与相对应的神经网络方法进行了比 较。 2 1引言 机器学习主要研究如何从一些观测数据出发得出目前尚不能通过原理分析 得到的规律，利用这些规律去分析客观现象，对未来数据或无法观测的数据进 行预测现实世界中确实存在大量人类尚无法准确认识但却可以进行观测的事 物，因此机器学习在从现代科学、技术到社会、经济等各领域都有着十分重要 的应用人的智慧中一个很重要的方面是从实例中学习知识的能力，即通过对已 知事实的分析总结出规律，预测无法直接观测的事实。在这种学习中，重要的 是举一反三的能力，即利用学习得到的规律，不但可以较好地解释己知事实， 而且能够对未来或无法观测的现象做出正确的预测和判断，这叫做推广能力。 在机器学习的研究中，希望用机器来模拟人的这种能力，这就是机器学习理论 的出发点。机器学习的目的是，设计某种方法，通过对己知数据的学习，找到 数据内在的相互依赖关系，从而对未知数据进行预测或对其性能进行判断。 统计学习理论从控制学习机器复杂度的思想出发，提出了结构风险最小化 原则。该原则使得学习机器在可容许的经验风险范围内，总是采用具有最低复 杂度的函数集。支持向量机是在统计学习理论基础上发展出的一种性能优良的 学习机器。其基本的思想是，在线性情况下，在原空间寻找两类样本的最优分 类超平面，而在非线性情况下，首先将原始模式空间映射到高维的特征空间， 并在该特征空间中寻找最优分类超平面。支持向量机利用一些具有特殊性质的 核函数，将特征空间中的内积运算转化为低维空间中的非线性运算，从而巧妙 地避免了高维空间中的计算问题。 2 2 机器学习的基本方法 2 2 1 学习问题的一般表示 机器学习一般地可以表示为：变量y 与x 存在一定的未知依赖关系，即遵循某 一未知的联合概率f ( x ，y ) ，( x 和y 之间的确定性关系可以看作是其特例) ，机器学 习问题就是根据1 个独立同分布观测样本： ( x 1 ，y 1 ) ，( x 2 ，y 2 ) ，( x 1 ，y t ) ( 1 ) 在一组函数 f ( x ，w ) ) 中，求一个最优的函数f ( x ，w o ) ，用以对x 和y 之间的依赖关 系进行估计，使期望风险最小，即： m i n r ( w ) = il ( y 文x ，w ) ) a f ( x ，y ) ( 2 ) 其中，预测函数集 f ( x ，w ) ) 可以表示任何函数集合，w 为函数的广义参 数，l ( y ，f ( x ，w ) ) 为用f ( x ，w ) 对y 进行预测而造成的损失，不同类型的学习问题有 不同形式的损失函数 因此，机器学习问题也可以表示为，从一组独立同分布的观测样本出发通 过最小化风险泛函r ( w ) ，确定学习机器的广义参数w 的过程。 2 2 2 经验风险最小化原则 统计模式识别的传统方法都是在样本数目足够多的前提下进行研究的，所 提出的各种方法只有在样本数趋于无穷大时其性能才有理论上的保证而在实 际的应用中，样本数目通常是有限的。于是，人们采用了所谓的经验风险最小 化( 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 ) 准则，即用样本定义经验风险 r e - 一( w ) = l ( 弘，f ( x i ，w ) ) ( 3 ) l 王l 机器学习就是要设计学习算法，使r 。，( w ) 最小化，作为对式( 2 ) 的估计。多 年来，人们将大部分注意力集中到如何更好地最小化经验风险上，但是，从期望 风险最小化到经验风险最小化并没有可靠的理论依据首先r 。( w ) 和r ( w ) 都是 w 的函数，概率论中的大数定理只说明了在一定条件下，当样本数趋于无穷大 时，r 。( w ) 将在概率意义上趋近于r ( 们，并没有保证使r 。，( w ) 最小的w i 与使r ( w ) 最小的w i 是同一个点，更不能保证r 。( 动能够趋近于r ( w i ) ：其次，即使有办法使 这些条件在样本数无穷大时得到保证，也无法认定在这些前提下得到的经验风 险最小化方法在样本数有限时仍能得到好的结果。多年来，经验风险最小化原 则作为解决模式识别等机器学习问题的基本思想，几乎统治了这个领域内的所 有研究。大部分的研究者们把注意力集中在如何更好地逼近最小化经验风险的 最优解上。 2 2 3 模型复杂度与推广能力 经验风险最小化原则希望通过最小化训练误差来实现最小化测试误差的目 的。在早期神经网络研究中人们总是把注意力集中在如何使r 。( w ) 更小，但很 快便发现，一味追求训练误差小并不是总能达到好的预测效果。人们将学习机 器对未来输出进行正确预测的能力称作推广性。某些情况下，当训练误差过小 反而会导致推广能力的下降，这就是几乎所有神经网络研究者都曾遇到的所谓 过学习( o v e r f i t t i n g ) 问题。从理论上看，模式识别中也存在同样的问题，但因 为通常使用的分类器模型都是相对比较简单( 比如线性分类器) ，因此过学习问 题并不像神经网络中那样突出。之所以出现过学习现象，一是因为学习样本不 充分，二是学习机器设计不合理，这两个问题是互相关联的。出现这种现象的 原因，就是试图用一个复杂的模型去拟合有限的样本，结果导致丧失了推广能 力。比如在神经网络中，如果对于有限的训练样本来说网络的学习能力过强， 足以记住每一个训练样本，此时经验风险很快就可以收敛到很小甚至零，但学 习机器却根本无法保证它对未来新的样本能够得到好的预测。这就是有限样本 下学习机器的复杂性与推广性之间的矛盾。在很多情况下，即使己知问题中的 样本来自某个比较复杂的模型，但由于训练样本有限，用复杂的预测函数去学 习对样本进行学习的效果通常也不如用相对简单的预测函数，当有噪声存在时 就更是如此。事实上，关于学习机器复杂性和推广能力，有以下的结论( 1 ) 经 验风险最小并不一定意味着期望风险最小：( 2 ) 学习机器的复杂性不但与所研究 的系统有关，而且要和有限的学习样本相适应。 2 3 统计学习理论的基本思想 任何学习机器都可以看成是一组函数集合，机器学习问题就是从函数集合 中选择合适的逼近函数并参数化的过程。所谓学习机器的容量也就是它所对应 的函数集的容量，或者叫复杂度。容量或复杂度代表了函数集实现从输入到输 出的映射的能力，对学习机器来说，叫做学习能力。容量越大，机器的学习能 力就越强。在模式识别问题中，学习能力强的机器能够得到更加复杂的分类面， 然而，越复杂的分类面，就越依赖于训练数据分布的细节，这种对训练数据的 过于细致的依赖，往往会导致学习机器的泛化能力不强。统计学习理论用v c 维 来描述学习机器的容量，并从控制学习机器容量的思想出发，结合经验风险和 训练样本数目，导出了期望风险在不同情况下的一组风险上界。这些界具有如 下特点： ( 1 )这些界是通用的，与具体数据的分布无关： ( 2 )在小样本情况下同样成立： 因此，统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳 理论。它从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本 下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等 问题。其主要内容包括四个方面： ( 1 ) 经验风险最小化原则下统计学习一致性的条件： ( 2 ) 在这些条件下关于统计学习方法推广性的界的结论： ( 3 ) 在这些界的基础上建立的小样本归纳推理原则： ( 4 ) 实现这些新的原则的实际方法或算法。 2 3 1v c 维 统计学习理论是关于小样本进行归纳学习的理论，其中一个最重要的概念 就是v c 维( v a p n i k c h e r v o n e n k i sd i m e n s i o n ) 。模式识别方法中v c 维的直观定义 是：对一个指示函数集，如果存在h 个样本能够被函数集里的函数按照所有可能 的2 ”种形式分开，则称函数集能够把h 个样本打散。函数集的v c 维就是它能打散 的最大样本数目h 。若对任意数目盼样本都有函数能将它们打散，则函数集的v c 维是无穷大。有界实函数集的v c 维可以通过用一定的阈值将它转化成指示函数 集来定义。v c 维反映了函数集的学习能力v c 维越大则学习机器越复杂( 容量越 大) 。v c 维是统计学习理论中一个核心的概念，是到目前为止对函数学习性能的 最好描述。但是目前尚没有通用的关于任意函数集v c 维计算的理论，只对一些 特殊的函数集知道其v c 维。 一般地，对于n 维空间r n 中，最多只能有n 个点是线性独立的，因此r “空间 超平面的v c 维是n + l 。 r ”中的超平面可以用下式表示： 1 4 o ( u 。a ) = e u m + a o = 0 i d 其中，u = u l ，1 1 2 ，u 。 表示r n 空问中的一组正交基，a = 8 , 0 ，a 1 ， a n ) 表示该超平面的广义参数。因此，r n 空间中的超平面共有n + 1 个独立的参 数，恰好等于v c 维数。 但是对于非线性学习机器而言，v c 维与独立参数的个数之间并没有明确的 对应关系，非但如此，在非线性情况下学习机器的v c 维通常是无法计算的。但 是实际中在应用统计学习理论时，可以通过变通的办法巧妙地避开直接求v c 维 的问题。 2 3 2 泛化误差的边界 统计学习理论从v c 维的概念出发，推导出了关于经验风险和实际风险之 间关系的重要结论，称作泛化误差的边界。这些界是分析学习机器性能和发展 新的学习算法的重要基础。统计学习理论中给出了如下的估计真实风险的不等 式，对于任意r ( r 是抽象参数集合) ，以至少卜n 的概率满足以下不等式 顾d ) 尼“4 ) + 壬，6 l 其中： 甲( 孚) = 凡，( a ) 表示经验风险，v ( ；) 称为置信风险：1 是样本个数：参数h 称为一个 l lv 函数集合的v c 维当芸较大时，置信风险较大，此时用经验风险近似期望风险 l l 就会出现较大的误差。如果样本数较多，使得导较小，则置信风险就会较小， f 经验风险最小化的最优解就会接近真正的最优解。对于一个特定的学习问题， 当样本数固定时，如果学习机器的v c 维越高( 复杂度越高) ，则置信风险越大， 导致真实风险与经验风险之间可能的差就越大。因此，在设计分类器时，不但 要使经验风险尽可能小，而且要控制其v c 维也尽可能小，从而缩小置信风险， 使期望风险最小。 由上面的公式可以知道，置信范围不但受置信水平卜i l 的影响，而且更是 函数集的v c 维和训练样本数目的函数，且随着它们比值的增加而单调减少因 为这个界限反映了根据经验风险最小化原则得到的机器学习的推广能力，所以 称它为推广性的界可以看出，置信界限反映了真实风险和经验风险差值的上确 界，它和学习机器的v c 维h 及训练样本数1 有关因此，要想得到期望风险最 小值，除了控制经验风险最小外，还要控制函数集的置信界限，而置信界限随 着函数集v c 维的增长而增大在神经网络中存在一个过学习现象，其原因首先是 学习样本不充分，其次是学习机器的复杂性过高，导致它的v c 维过大。以至于在 经验风险最小的情况下，函数集的置信界限很大，所以其推广能力仍然很差 2 3 3 结构风险最小化原理 结构风险最小化原理的基本想法是：如果我们要求风险最小，就需要使得 不等式中两项相互权衡，共同趋于极小：另外，在获得的学习模型经验风险最 小的同时，希望学习模型的泛化能力尽可能大，这样就需要h 值尽可能小，即 置信风险最小。 根据风险估计公式，如果固定训练样本数目1 的大小，则控制风险r ( a ) 的参量有两个：r 。( a ) 和h 。其中： ( 1 ) 风险依赖于学习机器所选定的函数f ( a ，x ) ，这样，我们可以通过控制a 来 控制经验风险。 ( 2 ) v c 维h 依赖于学习机器所工作的函数集合( 如前所述) 。为了获得对h 的控 制，可以将函数集合结构化，建立h 与各函数子结构之间的关系，通 过控制对函数结构的选择来达到控制v c 维h 的目的。 具体的作法如下：首先。运用以下的方法将函数集合( f ( x ，a ) 结构化。 考虑函数嵌套子集的集合 s l cs z c cs kc cs n cs 其中，s k = f ( x ，a ) ，a e1 - k ，并且有 s + = u s k 结构s 中的任何元素s k ( 或一个函数集合) 拥有一个有限的v c 维h ，且 h l 耋h 2 薹h k 董h 。耋h 1 6 如果给定一组样本( x l ，y 1 ) ，( x 2 ，y 2 ) ，( x l ，y 1 ) 结构风险最小化原理在函 数子集s 、中选择一个函数f ( x ，a ) 来最小化经验风险，同时s k 确保置信风险是最 小的。( 见图1 ) 根据这一分析，我们得到两种运用结构风险最小化原理构造的学习机器的 思想： ( 1 ) 给定一个函数集合，按照上面的方法来组织一个嵌套的函数结构，在每个 子集中求取最小经验风险，然后选择经验风险与置信风险之和最小的子 集。当子集数目较大时，此方法较费时，甚至不可行。 ( 2 ) 构造函数集合的某种结构，使得在其中的各函数子集均可以取得最小的经 验风险( 例如，使得训练误差为0 ) 。然后，在这些子集中选择适当的子集 使置信风险最小，则相应的函数子集中使得经验风险最小的函数就是所求 解的最优函数。 图1 可见，利用结构风险最小化原理的思想，就可以完美解决传统机器学习中 的过学习问题。支持向量机通过最大化分类边界以最小化v c 维，也即在保证 经验风险最小的基础上最小化置信风险，从而达到最小化结构风险的目的，因 此支持向量机方法实际上就是结构风险最小化思想的具体实现。 1 7 2 4 支持向量机 假定大小为1 的训练样本集 ( x i ，y i ) ，i = l ，2 ，1 ) ，由二类别组成，如 果x e r “属于第1 类，则标记为正( y i = 1 ) ，如果属于第2 类，则标记为负( y i 一1 ) 。 学习的目标是构造一个决策函数，将测试数据尽可能正确地分类。针对训练样 本集分为线性支持向量机和非线性支持向量机两种情况分别讨论。 2 4 1 线性支持向量机 如果存在分类超平面 x + b = 0 对于( x t ，y i ) 使得 国雨+ 易l ，y i = 1 粥+ 6 一l ，y i = - 1 i = 1 2 - - 1 则称训练集是线性可分的，其中u x 表示向量。r n 与x r n 的内积。 与b r 1 都进行了规范化，使每类样本集中与分类超平面距离最近的数据点满足 式条件的要求对于条件式子，可写成如下形式 ，( 国m + 功l ， 由统计学习理论知，如果训练样本集没有被超平面错误分开，并且距超平 面最近的样本数据与超平面之间的距离最大，则该超平面为最优超平面( 如图2 所示) ，由此得到的决策函数 f ( x ) = s g n ( 国m + 6 ) ( x ，+ b ) 其中s g n 是取符号的函数 。 图2 墨a 口a 口口a 口 o a b = - 1 o 第实 口a 第二擞 嚣近两个建羿囝的 商蠡秀玄箝自鹫 ( 1 ) 线性可分的情况 线性支持向量机可以归结为下面的( - - 次规划) 优化问题： 幽心 2 s t 页抄卫+ 功li = l ，2 ，l 引入l a g r a n g e 乘子n ，可以得到如下对偶形式的优化公式 m i n 去鳓( 刀，肃) 一回 l j = ij ：1 f f ：研0 i = l ，2 ，l 缈= o j 爿 ( 2 ) 线性不可分的情况 在线性不可分模式的情况下，给定这样一组训练数据，不可能建立一个不 具有分类误差的分离超平面。然而，我们希望找到一个最优超平面，它对整个 训练集合平均的分类误差的概率达到最小。 在类之间的分离边缘称为是软的，如果数据点不满足下面的条件 罗( 国m + 功l ，i = 1 2 l 是以下面两种方式之一出现： 1 ) 数据点落在分离区域之内，但在决策面正确的一侧。 2 ) 数据点落在决策面错误的一侧。 注意，在情况1 我们有正确的分类，但在情况2 分类是错误的。因此在必要 的时候放宽上面的约束条件，这可以通过在上式上中引入一个松弛变量e ，得到 优化问题公式为： 幽单+ c 杰参 s t ：梦茹+ 功1 一争争 1 0 ，i = 1 ，2 ，1 其中，c 为惩罚参数，c 越大表示对错误分类的惩罚越大。采用拉格朗日乘 子法求解这个具有线性约束的二次规划问题，即 ：妻忪1 1 2 + c 杰孝；一壹4 如岫。圳m 纠一壹，孝， 厶 i = li = 11 = 1 其中，ab 为拉格朗日乘子其中