10.3 SVM原理#

在前面两节内容中我们分别介绍了SVM算法的基本思想以及在sklearn的使用示例，即完成了第一阶段的学习过程。从本节内容开始，我们将开始详细介绍SVM背后的数学原理及其求解过程。根据10.1节内容可知，SVM的求解过程本质上就是最大化超平面到两侧样本点之间的间隔，因此需要先定义距离的计算公式。

10.3.1 超平面的表达#

在正式定义距离之前，这里先回顾一下超平面的表达式

$$ {{w}^{T}}x+b=0\tag{10-1} $$

其中，$w$表示权重参数（系数）； $b$表示截距；$x$表示样本点。

从上述表达式可知，当通过某种方法找到参数$w$和$b$后，也就代表确立了超平面，即求解得到了SVM分类器。下面，我们根据SVM的思想来定义对应的求解问题。

10.3.2 间隔的定义#

SVM的核心思想是最大化间隔，既然是最大化间隔那必须有对应的间隔度量方式，即样本点到超平面的距离，如图10-7所示$\text{AB}$之间的距离。

图 10-7 间隔定义图

如图10-7所示，直线方程为$w^Tx+b=0$，$A$为数据集中任意一个点${{x}^{(i)}}$，${{\gamma }^{(i)}}$为$A$到直线的距离，可以看成向量$BA$的模。$W$为垂直于$w^Tx+b=0$的法向量。此时便可以得到点$B$的坐标为

$$ {{x}^{(i)}}-{{\gamma }^{(i)}}\cdot \frac{W}{||W||}\tag{10-2} $$

又因为$B$点在直线上，所以满足

$$ {{w}^{T}}\left({{x}^{(i)}}-{{\gamma }^{(i)}}\cdot \frac{W}{||W||}\right)+b=0\tag{10-3} $$

进一步，可以通过化简等式(10-3)来得到距离的计算公式，不过此时的问题在于$W$该怎么得到。

现在假设有一直线$w^Tx+b=0,w=(w_1,w_2)^T$，即$w_1x_1+w_2x_2+b=0$，那么该直线的斜率便为$k_1=-w_1/w_2$。又因为$W$垂直于该直线，所以$W$ 的斜率为$k_2=w_2/w_1$，因此$W$的一个方向向量为$(1,k_2)$。进一步再同时乘以$w_1$即可得到$W=(w_1,w_2)=w$，即$W$其实就是$w$。也就是说，如果直线$w^Tx+b=0$，则$w$就是该直线的其中一条法向量。

所以根据式(10-3)有

$$ {{w}^{T}}\left({{x}^{(i)}}-{{\gamma }^{(i)}}\cdot \frac{w}{||w||}\right)+b=0\tag{10-4} $$

因此距离计算公式为

$$ {{\gamma }^{(i)}}=\frac{{{w}^{T}}{{x}^{(i)}}+b}{||w||}\tag{10-5} $$

同时，因为在SVM中分别用$y=+1$和$y=-1$来表示正样本和负样本，因此更一般的距离的计算公式为

$$ {{\gamma }^{(i)}}=\frac{y^{(i)}(w^Tx^{(i)}+b)}{\|w\|}\tag{10-6} $$

在式(10-6)中，分别称$\gamma^{(i)}$和$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$为任意样本$x^{(i)}$到直线$w^Tx+b=0$的几何间隔（Geometric Margin）和函数间隔（Functional Margin）。可以发现，几何间隔其实就是在函数间隔的基础上施加了一个约束限制。

如图10-8所示，直线方程为 $x_1+x_2-3=0$，$\text{A}$和$\text{B}$分别为正负样本，即$y^{\text{A}}=+1,y^{\text{B}}=-1$，那么便可以根据式(10-6)来分别计算两者各自到直线的几何距离。

图 10-8 几何间隔计算图

此时分别有

$$ \begin{aligned} & {{\gamma }^{A}}=+1\cdot \left( {{\left(\frac{w}{||w||}\right)}^{T}}{{x}^{(A)}}+\frac{b}{||w||} \right)={{\left(\frac{(1,1)}{\sqrt{1+1}}\right)}^{T}}(2,3)+\frac{-3}{\sqrt{1+1}}=\sqrt{2} \\[2ex] & {{\gamma }^{B}}=-1\cdot \left( {{\left(\frac{w}{||w||}\right)}^{T}}{{x}^{(A)}}+\frac{b}{||w||} \right)=-{{\left(\frac{(1,1)}{\sqrt{1+1}}\right)}^{T}}(1,1)+\frac{3}{\sqrt{1+1}}=\frac{1}{\sqrt{2}} \\ \end{aligned}\tag{10-7} $$

此时可以发现，只要在分类正确的情况下几何间隔将满足条件${{y}^{(i)}}\cdot {{\gamma }^{(i)}}>0$。进一步，定义训练集中样本点到超平面的几何间隔中最小值为

$$ \gamma =\underset{i=1,2,...,m}{\mathop{\min }}\,{{\gamma }^{(i)}}\tag{10-8} $$

同时，根据式(10-6)中函数间隔与几何间隔的关系有

$$ \gamma =\frac{{\hat{\gamma }}}{||w||}\tag{10-9} $$

此时，我们已经有了对于间隔度量的方式，所以下一步自然就是最大化这个间隔以便求得分类超平面。

10.3.3 最大间隔分类器#

