本文是机器学习技法系列文章的第二篇。介绍了拉格朗日对偶、KKT条件、对偶支持向量机算法的推导过程。

---

---

2. Dual Support Vector Machine

上一节介绍了线性支持向量机（Linear Support Vector Machine），其通过最小化各样本点到分隔超平面（二维空间中为一条直线）来找到最大的margin，降低VC Dimention，从而减少算法复杂度，进而提高模型泛化能力，求解方法是二次规划（QP）求解。那些能决定margin的样本点就成为支撑向量。本节课介绍另一种支持向量机，如题，即对偶支持向量机（Dual Support Vector Machine）。

---

2.1 Motivation of Dual SVM

回顾非线性SVM的求解方法，如上图所示。首先，通过特征转换函数 $\Phi$Φ ，将非线性空间中的 $x$x 变换到线性空间中的 $z$z ，然后，使用线性SVM的求解方法二次规划求解。二次规划的求解流程是将待求解参数 $z$z 转换成矩阵 $Q,p,a,c$Q,p,a,c ，通过最小化这四个参数矩阵决定的 $u$u ，求出合适的参数，进而求出 $z$z，然后反变换，求解非线性空间中的参数 $w,b$w,b 。此时对应的假设空间中的假设函数即为最优的假设函数，亦即最好的分类器矩g：

$g_{SVM}(x) = sign(w^TΦ(x) + b)$gSVM​(x)=sign(wTΦ(x)+b)

在以上求解过程中，通过最大化margin（边界），来降低算法复杂度；通过特征转换实现非线性分类。但是二次规划求解，要求解 $\tilde{d} + 1$d~+1 个变量，$N$N 个限制条件。求解的结果与两个参数有关，并且当 $\tilde{d}$d~ 很大时，会使得不易求解。为简化计算，将以上求解SVM的方法转化为对偶问题求解。其对比如下图所示：

转化成对偶问题后，可以发现求解结果只和 $N$N 有关，即变量变为 $N$N，限制条件变为 $N+1$N+1；并且经过特征转换之后，仍然只与 $N$N 有关。有关对偶SVM的求解，涉及到很多很深入的数学优化理论，本节课中并没有深入详细地讲解对偶SVM的求解流程，而是只在必要和关键步骤上下功夫，来辅助深入理解Dual SVM算法。如果对详细的推导过程感兴趣，可以翻阅相关的书籍。

回顾之前在正则化中学习的一个有力的工具：拉格朗日乘子。

正则化要解决的是有条件的最优化问题，想办法最小化 $E_{in}$Ein​ ，加入的限制条件是 $w^Tw\le C$wTw≤C，约束 $w$w 的长度不能太大。但是有条件的最优化问题不容易求解，因此通过一番推导，可以将这个限制条件融合到要最小化的目标函数中，从而将误差函数（目标函数）变为 augmented error（增广误差），进而将要求解的有条件的最优化问题转换为没有限制条件的最优化问题。最后，通过最小化转化后的目标函数 $E_{aug}(w)$Eaug​(w) 求解即可。其核心思想是：引入拉格朗日乘子 $\lambda$λ，将每个限制条件乘以一个系数，添加到目标函数中，再最优化求解。

在正则化中，限制条件 $w^Tw\le C$wTw≤C 中的 $C$C 等价于已知的大于零的 $\lambda$λ，容易求解。SVM本质上也是有条件的最优化问题，在对偶SVM中，也可以引入 $\lambda$λ 来代替限制条件（共 $N$N 个 $\lambda$λ ，每个限制条件一个），将其作为未知量求解，从而将有条件的最优化问题转换为无条件的最优化问题，使得易于求解。

如何转换呢？其转换思路如下：
约定：在很多SVM的文献或书籍中常常将拉格朗日乘子标记为 $\alpha_n$αn​ ，此后的推导也使用这个符号。

首先构造一个拉格朗日函数，这个函数中就包含了原来的目标函数和限制条件，引入了拉格朗日乘子，使得这个函数看起来好像没有限制条件。构造的函数中包含三个参数：$\alpha_n,w,b$αn​,w,b。通过这个函数，再加如下规则，就完成了转换：

这里的SVM表达式中包含最外层的最小化和内层的最大化，并且拉格朗日乘子 $\alpha_n \ge 0$αn​≥0 。首先看最大化，当没有最优解时，$1 − y_n(w^Tz_n+ b) \ge 0$1−yn​(wTzn​+b)≥0 ，又因为 $\alpha_n \ge 0$αn​≥0 ，所以求和之后恒为正，其最大值趋于无穷（$\infin$∞）；当有最优解时，拉格朗日函数中的限制条件项 $1 − y_n(w^Tz_n+ b) \le 0$1−yn​(wTzn​+b)≤0 恒成立， 又因为 $\alpha_n \ge 0$αn​≥0 ，所以求和之后必定小于零0，所以存在最大值，这个最大值就是原来的目标函数 $\frac{1}{2} w^Tw$21​wTw。再看最小化，此时对于存在最优解的情况，即为最小化目标函数 $\frac{1}{2} w^Tw$21​wTw。

