机器算法验证 - 为什么要在拟合 SVM 时遇到对偶问题？ - 吾爱随笔录

为什么要在拟合 SVM 时遇到对偶问题？

机器算法验证支持向量机

2022-01-19 02:15:51

给定数据点 $x_1, \ldots, x_n \in \mathbb{R}^d$ 和标签 $y_1, \ldots, y_n \in \left \{-1, 1 \right\}$ ，硬边距 SVM 原始问题是

{minimize}_{w, w_{0}} \frac{1}{2} w^{T} w

$\text{minimize}_{w, w_0} \quad \frac{1}{2} w^T w$

s.t. \forall i : y_{i} (w^{T} x_{i} + w_{0}) \geq 1

$\text{s.t.} \quad \forall i: y_i (w^T x_i + w_0) \ge 1$

这是一个二次程序 $d+1$ 要优化的变量和 $i$ 约束。双重的

{maximize}_{α} \sum_{i = 1}^{n} α_{i} - \frac{1}{2} \sum_{i = 1}^{n} \sum_{j = 1}^{n} y_{i} y_{j} α_{i} α_{j} x_{i}^{T} x_{j}

$\text{maximize}_{\alpha} \quad \sum_{i=1}^{n}{\alpha_i} - \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{y_i y_j \alpha_i \alpha_j x_i^T x_j}}$

s.t. \forall i : α_{i} \geq 0 \land \sum_{i = 1}^{n} y_{i} α_{i} = 0

$\text{s.t.} \quad \forall i: \alpha_i \ge 0 \land \sum_{i=1}^{n}{y_i \alpha_i} = 0$ 是一个二次规划

n + 1

$n + 1$ 要优化的变量和

n

$n$ 不平等和

n

$n$ 等式约束。

在实现硬边距 SVM 时，为什么我要解决对偶问题而不是原始问题？原始问题对我来说看起来更“直观”，我不需要关心对偶差距、库恩-塔克条件等。

如果解决双重问题对我来说是有意义的 $d \gg n$ ，但我怀疑有更好的理由。是这样吗？

4个回答

根据@user765195 的回答（谢谢！）中引用的讲义，最明显的原因似乎是：

解决原始问题，我们得到最优的 $w$ ，但对 $\alpha_i$ . 为了对查询点进行分类 $x$ 我们需要显式计算标量积 $w^Tx$ ,如果_ $d$ 很大。

解决对偶问题，我们得到 $\alpha_i$ （在哪里 $\alpha_i = 0$ 除了几个点之外的所有点 - 支持向量）。为了对查询点进行分类 $x$ , 我们计算

w^{T} x + w_{0} = {(\sum_{i = 1}^{n} α_{i} y_{i} x_{i})}^{T} x + w_{0} = \sum_{i = 1}^{n} α_{i} y_{i} ⟨ x_{i}, x ⟩ + w_{0}

$w^Tx + w_0 = \left(\sum_{i=1}^{n}{\alpha_i y_i x_i} \right)^T x + w_0 = \sum_{i=1}^{n}{\alpha_i y_i \langle x_i, x \rangle} + w_0$

如果只有很少的支持向量，则该术语的计算效率非常高。此外，由于我们现在有一个只涉及数据向量的标量积，我们可以应用内核技巧。

阅读第 13 页的第二段以及在这些注释中进行的讨论：

马腾宇和吴恩达。第五部分：内核方法。CS229 讲义。2020 年 10 月 7 日。

从数值优化的角度来看，这就是为什么对偶公式很有吸引力的一个原因。您可以在以下论文中找到详细信息：

Hsieh, C.-J.、Chang, K.-W.、Lin, C.-J.、Keerthi, SS 和 Sundararajan, S.，“大规模线性 SVM 的双坐标下降法”，Proceedings of the第 25 届机器学习国际会议，赫尔辛基，2008 年。

对偶公式涉及单个仿射等式约束和 n 个有界约束。

1. 仿射等式约束可以从对偶公式中“消除”。

这可以通过简单地查看您的数据来完成 $R^{d+1}$ 通过嵌入 $R^d$ 在 $R^{d+1}$ 由添加一个“ $1$ " 坐标到每个数据点，即 $R^d \to R^{d+1}: (a_1,..., a_d) \mapsto (a_1, ..., a_d, 1)$ .

