Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了线性支持向量机（Linear Support Vector Machine）。Linear SVM 的目标是找出最“胖”的分割线进行正负类的分离，方法是使用二次规划来求出分类线。本节课将从另一个方面入手，研究对偶支持向量机（Dual Support Vector Machine），尝试从新的角度计算得出分类线，推广 SVM 的应用范围。

Motivation of Dual SVM

首先，我们回顾一下，对于非线性 SVM，我们通常可以使用非线性变换将变量从 x 域转换到 z 域中。然后，在 z 域中，根据上一节课的内容，使用线性 SVM 解决问题即可。上一节课我们说过，使用 SVM 得到 large-margin，减少了有效的 VC Dimension，限制了模型复杂度；另一方面，使用特征转换，目的是让模型更复杂，减小。所以说，非线性 SVM 是把这两者目的结合起来，平衡这两者的关系。那么，特征转换下，求解 QP 问题在 z 域中的维度设为，如果模型越复杂，则越大，相应求解这个 QP 问题也变得很困难。当无限大的时候，问题将会变得难以求解，那么有没有什么办法可以解决这个问题呢？一种方法就是使 SVM 的求解过程不依赖，这就是我们本节课所要讨论的主要内容。

比较一下，我们上一节课所讲的 Original SVM 二次规划问题的变量个数是，有 N 个限制条件；而本节课，我们把问题转化为对偶问题（’Equivalent’ SVM），同样是二次规划，只不过变量个数变成 N 个，有 N+1 个限制条件。这种对偶 SVM 的好处就是问题只跟 N 有关，与无关，这样就不存在上文提到的当无限大时难以求解的情况。

如何把问题转化为对偶问题（’Equivalent’ SVM），其中的数学推导非常复杂，本文不做详细数学论证，但是会从概念和原理上进行简单的推导。

还记得我们在《机器学习基石》课程中介绍的 Regularization 中，在最小化的过程中，也添加了限制条件：。我们的求解方法是引入拉格朗日因子，将有条件的最小化问题转换为无条件的最小化问题：，最终得到的 w 的最优化解为：

所以，在 regularization 问题中，是已知常量，求解过程变得容易。那么，对于 dual SVM 问题，同样可以引入，将条件问题转换为非条件问题，只不过是未知参数，且个数是 N，需要对其进行求解。

如何将条件问题转换为非条件问题？上一节课我们介绍的 SVM 中，目标是：，条件是：。首先，我们令拉格朗日因子为（区别于 regularization），构造一个函数：

这个函数右边第一项是 SVM 的目标，第二项是 SVM 的条件和拉格朗日因子的乘积。我们把这个函数称为拉格朗日函数，其中包含三个参数：b，w，。

下面，我们利用拉格朗日函数，把 SVM 构造成一个非条件问题：

该最小化问题中包含了最大化问题，怎么解释呢？首先我们规定拉格朗日因子，根据 SVM 的限定条件可得：，如果没有达到最优解，即有不满足的情况，因为，那么必然有。对于这种大于零的情况，其最大值是无解的。如果对于所有的点，均满足，那么必然有，则当时，其有最大值，最大值就是我们 SVM 的目标：。因此，这种转化为非条件的 SVM 构造函数的形式是可行的。

Lagrange Dual SVM

现在，我们已经将 SVM 问题转化为与拉格朗日因子有关的最大最小值形式。已知，那么对于任何固定的，且，一定有如下不等式成立：

对上述不等式右边取最大值，不等式同样成立：

上述不等式表明，我们对 SVM 的 min 和 max 做了对调，满足这样的关系，这叫做 Lagrange dual problem。不等式右边是 SVM 问题的下界，我们接下来的目的就是求出这个下界。

已知是一种弱对偶关系，在二次规划 QP 问题中，如果满足以下三个条件：

• 函数是凸的（convex primal）
• 函数有解（feasible primal）
• 条件是线性的（linear constraints）

那么，上述不等式关系就变成强对偶关系，变成=，即一定存在满足条件的解，使等式左边和右边都成立，SVM 的解就转化为右边的形式。

经过推导，SVM 对偶问题的解已经转化为无条件形式：

其中，上式括号里面的是对拉格朗日函数计算最小值。那么根据梯度下降算法思想：最小值位置满足梯度为零。首先，令对参数 b 的梯度为零：

也就是说，最优解一定满足。那么，我们把这个条件代入计算 max 条件中（与同为条件），并进行化简：