---

习题1：

---

2.2 Lagrange Dual SVM

首先令 $\alpha'$α′ 表示非负的固定值的拉格朗日乘子，因为最大值肯定大于集合中所有元素，所以可以去掉内层括号，这就得到了上图中的第一个不等式。

作进一步转化，求解拉格朗日函数的最大值，得到上图中的第二个不等式。经过这两步转化，就把原来的目标函数中先求最大值再求最小值的问题转化为先求最小值再求最大值的问题。这样，将最大值最小值求解顺序做了对调，因为使用拉格朗日函数导出，所以称为拉格朗日对偶问题（Lagrange dual problem）。

也就是说，如果把对偶问题解决了，就得到原来目标函数的下限。下一步的工作就是要求出这个下限。

这种不等式（‘$\ge$≥’）在学术上称为弱对偶性（weak duality），如果以上不等式可以变为等式，则就变为强对偶性（strong duality），此时，原目标函数的求解就等价于对偶问题的求解，或者说求解出的 $w,b, \alpha$w,b,α 对等式两边的目标函数来说都是最优解。可以通过二次规划（QP）将弱对偶转化为强对偶。需要满足以下三个约束条件（constraint qualification）：

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

转化之后，要求解的拉格朗日对偶问题变为：

上式中，括号内为最小化拉格朗日函数 $L$L，括号外为求最大值。为简化运算，下面作进一步转化。
对于括号中的最小值计算，根据梯度下降算法的思想，梯度=0，首先将括号内的拉格朗日函数对偏置 $b$b 求偏导：

求导后，得到条件 $\Sigma ^N_{n=1}α_ny_n= 0$Σn=1N​αn​yn​=0，对拉格朗日对偶问题做进一步简化：

这样就把偏置 $b$b从目标函数中去掉了。经过简化后的拉格朗日问题变为：

处理完了参数偏置 $b$b，接下来对权重向量 $w_i$wi​ 求偏导：

通过上式运算，得到 $w$w 的限制条件；此时共有如下条件：

• $all α_n≥0$allαn​≥0；
• $\Sigma y_nα_n=0$Σyn​αn​=0；
• $w=\Sigma α_ny_nz_n$w=Σαn​yn​zn​

代入拉格朗日对偶问题：

至此，就得到了拉格朗日对偶问题的简化本，即将原来带限制条件求解参数 $w,b, \alpha$w,b,α 的问题，转化为无约束条件的求解参数 $\alpha$α 的问题。

---

KKT Optimality Conditions

拉格朗日对偶问题需要满足以下条件：

