附录 C、SVM 对偶问题

优质
小牛编辑
127浏览
2023-12-01

为了理解对偶性,你首先得理解拉格朗日乘子法。它基本思想是将一个有约束优化问题转化为一个无约束优化问题,其方法是将约束条件移动到目标函数中去。让我们看一个简单的例子,例如要找到合适的 xy使得函数 f(x, y) = x^2 + 2y最小化,且其约束条件是一个等式约束:3x + 2y + 1 = 0。使用拉格朗日乘子法,我们首先定义一个函数,称为拉格朗日函数g(x, y, alpha) = f(x, y) - alpha(3x + 2y + 1)。每个约束条件(在这个例子中只有一个)与新的变量(称为拉格朗日乘数)相乘,作为原目标函数的减数。

Joseph-Louis Lagrange 大牛证明了如果 (bar{x}, bar{y})是原约束优化问题的解,那么一定存在一个 bar{alpha},使得 (bar{x}, bar{y}, bar{alpha})是拉格朗日函数的驻点(驻点指的是,在该点处,该函数所有的偏导数均为 0)。换句话说,我们可以计算拉格朗日函数 g(x, y, alpha) 关于 x, y以及 alpha的偏导数;然后我们可以找到那些偏导数均为 0 的驻点;最后原约束优化问题的解(如果存在)一定在这些驻点里面。

在上述例子里,偏导数为

begin{align}frac{partial}{partial x}g(x, y, alpha) = 2x - 3alpha \ frac{partial}{partial y}g(x, y, alpha) = 2 - 2alpha \ frac{partial}{partial alpha}g(x, y, alpha) = -3x - 2y - 1 end{align}

当这些偏导数均为 0 时,即 2x − 3alpha = 2 − 2alpha = − 3x − 2y − 1 = 0,即可得 x = frac{3}{2}, y=-frac{11}{4}, alpha=1。这是唯一一个驻点,那它一定是原约束优化问题的解。然而,上述方法仅应用于等式约束,幸运的是,在某些正则性条件下,这种方法也可被一般化应用于不等式约束条件(例如不等式约束,3x + 2y + 1 geq 0)。如下公式 C-1 ,给了 SVM 硬间隔问题时的一般化拉格朗日函数。在该公式中,alpha^{(i)}是 KKT 乘子,它必须大于或等于 0。

译者注

alpha^{(i)}geq0抑或 leq0,取决于拉格朗日函数的写法,以及原目标函数函数最大化抑或最小化。

公式C-1

就像拉格朗日乘子法,我们可以计算上述式子的偏导数、定位驻点。如果该原问题存在一个解,那它一定在驻点 (bar{w}, bar{b}, bar{alpha})之中,且遵循 KKT 条件:

  • 遵循原问题的约束:t{(i)}((bar{w})T x^{(i)} +bar{b}) geq 1, 对于 i = 1, 2, ..., m
  • 遵循现问题里的约束,即 bar{alpha}^{(i)} geq 0
  • bar{alpha}^{(i)} = 0或者第i个约束条件是积极约束,意味着该等式成立:t{(i)}((bar{w})T x^{(i)} +bar{b}) = 1。这个条件叫做 互补松弛条件。它暗示了 bar{alpha}^{(i)} = 0和第i个样本位于 SVM 间隔的边界上(该样本是支持向量)。

注意 KKT 条件是确定驻点是否为原问题解的必要条件。在某些条件下,KKT 条件也是充分条件。幸运的是,SVM 优化问题碰巧满足这些条件,所以任何满足 KKT 条件的驻点保证是原问题的解。

我们可以计算上述一般化拉格朗日函数关于wb的偏导数,如公式 C-2。

公式C-2

令上述偏导数为 0,可得到公式 C-3。

公式C-3

如果我们把上述式子代入到一般化拉格朗日函数(公式 C-1)中,某些项会消失,从而得到公式 C-4,并称之为原问题的对偶形式。

公式C-4

现在该对偶形式的目标是找到合适的向量 bar{alpha},使得该函数 L(w, b, alpha)最小化,且 bar{alpha}^{(i)} geq 0。现在这个有约束优化问题正是我们苦苦追寻的对偶问题。

一旦你找到了最优的 bar{alpha},你可以利用公式 C-3 第一行计算 bar{w}。为了计算 bar{b},你可以使用支持向量的已知条件 t{(i)}((bar{w})T x^{(i)} +bar{b}) = 1,当第 k 个样本是支持向量时(即它对应的 0">),此时使用它计算 bar{b} =1-t{(k)}((bar{w})T . x^{(k)}) 。对了,我们更喜欢利用所有支持向量计算一个平均值,以获得更稳定和更准确的结果,如公式 C-5。

公式C-5