线性可分支持向量机的原理推导 9-27拉格朗日乘子和不等式约束关系 公式解析

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

公式 9-27 是支持向量机（SVM）优化过程中 Karush-Kuhn-Tucker (KKT) 条件的其中一项，表示 互补松弛条件（Complementary Slackness Condition）。该条件是拉格朗日对偶理论中的一个核心部分，它反映了优化问题中约束和拉格朗日乘子之间的关系。

公式 9-27 的表达式如下：
$${\alpha }_i^{\ast }\left(y_i\left(w^{\ast T}{x}_i+b^{\ast }\right)-1\right)=0,i=1,2,\dots ,N$$

1. 公式的含义

这个公式描述了拉格朗日乘子 ${\alpha }_i^{\ast }$ 和不等式约束 $y_i(w^{\ast T}{x}_i+b^{\ast })-1$ 之间的关系。具体来说，它表达了以下两种可能情况：

• 当 ${\alpha }_i^{\ast }>0$ 时，样本 $x_i$ 必须满足 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$，即样本 $x_i$ 位于分类超平面的边界上，这些点称为支持向量。
• 当 ${\alpha }_i^{\ast }=0$ 时，样本 $x_i$ 的分类间隔 $y_i(w^{\ast T}{x}_i+b^{\ast })$ 必须大于 1，也就是说，这些样本离分类超平面较远，它们对分类超平面的定义没有影响。

该公式本质上是 KKT 条件中的互补松弛条件，要求对于每个样本 $x_i$，只有当约束 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$ 严格成立时，拉格朗日乘子 ${\alpha }_i^{\ast }$ 才能大于 0。

2. 推导背景

在 SVM 中，我们的目标是找到一个超平面来最大化分类间隔，同时满足以下约束条件：
$$y_i(w^T{x}_i+b)\ge 1,\text{对于每个训练样本 }i$$

这个不等式意味着，所有的训练样本 $x_i$ 必须被正确分类，并且正类样本（$y_i=1$）必须位于分类超平面一侧的距离至少为 1，负类样本（$y_i=-1$）则必须位于另一侧的距离至少为 1。

为了处理这个带有不等式约束的优化问题，SVM 引入了拉格朗日乘子 ${\alpha }_i$，并构造拉格朗日函数：
$$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)$$

在最优条件下，KKT 条件要求满足互补松弛条件，即：
$${\alpha }_i^{\ast }\left(y_i\left(w^{\ast T}{x}_i+b^{\ast }\right)-1\right)=0$$

3. 互补松弛条件的解释

这个条件反映了不等式约束 $y_i(w^T{x}_i+b)\ge 1$ 和拉格朗日乘子 ${\alpha }_i$ 的关系。我们可以把它理解为两种情况的组合：

第一种情况：当 ${\alpha }_i^{\ast }>0$

• 互补松弛条件 ${\alpha }_i^{\ast }\left(y_i(w^{\ast T}{x}_i+b^{\ast })-1\right)=0$ 要成立时，如果 ${\alpha }_i^{\ast }>0$，那么 $y_i(w^{\ast T}{x}_i+b^{\ast })-1=0$。
• 这意味着对于那些拉格朗日乘子 ${\alpha }_i^{\ast }>0$ 的样本 $x_i$，它们必须严格满足 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$。这些点恰好位于分类超平面的边界上，也就是说，它们是支持向量。

第二种情况：当 ${\alpha }_i^{\ast }=0$

• 如果 ${\alpha }_i^{\ast }=0$，那么互补松弛条件自动成立，无论 $y_i(w^{\ast T}{x}_i+b^{\ast })-1$ 是否为 0 或更大。
• 这意味着对于那些不影响超平面的样本（即 ${\alpha }_i^{\ast }=0$），它们不需要严格位于边界上，可以离分类超平面更远，满足 $y_i(w^{\ast T}{x}_i+b^{\ast })>1$。换句话说，这些点距离分类超平面较远，它们不会影响分类器的构建。

4. 几何解释

几何上，公式 9-27 说明了样本点在 SVM 分类过程中所扮演的不同角色：

• 支持向量：这些样本点恰好位于分类超平面的边界上。对于这些点，${\alpha }_i^{\ast }>0$，并且它们满足 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$。这些点直接决定了分类超平面的形状和位置。

• 非支持向量：这些点的拉格朗日乘子 ${\alpha }_i^{\ast }=0$，它们不在分类超平面的边界上，距离超平面有一定的距离。对于这些点，$y_i(w^{\ast T}{x}_i+b^{\ast })>1$，它们对分类超平面的定义没有影响。

5. 公式 9-27 的作用

在 SVM 的优化问题中，公式 9-27 起到了筛选支持向量的作用。根据互补松弛条件，只有那些拉格朗日乘子 ${\alpha }_i^{\ast }>0$ 的点会成为支持向量，它们对分类超平面产生影响。而对于 ${\alpha }_i^{\ast }=0$ 的点，它们不会对分类器的最终结果产生影响，因为这些点在分类超平面的外侧，距离超平面较远。

具体作用如下：

• 确定支持向量：通过公式 9-27，我们知道只有那些满足 ${\alpha }_i^{\ast }>0$ 且 $y_i(w^{\ast T}{x}_i+b^{\ast })=1$ 的点才是支持向量。这些点是决定分类器超平面形状的关键点。
• 筛选无影响的点：对于那些 ${\alpha }_i^{\ast }=0$ 的样本点，它们对超平面的构造没有影响，可以认为这些点在优化过程中被“忽略”了。

6. 总结

公式 9-27 是支持向量机（SVM）优化问题中的互补松弛条件，表明了支持向量（${\alpha }_i^{\ast }>0$）和非支持向量（${\alpha }_i^{\ast }=0$）之间的区别。通过这个公式，我们可以知道哪些样本点会对分类超平面的构造产生影响（支持向量），以及哪些点不会（非支持向量）。互补松弛条件在优化问题中确保了有效约束的合理性。