没有合适的资源?快使用搜索试试~ 我知道了~
首页svm算法基本原理详解
资源详情
资源评论
资源推荐
(一)SVM 的八股简介
支持向量机是 和 于 年首先提
出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推
广应用到函数拟合等其他机器学习问题中。
支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上
的 , 根 据 有 限 的 样 本 信 息 在 模 型 的 复 杂 性 ( 即 对 特 定 训 练 样 本 的 学 习 精 度 ,
)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期
获得最好的推广能力(或称泛化能力)。
以上是经常被有关 的学术文献引用的介绍,有点八股,我来逐一分解并解释
一下。 是统计机器学习的大牛,这想必都不用说,他出版的《
!》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证
了统计机器学习之所以区别于传统机器学习的本质,就在于统计机器学习能够精确的
给出学习效果,能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维
相比,传统的机器学习基本上属于摸着石头过河,用传统的机器学习方法构造分类系
统完全成了一种技巧,一个人做的结果可能很好,另一个人差不多的方法做出来却很
差,缺乏指导和原则。
所谓 VC 维是对函数类的一种度量,可以简单的理解为问题的复杂程度, 维越
高,一个问题就越复杂。正是因为 关注的是 维,后面我们可以看到, 解
决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以,这使得 很
适合用来解决文本分类的问题,当然,有这样的能力也因为引入了核函数)。
结构风险最小听上去文绉绉,其实说的也无非是下面这回事。
机器学习本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好
的近似模型,这个近似模型就叫做一个假设),但毫无疑问,真实模型一定是不知道
的(如果知道了,我们干吗还要机器学习?直接用真实模型解决问题不就可以了?对
吧,哈哈)既然真实模型不知道,那么我们选择的假设与问题真实解之间究竟有多大
差距,我们就没法得知。比如说我们认为宇宙诞生于 亿年前的一场大爆炸,这个
假设能够描述很多我们观察到的现象,但它与真实的宇宙模型之间还相差多少?谁也
说不清,因为我们压根就不知道真实的宇宙模型到底是什么。
这个与问题真实解之间的误差,就叫做风险(更严格的说,误差的累积叫做风
险)。我们选择了一个假设之后(更直观点说,我们得到了一个分类器以后),真实
误差无从得知,但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分
类器在样本数据上的分类的结果与真实结果(因为样本是已经标注过的数据,是准确
的数据)之间的差值来表示。这个差值叫做经验风险 R
emp
(w)。以前的机器学习方法
都把经验风险最小化作为努力的目标,但后来发现很多分类函数能够在样本集上轻易
达到 "的正确率,在真实分类时却一塌糊涂(即所谓的推广能力差,或泛化能力
差)。此时的情况便是选择了一个足够复杂的分类函数(它的 维很高),能够精确
的记住每一个样本,但对样本之外的数据一律分类错误。回头看看经验风险最小化原
则我们就会发现,此原则适用的大前提是经验风险要确实能够逼近真实风险才行(行
话叫一致),但实际上能逼近么?答案是不能,因为样本数相对于现实世界要分类的
文本数来说简直九牛一毛,经验风险最小化原则只在这占很小比例的样本上做到没有
误差,当然不能保证在更大比例的真实文本上也没有误差。
统计学习因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻
画,一是经验风险,代表了分类器在给定样本上的误差;二是置信风险,代表了我们
在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分是没有办
法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计算上界,而无
法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。
置信风险与两个量有关,一是样本数量,显然给定的样本数量越大,我们的学习
结果越有可能正确,此时置信风险越小;二是分类函数的 维,显然 维越大,推
广能力越差,置信风险会变大。
泛化误差界的公式为:
#$%#
&
$'()
公式中 #$就是真实风险,#
&
$就是经验风险,()就是置信风险。统计
学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险
最小。
正是这样一种努力最小化结构风险的算法。
其他的特点就比较容易理解了。
小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几
乎总是能带来更好的效果),而是说与问题的复杂度比起来,SVM 算法要求的样本数
是相对比较少的。
非线性,是指 SVM 擅长应付样本数据线性不可分的情况,主要通过松弛变量
(也有人叫惩罚变量)和核函数技术来实现,这一部分是 SVM 的精髓,以后会详细
讨论。多说一句,关于文本分类这个问题究竟是不是线性可分的,尚没有定论,因此
不能简单的认为它是线性可分的而作简化处理,在水落石出之前,只好先当它是线性
不可分的(反正线性可分也不过是线性不可分的一种特例而已,我们向来不怕方法过
于通用)。
高维模式识别是指样本维数很高,例如文本的向量表示,如果没有经过另一系列
文章(《文本分类入门》)中提到过的降维处理,出现几万维的情况很正常,其他算
法基本就没有能力应付了, 却可以,主要是因为 产生的分类器很简洁,用
到的样本信息很少(仅仅用到那些称之为“支持向量”的样本,此为后话),使得即使样
本维数很高,也不会给存储和计算带来大麻烦(相对照而言,** 算法在分类时就要
用到所有样本,样本数巨大,每个样本维数再一高,这日子就没法过了……)。
下一节开始正式讨论 。别嫌我说得太详细哦。
+
SVM 入门(二)线性分类器
线性分类器一定意义上,也可以叫做感知机是最简单也很有效的分类器形式-在一
个线性分类器中,可以看到 形成的思路,并接触很多 的核心概念-
用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示
和
.
是要区分的两个类别,在二维平面中它们的样本如上图所示。中间的直线
就是一个分类函数,它可以将两类样本完全分开。一般的,如果一个线性函数能够将
样本完全正确的分开,就称这些数据是线性可分的,否则称为非线性可分的。
什么叫线性函数呢?在一维空间里就是一个点,在二维空间里就是一条直线,三
维空间里就是一个平面,可以如此想象下去,如果不关注空间的维数,这种线性函数
还有一个统一的名称——超平面(Hyper Plane)!
实际上,一个线性函数是一个实值函数(即函数的值是连续的实数),而我们的
分类问题(例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问
题)需要离散的输出值,例如用 表示某个样本属于类别
,而用 表示不属于(不
属于
也就意味着属于
.
),这时候只需要简单的在实值函数的基础上附加一个阈值
即可,通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。 例如我
们有一个线性函数
g(x)=wx+b
我们可以取阈值为 0,这样当有一个样本 x
i
需要判别的时候,我们就看 g(x
i
)的值。
若 g(x
i
)>0,就判别为类别 C
1
,若 g(x
i
)<0,则判别为类别 C
2
(等于的时候我们就
拒 绝判 断 ,呵 呵 ) 。 此 时 也 等 价 于 给 函 数 g(x) 附 加 一 个 符 号 函 数 sgn() , 即
f(x)=sgn [g(x)]是我们真正的判别函数。
关于 /0$/'1 这个表达式要注意三点:
一-式中的 x 不是二维坐标系中的横轴,而是样本的向量表示,例如一个样本点的
坐标是2,3,则 /
!
02,3,而不是 /02(一般说向量都是说列向量,因此以行向量
形式来表示时,就加上转置)。
二-这个形式并不局限于二维的情况,在 n 维空间中仍然可以使用这个表达式,只
是式中的 w 成为了 n 维向量(在二维的这个例子中,w 是二维向量,为了表示起来方
便简洁,以下均不区别列向量和它的转置,聪明的读者一看便知);
三-g(x)不是中间那条直线的表达式,中间那条直线的表达式是 g(x)=0,即
wx+b=0,我们也把这个函数叫做分类面。
实际上很容易看出来,中间那条分界线并不是唯一的,我们把它稍微旋转一下,
只要不把两类数据分错,仍然可以达到上面说的效果,稍微平移一下,也可以。此时
就牵涉到一个问题,对同一个问题存在多个分类函数的时候,哪一个函数更好呢?显
然必须要先找一个指标来量化“好”的程度,通常使用的都是叫做“分类间隔”的指标。下
一节我们就仔细说说分类间隔,也补一补相关的数学知识。
SVM 入门(三)线性分类器
上回说到对于文本分类这样的不适定问题(有一个以上解的问题称为不适定问
题),需要有一个指标来衡量解决方案(即我们通过训练建立的分类模型)的好坏,
而分类间隔是一个比较好的指标。
在进行文本分类的时候,我们可以让计算机这样来看待我们提供给它的训练样本,
每一个样本由一个向量(就是那些文本特征所组成的向量)和一个标记(标示出这个
样本属于哪个类别)组成。如下:
4
0/
,
/
就是文本向量(维数很高),
就是分类标记。
在二元的线性分类中,这个表示分类的标记只有两个值, 和5(用来表示属于
还是不属于这个类)。有了这种表示法,我们就可以定义一个样本点到某个超平面的
间隔:
6
0
$/
'1
这个公式乍一看没什么神秘的,也说不出什么道理,只是个定义而已,但我们做
做变换,就能看出一些有意思的东西。
首先注意到如果某个样本属于该类别的话,那么 wx
i
+b>0(记得么?这是因为
我们所选的 g(x)=wx+b 就通过大于 0 还是小于 0 来判断分类),而 y
i
也大于 0;
剩余56页未读,继续阅读
huoshandong
- 粉丝: 2
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- 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
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2