这样，SVM 表达式消去了 b，问题化简了一些。然后，再根据最小值思想，令对参数 w 的梯度为零：

即得到：

也就是说，最优解一定满足。那么，同样我们把这个条件代入并进行化简：

这样，SVM 表达式消去了 w，问题更加简化了。这时候的条件有 3 个：

• all
• 
• 

SVM 简化为只有的最佳化问题，即计算满足上述三个条件下，函数最小值时对应的是多少。

总结一下，SVM 最佳化形式转化为只与有关：

其中，满足最佳化的条件称之为 Karush-Kuhn-Tucker(KKT)：

在下一部分中，我们将利用 KKT 条件来计算最优化问题中的，进而得到 b 和 w。

Solving Dual SVM

上面我们已经得到了 dual SVM 的简化版了，接下来，我们继续对它进行一些优化。首先，将 max 问题转化为 min 问题，再做一些条件整理和推导，得到：

显然，这是一个 convex 的 QP 问题，且有 N 个变量，限制条件有 N+1 个。则根据上一节课讲的 QP 解法，找到 Q，p，A，c 对应的值，用软件工具包进行求解即可。

求解过程很清晰，但是值得注意的是，，大部分值是非零的，称为 dense。当 N 很大的时候，例如 N=30000，那么对应的的计算量将会很大，存储空间也很大。所以一般情况下，对 dual SVM 问题的矩阵，需要使用一些特殊的方法，这部分内容就不再赘述了。

得到之后，再根据之前的 KKT 条件，就可以计算出 w 和 b 了。首先利用条件得到 w，然后利用条件，取任一即>0 的点，得到，进而求得。

值得注意的是，计算 b 值，>0 时，有成立。正好表示的是该点在 SVM 分类线上，即 fat boundary。也就是说，满足>0 的点一定落在 fat boundary 上，这些点就是 Support Vector。这是一个非常有趣的特性。

Messages behind Dual SVM

回忆一下，上一节课中，我们把位于分类线边界上的点称为 support vector（candidates）。本节课前面介绍了>0 的点一定落在分类线边界上，这些点称之为 support vector（注意没有 candidates）。也就是说分类线上的点不一定都是支持向量，但是满足>0 的点，一定是支持向量。

SV 只由>0 的点决定，根据上一部分推导的 w 和 b 的计算公式，我们发现，w 和 b 仅由 SV 即>0 的点决定，简化了计算量。这跟我们上一节课介绍的分类线只由“胖”边界上的点所决定是一个道理。也就是说，样本点可以分成两类：一类是 support vectors，通过 support vectors 可以求得 fattest hyperplane；另一类不是 support vectors，对我们求得 fattest hyperplane 没有影响。

回过头来，我们来比较一下 SVM 和 PLA 的 w 公式：

我们发现，二者在形式上是相似的。由 fattest hyperplane 边界上所有的 SV 决定，由所有当前分类错误的点决定。和都是原始数据点的线性组合形式，是原始数据的代表。

总结一下，本节课和上节课主要介绍了两种形式的 SVM，一种是 Primal Hard-Margin SVM，另一种是 Dual Hard_Margin SVM。Primal Hard-Margin SVM 有个参数，有 N 个限制条件。当很大时，求解困难。而 Dual Hard_Margin SVM 有 N 个参数，有 N+1 个限制条件。当数据量 N 很大时，也同样会增大计算难度。两种形式都能得到 w 和 b，求得 fattest hyperplane。通常情况下，如果 N 不是很大，一般使用 Dual SVM 来解决问题。

这节课提出的 Dual SVM 的目的是为了避免计算过程中对的依赖，而只与 N 有关。但是，Dual SVM 是否真的消除了对的依赖呢？其实并没有。因为在计算的过程中，由 z 向量引入了，实际上复杂度已经隐藏在计算过程中了。所以，我们的目标并没有实现。下一节课我们将继续研究探讨如何消除对的依赖。

总结

本节课主要介绍了 SVM 的另一种形式：Dual SVM。我们这样做的出发点是为了移除计算过程对的依赖。Dual SVM 的推导过程是通过引入拉格朗日因子，将 SVM 转化为新的非条件形式。然后，利用 QP，得到最佳解的拉格朗日因子。再通过 KKT 条件，计算得到对应的 w 和 b。最终求得 fattest hyperplane。下一节课，我们将解决 Dual SVM 计算过程中对的依赖问题。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）