上海大学2013 ～2014学年冬季学期研究生课程考试
小论文格式石碳酸
课程名称：模式识别方法课程编号： 09SB59004
研究生姓名: 章云元学号: ******** 论文评语:
成绩: 任课教师: 李昕
评阅日期:
支持向量机原理及应用
学号：13721278 姓名：章云元
日期：2014.03.07
期望理论摘要：支持向量机是从统计学发展而来的一种新型的机器学习方法，在解决小样本、非线性和高维的机 器学习问题中表现出了许多特有的优势，但是，支持向量机方法中也存在着一些亟待解决的问题，主要包括：如何用支持向量机更有效的解决多类分类问题，如何解决支持向量机二次规划过程中存在的瓶颈问题、如何确定核函数以及最优的核参数以保证算法的有效性等。本文详细介绍系统的阐述了统计学习理论、支持向量机理论以及支持向量机的主要研究热点，包括求解支持向量机问题、多类分类问题、参数优化问题、核函数的选择问题等。 关键词：机器学习；统计学习理论；SVM；VC维；
The principle and application of Support Vector Machine ABSTRACT：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 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 introduced 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 on.
Keywords: Machine learning, SLT, SVM, VC dimension
1.引言
1.1支持向量机研究背景及意义
随着支持向量机的不断发展，人们对支持向量机的研究也越来越细化，其主要研究方向大致可分为：求解支持向量机问题，支持向量机多类分类问题，参数的选择和优化问题等。
求解一个SVM问题最终都转化为解一个具有线性约束的凸规划问题或其对偶问题的二次规划问题(Quadratic Programming，QP)。传统的方法是利用标准二次型优化技术解决对偶问题，这就导致算法的训练速度很慢，一方面是由于SVM需要计算和存储核函数矩阵，当样本规模较大时必然导致内存需求增加；另一方面，SVM在二次寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法占用了大部分的算法时间，这就使得存储空间和和计算时间成了求解二次规划问题的瓶颈。常用的解决方法是将一个大的二次规划问题转化为若干个小的二次规划问题以提高分类效率，如块算法、分解算法、SMO算法、增式算法等等。
支持向量机分类理论是针对两类分类问题提出的，然而，现实世界的分类问题，如船舰
识别、字体识别、人脸识别等，都属于多类分类的范畴。如何将二类分类方法扩展到多类分类情况是
支持向量机方法研究的重要内容之一。目前，用SVM 解决多类分类问题方法主要是通过构造或组合多个两类分类器来实现多类问题的分类。子分类器的构造和组合将两类分类扩展到多类问题，将多类分类问题逐步转化为两类分类问题。常用的算法有“one---against---one ”方法、“one--against--rest ”方法、“基于决策树的方法”等。支持向量机多类分类方法的引入拓展了支持向量机的应用范围，也加快了支持向量机方法的改进和创新，同时，支持向量机的核函数的选择以及核参数的选择也是一个重要的研究方向。
2.支持向量机的原理
支持向量机(Support Vector Machine ，SVM)是由Vapnik 及其合作者共同创造与发展起来的一种新的机器学习方法，其核心内容在1992年至1995年间提出的。
2.1统计学习理论
统计学习理论建立在一套较为坚实的理论基础之上，为解决有限样本的学习问题提供了一个统一的框架。它能将许多现有的方法纳入其中，有望帮助解决许多原来难以解决的问题，比如神经网络的结构选择问题、局部最小点问题等。
xiaoeni2.1.1机器学习问题
机器学习问题[1]可以看作是通过某种训练方法，对某一系统的输入与输出之间的依赖关系进行估计，并且期望这一估计可以对任意给定输入尽量准确地进行输出预测。一般地，机器学习问题可以表示为：假设变量y 与x 之间存在一定的未知依赖关系，即遵循某一未知的联合概率(),F x y (x 和y 之间的确定性关系可以看作是其特例)，机器学习问题就是根据n 个独立同分布观测样本()()()1122,,,,...,,n n x y x y x y ，在一组函数()()
,f x ω中求一个最优的函数(),a f x ω对依赖关系进行估计，使得期望风险最小。 ()()()(),,,L R y f x dF x y ωω=⎰ 2-(1) 其中(){},f x ω称作预测函数集，ω为函数的广义参数，(){}
,f x ω可以表示任何函数集；
()(),,L y f x ω为由于用(),f x ω对y 进行预测而造成的损失，
不同类型的学习问题有不同形式的损失函数。
在上面问题的表述中，学习的目标在于使期望风险最小化，但是，由于可以利用的信息只有样本最初的观测样本()()()1122,,,,...,,n n x y x y x y ，因此，期望风险2-(1)是无法计算的。传统的学习方法是采用了所谓经验风险最小化(ERM)准则[11]，即用样本定义经验风险 ()()()1
1,,n北京同性恋
emp i i i R L y f x n ωω==∑ 2-(2)
来逼近3-(1)定义的期望风险，用对参数ω求经验风险()emp R ω的最小值代替求期望风险()R ω的最小化，这就是所谓的经验风险最小化原则。
2.1.3VC 维理论
模式识别方法中VC 维的直观定义是：对一个指示函数集，如果存在h 个样本能够被函数集中的函数按所有可能的2h
种形式分开，则称函数集能够把h 个样本打散；函数集的VC 维就是它能打散的最大样本数目h 。若对任意数目的样本都有函数能将它们打散，则函数集的VC 维是无穷大。 VC 维反映了函数集的学习能力，VC 维越大则学习机器越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC 维计算的理论，只确定了一些特殊的函数集的VC 维。比如在n 维实数空间中线性分类器和线性实函数的VC 维是1n +，对于一些比较复杂的学习机器(如神经网络)，其VC 维除了与函数集(神经网结构)有关外，还受学习算法等的影响，其确定更加困难。但是，在实际应用统计学习理论时，可以通过变通的办法巧妙地避开直接求VC 维的问题。
美政府关门危机2.1.4推广性的界
统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之
间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有
函数(包括使经验风险最小的函数)，经验风险()emp R ω和实际风险()R ω之间以概率1η-满足如下关系：
八甲人
()()emp R R ωω≤其中h 是函数集的VC 维，n 是样本数。
这一结论从理论上说明了学习机器的实际风险是由两部分组成的：一是经验风险(训练误差)，另一部分称作置信范围，它和学习机器的VC 维及训练样本数有关，可以简单地表示为：
()()()emp R R h n ωω≤+Φ 2-(4)
它表明，在有限训练样本下，学习机器的VC 维越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC 维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，这一理论可以由图2.1说明。
图2.1 置信范围、经验风险与实际风险之间的关系
由图2.1可以看出，当样本数目n 固定，算法的VC 维增大时，它对给定训练样本集合有更强的分类或拟合能力，导致了更小的经验风险()emp R ω，甚至使它为零。但是，VC 维增大时，()h n Φ也随之增大，即放大了置信范围，从而减小了算法具有小的实际风险()R ω的可能性。反之，若VC 维缩小，那么它对给定的训练样本集合的分类或拟合能力减弱，导致了大的经验风险，此时，虽然置信区间()h n Φ缩小了，但仍不能保证获得小的实际风险。可以看出n 固定时()emp R ω与()h n Φ是一对矛盾体，它们不可能同时都减小，但确实存在某个h 值使实际风险上界达到最小值。
2.1.5结构风险最小化原则
经验风险最小化原则是目前绝大多数模式识别方法的基础，其定义为训练集上的平均错误率，用于对整个样本集的期望风险进行估计，它建立在样本数目足够多的前提下，致使各种方法只有在样本数趋向无穷大时，其性能才有理论上的保证。而在现实世界的应用中，这一前提并不总能被满足，这时大多数此类方法都难以取得理想的结果。
由2.1.4节中的推广性的界可以看出，影响期望风险上界的因子有两个方面：首先是训练集的规模n ，其次是VC 维h 。可见，在保证分类精度(经验风险)的同时，降低学习机器的VC 维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化(Structure Risk Minimization ，简称SR
M)的由来。
由VC 维的讨论可以看到，经验风险和期望风险依赖于学习机器函数族的选择。把函数集(){}
,,s f x ωω=∈Ω分解为一个函数子集序列 12......k s s s ⊂⊂⊂⊂⊂ 2-(5)
使各个子集能够按照置信范围Φ的大小排序，即
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议