SVM三合一 | SVM优化推导 + 拉格朗日算子讲解(KKT条件) + hingeLoss

SVM现在主流的有两个方法。

1. 一个是传统的推导，计算支持向量求解的方法.利用拉格朗日乘子法讲约束问题转化为非约束问题进行求解。本文会先介绍这种方法。
2. 一个是近几年兴起的梯度下降的方法。梯度下降方法的核心是使用了hinge loss作为损失函数，所以最近也有人提出的深度SVM其实就是使用hinge loss的神经网络。本文在后面会介绍hinge loss的推导过程。

1 SVM的优化推导

1.1 SVM的超平面

SVM模型的基本原理，就是寻找一个合适的超平面，把两类的样本正确分开。单个SVM只能处理二分类，多分类需要多个SVM。

【什么是超平面？】 超平面就是n维度空间的n-1维度的子空间。换成人话就是2维空间中的1维度的线，三维立体空间的二维平面。

图中总共有5个超平面，那么哪一个是最好的呢？我们认为中间的那个是最好的。因为他对两侧的间隔较大。

1.2 SVM基本型

超平面我们可以用这个方程来表示：

空间中任意一个点x到这个超平面的垂直距离为：

这里不得不提到一下逻辑回归，对于逻辑回归来说：

就是在超平面一侧的样本，逻辑回归给出的预测类别是1，另外一侧就是0.

但是SVM觉得这样有一些过于绝对了，所以：

不仅仅要一个样本在平面的一侧，还要在平面的这一侧足够远的地方，才能算作某一类的样本。

从图中可以看到，两条虚线之外的点，才是SVM能确定是正样本还是负样本的点。

【什么是支持向量？】图中距离超平面最近的几个训练样本，并且这几个训练样本可以让上式的等号成立。这个点就是支持向量。

【什么是SVM的间隔】两个不同类别的支持向量到超平面的最小距离之和。其实也就是

到这里，我们可以隐隐约约的发现，寻找最优的超平面其实等价于寻找一个最大的间隔，或者说让间隔最大化。所以可以得到：这个的约束条件就是：让SVM给正样本的打分大于1，给负样本的打分小于-1,也就是：

简化一下这个约束条件，可以得到：

一般我们都是求取最小化问题，所以把最大化max问题取倒数，变成最小化问题：这里为了后续的计算方便，最小化等价于最小化,所以得到：

总之SVM的基本型就是:

1.3 SVM求解

现在求得了基本型。现在可以来进一步优化这个最小化问题。但是首当其冲的问题便是，如何处理这个约束条件。这里用到的方法是拉格朗日乘子法。将约束条件以的权重加入到优化问题中，所以可以得到：

• 这里的loss就是我们要最小化的对象；
• 这里的m就是支持向量的数量。

为了最小化这个问题，对w和b求偏导数，可以得到：

然后把这两个公式代入到：

可以消掉w和b，得到：

约束条件为：

从而根据这个计算出的取值，然后得到w和b的取值。

【到底如何求解?】上面说的最后一部求解alpha，都是理论可以求解，但是实际中如何做到呢？其实这里如何求解要用到另外一个条件。

就是上述过程要满足一个叫做KKT的条件（KKT具体是什么有点复杂，就不多说了）：

• 想要第三个公式成立，要么等于0，要么.如果alpha=0，那么意味着这个样本不是支持向量，不应该对SVM超平面起到任何影响，所以是不可能的。所以只有。

加上了这个条件，我们可以求解出来的具体数值，然后求解w和b的数值。

假设有3个支持向量，那么就会有三个 ,然后根据可以列出3个关于的三元一次方程组，然后得到唯一解。

2 拉格朗日乘子法详解

在SVM中，将约束问题转化成非约束问题采用到了拉格朗日乘子法。这个文章就讲一下拉格朗日乘子法与KKT约束是怎么回事。本人不是数学科班出身，但是也只能硬着头皮讲一讲了。

2.1 从零理解

现在我们要解决这样一个问题：这个函数距离原点最近的距离是多少。

先画出函数图像：

然后想求出最短距离：

这里的思路就是，做一个以原点为中心的圆形：

不断扩大圆形的半径，直到圆与蓝色的曲线相切：

现在。第一次与相交的点就是距离原点最近的那个点：

这个，圆形与曲线相切，且切线既是圆形的切线，也是曲线的相切。

这时候，这个切线的垂线其实也就是我们所说的梯度，也叫做等高线的法线，看下面两个图可能会好理解一些：

那么这个梯度怎么计算呢？先看圆形的梯度：

再看曲线的梯度计算的梯度：

在相切的时候，两者的梯度方向都在同一条直线上，可以称之为，成比例，这里用比例系数来表示：

所以我们汇总一下所有的已知信息，得到下面的方程组：

可以求解得到：

这个就是拉格朗日乘子法的直观理解。

2.2 抽象成数学的形式

我们要解决的问题：

我们会将约束问题通过拉格朗日乘子法转换成非约束问题：

【为什么可以这样呢？】

如果求极值，偏导数为0。先对上面的公式进行求偏导数：

这两个等式与这个等价，唯一的不同就是一个是正数一个是负数:

当然，对于这个条件，我们也可以写成，所以，可以得到这样的一个方程组：

2.3 KKT条件

