机器学习笔记(九)——手撕支持向量机SVM之间隔、对偶、KKT条件详细推导

SVM概述

支持向量机(SVM)是一种有监督的分类算法，并且它绝大部分处理的也是二分类问题，先通过一系列图片了解几个关于SVM的概念。

上图中有橙色点和蓝色点分别代表两类标签，如果想要将其分类，需要怎么做呢？可能有的伙伴会想到上一篇文章讲到的逻辑回归拟合决策边界，这肯定是一种不错的方法，本文所讲的SVM也是可以解决这种分类问题的；既然都是分类算法，所以通过一个例子可以比对出二者的相同点和不同点。

超平面

可以看到，这里给出了两种划分方式，就图中实线而言，在逻辑回归中可以称作决策边界，而在SVM中它被称为超平面(hyperplane)。

上面例子中数据点都分布在二维平面上，所以此时超平面就为一条直线。如果给出的数据集是三、四、... 、N维呢？此时超平面对应的维度就是二、三、...、N-1维的，下图展示了数据集多维时的超平面。

最大间隔

对于这个例子，可以将其准确分类的超平面可能有多个，其中具有最大间隔(两条虚线之间的距离)的超平面就是SVM要找的最优解，这个最优解对应两侧虚线所穿过的样本点，就是“支持向量(support vector)”,支持向量到超平面的距离被称为间隔(margin)，如下图绘制标识。

公式推导

超平面方程

我们利用SVM算法建模最后想要从众多超平面中求解具有最大间隔的超平面，所以这也是一个最优化问题。

这里需要了解一下最优化问题的两个基本因素：

• 目标函数：你希望什么东西的什么指标达到最好。
• 优化对象：你希望改变哪些因素使目标函数达到最优。 在线性SVM算法中，目标函数就是“间隔”，优化对象则是“超平面”。

所以首先需要推导“超平面”的方程，二维空间内“超平面”的公式也就是直线方程，如下：

这里将x变成x1，y变成x2的操作是为了将其向量化。

最后将其整理成：

一般的向量为列向量，所以这里对$\omega$进行了转置，并且$\omega$向量与我们所设直线是相互垂直的，只需要假定直线斜率a为一个常数，绘图即可证明，其中$\omega$控制着直线的方向，b则控制着直线的位置，所以直线方程中需要改变$\omega$和b使目标函数达到最优。

间隔公式

“间隔”就是图中点到“超平面”的距离，公式如下：

其中d代表间隔，$||\omega||$代表的是$\omega$的二范数(模)，即对所有元素的平方和开平方。

建模的目标就是为了找到最大间隔，其中最大间隔W=2d，只要W越大，则代表该模型分类的效果越好，最后也就变成了求解d最大化的问题。

约束条件

针对上述我们所建分类器，当我们输入数据给分类器时，它会返回一个类别标签，这里先规定蓝色为负样本(-1)、红色为正样本(+1)，我们可以得到一组公式，如果超平面能够准确对图中样本点分类，则可得到以下公式：

上述公式可归化成：

s.t.表示"subject to"即服从某种条件

这里再回顾一下上面的最大间隔方程，求最大间隔的思想可以概括为求最小的点到超平面的几何距离的最大化。最小是为了分类时不同类别都能够得到准确分类，距离最大化则是为了获取”最大间隔“，以达到对分类器调优，公式如下：

如果我们希望最优的超平面的间隔的几何距离为$\gamma$,即所有样本点到超平面的几何距离至少为$\gamma$，所以下面公式一定成立。

这里$\gamma$将其设定为1。可以这么想，不论我们$\gamma$设定的是几，将等式两边同时除以$\gamma$，$\omega$和b的系数缩小了$\gamma$倍，但超平面是不动的，系数是可以同比例缩放的，可以类比直线方程。

固定$\gamma$之后，可以得到以下公式。

这里对$\omega$做了一定处理，最大化$\frac{1}{||\omega||}$和最小化$\frac{1}{2}||\omega||^2$是等价的，这样做是为了在进行最优化时对目标函数求导方便，对最优解没有影响。

其中第一个公式为我们的目标函数，第二公式也就是这个最优化问题中的约束条件，由于$min\frac{1}{2}||\omega||^2$是一个凸函数，所以这个问题是凸优化问题。

求解最优化问题

最优化问题分类

最优化问题一般可分为两大类：无约束优化问题和约束优化问题，而约束优化问题又可分为含等式约束优化问题和含不等式约束优化问题。

