支持向量机SVM（1）线性可分支持向量机、拉格朗日乘子法、KKT条件、SMO

支持向量机（SVM，Support Vecor Machine）是一种二分类算法，在集成学习和深度学习火起来之前支持向量机的使用非常广泛，其分类效果好、适用性广（线性、非线性都可用），功能真的是很棒棒，下来我们就来梳理一下支持向量机的原理。

1 支持向量机的原理

1）背景

回想一下之前讲过的逻辑回归和感知机，他们的目标都是找到一个将线性可分的数据一分为二的决策超平面：

如上图所示，决策超平面的一侧为正样本，另一侧为负样本，但是我们可以发现，满足这个特性的决策超平面并不是唯一的，在有限的线性可分样本中，正负样本点之间的间隔使得不同的决策超平面存在，那么如果样本点继续增加，这些决策超平面中那个分类效果最好呢？也就是说谁的泛华效果最好呢？——这就是支持向量机要解决的主要问题，也是支持向量机与感知机的主要区别。

2）支持向量

就上面的图来说，主观上看哪个超平面的分类泛化能力最强呢？我们认为红色的那条可能会比较好，这条线距离最近的红点区域和最近的蓝点区域都比较远，无论是红点还是蓝点，再向靠近超平面的方向增加一些点都没问题，还可以被这条超平面分的比较开，那两条虚线就没有这么好的效果，如下图所示，我们新增几个点，可以看出其分类效果的差别：

似乎可以得出这样的结论：超平面离直线两边的数据的间隔越大，对训练集的数据的局限性或噪声有最大的容忍能力，也就是所谓的鲁棒性。

所以，如果所有的样本点不只是可以被决策超平面分开，还和超平面保持一定的距离间隔，那么这样的分类超平面是更优的，支持向量机就是要找到使这个间隔最大的决策超平面（即最大化下图中的margin）。训练样本中和这个超平面距离最近的样本点被称为支持向量，如下图虚线所经过的样本点即为支持向量：

3）函数间隔、几何间隔

最大化间隔的思想我们大概了解了，不过要最大化这个间隔首先得量化，怎么量化呢？

支持向量是距离分类超平面最近的样本点，那么样本点距离超平面的距离不就是支持向量与分类超平面的距离吗？在前面的几篇文章中我们也经常提到样本点到超平面的距离的度量，这里我们就稍微详细点说下函数间隔和几何间隔。

函数间隔

在决策超平面 $𝑤^𝑇𝑥+𝑏=0$ 确定的情况下， $|𝑤^𝑇𝑥+𝑏|$ 能够表示点 $x$ 到超平面的距离远近； $𝑤^𝑇𝑥+𝑏$ 和 $y$ 是否同号能够表示分类是否正确，所以可用 $y(𝑤^𝑇𝑥+𝑏)$ 来表示分类的正确性及确定性，我们在罗辑回归和感知机中就有类似的用法，这就是函数间隔的概念，定义函数间隔 $𝛾′$ 为：