• 满足原始问题的条件 $y_n(w^Tz_n+ b) ≥ 1$yn​(wTzn​+b)≥1；
• 满足拉格朗日对偶问题的条件 $α_n≥ 0$αn​≥0；
• 满足拉格朗日对偶问题内括号的条件 $\Sigma y_nα_n=0; w =\Sigma α_ny_nz_n$Σyn​αn​=0;w=Σαn​yn​zn​，即最小化括号内朗格朗日函数的条件；
• 满足对偶SVM目标函数内括号的条件 $α_n(1 − y_n(w^Tz_n+b)) = 0$αn​(1−yn​(wTzn​+b))=0；这个条件又称为松弛条件（Complimentary Slackness），即该等式的两部分 $\alpha_n$αn​ 和 $(1 − y_n(w^Tz_n+b)$(1−yn​(wTzn​+b) 至少要有一部分为零。

以上这些条件称为 KKT条件（ Karush-Kuhn-Tucker conditions）。

下一小节介绍使用KKT条件计算最优化问题中的 $\alpha_n$αn​ ，进而求出 $b,w$b,w。

---

习题2：

2.3 Solving Dual SVM

上一小节中得到的拉格朗日对偶问题的最优化公式为：

从之前的学习经验可知，求解最优化问题最常用的是最小化，上式是最大化，那么就需要进一步的转化，转化为最小化问题。根据以往的经验，在原函数基础上添加负号，同时转换成矩阵乘法，即可实现转化：

这里的表达式没有 $w=\Sigma α_ny_nz_n$w=Σαn​yn​zn​ 条件，只专心求解 $\alpha$α ，其实 $w$w 的限制条件是隐藏的条件。此时，转化为有 $N$N 个变量和 $N+1$N+1 的限制条件的二次规划问题。二次规划问题的求解：

一般的二次规划问题中，需要四个参数：

• Q：二次项的系数；$q_{n,m}$qn,m​
• p：一次项的系数；$p$p
• A：条件里的系数；$a^T_n$anT​
• c：条件中的常数；$c_n$cn​

然后使用相应的二次规划计算程序即可求解。注意：许多求解的工具包针对等式（$a≥，a≤$a≥，a≤）和边界（$a_n$an​）约束考虑数值稳定性，封装好了函数接口。所以，实际使用过程中不需要做这么复杂的拆解。但是有以下问题需要注意：

如果 $N$N 非常大，则会导致运算消耗大量的计算资源。通常在实践中，最好使用特殊的求解器求解二次规划问题。

求解出 $\alpha_n$αn​ 之后，再根据KKT条件，即可求解出 $w,b$w,b，求解过程如下：

先利用公式求解 $w$w，然后找一个大于零的 $\alpha_n$αn​ 求解 $b$b 。使得等式 $y_n(w^Tz_n+ b) =1$yn​(wTzn​+b)=1 成立的样本点表示落在margin上的点，即支持向量。

---

习题3：

---

2.4 Messages behind Dual SVM

在上一节介绍的线性支持向量机中，支持向量（Support Vector, SV）的定义是决定margin（边界）的样本点或者说落在margin上的样本点。本节课的对偶支持向量又加了一个限制，即 $\alpha_n > 0$αn​>0，并且证明了满足这个条件的样本点一定落在margin上，即一定是支持向量。根据这个定义，对偶支持向量机中对SV的定义是 $\alpha_n>0$αn​>0 的样本，其它落在margin上但不满足此条件的样本不是SV。也就是说，通过 $\alpha_n>0$αn​>0 这个限制条件，可以把落在margin上的样本点分为两类，一类可以决定“最胖”（边界最宽）超平面（hyperplane），另一类对超平面的选取没有影响。

学到这个地方，发现SVM好像跟之前学习的PLA有点相像：

SVM和PLA算法的权重向量参数 $w$w 的表达式形式相同，都有系数；$w_{SVM}$wSVM​ 由满足 $\alpha_n>0$αn​>0 的支持向量（落在margin上的样本点）决定；$w_{PLA}$wPLA​ 由当前分类错误的样本点决定。其实梯度下降（GD）、随机梯度下降（SGD）、逻辑回归、线性回归算法中也有类似的表示。即权重向量 $w$w 可以表征原始数据。

对比一下之前一节课和本节课所学的两种支持向量机，即线性支持向量机（可以通过特征空间转换，求解非线性支持向量机）和对偶支持向量机。这两种支持向量机都是硬边界（Hard-Margin）的支持向量机，即要求样本点严格的可分。两者都使用二次规划（QP）求解。

对于线性支持向量机而言，有 $\tilde{d} + 1$d~+1 个变量需要求解，有 $N$N 个限制条件；当VC Dimention比较大时，计算比较困难，不易求解。而对偶支持向量机，有 $N$N 个变量需要求解，有 $N+1$N+1 的限制条件，当数据量比较大时，求解也比较困难。两者最后求解出的参数 $(w,b)$(w,b) 对应的假设函数即为最佳的假设函数矩g：

$g_{SVM}(x) = sign(w^TΦ(x) + b)$gSVM​(x)=sign(wTΦ(x)+b)

将使用拉格朗日乘子构造的拉格朗日函数引入原始的SVM变为对偶SVM的目的是：消除原始的SVM求解过程中VC Dimention $\tilde{d}$d~ 的影响，但是通过本节课可以知道，实际上并没有真正消除 $\tilde{d}$d~ 的影响，因为在二次规划中求解二次项系数 $q_{n,m}=y_ny_mz^T_nz_m$qn,m​=yn​ym​znT​zm​ 中由 $z$z 引入了 $\tilde{d}$d~，所以只是从构造的表达式中看起来好像没有影响了。下节课将介绍如何消除对 $\tilde{d}$d~ 的影响。

---

习题4：

---

Summary

本节课一开始提出问题，为了消除一般的支持向量机计算过程中，VC Dimention $\tilde{d}$d~ 的影响，通过引入拉格朗日乘子，构造拉格朗日函数，通过KKT条件限制，构造了对偶支持向量机，同样使用二次规划求解。与一般的支持向量机的区别是，得到了更精细化的 支持向量 ，即满足拉格朗日乘子 $\alpha_n >0$αn​>0 条件并且在margin上的样本点才是支持向量。

---