没有合适的资源?快使用搜索试试~ 我知道了~
首页A_Tutorial_on_Support_Vector_Machines_for_Pattern_Recognition的中文翻译
资源详情
资源评论
资源推荐
All Right Reserved From:NZQ
1
模式识别支持向量机教程
摘要:本教程首先综述 VC 维和结构风险最小化的概念。然后通过详细地求解一
个非平凡的例子,针对可分的以及不可分的数据,描述了线性支持向量机。我们
描述了一个力学的比喻,而且讨论了何时 SVM 的解是惟一的以及何时 SVM 的
解是全局解。我们描述了支持向量训练的切实可行性,并详细讨论了应用于构建
非线性支持向量机的核映射技术。通过计算齐次多项式和高斯径向基核函数的
VC 维,我们表明支持向量机可以有非常高的 VC 维。尽管非常高的 VC 维预示
着很差的泛化能力,而且目前没有理论可以保证 SVM 具有良好的泛化能力,但
是,我们文中所写的一些观点支持我们所观测到的 SVM 的高精度。基于这些观
点的实验的结果也证实了这一点。我们给出了许多案例已经大多数重要定理的证
明。本书中有一些新的素材,同时我希望读者可以用新的眼光重新审视原有的素
材。
关键字:支持向量机,统计学习理论,VC 维,模式识别
1. 引言
本文的目的是在基本思想上对支持向量机做一个介绍而非作为一个广泛应用
的教程。瓦普尼克的专著(Vapnik,1995;Vapnik,1998)对 SVM 有出色的描
述,但是没有解释 SVM 应被学习的目的。尽管这个问题可以说开始于 70 年代
末(Vapnik,1979),但是现在才引起足够的重视,所以现在适合进行一个介绍
性的回顾。本教程着力点完全在于模式识别问题。许多此处的理论可以直接应用
于回归估计和线性算子反演,但限于篇幅此处不做进一步介绍。
本教材包含一些新的素材。其所有的证明都源自我自己,我着重于让这些证
明清晰而完备,以使这些素材尽可能易于理解。这样做的代价是使本文不再精简
通俗:然而如果基本定理是清晰的,通俗就是显而易见的了(
笑,不懂老外的逻
辑
~)。
为了激励并敦促本文献的部分读者,我们首先总结了下支持向量机近期的应
用与延伸。在模式识别领域,SVM 已被用于独立手写数字识别(Cortes 和 Vapnik,
1995;Scholkopf,Burges 和 Vapnik,1995;Scholkopf,Burges 和 Vapnik,1996;
Burges 和 Scholkopf,1997),对象识别(Blanz 等,1996),语音识别(Schmidt,
1996),笑脸捕捉,面部图像检测(Osuna,Freund 和 Girosi,1997a),以及文本
分类(Joachims,1997)。 在回归估计领域,SVM 被应用于基准时间序列预测
(Muller 等,1997;Mukherjee,Osuna 和 Girosi,1997),波士顿住房问题(Drucker
等,1997),以及(基于人工数据的)PET 算子反演问题(Vapnik,Golowich 和
smola,1996)。通常, SVM 的泛化能力(即测试集的错误率)显著优于其它算
法,如果说不是相同的话。SVM 还被研究应用于密度估计(Weston 等,1997)
与方差分解(Stitson 等,1997)。进一步说明,狭义上的 SVM 不需要待求问题
的先验信息(比如,对于图像识别问题,如果各图像按照相同的规则随机的改变
像素序列,之前表现最好的神经网络将表现的一塌糊涂,而各类 SVM 仍会给出
相同的分类结果),同时在 SVM 中应用先验信息的大量工作已经完成(Scholkopf,
Burges 和 Vapnik,1996;Scholkopf 等,1998a;Burges,1998)。一个案例(Burges,
1996;Osuna 和 Girosi,1998)表明,尽管 SVM 具有良好的泛化能力,然而其
求解速度慢的一塌糊涂。近期的研究集中于,推广基础思想(Smola,Scholkopf
All Right Reserved From:NZQ
2
和 Muller,1998a;Smola 和 Scholkopf,1998),引入正则化理论(Smola,Scholkopf
和 Muller,1998b),已经探究如何与其他各种各样的算法进行结合(Scholkopf,
Smola 和 Muller,1998b;Scholkopf 等,1998c)。读者也可以找到有用的相关论
文(Scholkopf,1997)。
最初推动 SVM 发展的问题源自以下几个看来不同的方面:偏差方差权衡
(Geman 和 Bienenstock,1992),容量控制(Guyon 等,1992),过学习(Montgomery
和 Peck,1992)但其基本思想是相同的。粗略的讲,对于一个给定的学习
任务,且给定了有限数目的训练数据,只有当在样本的训练误差和学习机器的容
量中取得一个好的平衡,学习机器才会有好的泛化能力,也就是说,这个学习机
器可以无误差的应用于任何训练。一个容量太大的学习机器就像一个拥有照相存
储器的植物学家,如果新发现的树木的叶子他不曾见过她就认为这不是树;而一
个容量太小的学习机器就像是这个植物学家懒惰的弟弟,认为绿色的就是树木。
(感觉此处对欠学习与过学习的比喻很形象~)上述两种学习机器都不能很好的
泛化。对于这些概念的探索与形式化的归纳,产生了统计学习理论中最闪亮的分
支之一(Vapnik,1979)。
以下将用粗体表示向量与矩阵;正常字体表示向量和矩阵中的元素以及标量。
我们用希腊数字来标示向量与矩阵的元素,而用罗马数字标示向量与矩阵本身。
默认假定使用拉格朗日乘子解决带有等式与不等式约束的优化问题。
2. 模式识别学习机器泛化能力的界
在学习机器的容量与其泛化能力之间,有一类显著的界控制其关系。随着样
本数目的增多,经验风险在什么条件下,以多快的速度收敛于真实误差(当样本
数据趋于无限时可以求解其值),对上述问题的思考产生了界这个理论(Vapnik,
1979)。让我们以其中一个界开始讨论。
此处的符号将很大程度上遵循 Vapnik 的专著(1995)。假定给定了 L 个样本。
样本数据来源可靠,每一个样本包括这样一对数据:向量
,i=1,,l,
和与之相关的输出
。在树木图像识别问题中,
可能是像素数值的向量(例如,
n=256 在 1616 的图像中),当图像中有树时
取值 1,否则取值-1(此处我们使
用-1 而不是 0 以简化之后的计算)。我们假定那些数据服从一个未知的概率分布
P(x,y),同时假定样本数据是独立同分布的(我们使用经验分布函数(原文是
cumulative probability distributions)代表 P,其密度函数代表 p)。 注意到这个假
定比给定每个 x 一个固定的输出 y 更具有一般性:它允许对于每个给定的 x 其输
出值依赖某个分布。如此的话,信息源会根据一个固定的分布函数以及与之相关
的
为
分配数值。尽管如此,在以下章节,我们仍然会假定对于某个
有个固
定的
与之相应。
假设有一台学习机器,其任务就是学习
这一映射关系。这个机器由一
系列的映射,所构成,其中函数,由其自由参数决定。学习机器
被认为是确定性的:给定一个
和固定的参数,其输出总是固定的值,。
对参数的选择我们称作是训练学习机器。例如,在这种意义上,有固定拓扑结
构的神经网络就是一个学习机器,其参数就是权值和偏差。
学习机器训练误差的期望风险定义如下:
,, (1)
All Right Reserved From:NZQ
3
我们注意到,如果存在密度函数,,则 d,可以写成,。
这是一个计算期望风险很好的途径,但是除非我们知道概率分布函数,的
估计,否则这种方法没有什么意义。
的数值被称为期望风险,或者直接说风险。此处我们称其为真实风险,
以强调我们最终感兴趣的是这个数值。我们定义训练集(对应固定有限个样本)
上的测量平均误差为经验风险
:
,
(2)
注意到,上式没有出现概率分布函数。对于一个选定的参数和固定的训练集
{
,
},
是一个固定的数值。
数值
,被称为损失函数,在上述情况下,其取值只能是 1 或者
0。现在选定一个数值,其中。损失函数如上所述取值 0 或 1,则下式
所示的界以 的概率成立:
(3)
上式中 h 是一个非负整数,称为 VC 维(Vapnik-Chervonenkis 维),是衡量上
述容量概念的一个标准。下文中我们将称公式(3)的右边第二项为风险的界。
我们从以前的术语开始探究:Guyon 等作家(1992)称它为保证风险(原文是
guaranteed risk),这样命名有一点不恰当,因为它只是风险的界而非风险;并且
它仅是提供一种确定的可能性,而非保证。对右端第二项的第二种命名方式是称
之为 置信区间。
我们注意到关于这个界有三个关键点。第一,明显地这个界与概率分布函数
,无关。它仅假定训练数据与测试数据服从同一未知概率分布,。其
次,通常没有办法具体求出上式左端项的数值。第三,如果我们知道了 h 的值,
我们很容易可以计算上式右端项的数值。因此,对于给定的学习机器(学习机
器仅表示函数集,),选定一个固定且足够小的,然后选择使上式右端项
最小化的学习机器,则这个学习机器可以使真实风险的上界最小。这个理论是结
构风险最小化(见章节 2.6)的基本思想,对于为给定任务选择合理的学习机器,
其提供了一个理论上的方法。给定一组学习机器,则至少有一个学习机器,相对
于其他机器来说,其界是紧的。即使对于任一学习机器来说,这个界也不是紧的,
上式右端项仍能为最小化经验风险提供一些有用的信息。这个界可能对于所有的
函数集都不是紧的,使得反对者可以借此批评这一理论。目前这种情况下,一切
都只能以实验作为依据(
貌似
Vapnik
已经证明这个界是紧的
~)。
2.1 VC 维
VC 维表征了函数集{f()}(我们再次使用作为一个一般的参数,确定了也
就确定了特定的函数)的一种特性,其可以用各类函数关系 f 进行定义。此处我
All Right Reserved From:NZQ
4
们仅考虑对应于两类模式识别问题的函数,所以,,
,。如
果给定的长度为 l 的样本集可以被函数集{f()}中的一个函数以
种方式分开,我
们则说该样本可以被这个函数集打散。函数集 f()的 VC 维定义为其可以打乱的
样本点最大的个数。请注意,如果函数集的 VC 维为 h,则至少存在一组长度为
h 的样本集可以被该函数集打散,但是这并不意味着该函数集可以把任意长度为
h 的样本集打散。
2.2
空间中定向超平面打散样本点
假定样本都是二维空间
中的数据,函数集 f()是一个定向直线的集合,对
于一条给定直线,位于直线一侧的是 1 类,另一侧的是-1 类。直线的方向如图 1
中箭头所示,箭头所指一侧的样本点标记为 1 类。我们可以发现,这一函数集可
以打散某一长度为 3 的样本集,却无法打散任意长度为 4 的样本集,因此,二维
空间
中定向直线的 VC 维是 3。
图 1 二维空间
中三个样本点被定向直线打散
现在让我们考虑 n 维空间
中的超平面。可能要利用下述定理:
定理 1 n 维空间
中的长度为 m 的样本集可以被相应定向超平面打散的充
要条件是,任选一个样本点作为原点,其它样本点的位置向量线性无关。
推论: n 维空间
中定向超平面的 VC 维是 n+1,因为我们总可以选出 n+1
个点,其中一个点作为原点,其余 n 个点的位置向量线性无关,但是我们选不出
n+2 个点(因为 n 维空间
中不会有 n+1 个线性无关的向量)。
本推论的另一种证明方法见于 Anthony 和 Biggs(1995)的著作,见于参考
文献。
2.3 VC 维与参数数目
VC 维使得函数集容量的概念得以具体化。人们直观上容易认为,参数多的
函数集 VC 维会很高,而参数少的函数集的 VC 维会很低。然而 E.Levin 和
J.S.Denker(Vapnik,1995)提出了一个很明显的反例:仅含一个参数的学习
机器可以有无穷大的 VC 维(对于分类器来说,有无穷大的 VC 维,意味着
无论 l 有多大,它都可以打散长度为 l 的样本集)。定义阶跃函数,:
All Right Reserved From:NZQ
5
{
;
}。考虑如下定义的仅有一个参数的函
数集:
,
, , (4)
对于任意大的数字 l,可以找到按照如下方式选择的长度为 l 的样本集,
其能被该函数集打散:
, i=1,,l (5)
可以为指定任意标号:
,
, ,
,
(6)
只需选择如下式所示的,
就能按照上式中标号分开样本集:
(7)
因此,这个学习机器的 VC 维是无穷大的。
图 2 VC 维无限大的函数集
无法打散的 4 个点
有意思的是,尽管上述函数集可以打散某个任意长度的样本集,我们仍能找
出一个仅有 4个点的样本集,使其无法打散。这 4 个样本点只是简单地均匀分布,
其标号如图 2 所示。这种情况看作:样本点
位于相位
处,其标号
,其中。
的相位对取余为,令
。
简单地点
会使得
。然后,在点
处,
会使得
,
与给定的标号相反。这四个点是空间
中有向超平面对于位于同一直线上三个点
按照公式(4)的一种类推。这两种情况下,函数集都无法打散这些点集。
2.4 通过最小化 h 最小化界
图 3 说明了,在置信度为 95%(),样本数量为 10000 的情况下,公
式 3 右端第二项是如何随 h 变化的。对于任意的样本数 l,VC 置信区间都是 h
的单调增函数。
因此,给定一些经验风险为零的学习机器,我们应该选择 VC 维小的函数集。
这样才能有一个更小的误差上界。总体而言,对于经验误差不为零的情况,我们
应该选择使得公式 3 右端项最小的学习机器。
注意到采用这种策略时我们仅依据公式 3。公式 3(在给定概率下)可以给
出真实风险的上界。这并不意味着,一个具有同样的经验风险然而 VC 维更高的
学习机器不可以有更好的泛化能力。事实上,下一节我们将给出一个例子,它有
无穷大的 VC 维然而其泛化能力同样很好。从图形中可以注意到,对于 h/l>0.37
(且)的情况,VC 置信区间超过了单位 1,所以对于更高的
h/l 值,这个界不能保证是紧的。
剩余31页未读,继续阅读
普通网友
- 粉丝: 3
- 资源: 156
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论3