支持向量机SVM（2）线性支持向量机、软间隔最大化

1 原理

1）背景

线性可分支持向量机基于硬间隔最大化，所谓硬间隔最大化，我理解的就是指这个间隔最大化是被严格要求的，不允许任何例外的样本点跨过间隔边界，因此这种方法是不适用于线性不可分数据的，因为约束条件 $y_i(w^Tx_i+b)\geq1$ 是不能完全成立的，这样一来线性可分支持向量机的适用性就大大降低了，因此我们需要线性支持向量机和软间隔最大化。

2）原理

首先我们需要定义这里的线性不可分的含义，这里的线性不可分并不是指完全的线性不可分，而是指一批训练数据中有少部分的异常点，如果剔除这些异常点，剩下的大部分训练数据是线性可分的，即相当于是本来线性可分的数据中加入了一些噪音，噪音可能产生下图两种负面影响：

根据背景中的分析我们知道，对于这样的数据，线性可分支持向量机的问题是约束 $y_i(w^Tx_i+b)\geq1$ 太“硬”，太严格，数据无法满足，那么如果我们把约束放宽松一点呢？我们把约束变为：

$y_i(w^Tx_i+b)\geq1-\xi_i，\xi_i\geq 0$

式中， $\xi_i$ 是松弛变量，顾名思义它将约束条件变得宽松了，这样那些异常点也可以满足约束了，但是其 $\xi_i$ 会比较大，也就是要多“宽松”一些，如下图所示，松弛变量表示了异常点到间隔边界的函数间隔：

问题是，约束变得宽松了怎么能保证分类的效果呢？要知道支持向量机的优势就是其严格的约束使得分类超平面与两个类别间隔最大且相等，为了弥补约束放松的缺点，引入“代价” $\xi_i$ ，即放松了多少约束，就有承受多大的代价，因此目标函数变为：

$\min_{w,b,\xi}\;\frac{1}{2}||w||_2^2+C\sum_{i=1}^{m}\xi_i$

$s.t. \; y_i(w^Tx_i+b)\geq1-\xi_i，\;\xi_i\geq 0 ,\;\; i=1,2,...,m$

式中， $C>0$ 是惩罚参数， $C$ 越大对异常点的惩罚越大，约束越严格， $C$ 的具体取值由实际应用决定。这里的目标函数既要使 $\frac{1}{2}||w||_2^2$ 尽量小即间隔尽量大，又要使满足约束的样本尽量多即误分类点尽量少，这两个目标使互相矛盾的，由 $C$ 来控制二者的强弱关系。

综上所述，对于有噪音的线性不可分数据，我们选择放松其约束，相对于基于严格约束的硬间隔最大化来说，这种做法称为软间隔最大化，解决这种线性不可分数据的分类问题，基于软间隔最大化的支持向量机称为线性支持向量机（看名字也能感受到线性支持向量机应该包含线性可分支持向量机，线性可分支持向量机是松弛变量都为0的线性支持向量机特例）。

线性支持向量机模型：

$f(x)=sign(w^*x+b^*)$

$w^*x+b^*=0$ 为决策超平面，线性支持向量机看起来与线性可分支持向量机一样，只是在决策超平面的计算思路上有些不同。

2 支持向量机模型求解

1）目标函数

$\min_{w,b,\xi}\;\frac{1}{2}||w||_2^2+C\sum_{i=1}^{m}\xi_i$

$s.t. \; y_i(w^Tx_i+b)\geq1-\xi_i，\;\xi_i\geq 0 , i=1,2,...,m$

2）转化为对偶问题

转化过程与线性可分支持向量机是一样的，首先是拉格朗日乘子法：

$L(w,b,\xi,\lambda,\mu) = \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum\limits_{i=1}^{m}\mu_i\xi_i$

目标函数的优化转变为：

$\min_{w,b,\xi}\; \max_{\lambda,\mu} L(w,b,\xi,\lambda,\mu)$

通过拉格朗日对偶将其转化为等价的对偶问题：

$\max_{\lambda,\mu}\;\min_{w,b,\xi} L(w,b,\xi,\lambda,\mu)$

通过求导求里面的极小值部分：

$\frac{\partial L}{\partial w} = 0 \;\rightarrow w-{m}\lambda_iy_ix_i=0\;\rightarrow w = \sum\limits_{i=1}^{m}\alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \;\rightarrow \sum_{i=1}^m\lambda_iy_i=0$

$\frac{\partial L}{\partial \xi_i} = 0 \;\rightarrow C-\lambda_i-\mu_i=0$

代入原式可得：

$\begin{align} J(\lambda,\mu)&=\min_{w,b}\; L(w,b,\xi,\lambda,\mu) \\& = \frac{1}{2}||w||_2^2 +C\sum\limits_{i=1}^{m}\xi_i - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] - \sum\limits_{i=1}^{m}\mu_i\xi_i 　 \\&= \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1 + \xi_i] + \sum\limits_{i=1}^{m}\lambda_i\xi_i \\& = \frac{1}{2}||w||_2^2 - \sum\limits_{i=1}^{m}\lambda_i[y_i(w^Tx_i + b) - 1] \\& = \frac{1}{2}w^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - w^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - \sum\limits_{i=1}^{m}\lambda_iy_ib + \sum\limits_{i=1}^{m}\lambda_i \\& = -\frac{1}{2}\sum\limits_{i=1}^{m}\lambda_iy_ix_i^T\sum\limits_{i=1}^{m}\lambda_iy_ix_i - b\sum\limits_{i=1}^{m}\lambda_iy_i + \sum\limits_{i=1}^{m}\lambda_i \\& = -\frac{1}{2}\sum\limits_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j + \sum\limits_{i=1}^{m}\lambda_i \\& = \sum\limits_{i=1}^{m}\lambda_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\lambda_i\lambda_jy_iy_jx_i^Tx_j \end{align}$

