深入浅出SVM（PART I）

导读

今天是该系列第五篇文章，介绍支持向量机原理(PART I)。

支持向量机（Support Vector Machine）是由Vapnik等人于1995年提出来的，之后随着统计理论的发展，支持向量机SVM也逐渐受到了各领域研究者的关注，在很短的时间就得到了很广泛的应用。支持向量机是被公认的比较优秀的分类模型，同时，在支持向量机的发展过程中，其理论方面的研究得到了同步的发展，为支持向量机的研究提供了强有力的理论支撑。

本文分为两部分，先介绍SVM原理第一章。

发展历程

这部分说下SVM的发展历程，其实相当于介绍它是怎么被提出来的，由该系列第一篇文章"逻辑回归算法原理及实现"中可以看到一维特征的情况下即二维空间中的样本如果是线性可分的话可以找到一个线性的超平面来将不同类别的样本分隔开来。具体形式改写为：

接下来如果想要实现分类的功能就需要设计一个和逻辑回归里Sigmoid类似的分类决策函数：

此时，决策函数内的值若大于0，可认为是正类；否则小于0为负类。

但是要把所有样本都分类正确，也就是说分隔超平面要做到正确区分所有样本，这不是一件容易的事。为了解决这个问题，1957年由Rosenblatt提出了感知机算法，在感知机算法中直接使用通误分类的样本到分隔超平面之间的距离S作为其损失函数，并利用梯度下降法求得误分类的损失函数的极小值，得到最终的分隔超平面。 关于某一点到分隔超平面的直线最短距离，可将高中学过的二维距离公式进行拓展得到：

其中这里的b由上式转变而来。对于分类错误的样本，标签值与样本代入超平面公式所得值异号，因此取两者乘积的负数为该样本到超平面的距离：

不考虑分母的话，损失函数即为：

通过求解J的最小值，即可得到最终的分隔超平面。但是感知机这样设计的算法存在一个缺陷：那就是权重参数的初始值和选择误分类样本的顺序会对超平面的确定有很大的影响。不同的影响条件下确定的超平面就不同，那么，存不存在一个分隔性能最好的超平面呢？

函数间隔和几何间隔

一般来讲，一个样本点距离分隔超平面的远近可以表示分类预测的确信程度。为了能够表示分类预测的确信程度，我们分别定义函数间隔和几何间隔。从上一小节来看正确分类的样本代入超平面公式所得值仅仅考虑分子且去掉绝对值与标签的乘积也可等同于距离分隔超平面的远近，即为函数间隔：

同时，定义分隔超平面关于训练数据集的函数间隔为分隔超平面关于训练数据集中所有样本点的函数间隔的最小值：

但函数间隔的缺点是当权重参数发生一定倍数的变化，此时分隔超平面的空间位置并未因此而改变，也就是超平面位置对权重参数不敏感，更深一步地说是对优化问题和约束条件并没有影响。因此不利于在实际条件下模型的调优，为了解决这个问题，引入几何间隔。 为了能够使得间隔是一个确定的值，可以对分隔超平面的参数W加上某些约束，比如将W进行归一化，则距离公式可变为：

此外考虑到标签与距离是否异号，距离公式可进一步变为：

同时，定义分隔超平面关于训练数据集的几何间隔为分隔超平面关于训练数据集中所有样本点的几何间隔的最小值：

可以发现，几何间隔其实就是样本到分隔超平面的距离。对于几何间隔和函数间隔，有如下的关系：

支持向量机

在介绍了函数和几何间隔后，可以更容易地讲解SVM具体原理了。与感知机算法不同，在支持向量机中，求解出的分隔超平面不仅能够正确划分训练数据集，而且几何间隔最大，即：

同时，对于每一个样本，需要满足：

考虑到几何间隔和函数间隔之间的关系，可将上式改为：

在这里像上一小节一样为了解决函数间隔存在的问题，函数间隔可取为1，整个优化问题则变为：

SVM中与分隔超平面距离最近的样本称为支持向量。其对应着约束条件为：

为了更形象地解释什么是支持向量，可看下图。H1和H2所在的样本代入上式所得值均为0。

超平面H1和超平面H2之间的距离成为间隔，超平面H1和超平面H2又称为间隔边界。在确定最终的分隔超平面时，只有支持向量起作用，其他的样本点并不起作用，由于支持向量在确定分割超平面中起着重要的作用，因此，这种分类模型被称为支持向量机。

非线性场景

上面的介绍都是基于样本线性可分场景下的，而现实生活中大部分情况都是非线性场景(为近似线性可分和线性不可分)，近似可分中存在一些点不满足函数间隔大于或等于1的约束条件，为了解决这个问题，可以对每一个点引进一个大于等于零的松弛变量，使得函数间隔加上松弛变量大于或等于1，约束条件变为

还需要对每个松弛变量支付一个代价C，目标函数即为：

因此整个优化目标为：

到这里原理部分基本就结束了，下一部分继续讲解SVM的求解过程。