1.0 什么是SVM

1.1 分类中的不适定问题

简单的分类问题例子：在二维的特征平面中，已有一条决策边界将所有的数据点分两类，即蓝色圆形和黄色三角。

但实际上，可以找到多条决策边界完成相同的分类结果，这就所谓的“不适定问题”。“不适定问题”会影响模型的泛化性。比如在下图的分类中，被黄色箭头标出的点被决策边界划为蓝色圆点，但实际上它和黄色三角更近一些，这个点就是决策的“损失”。

事实上，一般分类模型都具有不适定问题，如最常用的logistics模型。为了解决或减弱不适定问题的对模型泛化能力的影响，就引出了SVM。

1.2 SVM的决策边界

SVM在寻找决策边界时，要求边界距离两个分类都尽可能的远。如下图所示：离决策边界最近的点到决策边界的距离尽可能地远。此时就可以忽略其他大部分的数据点，只关注靠近决策边界的几个特殊点即可。

1.3 SVM的定义

仍以上图为例，将最优决策边界向上和下平移，在遇到第一个点时停下来，这个点被称为支撑向量Support Vector；支撑向量到决策边界的距离是d；这两条平移后的直线的间隔（2d）被称为最大间隔Margin。

支撑向量就是支撑着两条平移边界的点，解决分类问题只需要重点研究支撑向量即可，这就是SVM名称的由来；Margin就是分界面可以移动的范围，范围越大表示容错能力越强。

所以支撑向量机的本质就是一个线性分类器，只不过这个线性分类器不仅能把样本分对，还可以最大化Margin。

2.0 SVM的目标函数

由SVM的定义可知，SVM就是要找到使得margin最大的决策边界，那么就可以将SVM转化为一个最优化问题。

2.1 Margin的函数表达

Margin是支撑向量到决策边界的距离。由空间几何知识可得在二维空间里，点到线的距离公式：

$d=\frac{\vert Ax+By+C \vert }{\sqrt[2]{A^2+B^2} }$

拓展到n维空间，点 $x$ 到 $w^Tx+b=0$ （其中 $w$ 为n为向量，即 $x$ 的系数矩阵， $b$ 为截距）的距离为 $d=\frac{w^Tx+b}{\vert\vert w \vert \vert }$ ， $\vert\vert w \vert \vert=\sqrt[2]{w_1^2+w_2^2+...w_n^2}$

则margin的范围为 $2d=\frac{2\vert w^Tx+b\vert }{\vert\vert w \vert \vert }$ 。

2.2 决策边界的函数表达

如下图所示，假设最优决策边界，下方margin边界，上方的margin边界分别为： $w^Tx+b=0$ ， $w^Tx+b=-1$ ， $w^Tx+b=1$ 。

于是得到函数方程组，该方程组的含义为：过所有点作与边界平行的直线，这些直线都应当是在margin边界之外，即所有点都要在margin之外：

进步一可得： $y_i(w^Tx_i+b)\geq 1$ 。取临界值带入margin的函数式，简化为 $2d=\frac{2}{\vert\vert w \vert \vert }$ ，此时求最大决策空间 $max(\frac{2}{\vert\vert w \vert \vert } )$ ，就转换为求 $min(\frac{1}{2} w^Tw)$ 。

综上，得到SVM的最优化问题：

$\Phi (x)=\frac{1}{2} w^Tw=\frac{1}{2}\vert\vert w\vert \vert ^2$ ， $s.t.$ $y_i(w^Tx_i+b)\geq 1$

3.0 求解SVM最优化问题

SVM的最优化问题属于有约束条件的最优问题，使用拉格朗日乘数法构造目标函数：

$L_p=\frac{1}{2} \vert \vert w \vert \vert ^2-\sum_{i=1}^la_iy_i(w^Tx_i+b)+\sum_{i=1}^la_i$ ， $a_i\geq 0$

SVM的目标就是求 $L_p$ 的最小值。

对 $L_p$ 分别对 $w$ 和 $b$ 求导，得：

$\frac{d L_p}{d w} =w-\sum_{i=1}^la_iy_ix_i=0$ $\implies$ $w=\sum_{i=1}^la_iy_ix_i$

$\frac{d L_p}{d b} =-\sum_{i=1}^la_iy_i=0$ $\implies$ $\sum_{i=1}^la_iy_i=0$

将上面两个推导结果带入目标函数 $L_p$ 中，得到一个新的目标函数 $L_D$ ：

$L_D=\sum_{i}^l a_i-\frac{1}{2} \sum_{i,j}^la_ia_jy_iy_jx_i·x_j=\sum_{i}^l a_i-\frac{1}{2} a^THa$

其中 $H_{i,j}=y_iy_jx_i·x_j$ ， $a_i\geq 0$ 。

$L_D$ 和 $L_p$ 是对偶问题，在SVM的情况下，二者是等价的，对 $L_D$ 求解即可。

求解方程，得到的 $a$ 中，大部分都为0，少部分非0，非0的就是支撑向量的系数，因为SVM只研究支撑向量。

前面求导已经得到得到 $w=\sum_{i=1}^l a_iy_ix_i$ ，再将 $w$ 带入到约束条件中 $y_i(w^Tx+b)=1$ ，等式两边同时乘以 $y_i，$ 得 $y_i^2 (w^Tx_i+b)=y_i$ 。由于 $y_i=\pm 1$ ，于是有 $b= y_i-w^Tx_i$ 。（从上图可以看出 $b$ 对于任意 $x_i$ 来说是相同的，因此选择任一点就可算出 $b$ ）。