什么是最大间隔分类器（Maximum Margin Classifier）呢？上面讲到，有了间隔的度量方式后，接着就是最大化这一间隔了，然后求得超平面$w^Tx+b=0$。最后通过函数$g(w^Tx+b)$将所有样本点输出只含$\{-1,+1\}$的值，以此来完成对数据样本的分类任务。由于$g(w^Tx+b)$是一个分类器，又因为它是通过最大化几何间隔得来的，故将其称为最大间隔分类器。

因为在式(10-8)中已经得到了几何间隔的表达式，所以再对其最大化即可

$$ \begin{aligned} &\underset{w,b}{\mathop{\max }}\,\gamma \\[2ex] \text{s}.\text{t}.\; & {{y}^{(i)}}\left[{{\left(\frac{w}{||w||}\right)}^{T}}{{x}^{(i)}}+\frac{b}{||w||}\right]\ge \gamma,i=1,2,...m \end{aligned}\tag{10-10} $$

其中$\text{s}.\text{t}.$表示服从于约束条件。同时，式(10-10)的含义就是找到参数$w$、$b$，使满足以下条件：

(1) $\gamma$尽可能大，因为其目的就是最大化$\gamma$；

(2) 同时要使样本中所有的几何距离都大于$\gamma$，因为由式(10-8)可知$\gamma$是所有间隔中的最小值。

所以，进一步由式(10-9)中函数间隔与几何间隔的关系，可以将式(10-10)中的优化问题转化为

$$ \begin{aligned} & \underset{w,b}{\mathop{\max }}\,\frac{{\hat{\gamma }}}{||w||} \\[2ex] \text{s}.\text{t}.\; & {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge \hat{\gamma },i=1,2,...m \\ \end{aligned}\tag{10-11} $$

此时可以发现，约束条件由几何间隔变成了函数间隔。

进一步，令$\hat{\gamma}=1$，式(10-11)中的优化问题便可以再次转化为如下形式

$$ \begin{aligned} & \underset{w,b}{\mathop{\max }}\,\frac{1}{||w||} \\[2ex] \text{s}.\text{t}.\;& {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1,i=1,2,...m \\ \end{aligned}\tag{10-12} $$

但是对于式(10-12)这样一个优化问题还是无法直接解决。不过，对于$f(x)>0$来讲，$\max 1/f(x)$等价于$\min f(x)$，进一步也就等价于$\min (f(x))^2$，这三者求解出的结果都相同，所以进一步可以将式(10-12)转换为

$$ \begin{aligned} & \underset{w,b}{\mathop{\min }}\,\frac{1}{2}||w|{{|}^{2}} \\[2ex] \text{s}.\text{t}.\;& {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\ge 1,i=1,2,...m \\ \end{aligned}\tag{10-13} $$

之所以要进行这样的处理，是因为这样可以将其转换为一个典型的凸优化问题，并且可用现有的方法进行求解，而在前面乘以1/2是为了后面求导时方便，同时这也不会影响优化结果。到这一步，我们便搞清楚了SVM的基本思想，以及它需要求解的优化问题。

10.3.4 函数间隔的性质#

在10.3.3节优化问题的化简过程中我们直接将函数间隔设置为了1，不少读者在这一点上仍旧比较疑惑。当然，这也是一个在学习SVM中最典型的问题，因此接下来就这一点进行简要的说明。

假设现在有以下函数间隔

$$ \hat{\gamma }={{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)\tag{10-14} $$

那么对等式(10-14)两边同时除以$\hat{\gamma}$便有

$$ {{y}^{(i)}}\left[{{\left(\frac{w}{{\hat{\gamma }}}\right)}^{T}}{{x}^{(i)}}+\frac{b}{{\hat{\gamma }}}\right]=1\tag{10-15} $$

此时令$W=\frac{w}{{\hat{\gamma }}},B=\frac{b}{{\hat{\gamma }}}$，便可以将式(10-15)转换为

$$ {{y}^{(i)}}({{W}^{T}}{{x}^{(i)}}+B)=1\tag{10-16} $$

接着把式(10-16)中的$W$和$B$换成$w$和$b$即可得到

$$ {{y}^{(i)}}({{w}^{T}}{{x}^{(i)}}+b)=1\tag{10-17} $$

不过需要明白的是，式(10-14)和式(10-17)中的$w$和$b$并不是同一个。

例如现有以下平面方程

$$ 2{{x}_{1}}+4{{x}_{2}}-8=0\tag{10-18} $$

某正样本${{y}^{(k)}}=+1$的函数间隔为${{\hat{\gamma }}^{(k)}}=2$，所以有

$$ +1(2x_{1}^{(k)}+4x_{2}^{(k)}-8)=2\tag{10-19} $$

进一步在等式(10-19)两边同时除以2有

$$ x_{1}^{(k)}+2x_{2}^{(k)}-4=1\tag{10-20} $$

虽然此时的$w$和$b$同时都缩小了两倍，函数间隔变成了1，但是$2x_1+4x_2-8=0$与$x_1+2x_2-4=0$所表示的依旧是同一个平面，所以此时可知，${{w}^{T}}{{x}^{(i)}}+b=0$与${{W}^{T}}{{x}^{(i)}}+B=0$代表的是同一个平面，故可以直接由式(10-14)得到式(10-17)，也就是说同一个平面与用什么字母表示无关，因此可以将函数间隔直接设为1（实际是同时除以了函数间隔）。

10.3.5 小结#

在本节中，我们首先回顾了超平面的表达式并且根据SVM的核心思想完成了样本点到超平面间隔的定义；然后通过最大化几何间隔得到了SVM中的求解优化问题；最后还介绍了SVM中的一个经典问题，即函数间隔为什么可以设为1。在下一节内容中将开始介绍SVM中的软间隔问题。