以上这些推导的每个步骤处理的原理就不细说了，想弄明白的话可以看上一篇线性可分支持向量机

$J(\lambda,\mu)$ 完全是关于参数 $\lambda,\mu$ 的函数，因此：
$\max_{\lambda,\mu}\;\min_{w,b,\xi} L(w,b,\xi,\lambda,\mu) =\max_{\lambda,\mu}\;J(\lambda,\mu)=\max_{\lambda}\;\sum_{i=1}^{m}\lambda_i-\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j$

$s.t. \sum_i^m \lambda_iy_i=0,\;C-\lambda_i-\mu_i=0,\;\lambda_i\geq0,\;\mu_i\geq0$

转化为：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;0\leq\lambda_i\leq C$

与线性可分支持向量机基本上是一样的，只是约束不同，求出上式取得极小值时对应的 $\lambda$ 向量就可以求出 $w$ 和 $b$ 了，这里同样需要用到SMO算法来求 $\lambda$ 。

3）线性支持向量机的算法过程

输入：样本 $T=(x_1,y_1),(x_2,y_2),...,(x_m,y_m)$ ， $x$ 为 $n$ 维特征向量， $y\in[+1,-1]$ ；

输出： $w,b$ ，支持向量机模型 $f(x)=sign(w^Tx+b)$ 。

确定惩罚系数 $C>0$ ，确定目标函数：

$\min_{\lambda}\;\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j-\sum_{i=1}^{m}\lambda_i$

$s.t. \sum_i^m \lambda_iy_i=0,\;\;0\leq\lambda_i\leq C$

使用SMO优化目标函数，得到对应的 $λ^*$ ；

根据 $λ^*$ 找到样本中的共k个支持向量，计算参数 $w,b$ ：

$w^* = \sum_{i=1}^{m}λ_i^*y_ix_i$

$b^*=\frac{1}{k}\sum_i^k (y_i-w^Tx_i)$

得到支持向量机模型 $f(x)=sign(w^{*T}x+b^*)$ 。

注意：
（1）第三步计算参数 $b$ 的公式

这里的求b公式看起来跟线性可分支持向量是一样的，其实是有区别的，在上一篇中我们说过线性可分支持向量机的 $b$ 是存在且唯一的，而线性支持向量机的 $b$ 不唯一，正是因为这里的 $b$ 是考虑了松弛变量 $ξ_i$ 的，实际上求出来 $b_i=b^0+ξ_i$ ，这就是为什么 $b$ 值有多个，因为不同支持向量的 $ξ_i$ 是不相等的。

（2）第三步需要找的样本中的支持向量，怎么判断样本点是不是支持向量呢？

我们知道，所谓支持向量，就是最靠近分类超平面的，能够影响我们确定分类超平面的样本点。

我们从代数上理解，在计算超平面参数 $w$ 的那个式子可知，只要使 $λ_i^*>0$ 的样本点就会对超平面参数 $w$ 产生影响，即为支持向量，由KKT条件知， $λ_i(w^Tx_i+b-1+\xi_i)=0$ ，故此时 $w^Tx_i+b-1+\xi_i=0$ ，KKT条件中还有一条 $\mu_i\xi_i=0$ ，所以可知：

$0<λ_i<C$ 时， $\mu_i=C-λ_i>0$ ，故 $\xi_i=0$ ，支持向量 $i$ 不需要松弛变量，即支持向量在间隔边界上，如下图 $x_1$ ；
$λ_i=C$ 时， $\mu_i=C-λ_i=0$ ，故 $\xi_i>0$ ，支持向量 $i$ 在间隔边界上之外，如果 $1>\xi_i>0$ ，则支持向量 $i$ 还在分类边界与间隔边界之间，还可以被正确分类，如下图 $x_2$ ；如果 $\xi_i>1$ ，则到了分类边界另一侧，被错误分类了，如下图 $x_3$ 。

3 从合页损失函数理解线性支持向量机

以上我们讨论的支持向量机的目标函数都是从间隔最大化的角度来理解的，我们还可以通过合页损失函数的角度来理解其目标函数：

$\min_{w, b}\;[1-y_i(w \cdot x + b)]_{+} + \lambda ||w||^2$

$[z]_+=\begin{cases} z,\; z>0 \\ \\ 0 ,\;z\leq 0 \end{cases}$

式中， $[1-y_i(w \cdot x + b)]_{+}$ 是经验风险，成为称为合页损失函数（hinge loss function）； $\lambda ||w||^2$ 是L2范数表示的结构风险，也就是正则项。损失函数 $[1-y_i(w \cdot x + b)]_{+}$ 在样本点 $(x_i,y_i)$ 被正确分类且函数间隔大于1时值为0，否则损失函数值为 $1-y_i(w \cdot x + b)$ ，这个值是大于0的。

在下图中，绿色的函数即为合页损失函数，因为其形状像一个合页，故名为合页损失函数。下图中还可以看出其他多种模型损失和函数间隔的关系：

对于0-1损失函数，如果正确分类，损失是0，误分类损失1，如下图黑线，可见0-1损失函数是不可导的；
对于感知机模型，感知机的损失函数是 $[−yi(w\cdot x+b)]+$ ，这样当样本被正确分类时，损失是0，误分类时，损失是 $−yi(w\cdot x+b)$ ，如下图紫线；
对于逻辑回归和最大熵模型对应的对数损失，损失函数是 $log[1+exp(−y(w\cdot x+b))]$ , 如下图红线所示：