《系统建模之向量机》由会员分享，可在线阅读，更多相关《系统建模之向量机（14页珍藏版）》请在金锄头文库上搜索。
1、摘要：摘要：支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。本文详细介绍系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等。关键词：关键词：机器学习；统计学习理论；SVM；维；VCThe principle and applicatio
2、n of Support Vector MachineABSTRACT： SVM(Support Vector Machine) is a novel method of machine learning evolving from Statistics. SVM presents many own advantages in solving machine learning problems such as small samples, nonlinearity and high dimension. However, SVM methods exist some problems need
3、 to be resolved, mainly including how to deal with multi-classification effectively, how to solve the bottle-neck problem appearing in quadratic programming process, and how to decide kernel function and optimistical kernel parameters to guarantee effectivity of the algorithm.This paper has introduc
4、ed in detail the structure, evolvement history, and kinds of classification of machine learning, and demonstrated system SLT(Statistical Learning Theory), SVM and research hotspots of SVM, including seeking SVM problems, multi-classification, parameters optimization, kernel function selection and so
5、 on. Keywords: Machine learning, SLT, SVM, VC dimension1.1.引言引言1.11.1 支持向量机研究背景及意义支持向量机研究背景及意义随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选择和优化问题等。求解一个 SVM 问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(Quadratic Programming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于 SVM 需要计算和存储
6、核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，SVM 在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO 算法、增式算法等等。支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是支持向量机方法研究的重要内容之一。目前，用 SVM 解决多类分类问题方法主要是通过构造或组合多个两类
7、分类器来实现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one-against-one”方法、 “one-against-rest”方法、 “基于决策树的方法”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。2.2.支持向量机的原理支持向量机的原理支持向量机(Support Vector Machine，SVM)是由 Vapnik 及其合作者共同创造与发展起来的一种新的机器学习方法，其核心内容在 1992 年
8、至 1995 年间提出的。2.12.1 统计学习理论统计学习理论统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。2.1.12.1.1 机器学习问题机器学习问题机器学习问题1可以看作是通过某种训练方法，对某一系统的输入与输出之间的依赖关系进行估计，并且期望这一估计可以对任意给定输入尽量准确地进行输出预测。一般地，机器学习问题可以表示为：假设变量与之间存在一定的未知依赖关系，即遵循某一未yx知的联合概率(和之间的确定性关系可以看作是其特例)，机
9、器学习问题就是,F x yxy根据 n 个独立同分布观测样本，在一组函数中求一 1122,.,nnx yxyxy,f x个最优的函数对依赖关系进行估计，使得期望风险最小。,af x2-(1) , LRy f xdF x y其中称作预测函数集，为函数的广义参数，可以表示任何函数集；,f x,f x为由于用对进行预测而造成的损失，不同类型的学习问题有不,L y f x,f xy同形式的损失函数。在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利用的信息只有样本最初的观测样本，因此，期望风险 2-(1)是无法计 1122,.,nnx yxyxy算的。传统的学习方法是采用了所谓经验风
10、险最小化(ERM)准则11，即用样本定义经验风险2-(2) 11,nempii iRL yf xn来逼近 3-(1)定义的期望风险，用对参数求经验风险的最小值代替求期望风险 empR的最小化，这就是所谓的经验风险最小化原则。 R2.1.32.1.3维理论维理论VC模式识别方法中维的直观定义是：对一个指示函数集，如果存在个样本能够被函数集中的函VCh数按所有可能的种形式分开，则称函数集能够把个样本打散；函数集的维就是它能打散的最大2hhVC样本数目。若对任意数目的样本都有函数能将它们打散，则函数集的维是无穷大。hVC维反映了函数集的学习能力，维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没
11、VCVC有通用的关于任意函数集维计算的理论，只确定了一些特殊的函数集的维。比如在维实数空VCVCn间中线性分类器和线性实函数的维是，对于一些比较复杂的学习机器(如神经网络)，其维VC1nVC除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计学习理论时，可以通过变通的办法巧妙地避开直接求维的问题。VC2.1.42.1.4 推广性的界推广性的界统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险和实际风险之间以概率 empR R满足
12、如下关系：12-(3) ln 21ln4emphn hRRn其中是函数集的维，是样本数。hVCn这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学习机器的维及训练样本数有关，可以简单地表VC示为：2-(4) empRRh n它表明，在有限训练样本下，学习机器的维越高(复杂性越高)则置信范围越大，导致VC真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使维尽量小以缩小置信范围，才能取得较小的VC实际风险，即对未来样本有较好的推广性，这一理论可以由图 2.1 说明。图 2.
13、1 置信范围、经验风险与实际风险之间的关系由图 2.1 可以看出，当样本数目固定，算法的维增大时，它对给定训练样本集合有更nVC强的分类或拟合能力，导致了更小的经验风险，甚至使它为零。但是，维增 empRVC大时，也随之增大，即放大了置信范围，从而减小了算法具有小的实际风险h n的可能性。反之，若维缩小，那么它对给定的训练样本集合的分类或拟合能力 RVC减弱，导致了大的经验风险，此时，虽然置信区间缩小了，但仍不能保证获得小h n的实际风险。可以看出固定时与是一对矛盾体，它们不可能同时都减n empRh n小，但确实存在某个值使实际风险上界达到最小值。h2.1.52.1.5 结构风险最小化原则结
14、构风险最小化原则经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的结果。由 2.1.4 节中的推广性的界可以看出，影响期望风险上界的因子有两个方面：首先是训练集的规模，其次是维。可见，在保证分类精度(经验风险)的同时，降低学习nVCh机器的维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最VC小化(Structure Risk Minim
15、ization，简称 SRM)的由来。 由维的讨论可以看到，经验风险和期望风险依赖于学习机器函数族的选择。把函VC数集分解为一个函数子集序列,sf x2-(5)12.ksss使各个子集能够按照置信范围的大小排序，即2-(6)12.khhh所谓结构风险最小化，便是构造一组嵌套的函数子集，使得其维由内向外依次递VC增，然后在其上寻找经验风险和置信范围之和最小的子集，从而使得实际风险的上界最小化，如图 2.2 所示图 3.2 结构风险最小化示意图基于结构风险最小化准则的统计学习理论是一种专门研究小样本的统计理论，它为研究有限样本情况下的统计模式识别，并为更广泛的机器学习问题建立了一个较好的理论框架，
16、同时也发展出了一种新的模式识别方法支持向量机，从而能够较好地解决小样本的学习问题。2.22.2 支持向量机理论支持向量机理论SVM 方法是由 Vapnik 及其合作者 Boser、Guyon、Cortes 及 Scholkopf 在 AT&TBell 实验室共同创造与发展起来的一种新的学习方法。近年来，许多关于 SVM 方法的研究，包括算法本身的改进和算法的实际应用，都陆续被提了出来，其中在理论上主要以 Vapnik 及其研究小组做了大量开创性及奠基性的工作。目前 SVM 正处于不断发展阶段，现在已经成为机器学习领域的标准工具之一。支持向量机是个三层网络结构，是一个多输入、单输出的学习机器，其体系结构如图
