线性支持向量机模型

和感知机模型一样,SVM(支持向量机模型)也是旨在求出n维空间的最优超平面将正负类分开。这里的达到的最优是指在两类样本点距离超平面的最近距离达到最大,间隔最大使得它区别于感知机学习,SVM中还有核技巧,这样SVM就是实际上的非线性分类器函数。

更多:支持向量机

在前一篇 逻辑回归 中已经知道逻辑回归能够完成二分类,这篇文章介绍另外一个能够实现二分类的模型:支持向量机(support vector machine,SVM)。这个名字会让初学者有很大的困惑,不理解到底什么是所谓的”支持向量”。相信通过这篇文章后,你会明白这个名称的含义。

从逻辑回归到支持向量机

支持向量机其实要做的就是找到这样一个划分超平面(w,b) ,能够在特征空间将两类样本分开,并且该超平面距离各样本最远。此外,相比于距离超平面较远的一些样本,我们更关心距离超平面较近的一些样本是否能被正确划分,这些距离焦平面较近的样本就是支持向量。也就是说,支持向量机只是使用少量的训练样本(支持向量)来学习超平面参数w和b。这是支持向量机与逻辑回归不一样的一个地方,因为逻辑回归是使用全部的训练样本学习参数w和b。可以看出,支持向量机的思想是非常简单的。

函数间隔与几何间隔

我们已经知道,支持向量机要找的超平面需要在特征空间中距离各样本最远,那如何衡量远近呢?我们可以使用间隔来衡量。说到间隔,存在函数间隔几何间隔两种。

我们先来说下函数间隔,

我们定义一个样本的函数间隔为:

也就是说训练数据上的函数间隔就是训练数据中最小的一个训练样本的函数间隔。

不过函数间隔有这样一个问题:如果等比例的改变参数w和b,这时候超平面并没有发生改变,但是函数间隔却会发生改变。比如将参数  和  同时乘以 2,函数间隔也会变为之前的 2 倍。

为了解决上面的问题,我们引入了几何间隔的概念。一个样本的几何间隔的表示如下:

可以看到,几何间隔表示的就是空间中的点x到超平面的距离。如何证明呢?其实  到超平面的距离其实等于x与超平面上某点X0 连线向法向量w 的投影:

也就是说,几何间隔就是将函数间隔对w做了归一化。类似的,所有训练数据上的几何间隔就是训练数据中最小的一个训练样本的几何间隔:

最大间隔分类器

了解了间隔之后,SVM 要做的就是找到一个划分超平面,使得距离超平面最近的样本能有更大的间隔。间隔表示距离划分超平面最近的样本到划分超平面几何间隔的两倍。

想要找到具有最大间隔的划分超平面,也就是找到满足下面公式中约束的参数w和b,

原始问题与对偶问题

前面已经得到了最大间隔分类器的目标函数,这是一个典型的带不等式约束的二次规划求解问题。这时我们可以通过一些优化的计算包来求解,不过借助拉格朗日 (Lagrange) 函数和对偶问题(dual problem), 我们可以将问题更加简化。

首先,可以将目标函数进行变形,得到:

这个性质叫做弱对偶性(weak duality),对于所有优化问题都成立,即使原始问题非凸。与弱对偶性相对应的有一个强对偶性(strong duality) ,如果满足强对偶性,对偶问题的最优解与原始问题的最优解相同。也就是说,在强对偶性成立的前提下,可以通过求解对偶问题的解来得到原始问题的解。

那么什么条件下满足强对偶性呢?一种情况是如果满足 Slater  条件,对偶问题等价于原始问题。Slater 条件是说如果原始问题是凸优化问题, 且可行域中至少有一 点使不等式约束严格成立(不等式约束严格成立是说要将不等式严格到不能取等号,在这里就是只能取小于号)。

《线性支持向量机模型》有一个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注