$\gamma^{'} = y(w^Tx + b)$

几何间隔

函数间隔虽然可以表示分类的正确性和确定性，但其缺点是只能在一个确定的超平面 $𝑤^𝑇𝑥+𝑏=0$ 下比较样本点到超平面的相对距离，不同参数的超平面条件下计算的距离是不能比较大小的，比如超平面 $2𝑤^𝑇𝑥+2𝑏=0$ 与 $𝑤^𝑇𝑥+𝑏=0$ 是同一个超平面，样本点与其真实距离没有变化，但是函数距离却翻了一倍，因此我们需要将参数加以约束，使其具备可比性，我们定义几何间隔：

$\gamma = \frac{y(w^Tx + b)}{||w||_2} = \frac{\gamma^{'}}{||w||_2}$

可见，几何间隔才是点到超平面的真正距离，上一篇感知机中的损失函数正是几何间隔的形式，我们支持向量机也使用几何间隔来表示支持向量到分类超平面的间隔，如上图中的margin即为两个支持向量与超平面的几何间隔之和 $\frac{2}{||w||_2}$ 。

4）线性可分支持向量机模型

综合上述内容可知，线性可分支持向量机可以表示为：

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

式中， $w^*x+b^*=0$ 为与支持向量间隔最大化的分类超平面，可见与感知机是基本一样的，就多了个间隔最大化的要求。

2 支持向量机模型求解

1）目标函数

通过上述已知，支持向量机是要最大化支持向量与决策超平面之间的几何间隔，所以目标函数为：

$\max_{w,b} \;\; \gamma = \frac{y(w^Tx + b)}{||w||_2} \;\; s.t \;\; \frac{y_i(w^Tx_i + b)}{||w||_2} \geq \gamma ,i =1,2,...m$

这个式子表示，最大化训练样本与超平面的几何间隔 $𝛾$ ，同时要保证约束条件每个训练样本与超平面的几何距离不小于 $𝛾$ ，目标函数可以改写为：

$\max_{w,b} \;\; \gamma=\frac{𝛾′}{||w||_2}\;\; s.t \;\; y_i(w^Tx_i + b) \geq 𝛾′ ,i =1,2,...m$

一般我们都取函数间隔 $𝛾′$ 为1，为什么呢，因为 $𝛾′$ 的取值不影响最优化问题的解，假设 $𝛾′$ 不为1，就相当于 $w$ 和 $b$ 变为了 $𝛾′w$ 和 $𝛾′b$ ，对目标函数和约束不等式都没有影响，都是可以约掉的，所以 $𝛾′$ 为1完全没问题，此时最优化问题变为：

$\max_{w,b} \;\; \frac{1}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 ,i =1,2,...m$

可以转变为：

$\min_{w,b} \;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 ,i =1,2,...m$

（有的地方说要最大化margin同时保证两类的支持向量到超平面的距离相等，所以有 $max\frac{2}{||w||_2}$ ，个人认为这个解释很牵强，明明优化 $\gamma$ 的过程中两类就会互相博弈找到这个最优的超平面）根据下面定义的描述发现，这个凸最优化问题是一个凸二次规划问题（convex quadratic programming）。

目标函数和约束条件都为变量的线性函数——线性规划问题；
目标函数为变量的二次函数和约束条件为变量的线性函数——二次规划问题；
目标函数和约束条件都为非线性函数——非线性规划问题。

2）对偶问题转化及求解

在感知机中我们说过，利用对偶问题可以从不同角度看待同一个问题，可能会引入新的参数来帮助我们优化，在约束最优化问题中，常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题，通过解对偶问题得到原始问题的解。

首先我们的优化目标函数可以使用拉格朗日乘子法（详细内容见附录）转变成拉格朗日函数：

$L(w,b,\lambda)= \frac{1}{2}||w||_2^2 +\sum_i^m \lambda_i [1-y_i(w^Tx_i + b)], \; \lambda_i\geq0$

目标函数的优化转变为：

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

这一步是什么意思呢，因为约束不等式 $1-y_i(w^Tx_i + b)\leq 0,\lambda_i\geq 0$ ，所以加号后面整体小于等于0，只有当其取最大值是为0，此时 $\max_{\lambda}\; L(w,b,\lambda)= \frac{1}{2}||w||_2^2$ ，即为原目标函数，这个变形称为广义拉格朗日函数的极小极大问题，它与原问题是完全等价的，在对偶性中，这个问题被称为原始问题（Primal problem）。

这个优化函数满足KKT条件（详细内容见附录），可以实现强对偶，即可以通过拉格朗日对偶（Lagrange duality）将其转化为等价的对偶问题：

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

所以我们可以先求优化函数极小值对应的 $w$ 和 $b$ ，再求的极大值对应的拉格朗日乘子系数 $\lambda$ ：

$\frac{\partial L}{\partial w} = 0 \;\rightarrow w+\sum_i^m \lambda_iy_ix_i=0 \;\rightarrow w = \sum_{i=1}^{m}\lambda_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \;\rightarrow \sum_i^m \lambda_iy_i=0$

优化函数取得极小值时， $w$ 可以用 $\lambda$ ，而 $b$ 无所谓，取什么值都不影响优化函数取得极小值，所以可得：

$\begin{align} J(\lambda)&=\min_{w,b}\; L(w,b,\lambda)\\&= \frac{1}{2}||w||_2^2 +\sum_i^m \lambda_i [1-y_i(w^Tx_i + b)]\\ &= \frac{1}{2}w^Tw-\sum_{i=1}^{m}\lambda_iy_iw^Tx_i - \sum_{i=1}^{m}\lambda_iy_ib + \sum_{i=1}^{m}\lambda_i\\ &= \frac{1}{2}\sum_{i=1}^{m}(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i-(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i- \sum_{i=1}^{m}\lambda_iy_ib + \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1}^{m}(\lambda_iy_ix_i)^T\sum_{i=1}^{m}\lambda_iy_ix_i- b\sum_{i=1}^{m}\lambda_iy_i + \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1}^{m}\lambda_iy_ix_i^T\sum_{i=1}^{m}\lambda_iy_ix_i+ \sum_{i=1}^{m}\lambda_i\\ &=-\frac{1}{2}\sum_{i=1,j=1}^{m}\lambda_iy_ix_i^T\lambda_jy_jx_j+ \sum_{i=1}^{m}\lambda_i \end{align}$

$J(\lambda)$ 完全是关于参数 $\lambda$ 的函数，因此：
$\max_{\lambda}\;\min_{w,b}\; L(w,b,\lambda)=\max_{\lambda}\;J(\lambda)=\max_{\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,\;\lambda_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,\;\lambda_i\geq0$

求出上式取得极小值时对应的 $\lambda$ 向量就可以求出 $w$ 和 $b$ 了，这里一般需要用到SMO(Sequential Minimal Optimization，序列最小优化算法) 算法，还是比较复杂的，下面来看看怎么做。

3）序列最小优化算法（SMO）

上述最优化问题是要求解 $m$ 个参数 $(λ_1,λ_2,λ_3,...,λ_m)$ ，其他参数均为已知，有多种算法可以对上述问题求解，比如之前介绍过的次梯度下降应该就可以，但是算法复杂度均很大。序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解两个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。

为什么每次优化两个参数呢？像坐标下降不是每次只优化一个参数吗？因为我们这里有个约束， $\sum_i^m \lambda_iy_i=0$ ，如果认为m-1个都是固定值，那么剩下的那个也就确定了，所以选择每次优化两个。因为SMO比较复杂，本篇文章就不细说了，这里先这样提一下SMO，大家知道上面的优化是用SMO计算的就好。

使用SMO算法，我们得到了 $\max_{λ}\;J(λ)$ 对应的 $λ^*$ ，所以：

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

因为对支持向量有： $y_i(w^Tx_i+b)=1$ ，所以要根据这个等式解出 $b$ 需要将支持向量样本点代入，怎么获得支持向量呢？KKT条件中的对偶互补条件 $λ_i(y_i(w^Tx_i+b)−1)=0$ ，我们已经求出了 $λ^*$ ，如果 $λ_i>0$ 则有 $y_i(w^Tx_i+b)=1$ ，即样本点为支持向量，求解 $b$ ：

$y_i^2(w^Tx_i+b)=y_i$

$b=y_i-w^Tx_i= y_i-\sum_{i=1}^{m}λ_i^*y_ix_i^Tx_i$

显然，支持向量大多不止一个，对线性可分支持向量机来说，可以证明分类超平面是存在且唯一的， $b$ 的解也就只有一个，此时用不同的支持向量求出来的 $b$ 都是相同的，如果数据有噪声，并不是完全线性可分的，那么为了增加模型的鲁棒性， $b$ 取所有值的平均值，即假设有n个支持向量，则：

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

至此，线性可分支持向量机的模型参数就求出来了，模型也就确定了。

4）线性可分支持向量机算法流程

综合以上全部内容，可以得到线性可分支持向量机的算法流程：

输入：线性可分的样本 $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)$ 。

确定目标函数：

$\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,\;\lambda_i\geq0$

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

根据 $λ^*$ 找到样本中的共k=1个支持向量，计算参数 $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^*)$ 。

3 线性可分支持向量机小结

线性可分支持向量机假设数据是线性可分的，这点跟感知机、逻辑回归是一样的，就是为了最大化间隔才使得线性可分SVM的理论复杂了这么多，不过对于非线性可分的数据还是没法处理，怎么办呢？我们接下来看一下基于软间隔最大化的线性支持向量机（linear support vector machine）。

附录

1）拉格朗日乘子法

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法，通过引入拉格朗日乘子，可将有d个变量与k个约束条件的优化问题转换为具有d+k个变量的无约束优化问题。这种方法引入了一种新的标量未知数，即拉格朗日乘子：它是约束方程的梯度的线性组合中，每个梯度向量的系数。

（1）无约束条件
我们一般对函数变量求导，令导数等于0的点认为是极值点。

（2）等式约束条件
设目标函数为 $f(x)$ ，约束条件为 $h_i(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n$

对于这种形式的优化问题我们一般使用拉格朗日乘子法（Lagrange multiplier），当然也能用消元法，不过太麻烦了，先从几何上理解拉格朗日乘子法（以二维为例），假设要求f(x,y)极值，约束条件 $h(x,y)=0$ ，函数 $f(x,y)$ 相当于其在三维坐标系下 $f(x,y)$ 的等高线， $h(x,y)=0$ 是一条曲线，试想如果是等高线与曲线的相交点，说明曲线还可以沿着等高线变大或变小的方向走下去，必然不是极值点，所以约束曲线 $h(x,y)=0$ 与某一条等高线 $f(x,y)=a$ 相切时，函数取得极值：

在切点处 $h(x,y)=0$ 与 $f(x,y)$ 的法向量共线，也就是函数 $f(x,y)$ 与 $h(x,y)$ 在切点处的梯度平行，有：

$\nabla f=λ'\nabla h$

因此满足：

$\begin{cases} \nabla f+λ\nabla h=0 \\ \\ h(x,y)=0 \end{cases}$

即为约束下目标函数的极值点，也可以写成我们常见的：

$F(x,y)=f(x,y)+λh(x,y)$

因为对其求导并令导数为0可得：

$\begin{cases} \frac{\partial F}{\partial (x,y)}=\nabla f+λ\nabla h =0 \\ \\ \frac{\partial F}{\partial λ}=h(x,y)=0 \end{cases}$

跟上面的方程组是一样的，这也是从代数上理解拉格朗日乘子法的方式，因此拉格朗日乘子法可以用来求多元函数在一组等式约束下的极值。

（3）不等式约束条件
设目标函数 $f(x)$ ，不等式约束为 $g(x)$ ，等式约束条件 $h(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n \\ \;\;g_j(x)\leq0,\;\;j=1,2,...,m$

在不等式约束下，极值点的位置可能有两种情况，一种是极值点被不等式约束包含，如下左图所示；另一种是极值点没有被不等式约束包含，如下右图所示：

对于第一种情况来说，显然满足 $\nabla f=0$ 即可，对于第二种情况，依然是等高线与不等式的边界相切的点为极值点，可知：

$\begin{cases} \nabla f+\mu\nabla h=0 \\ \\ h(x,y)=0 \end{cases}$

看起来似乎跟等式约束的一样，其实是有一些区别的，我们知道，等高线在切点处的梯度（也就是切线的法向量）的方向是向着等高线值增大的方向的，对于图示的凸函数来说，就是如图所示向外的，而对于不等式 $g_j(x)\leq0$ ，其梯度方向必然是相反朝向的，因为梯度要指向增长的方向，肯定会指向 $g_j(x)>0$ 的方向了：

因此，等式约束的拉格朗日乘子 $λ$ 没有符号限制，而不等式约束的拉格朗日乘子 $\mu\geq 0$ ，所以将初始求极值问题转化为：

$\begin{cases} \nabla f+\mu\nabla h=0 \\ \\ h(x,y)=0 \\ \\ \mu\geq 0 \end{cases}$

可以写成我们常见的：

$F(x,y)=f(x,y)+\sum_i^nλ_ih_i(x,y)+\sum_j^m\mu_j g_j(x,y), \;\; \mu_j\geq 0$

2）KKT条件

仍然是设目标函数 $f(x)$ ，不等式约束为 $g(x)$ ，等式约束条件 $h(x)$ ：

$min f(x) \;\\ s.t. \;\;h_i(x)=0,\;\;i=1,2,...,n \\ \;\;g_j(x)\leq0,\;\;j=1,2,...,m$

通过拉格朗日乘子法我们可以将求有约束的函数极值的问题统一转化为求解：

$\begin{cases} \nabla f+\sum_i^nλ_i\nabla h_i+\sum_j^m\mu_j \nabla g_j=0 \\ \\ h_i=0,i=1,2,...,n \\ \\ g_j\leq 0,j=1,2,...,m \\ \\ \mu_i\geq 0\\ \\ \mu_j g_j= 0 \end{cases}$

这个方程组也就是所谓的KKT条件，前面四项应该都比较好理解，最后一个 $\mu_j g_j= 0$ 是什么意思呢？在上一节不等式约束中，第一种情况不等式约束相当于不影响极值点，所以 $\mu_j= 0 ， g_j\leq 0$ ，在第二种情况中使用不等式的边界，有 $\mu_j\geq 0 ， g_j= 0$ 。

主要参考

《统计学习方法》李航
如何理解拉格朗日乘子法和KKT条件？
如何理解拉格朗日乘子法？