支持向量机（三）——线性支持向量机

〇、说明

支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参考学习的是李航老师《统计学习方法（第二版）》[1]和周志华老师的西瓜书《机器学习》[2]。

如有错误疏漏，烦请指正。如要转载，请联系笔者，hpfhepf@gmail.com。

一、问题引出

一方面，线性可分支持向量机只适用于线性可分的训练数据集，对于线性不可分的训练数据集则是无能为力的。

另一方面，即使训练数据集线性可分，线性可分支持向量机强依赖于离分类超平面最近的样本[3]，过拟合的风险很大。

这时候就需要有一定容错能力的分类模型，线性支持向量机，或者叫软间隔支持向量机，就可以做到这样的容错性。

二、模型描述

这里我采用周志华老师西瓜书[2]的思路来整理这部分。

对于线性可分支持向量机，要求所有样本满足以下约束

$y_{i}(w\cdot x_{i}+b)\geq 1, \ i=1,2,\dots,N \tag{1}$

而软间隔则允许某些样本不满足这样的约束。

在最大化间隔的同时，不满足约束的样本要尽量少。此时，优化目标可以写为

$\mathop{min}\limits_{w,b} \quad \frac{1}{2} ||w||^2+C\sum_{i=1}^N L(y_{i}(w \cdot x_{i}+b)-1) \tag{2}$

其中， $L(z)$ 是一般化的损失函数， $C>0$ 被称作惩罚参数，调节间隔最大化和参数惩罚这二者关系。

我们先看惩罚参数 $C$ 。当 $C$ 值较大时对误分类惩罚较大，特别地，当C取无穷大时，所有样本都要满足式 $(1)$ 约束，模型等价于线性可分支持向量机[3]；当 $C$ 取有限值时，模型允许一些样本不满足约束。

接下来讨论损失函数 $L(z)$ 。当 $L(z)$ 使用不同的损失函数时的模型状态，周志华老师的西瓜书[2]有简单讨论。当 $L(z)$ 是合页损失函数时，模型就是线性支持向量机。李航老师《统计学习方法（第二版）》[1]的相关章节证明了线性支持向量机和基于合页损失函数的优化问题的等价性。合页损失函数如下

图1[2]

当 $L(z) = L_{hinge}(z)$ 时，式 $(2)$ 可重写为

$\mathop{min}\limits_{w,b} \quad \frac{1}{2} ||w||^2+C\sum_{i=1}^N max(0,1-y_{i}(w\cdot x_{i}+b)) \tag{4}$

引入松弛变量 $\xi_{i} \geq 0$ ，将上式再重写为

优化问题一：

$\begin{split}&\mathop{min}\limits_{w,b} \ & \frac{1}{2} ||w||^2+C\sum_{i=1}^N \xi _{i} \\& s.t. & y_{i}(w\cdot x+b)\geq 1-\xi _{i} \\&& \xi_{i} \geq 0, \ i=1,2,\dots,N\end{split}\tag{5}$

三、拉格朗日对偶问题推导

与线性可分支持向量机类似，线性支持向量机（式 $(5)$ ）的拉格朗日对偶函数如下