• 对于无约束优化问题，可以对函数求导，然后令其为零，从候选值中选取最优值，并加以验证；若函数为凸函数，则可以保证是最优解。随机梯度下降和批量梯度下降就是无约束优化方法。
• 对于含等式约束优化问题，常用的方法是利用拉格朗日乘子法将其转化为无约束优化问题求解。具体为将约束条件和函数写成一个函数，称为拉格朗日函数，系数为拉格朗日乘子；通过拉格朗日函数对各个变量求导，令其为零，从候选值中选取最优值，并加以验证。
• 对于含不等式约束优化问题，主要通过KKT条件将其转化成无约束优化问题求解。具体为通过构建拉格朗日函数，在一些条件下求出最优值的必要条件，这个条件就是KKT条件。

A的必要条件就是A可以推出的结论

对于我们所构造出的最优化问题明显是属于含不等式约束优化问题，关于拉格朗日函数的概念不过多介绍，下面介绍拉格朗日乘子法，并通过拉格朗日乘子法引出对偶问题和KKT条件。

拉格朗日乘子法

拉格朗日乘子法的思想就是通过引入拉格朗日乘子，将有d个变量和k个约束条件的最优化问题转化为d+k个变量的无约束优化问题求解。

这里感兴趣的伙伴可以搜一下大佬的博客或者西瓜书上都有详细介绍，真是后悔高数课上没有仔细听这部分。

通过引入拉格朗日乘子$\lambda$可以将上述的最优化问题转化成下面形式：

其中需要注意的是$\lambda>=0$,$1-y_i(\omega^Tx_i+b)<=0$,通过拉格朗日函数我们可以将上述公式转化为：

有的伙伴这里可能会不理解，为什么是拉格朗日函数最大值的最小化，下图介绍了原因。

很明显当$1-y_i(\omega^Tx_i+b)>0$时，目标函数取值为正无穷是没有意义的，而当$1-y_i(\omega^Tx_i+b)<=0$时,两者则是等价的。

对偶问题

利用对偶性可以将上述原问题转化成对偶问题，如下：

这个过程的主要操作就是将min和max互掉位置，并且二者之间有一个性质，即前者>=后者，这就好比在高个子人群中挑一个身高较矮的要高于在矮个子人群中挑一个身高较高的。默认情况下二者是呈弱对偶关系的，但在此目标函数和约束条件下是呈强对偶关系(等价关系)的。

在转化成对偶问题之后，我们可以先求$min_\omega,bL(\omega,b,\lambda)$,分别令函数$L(\omega,b,\lambda)$对$\omega,b$求偏导，并使其等于0。

在将上述两个式子带入至构建的拉格朗日函数中，可得：

最后整理一下得出我们推导过后最终的优化问题，如下：

KKT条件

假设有这样一个含不等式约束的优化问题：

如果想利用KKT条件处理此优化问题，需要利用拉格朗日乘子法将不等式约束、等式约束和目标函数合并写成一个式子，如下：

KKT条件就是说取到的最优值必须满足以下条件：

当原问题与对偶问题呈强对称关系是此问题满足KKT条件的充分必要条件，所以本文最优化问题满足的条件如下：

根据这些条件，我们可以得出只有在样本点为支持向量(样本点处于虚线上)时，$\lambda$可以取任意值，而其他位置的样本点$\lambda$一定为0。这就和逻辑回归有不同之处了，逻辑回归在拟合决策边界时，所有样本都会有影响，而SVM有作用的主要是边界线附近的样本。

因为我们所设超平面方程为$f(x)=\omega^Tx+b$，所以我们求得原始最优化问题的解为$\omega^、b^$，在L对$\omega$求导时得到了$\omega^$的解，而对于$b^$,求解过程如下：

这里需要注意的点是设定$(x_k,y_k)$是支持向量，所以$y_k=+1或y_k=-1$,$(y_k)^2=1$就可以消去。最终获取到的最优超平面方程如下：

总结

• 介绍了超平面与最大间隔的概念。
• 在二维空间内推导超平面方程并介绍间隔公式。
• 推导该优化问题的约束条件。
• 介绍了最优化问题的分类及对应解决思想。
• 通过拉格朗日乘子法引出对偶问题。
• 在对偶问题的基础上讲解KKT条件。
• 博主还是个菜鸟，欢迎指出文中出现的问题。 本文不包含代码，着重于公式推导，对于手写代码比较重要的部分应该在于公式推导，只有了解每一步骤的思想及由来，才能更好的进行编程，下篇文章将会介绍一个简化版的序列最小化(SMO)算法，欢迎关注、感谢阅读。

关注公众号【奶糖猫】获取更多精彩好文