5.2.1 原始优化问题

我们现在推导出定义 SVM 解决方案的方程和优化问题。

fig 5.2 点 $x$ 在情况 $w \cdot x > 0$ 和 $b > 0$ 下的几何间隔示例。 0192515b-435f-75ef-9b27-37409ba7b98f_2_610_242_585_446_0.jpg

根据几何间隔的定义(也见 ^fig-5-2 )，分隔超平面的最大间隔 $ρ$ 由以下公式给出

ρ = w, b : y_{i} (w \cdot x_{i} + b) \geq 0 max i \in [m] min \frac{∣ w \cdot x _{i} + b ∣}{∥ w ∥} = w, b max i \in [m] min \frac{y _{i} ( w \cdot x _{i} + b )}{∥ w ∥} . (5.5)

第二个等式源于这样一个事实:
- 由于样本是线性可分的，对于最大化对 $(w, b)$ , $y_{i} (w \cdot x_{i} + b)$ 来说，必须对所有 $i \in [m]$ 非负。
现在，注意到最后一个表达式对于 $(w, b)$ 乘以正数标量是不变的。
- 因此，我们可以限制自己考虑那些使得 $i \in [m] min y_{i} (w \cdot x_{i} + b) = 1$ 的 $(w, b)$ 。

ρ = w, b : i \in [m] m i n y_{i} (w \cdot x_{i} + b) = 1 max \frac{1}{∥ w ∥} = w, b : \forall i \in [m], y_{i} (w \cdot x_{i} + b) \geq 1 max \frac{1}{∥ w ∥} . (5.6)

^fig-5-3 展示了最大化(5.6)的解 $(w, b)$ 。除了最大间隔超平面外，它还显示了边缘超平面，这些是

fig 5.3 (5.6) 的最大间隔超平面解。边际超平面在图中由虚线表示。 0192515b-435f-75ef-9b27-37409ba7b98f_3_555_239_699_414_0.jpg

与分离超平面平行且通过负侧或正侧最近点的超平面。由于它们与分离超平面平行，因此具有相同的法向量 $w$ 。此外，由于 $∣ w \cdot x + b ∣ = 1$ 对于最近点，边际超平面的方程为 $w \cdot x + b = \pm 1.$

由于最大化 $1/ ∥ w ∥$ 等同于最小化 $\frac{1}{2} ∥ w ∥^{2}$ ，考虑到 (5.6)，SVM 在可分情况下返回的 $(w, b)$ 对是以下凸优化问题的解:

优化问题 (5.7)

$w, b min \frac{1}{2} ∥ w ∥^{2} (5.7)$
subject to:
$y_{i} (w \cdot x_{i} + b) \geq 1, \forall i \in [m] .$

目标函数 $F : w \mapsto \frac{1}{2} ∥ w ∥^{2}$ 是无限可微的。

约束都由仿射函数 $g_{i} : (w, b) \mapsto 1 - y_{i} (w \cdot x_{i} + b)$ 定义，因此是合格的。因此，考虑到凸优化已知的结果 (详见附录B)，优化问题 (5.7) 具有唯一解，这是一个重要且有利的特点，并非所有学习算法都具备。

此外，由于目标函数是二次的，约束是仿射的，优化问题 (5.7) 实际上是二次规划(QP)的一个特例，

有许多商业和开源求解器可用于解决凸QP问题。另外，受到SVM在经验上的成功及其丰富的理论基础的启发，已经开发了专门的方法来更有效地解决这个特定的凸QP问题，尤其是只有两个坐标的块坐标下降算法。

Youliang Zhong