支持向量机(Support Vector Machine)算法原理详细推导

1.前言

支持向量机(Support Vector Machine，SVM)在2012年之前基本上是最优秀的分类算法。注意SVM常常用作分类任务，但是也可以完成回归任务。

2. 对于线性可分的数据

假设：存在线性可分的二分类数据及标签为：(x1, y1), (x2, y2), … , (xn, yn)，此时我们希望找到参数(W, b)使用模型XWT+b=0(超平面)能够将以上数据分开。

对于线性可分数据，顾名思义一定存在一条直线可以将其分开（在二维情况下）。进一步可以从数学的角度证明出：如果数据可以被一条直线线性可分，那么存在无数条直线可以将该数据分开。

因此，如下图所示，对于一个二分类线性可分数据，有无数条直线可以将其分开，那么哪一条直线将数据拆分的效果最好呢？乍一看最粗的那么条效果比较好，但是如何精确地知道哪条线最好呢？继续观看图1，我们发现两条较细的直线似乎在衡量x1、x2特征时更倾向于其中某一个特征，而较粗的直线似乎以相等的权重看待x1、x2这两个特征，这也是我们希望的，即模型对所有的特征都具有相同的权重。

图1. 二分类线性可分数据模型分类示意图

此时，为了分析或度量的方便，我们指定一个将数据划分成两类的直接效果好坏的标准。对于任何一条能将数据分开的直线，分别向垂直的两个方向移动直到至少一个数据点过平行线。如下图所示，我们将两条虚线之间的距离d作为衡量直线划分数据好坏的标准。

图2. 衡量模型好坏的标准

如图2所示，两条虚线为中间实线的平行线，两条虚线之间的距离为d，称作margin（间隔）。红色圆圈中的样本组成的向量称为支持向量，这些样本点经过虚线，或者说这些样本点被虚线插到了。而我们最终这条直线代表的模型（二维空间中为直线，高维空间中为平面）仅仅由这些支持向量所决定，与其它样本点无关。

注意实线一定要在两条虚线的正中间，即实线到两条虚线的距离相等（d/2）。如图3所示，虽然两条虚线之间的距离也是d，但实线不在正中间，这种模型不是我们希望的。

图3. 实线更偏向于左边虚线

为了进一步推导SVM的算法，我们先用数学的方式来定义线性可分的概念。对于数据集xi,yii=1~N，其中N为特征个数，其线性可分是指存在(W,b)使得对任意i=1~N，有：

1. 若yi=+1，则xiW+b ≥ 0
2. 若yi=-1，则xiW+b ≤ 0

综合上面两式得：yi(XiW+b) ≥ 0                (1)

 

定理1：XW+b=0和X(aW)+b=0为同一个平面，其中a为正实数（a∈R+），则(aW, ab)也满足(1)式。

定理2：在二维空间中点(x0, y0)到平面W1X+W2y+b=0的距离公式为：

将其推广到更高维空间中，即向量x0到超平面XW+b=0的距离为：

根据定理1，使用a缩放(W, b)得到(aW, ab)，使得在所有支持向量x0上有：

则此时支持向量到超平面的距离为：