文档介绍：SVM 入门
SVM 入门(一)SVM 的八股简介 
支持向量机(SupportVectorMachine)是 Cortes 和 Vapnik 于 1995 年首先提
出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能
够推广应用到函数拟合等其他机器学****问题中[10]。
支持向量机方法是建立在统计学****理论的 VC 维理论和结构风险最小原理基础
上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学****精度,
Accuracy)和学****能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,
以期获得最好的推广能力[14](或称泛化能力)。
以上是经常被有关 SVM 的学术文献引用的介绍,有点八股,我来逐一分解并解
释一下。
Vapnik 是统计机器学****的大牛,这想必都不用说,他出版的《Statistical
LearningTheory》是一本完整阐述统计机器学****思想的名著。在该书中详细的
论证了统计机器学****之所以区别于传统机器学****的本质,就在于统计机器学****能
够精确的给出学****效果,能够解答需要的样本数等等一系列问题。与统计机器学<br****的精密思维相比,传统的机器学****基本上属于摸着石头过河,用传统的机器学<br****方法构造分类系统完全成了一种技巧,一个人做的结果可能很好,另一个人差
不多的方法做出来却很差,缺乏指导和原则。
所谓 VC 维是对函数类的一种度量,可以简单的理解为问题的复杂程度,VC 维
越高,一个问题就越复杂。正是因为 SVM 关注的是 VC 维,后面我们可以看到,
SVM 解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,
这使得 SVM 很适合用来解决文本分类的问题,当然,有这样的能力也因为引入
了核函数)。
结构风险最小听上去文绉绉,其实说的也无非是下面这回事。
机器学****本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好
的近似模型,这个近似模型就叫做一个假设),但毫无疑问,真实模型一定是不
知道的(如果知道了,我们干吗还要机器学****直接用真实模型解决问题不就可
以了?对吧,哈哈)既然真实模型不知道,那么我们选择的假设与问题真实解之
间究竟有多大差距,我们就没法得知。比如说我们认为宇宙诞生于 150 亿年前
的一场大爆炸,这个假设能够描述很多我们观察到的现象,但它与真实的宇宙模
型之间还相差多少?谁也说不清,因为我们压根就不知道真实的宇宙模型到底是
什么。
这个与问题真实解之间的误差,就叫做风险(更严格的说,误差的累积叫做风险)。
我们选择了一个假设之后(更直观点说,我们得到了一个分类器以后),真实误
差无从得知,但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用
分类器在样本数据上的分类的结果与真实结果(因为样本是已经标注过的数据,
是准确的数据)之间的差值来表示。这个差值叫做经验风险 Remp(w)。以前的
机器学****方法都把经验风险最小化作为努力的目标,但后来发现很多分类函数能
够在样本集上轻易达到 100%的正确率,在真实分类时却一塌糊涂(即所谓的推
广能力差,或泛化能力差)。此时的情况便是选择了一个足够复杂的分类函数(它
的 VC 维很高),能够精确的记住每一个样本,但对样本之外的数据一律分类错
误。回头看看经验风险最小化原则我们就会发现,此原则适用的大前提是经验风
险要确实能够逼近真实风险才行(行话叫一致),但实际上能逼近么?答案是不
能,因为样本数相对于现实世界要分类的文本数来说简直九牛一毛,经验风险最
小化原则只在这占很小比例的样本上做到没有误差,当然不能保证在更大比例的
真实文本上也没有误差。
统计学****因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻
画,一是经验风险,代表了分类器在给定样本上的误差;二是置信风险,代表了
我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分
是没有办法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计
算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。
置信风险与两个量有关,一是样本数量,显然给定的样本数量越大,我们的学****br/>结果越有可能正确,此时置信风险越小;二是分类函数的 VC 维,显然 VC 维越
大,推广能力越差,置信风险会变大。
泛化误差界的公式为:
R(w)≤Remp(w)+Ф(n/h)
公式中 R(w)就是真实风险,Remp(w)就是经验风险,Ф(n/h)就是置信风险。统
计学****的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结
构风险最小。
SVM 正是这样一种努力最小化结构