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

作者: 蛋仔鱼丸 | 来源:发表于2020-06-15 21:02 被阅读0次

支持向量机
穷则变，变则通：支持向量机
11 SVM - SMO - 序列最小优化算法
支持向量机SVM（3）核函数、非线性支持向量机
支持向量机-QA
支持向量机SVM（2）线性支持向量机、软间隔最大化
机器学习-吴恩达笔记7
07 SVM - 软间隔模型
支持向量机SVM
ML--支持向量机

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))]$ , 如下图红线所示：

多种损失函数的图像

*图像来自博客刘建平Pinard

4 线性支持向量机小结

线性支持向量机通过软间隔最大化的方式，处理因噪声导致的线性不可分数据的分类问题，究其根本，只是在线性可分数据基础上做了一点妥协，并不是真的可以处理线性不可分数据的分类问题，对于真的非线性可分的问题，应该怎么办呢？我们接下来看看基于核函数的非线性支持向量机。

主要参考

《统计学习方法》李航
刘建平Pinard

支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
穷则变，变则通：支持向量机
线性可分支持向量机通过硬间隔最大化求出划分超平面，解决线性分类问题；线性支持向量机通过软间隔最大化求出划分超平面...
11 SVM - SMO - 序列最小优化算法
05 SVM - 支持向量机 - 概念、线性可分06 SVM - 线性可分模型算法和案例07 SVM - 软间隔模...
支持向量机SVM（3）核函数、非线性支持向量机
前面已经分别介绍了基于硬间隔最大化的线性可分支持向量机、基于软间隔最大化的线性支持向量机，这次来总结下使用核函数来...
支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
支持向量机SVM（2）线性支持向量机、软间隔最大化
1 原理 1）背景线性可分支持向量机基于硬间隔最大化，所谓硬间隔最大化，我理解的就是指这个间隔最大化是被严格要...
机器学习-吴恩达笔记7
Week7-SVM 本周主要是讲解了支持向量机SVM的相关知识点硬间隔支持向量软间隔对偶问题优化目标Op...
07 SVM - 软间隔模型
六、硬间隔和软间隔模型之前两章介绍的内容是硬间隔模型：《05 SVM - 支持向量机 - 概念、线性可分》《06...
支持向量机SVM
支持向量机SVM（Support Vector Machine）【关键词】支持向量，最大几何间隔，拉格朗日乘子法...
ML--支持向量机
ML——支持向量机支持向量机（SVM）是一种二类分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类...

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

1 原理

1）背景

2）原理