《近似线性可分支持向量机的原理推导》KKT（Karush-Kuhn-Tucker）条件 公式解析

本文是将文章《近似线性可分支持向量机的原理推导》中的公式单独拿出来做一个详细的解析，便于初学者更好的理解。

公式 9-51 到 9-59 是在近似线性可分支持向量机（SVM）的优化过程中推导出来的 KKT（Karush-Kuhn-Tucker）条件。KKT 条件是求解带约束优化问题的必要条件，通过这些条件，我们可以找到支持向量机的最优解。接下来，我将详细解释这些公式及其作用。

背景

我们从原始问题的拉格朗日函数出发：
$$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i\left(y_i(w^T{x}_i+b)-(1-{\xi }_i)\right)-\sum _{i=1}^N{\mu }_i{\xi }_i$$

通过对拉格朗日函数对 $w$、$b$、和 ${\xi }_i$ 求偏导数并设为 0，以及利用 KKT 条件，我们可以得到公式 9-51 到 9-59。

公式解释

公式 9-51

$$\frac{\partial L}{\partial w}=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0$$

• 解释：对 $L$ 关于 $w$ 求偏导数并设为 0。
• 含义：该公式表明权重向量 $w$ 可以表示为一系列样本点的线性组合。换句话说，最优的 $w$ 是支持向量（即 ${\alpha }_i>0$ 的点）乘以对应标签 $y_i$ 和特征 $x_i$ 的加权和。
• 解出：可以得到 $w$ 的表达式：
  $$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$

公式 9-52

$$\frac{\partial L}{\partial b}=-\sum _{i=1}^N{\alpha }_i{y}_i=0$$

• 解释：对 $L$ 关于 $b$ 求偏导数并设为 0。
• 含义：这个条件确保了所有支持向量的贡献在决策边界上是平衡的。
• 解出：可以得到如下约束：
  $$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

公式 9-53

$$\frac{\partial L}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0$$

• 解释：对 $L$ 关于 ${\xi }_i$ 求偏导数并设为 0。
• 含义：这个条件确保惩罚系数 $C$ 与拉格朗日乘子 ${\alpha }_i$ 和 ${\mu }_i$ 之间的关系。它表明每个样本的 ${\xi }_i$ 都要满足这个平衡条件。
• 解出：可以得到如下关系：
  $${\alpha }_i+{\mu }_i=C$$

公式 9-54（互补松弛条件）

$${\alpha }_i\left(y_i(w^T{x}_i+b)-1+{\xi }_i\right)=0$$

• 解释：这是 KKT 条件中的互补松弛条件之一。
• 含义：如果 ${\alpha }_i>0$，那么 $y_i(w^T{x}_i+b)-1+{\xi }_i=0$，说明这个点正好落在分类边界上，是一个支持向量。反之，如果 $y_i(w^T{x}_i+b)-1+{\xi }_i>0$，则 ${\alpha }_i=0$，即这个点不是支持向量。
• 直观理解：互补松弛条件确保了只有支持向量的 ${\alpha }_i$ 才会对分类边界产生影响。

公式 9-55（互补松弛条件）

$${\mu }_i{\xi }_i=0$$

• 解释：这是另一个互补松弛条件。
• 含义：如果 ${\mu }_i>0$，则 ${\xi }_i=0$，这意味着该点严格满足分类边界条件；如果 ${\xi }_i>0$，则 ${\mu }_i=0$，即此时允许该点不满足严格的分类边界条件。
• 直观理解：该条件确保了只有误分类的点才会有非零的松弛变量 ${\xi }_i$，而那些在间隔内或超出间隔的点的松弛变量 ${\xi }_i$ 为 0。

公式 9-56

$$y_i(w^T{x}_i+b)-1+{\xi }_i\ge 0$$

• 解释：这是分类间隔的约束条件。
• 含义：这表明对于每个样本点，模型输出与真实标签 $y_i$ 的乘积至少要大于等于 $1-{\xi }_i$。
• 直观理解：这表明在软间隔的情况下，允许有误差（即 ${\xi }_i>0$）的样本点。

公式 9-57

$${\xi }_i\ge 0$$

• 解释：这是松弛变量的非负约束。
• 含义：松弛变量 ${\xi }_i$ 是非负的，这意味着我们允许一定程度的误分类或间隔违规，但不允许出现负间隔。
• 直观理解：保证松弛变量为非负值，以确保松弛变量可以表示样本点与超平面的正确偏差。

公式 9-58

$${\alpha }_i\ge 0$$

• 解释：这是拉格朗日乘子 ${\alpha }_i$ 的非负约束。
• 含义：该条件确保拉格朗日乘子 ${\alpha }_i$ 为非负数，这是对偶优化中的标准条件。
• 直观理解：非负的 ${\alpha }_i$ 确保支持向量的贡献是向决策边界方向的。

公式 9-59

$${\mu }_i\ge 0$$

• 解释：这是拉格朗日乘子 ${\mu }_i$ 的非负约束。
• 含义：该条件确保了 ${\mu }_i$ 是非负的，它与 ${\xi }_i\ge 0$ 的约束共同作用，满足互补松弛条件。
• 直观理解：非负的 ${\mu }_i$ 确保松弛变量的约束条件满足互补松弛条件，从而满足优化问题的约束条件。

总结

公式 9-51 到 9-59 是近似线性可分支持向量机在对偶优化问题下的 KKT 条件。这些条件包括偏导数设为零的条件、互补松弛条件、以及拉格朗日乘子的非负约束。通过这些条件，可以找到支持向量机的最优解，进而确定分类超平面的位置和形状：

• 互补松弛条件：定义了哪些点是支持向量，即对分类边界产生影响的点。
• 偏导数为零的条件：提供了 $w$ 和 $b$ 的计算方式。
• 非负约束条件：确保解的合理性。

这些条件共同作用，确保我们能够找到最优的分类超平面，即最大化分类间隔，并在允许一定误差的情况下优化分类性能。