线性可分支持向量机的原理推导 9-29对偶可行性条件 公式解析

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

公式 9-29 是支持向量机（SVM）优化过程中 Karush-Kuhn-Tucker（KKT） 条件的一个部分，表示对偶可行性条件（Dual Feasibility Condition）。它要求拉格朗日乘子 ${\alpha }_i^{\ast }$ 必须是非负的。这个条件是拉格朗日对偶问题的基本要求之一，用于确保优化问题的解在对偶空间是可行的。

公式 9-29 的表达式如下：
$${\alpha }_i^{\ast }\ge 0,i=1,2,\dots ,N$$

1. 公式的含义

公式 9-29 表示在支持向量机的优化问题中，所有拉格朗日乘子 ${\alpha }_i^{\ast }$ 必须是非负的：

• ${\alpha }_i^{\ast }$ 是第 $i$ 个样本点对应的最优拉格朗日乘子。
• 这些乘子用于表示每个样本对优化问题的贡献。
• 非负性要求：${\alpha }_i^{\ast }\ge 0$ 的意思是，拉格朗日乘子 ${\alpha }_i^{\ast }$ 不能是负值。只有正的或零的拉格朗日乘子才是合理的，因为它们代表样本对分类器构造的贡献程度。

2. 公式的背景与推导

SVM 的优化问题是一个带有约束条件的优化问题，通过拉格朗日乘子法进行求解。具体来说，SVM 的目标是最小化超平面的法向量 $w$ 的二次范数 $\frac{1}{2}\Vert w{\Vert }^2$，同时满足分类约束：
$$y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,N$$

为了处理这些约束，SVM 构造了拉格朗日函数，将目标函数和约束结合在一起：
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^N{\alpha }_i\left(y_i(w^T{x}_i+b)-1\right)$$

• ${\alpha }_i$ 是拉格朗日乘子，它们表示约束对目标函数的贡献。
• 拉格朗日乘子法的理论要求，对于不等式约束（如 $y_i(w^T{x}_i+b)\ge 1$），拉格朗日乘子 ${\alpha }_i$ 必须是非负的，即 ${\alpha }_i\ge 0$。

这就是为什么我们有公式 9-29 的约束条件。

3. 对偶可行性条件的解释

对偶可行性条件（Dual Feasibility Condition）要求拉格朗日乘子必须为非负值，这在优化理论中是处理不等式约束的基本要求。该条件确保解的合理性，即样本点的贡献程度不能是负的。否则，它将违反物理或逻辑意义上的约束。

原因：

• 拉格朗日乘子 ${\alpha }_i$ 用来表示样本点的影响力。如果 ${\alpha }_i<0$，这意味着对应样本对分类器的影响是“反向的”或不合理的。
• 在支持向量机中，只有那些 ${\alpha }_i^{\ast }>0$ 的点（即支持向量）对超平面的构造有影响。如果 ${\alpha }_i^{\ast }=0$，则该样本点不会对分类器的构造产生影响。

因此，非负性条件 ${\alpha }_i^{\ast }\ge 0$ 确保每个样本对分类器的贡献是非负的，这符合拉格朗日乘子法处理不等式约束的要求。

4. 几何意义

几何上，公式 9-29 保证了在 SVM 的分类过程中，只有那些距离超平面较近的点（即支持向量）会对分类器的构造产生影响，而远离超平面的点（非支持向量）的拉格朗日乘子 ${\alpha }_i^{\ast }=0$，它们对分类器的构造没有影响。

• 支持向量：对于 ${\alpha }_i^{\ast }>0$ 的样本点，它们是支持向量，位于分类超平面的边界上，直接影响超平面的构造。

• 非支持向量：对于 ${\alpha }_i^{\ast }=0$ 的样本点，它们远离分类超平面，虽然被正确分类，但不影响分类器的构造。

5. 物理解释

• 正值拉格朗日乘子：当 ${\alpha }_i^{\ast }>0$ 时，表示该样本点是支持向量，对分类器超平面的构造起到了实际作用。它们位于分类边界上，定义了分类器的决策边界。

• 零拉格朗日乘子：当 ${\alpha }_i^{\ast }=0$ 时，表示该样本点距离分类超平面较远，它不会对分类器的决策边界产生任何影响。这些点不作为支持向量。

这个条件确保了支持向量机在优化过程中，只会选择对超平面有实际影响的样本点参与构造超平面，而忽略那些对分类器没有影响的样本。

6. 在 SVM 中的作用

在 SVM 的优化过程中，公式 9-29 的作用是筛选支持向量。它确保只有那些 ${\alpha }_i^{\ast }>0$ 的点才对分类器有影响，而其他 ${\alpha }_i^{\ast }=0$ 的点不会影响分类器的构造。这是对偶可行性条件的基本作用。

具体作用如下：

• 确保非负性：公式 9-29 确保了拉格朗日乘子 ${\alpha }_i^{\ast }$ 的非负性，避免了违反物理意义的解出现。
• 筛选支持向量：它通过非负性条件筛选出哪些点对分类器有实际影响（支持向量），哪些点没有影响（非支持向量）。
• 优化问题的合理性：拉格朗日乘子法在处理不等式约束时，必须满足拉格朗日乘子的非负性条件。公式 9-29 正是这个非负性条件在 SVM 优化中的体现，确保优化问题的合理解。

7. 总结

公式 9-29 是支持向量机中的一个关键条件，它是拉格朗日乘子法中的对偶可行性条件，要求所有拉格朗日乘子 ${\alpha }_i^{\ast }$ 必须为非负。这确保了优化问题在对偶空间的合理性，并且通过这一条件，SVM 能够筛选出哪些样本点对分类超平面的构造产生实际影响（支持向量）。