支持向量机简介


支持向量机(support vector machine, 或SVM)是一种监督式学习方法。它最早被用于二值分类,近年来也被用于多值分类,排序,和回归。

支持向量机源自用超平面来分割数据。我们先看这个例子:

平面分割数据

图中的两类样本线性可分,并且存在无穷多个超平面都可以将这两类样本分割。我们希望找到“最优”的 一个超平面来分割这两类样本。对图中的任意一个超平面,我们将该超平面到离它最近的样本的距离的两倍定义 为“间隔”。支持向量机将间隔最大的超平面视为最优。

用数学的语言来说,假设我们有如下训练样本:

训练样本

这里每一个xi都是一个n维向量,即

样本向量

而yi则为+1或-1。 超平面用数学形式来表达可以写成:

超平面

这里w是一个n维向量,即

w向量

而w0则是一个矢量。

对于任意样本xi,超平面到xi的“方向性距离” 可以表示为

样本到平面距离

这里所指的方向性距离,是说距离带有方向性,如果从超平面到xi是顺着 w方向,则其值为正,反之,则其值为负。而样本到超平面的真实距离则 是γi的绝对值。

由于样本的标签yi的取值为+1或-1,求间隔最大的超平面可以表达成

间隔最大

如果我们设

间隔

则上述表达式可以写成

间隔最大

这一表达式还有一个问题,那就是解不唯一,如果(w, w0)是该问题的解,则 (βw, βw0)也是该问题的解。如果我们增加一个限制 条件

模限制条件

则上述表达式可写成

间隔最大

由于平方函数的单调性,上述表达式等价于

间隔最大

该表达式是一个目标函数为凸函数的二次规划问题,可以求解。

实际问题的训练数据通常不是线性可分的,因此上式还需要作一些修改以允许错误分类的存在。这可以 通过放松限制条件来实现:

放松限制

上式中ξi大于或等于0。如果ξi在0到1之间,则相应的样本的分类 依然正确但处在“间隔”之内,如果ξi大于1,则相应的样本的分类是错的。允许错误分类 存在的支持向量机可表述如下:

支持向量机原型 (1)

式中常数C的选择可以控制拟合的程度。C取值小意味着允许在训练数据上更多错误分类的存在但两类之间的“间隔”会比较 宽,而C取值大的话则训练数据上错误分类会比较少,但两类之间的“间隔”会比较小。最优的C的取值经常是通过交叉验证 (cross validation)的方式来获取的。

式(1)依然是一个目标函数为凸函数的二次规划问题。该类问题的求解过程通常是原型和对偶型一并求解。式(1)的对偶型为:

支持向量机对偶型 (2)

点此在线求解支持向量机

喜欢我们的网站吗?
将本站加入收藏夹

或者和好友分享本站吧:
分享到QQ空间 分享到人人

对我们的网站有建议吗?
给我们来信吧。