$L(w,b,\xi;\alpha,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_{i} + \sum_{i=1}^N\alpha_{i}(1-\xi_{i}-y_{i}(w\cdot x_{i}+b))-\sum_{i=1}^N\mu_{i}\xi_{i} \tag{6}$

原问题（式 $(5)$ ）是凸优化问题，则优化问题 $\mathop{max}\limits_{\alpha,\mu} \ \mathop{min}\limits_{w,b,\xi} \ L(w,b,\xi;\alpha,\mu)$ 与原问题等价。

第一步，求 $L(w,b,\xi;\alpha,\mu)$ 对 $w,b,\xi$ 的极小值。

$\frac{\partial}{\partial w} L(w,b,\xi;\alpha,\mu)=w-\sum_{i=1}^N \alpha_{i}y_{i}x_{i}=0 \tag{7}$

$\frac{\partial}{\partial b} L(w,b,\xi;\alpha,\mu)=-\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{8}$

$\frac{\partial}{\partial \xi_{i}} L(w,b,\xi;\alpha,\mu)=C-\alpha_{i}-\mu_{i}=0 \tag{9}$

得

$w=\sum_{i=1}^N \alpha_{i}y_{i}x_{i} \tag{10}$

$\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{11}$

$C-\alpha_{i}-\mu_{i}=0 \tag{12}$

将式 $(10)-(12)$ 代入式 $(6)$ ，可得

$\mathop{min}\limits_{w,b,\xi} L(w,b,\xi;\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \tag{13}$

第二步，求 $\mathop{min}\limits_{w,b,\xi} L(w,b,\xi;\alpha,\mu)$ 对 $\alpha,\mu$ 的极大值，即得对偶问题。

这里需要注意，式 $(13)$ 等号右边表达式没有 $\mu$ ，直接求解对 $\alpha$ 的极大值即可。对偶问题如下

$\begin{split}&\mathop{max}\limits_{\alpha} \ &-\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& C-\alpha_{i}-\mu_{i}=0 \\&& \alpha_{i} \geq 0 \\&& \mu_{i} \geq 0, \ \ i=1,2,\dots,N\end{split} \tag{14}$

上式中，因为 $\mu$ 不在最优化表达式中，可以利用等式约束消去，简化约束。再把求极大转换成求极小，得到对偶问题如下

优化问题二：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) - \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2,\dots,N\end{split} \tag{15}$

第三步，求解分类超平面和分类模型。

对于已求解出优化问题二（式 $(15)$ ）的最优解 $\alpha^*$ ，则类似于线性可分支持向量机[3]的推导过程。

原问题（式 $(5)$ ）是凸优化问题，则满足KKT条件的点是原问题和对偶问题的最优解（具体请参见[4]）

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*)\geq 1-\xi^* _{i},\ i=1,2,\dots,N \tag{16a}\\& \xi^*_{i} \geq 0, \ i=1,2,\dots,N \tag{16b} \\& \alpha^*_{i} \geq 0, \ i=1,2,\dots,N \tag{16c} \\& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0 \tag{16d} \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \tag{16e}\\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{16f} \\& \frac{\partial}{\partial b} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{16g} \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N\tag{16h} \end{align}$

根据式 $(16f)$ 可得

$w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \tag{17}$

观察式 $(16d)$ 、 $(16e)$ 和 $(16h)$ ，先看式 $(16d)$ ，当 $0 <\alpha^*_{i}<C$ 时，有

$y_{i}(w^* \cdot x_{i}+b^*)=1-\xi^*_{i} \tag{18}$

再看式 $(16h)$ ，当 $0 <\alpha^*_{i}<C$ 时，有 $\mu^*_{i}=C-\alpha^*_{i}>0 \tag{19}$

此时再看式 $(16e)$ ，当 $\mu^*_{i} >0$ 时，必有 $\xi^*_{i}=0$ ，综上讨论，当 $0 <\alpha^*_{i}<C$ 时，有

$y_{i}(w^* \cdot x_{i}+b^*)=1 \tag{20}$

再将式 $(17)$ 代入上式，并于式 $(17)$ 联立，可得线性支持向量机的最优分类超平面参数为

$\begin{align}& w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \\& b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) , \ 0 </p><p>这里需要注意，在李航老师《统计学习方法（第二版）》[1]相关章节中，和式<img class=$

这里需要注意，在李航老师《统计学习方法（第二版）》[1]相关章节中，和式 $(16h)$ 相同表达的式子是不严谨的，如果没看到这一段，这句话略过。

四、支持向量

线性支持向量机的支持向量会复杂一些。如下图

图1[1]

首先，定义 $\alpha^*_{i}>0$ 的样本点 $(x_{i},y_{i})$ 为支持向量。

其次，每个支持向量 $(x_{i},y_{i})$ 到其对应的间隔边界的距离为 $\frac{\xi^*_{i}}{||w^*||}$ 。推导过程如下。

点到超平面的距离公式为： $r=\frac{|w\cdot x+b|}{||w||}$

先看正类，正类的间隔边界超平面为： $w^*\cdot x+b^*=1$ ，对应的点到间隔边界超平面的距离公式为： $r=\frac{|w^*\cdot x_{i}+(b^*-1)|}{||w^*||}$ 。对于正例的支持向量，有 $y_{i}=+1$ ，根据式 $(18)$ ，有 $w^*\cdot x_{i} +b^*-1=\xi^*_{i}$ ，代入距离公式，即可到结论。