File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 18
保证最终所获得的分割平面位于两个类别的中 心对于分类问题的实际应用是很重要的。支持 向量机方法很巧妙地解决了这一问题。 该方法的机理可以简单描述为：寻找一个满足 分类要求的最优分类超平面，使得该超平面在 保证分类精度的同时，能够使超平面两侧的空 白区域最大化；从理论上来说，支持向量机能 够实现对线性可分数据的最优分类。为了进一 步解决非线性问题，Vapnik等人通过引入核映 射方法转化为高维空间的线性可分问题来解 决。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 21
支持向量 Support Vector
最优分类面示意图
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 22
其中距离超平面最近的异类向量被称为支持向 量（Support Vector），一组支持向量可以唯 一确定一个超平面。SVM是从线性可分情况下 的最优分类面发展而来，其超平面记为： wxb 0
其中 i ＞ 0为Lagrange乘数。约束最优化问题的解由Lagrange函 数的鞍点决定。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 19
最优分类超平面
（Optimal Hyperplane ）
对于两类线性可分的情形，可以直接构造最优 超平面，使得样本集中的所有样本满足如下条 件： （1）能被某一超平面正确划分； （2）距该超平面最近的异类向量与超平面之间 的距离最大，即分类间隔（margin ）最大； 以上两个条件体现了结构风险最小化（SRM） 的原则。 保证经验风险最小
Slide 16
支持向量机 （Support Vector Machine，SVM）
90年代中期，在统计学习理论的基础上发展出 了一种通用的学习方法－－支持向量机。它根 据有限的样本信息在模型的复杂性和学习能力 之间寻求最佳折衷，以获得最好的泛化能力。
支持向量机在很多机器学习问题的应用中已初 步表现出很多优于已有方法的性能。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 15
欠学习 风险
过学习 实际风险的界
置信范围
经验风险
h S1 S2 S3
S1 S 2 S3 函数集子集：
h1 h2 h3 VC维：
结构风险最小化示意图
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 5
机器学习问题的表示
基于数据的机器学习是现有智能技术中的重要 方面，其研究的实质是根据给定的训练样本求 出对系统输入输出之间依赖关系的估计，使它 能对未知样本的输出做出尽可能准确的预测。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 6
保证置信范围最 小
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 20
i 1, 设训练样本输入为 xi ， 对应的期望输出为 yi 1,1
,l
d x R ， i
如果训练集中的所有向量均能被某超平面正确 划分，并且距离平面最近的异类向量之间的距 离最大（即边缘margin最大化），则该超平面 为最优超平面（Optimal Hyperplane ） 。
Return
Slide 4
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
统计学习理论
（ Statistical Learning Theory ，SLT）
机器学习的基本问题 统计学习理论
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 11
函数集的VC维 （Vapnik Chervonenkis Dimension ）
模式识别方法中VC维的直观定义是：对于一 个指标函数集，如果存在n个样本能够被函数 集中的函数按所有可能的2h 种形式分开， 则称 函数集能够把n个样本打散；函数集的VC维就 是它能打散的最大样本数目h。有界实函数的 VC维可以通过用一定的阈值将其转化为指示 函数来定义。 VC维反映了函数集的学习能力，VC维越大则 学习机器越复杂（学习能力越强）。
协同形成结构
竞争促进发展
支持向量机及其学习算法
合肥工业大学图像信息处理研究室
/organ/images/
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 1
主要内容
一、 二、 三、 四、 五、 六、 七、 历史背景 统计学习理论 支持向量机 支持向量机的分类学习算法 用于函数拟合的支持向量机 支持向量机算法的研究与应用 仿真实例
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 8
事实上，从期望风险最小化到经验风险最小化 并没有可靠的理论依据，只是直观上合理的想 当然做法。 经验风险最小化原则不成功的一个例子就是神 经网络的过学习问题:训练误差（经验风险） 过小反而会导致推广能力的下降，即真实误差 （期望风险）的增加。 出现过学习现象的原因主要是由于学习样本不 充分和学习机器设计不合理。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 12
推广性的界
统计学习理论系统地研究了各种类型函数集的 经验风险（即训练误差）和实际风险（即期望 风险）之间的关系，即推广性的界。 关于两类分类问题有如下结论：对指示函数集 中的所有函数，经验风险和实际风险之间至少 以概率1 满足如下关系：
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 17
支持向量机的理论最初来自于对数据分类问题 的处理。对于线性可分数据的二值分类，如果 采用多层前向网络来实现，其机理可以简单描 述为：系统随机的产生一个超平面并移动它， 直到训练集合中属于不同类别的点正好位于该 超平面的不同侧面，就完成了对网络的设计要 求。但是这种机理决定了不能保证最终所获得 的分割平面位于两个类别的中心，这对于分类 问题的容错性是不利的。
F x,al Risk Minimization ，ERM）
实际应用中，一般根据概率论中的大数定理， 即采用下式的算术平均来逼近期望风险。
1 n Remp L yi , f xi , n i 1
用对参数 求经验风险 Remp 的最小值代替求 期望风险 R 的最小值。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
h R Remp 可以简单的表示为： l
Slide 14
结构风险最小化
（Structural Risk Minimization，SRM） 经验风险最小化原则在样本有限（即 h l 较大）时 是不合理的，此时一个小的经验风险值并不能保 证小的实际风险值。为解决此问题，就需要在保 证分类精度（即减小经验风险）的同时，降低学 习机器的VC维，从而使得学习机器在整个样本集 上的期望风险得到控制，这就是结构风险最小化 （SRM）原则的基本思想。 结构风险最小化为我们提供了一种不同于经验风 险最小化的更科学的学习机器设计原则，显然， 利用结构风险最小化原则的思想，就可以完美解 决神经网络中的过学习问题。支持向量机方法实 际上就是这种思想的具体实现。
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 2
传统统计学是一种渐进理论，研究的是样本数 目趋于无穷大时的极限特性。 现有的学习方法多基于传统统计学理论，但在 实际应用中，样本往往是有限的，因此一些理 论上很优秀的学习方法在实际中的表现却不尽 人意，存在着一些难以克服的问题，比如说如 何确定网络结构的问题、过学习问题、局部极 小值问题等，从本质上来说就是因为理论上需 要无穷样本与实际中样本有限的矛盾造成的。
Slide 23
可以计算出分类间隔为 2 w ，因此构造最优超平面的 问题就转化为在约束式下求：
1 min w w 2
2
1 w w 2
为了解决这个约束最优化问题，引入下式所示的 Lagrange函数： l l 1 2 L w i yi xi w b i 2 i 1 i 1
定义期望风险：
R L y, f x , dF x , y
f x,

L y, f x,
－－预测函数集 －－广义参数 －－损失函数 －－联合概率分布
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
实际 风险
hln2l h 1 ln 4 R Remp l
其中h是函数集的VC维，l是样本数。
置信范围
File: /ram/wgchairs.sxi Date: 2014年5月14日星期三
Slide 13
学习机器的实际风险由两部分组成：
经验风险Remp ，即训练误差； 置信范围（Confidence Interval） 它表明在有限样本训练下，学习机VC维越高 （机器的复杂性越高），则置信范围越大， 导致真实风险与经验风险之间可能的差别越 大。这就是为什么出现过学习现象的原因。