对训练集中的所有点执行此操作将重铸线性可分性问题 $R^{d+1}$ 并消除常数项 $w_0$ 来自您的分类器，这反过来又消除了对偶的仿射等式约束。

2. 到第 1 点，对偶可以很容易地转换为一个凸二次优化问题，其约束只是有界约束。

3. 现在可以有效地解决对偶问题，即通过对偶坐标下降算法产生 epsilon 最优解 $O(\log(\frac{1}{\varepsilon}))$ .

这是通过注意固定除一个以外的所有 alpha 产生一个封闭形式的解决方案来完成的。然后，您可以一个一个地循环遍历所有 alpha（例如，随机选择一个，修复所有其他 alpha，计算封闭形式的解决方案）。可以证明，您将因此“相当快”地获得一个接近最优的解决方案（参见上述论文中的定理 1）。

从优化的角度来看，对偶问题具有吸引力还有许多其他原因，其中一些利用了它只有一个仿射等式约束（剩余约束都是有界约束）这一事实，而另一些则利用了在解对偶问题的“通常大多数阿尔法”为零（对应于支持向量的非零阿尔法）。

您可以从 Stephen Wright在 Computational Learning Workshop (2009)上的演讲中对 SVM 的数值优化注意事项有一个很好的概述。

PS：我是新来的。抱歉在本网站上不擅长使用数学符号。

在我看来，预测时间的论点（双重解决方案的预测比原始解决方案的预测更快）是无稽之谈。仅当您首先使用线性内核时，比较才有意义，因为否则您无法使用原始内核进行预测（或者至少我不清楚它是如何工作的）。但是如果你有一个线性内核，那么计算内核是点积，并且对于对偶来说比对原始的要慢得多，因为你需要至少计算 2 个（通常更多的点）。然后依靠简单的点积会快得多 $\mathbf w^Tx$ . 事实上，如果你有一个线性内核，你只需计算 $\mathbf w$ 明确地将其用于预测，就像您使用原始解决方案一样。

两个真正的论点是：

可以应用内核技巧（其他人已经提到过）
对偶问题的优化过程更加直接，并且可以通过梯度下降轻松完成

我将阐明第二点，因为对此很少有人说。

原始问题的主要问题是尽管它具有凸性，但它不能使用标准梯度下降轻松优化。如果您尝试使用梯度下降方法来解决这两个问题（原始问题和对偶问题），您可以轻松检测到这一点。顺便提一句。你制定的对偶也有一个问题，但这可以如下解决。

实际上，优化原始算法存在三件烦人的事情，至少在尝试使用梯度下降来解决它时：

没有平凡的有效初始解。事实上，已经有一个初始解决方案必须是一个完美的分离器。您可以使用感知器算法找到一个。在对偶中，您可以初始化所有 $\alpha_i := 0$ ，这也是常见的做法。值得注意的是，这对应于设置 $w = 0$ ，这不是原始的可行解决方案。然而，在对偶中这不是问题，因为只有最优解需要在原始中是可行的。
标准梯度更新规则 $\mathbf w' \leftarrow \mathbf w + \eta \nabla$ 没有多大意义，即使问题是凸的，也不会帮助您收敛到最佳状态。问题是梯度 $\nabla$ 是 $\mathbf w$ 本身，所以你实际上只会缩短或拉伸 $\mathbf w$ 但不改变它的方向。但后者通常是必要的，除非您的初始解决方案已经具有正确的斜率。
门槛 $w_0$ 目标函数中不出现，其梯度为0，但应根据变化进行更新 $\mathbf w$ .

综上所述，我个人不优化 primal 的原因是，即使它是凸的，也没有直接的梯度下降方法可以做到这一点。注意这个问题在软边距分类器中并不普遍，因为在这里你可以初始化 $\mathbf w = 0$ 并且还有更合理的梯度步骤。问题只是处理线性约束很烦人。

你提出的对偶问题在用GD解决时也很烦人，因为你仍然有平衡约束 $\sum y_i\alpha_i = 0$ . 您可以在添加时摆脱它 $\mathbf 1$ 列到数据并将其视为 $\mathbf w$ . 如果你这样做，你就不再有拉格朗日最优的条件，并且可以通过简单的批量梯度下降轻松有效地完成优化。

其它你可能感兴趣的问题

上一篇收缩方法解决了什么问题？下一篇不平衡的数据集是否存在问题，以及（如何）过采样（声称）有帮助？