• KKT的英文全称：Karush-Kuhn-Tucker

之前的拉格朗日的约束条件是等值的，现在可以通过KKT条件推广到不等式。因为限制条件往往是不大于，小于这样的不等式，所以KKT才是拉格朗日化约束问题为非约束问题的关键。

对于不等式问题，就是有两种情况：

• 可行解在g(x)<0；
• 可行解在g(x)=0。

可行解在g(x)<0，就表示这个约束条件并没有起到约束效果，有根没有事一个效果（下图中的左图）；可行解g(x)=0,就表示这个约束条件起到作用了，这就表示g(x)与f(x)相切，也就是下图中右边的图。

【g(x)<0的情况】这种情况下，就是没有限制条件下的情况，其实就是没有约束条件的限制，也就是的情况，所以我们的等式就是直接求解：

【g(x)=0的情况】如果是g(x)=0的情况，那也就是约束条件起到作用了，也就意味着。在这种情况下，存在着:并且两个函数的扩张的方向相反，所以表明两个g(x)和f(x)的梯度一个是正数，一个是负数。所以这个表示。

所以综上所述，在这种情况下，我们所有的条件综合起来可以得到，其中就是最优解：

这三个就是KKT条件。

3 Hinge Loss

【主要讨论的问题】：

• 分类任务中为什么用交叉熵而不是平方差？
• hingeloss是什么？为什么用？

3.1 SVM的基础内容

这里先介绍一下对SVM的部分基础知识，以及本文使用的算法符号。

• SVM是支持向量机，用在分类任务上，一般是二分类任务，如果是多分类任务的话，就需要多个SVM进行集成；
• SVM中的两类样本的真是标签是【+1】，【-1】，而不是神经网络中的0和1。
• 表示第n个样本的真实标签，正一或者负一；
• 就是第n个样本的SVM预测值；
• 表示第n个样本的第i个属性（特征）。这里，如果SVM是一个线性的，那么SVM模型其实就是一个线性分类器：

基本就这么多了，咱们开始看损失函数吧。

3.2 浅谈损失函数

谈到损失函数，我们必须要明确一点：分类任务的目标是什么？

对于SVM来说:

• 的时候，至少要大于0吧，也许越大越好；
• 的时候，至少要小于0吧，也许越小越好；

【为什么用“也许”呢？如果?】的时候，和哪个更好，其实我们并不能得到正确答案。因为两种情况都是分类正确的。

3.3 平方损失和交叉熵

一般的平方损失就是：

但是因为这里的两类是用+1和-1来表示的，所以可以写成这个样子：

这样的写法的话，就是希望:

• 时，;
• 时，;

这里放一个loss function的函数图：

然后上面的平方损失，就是途中的红色的曲线。我们先品一品是什么？

• 当大于0的时候，其实就是和同符号，也就是预测正确了。
• 越大的时候，也就是模型预测也稳。比较抽象哈。相当于考试的时候，你刚好61分和70分，肯定是70分的学生及格更稳一点。

回到平方损失，可以看到，平方损失在大于1的时候，损失越来越大。这个不合理呀。你考试，肯定是越高越好，不可能只要求你考70分。你考80分怎么还比70分得到更大的损失。

【这也是分类问题为什么不使用平方损失的原因。因为回归的时候，要预测的是一个数值，高了低了都不好。但是回归的时候，是一个阈值，距离这个阈值越远，越好，没有上限。】

来看一下交叉熵损失。交叉熵需要把模型的结果归一化到0~1中间，所以先对的结果，加上一个sigmoid函数。

看一下交叉熵的SVM损失函数：

这个绿色的损失看起来不错，比平方损失强多了。

目前：交叉熵完爆平方损失。

有人提出，假设使用sigmoid将限制在0~1内，那么，就可以避免平方损失在大于1的区间内出现的问题。

损失函数变成：

图像是下图中的蓝色的线。

但是sigmoid+平方损失还是不如交叉熵。举个例子：假如一个样本的非常小，那么交叉熵的梯度就会非常大而sigmoid+平方损失的梯度却非常小。非常小的梯度意味着小的变化，如果使用sigmoid+平方损失作为损失函数，会让模型收敛的非常慢。

总之，分类问题，用交叉熵非常的好。

3.4 hinge loss

那么SVM的hinge loss是什么呢？

其实这个的函数图像与交叉熵非常的像：

图中紫色的就是hinge loss的图像了，为了让其更加明显，用红色的箭头来凸显了。

【PS:有一点点像ReLu的翻转】

【Hinge Loss vs CrossEntropy】

• Hinge Loss：当大于1的时候，就达到了最好的情况，类似于，考试考及格就行了，不用最高分；
• CrossEntroy要求尽可能地得分高。我个人感觉，如果尽可能地得分高的话，可能会造成一定程度的过拟合，模型不太会兼顾全部的样本。

Hinge loss感觉就会把更多的注意力放在没有分类分的很好的那些样本上，不会再注意的样本了。像是focal loss的感觉。

最后，可以感觉到。如果线性SVM使用交叉熵损失函数的那，那就是Logistic Regression逻辑回归了。所以SVM与其他模型区分的关键就是Hinge Loss损失函数。

所以有的时候，对于一个多层感知机，使用了Hinge Loss的话，也会被成为深度SVM模型。