线性可分支持向量机的原理推导 9-23拉格朗日乘子α的最大化问题 公式解析

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

---

公式 9-23 是支持向量机（SVM）优化过程中从最大化问题到对偶问题的关键步骤之一。它将目标函数简化为关于拉格朗日乘子 $\alpha$ 的最大化问题，并附加了一些重要的约束条件。我们将详细解释公式 9-23 的各个部分，包括目标函数和约束条件。

公式 9-23 的具体形式

公式 9-23 可以分为三行：

1. 目标函数：
   $$\underset{\alpha }{\max }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)-\sum _{i=1}^N{\alpha }_i$$

2. 约束条件 1：
   $$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

3. 约束条件 2：
   $${\alpha }_i\ge 0,i=1,2,\dots ,N$$

现在，我们逐步解释公式 9-23。

1. 目标函数解释

原始目标：

首先，回顾原始问题，支持向量机的优化问题是通过最小化法向量 $\mathbf{w}$ 的二次范数 $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$，同时满足分类约束条件：
$$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,i=1,2,\dots ,N$$

通过拉格朗日乘子法，优化问题被转换为一个关于拉格朗日乘子 ${\alpha }_i$ 的对偶问题。

目标函数的推导过程：

回顾之前得到的公式 9-22，它是对偶问题的形式：
$$L(\alpha )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)+\sum _{i=1}^N{\alpha }_i$$

在公式 9-23 中，我们进行最大化目标函数时，由于之前的公式是最小化的，我们将符号反转，从而得到新的目标函数：
$$\underset{\alpha }{\max }\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)-\sum _{i=1}^N{\alpha }_i$$

这个目标函数具有两部分：

• 第一部分： $\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j({\mathbf{x}}_i\cdot {\mathbf{x}}_j)$

  • 这是一个二次项，它描述了样本之间的相互作用，具体是通过拉格朗日乘子 ${\alpha }_i{\alpha }_j$、类别标签 $y_i{y}_j$、以及样本点的内积 $({\mathbf{x}}_i\cdot {\mathbf{x}}_j)$ 进行加权的。
  • 二次项通常出现在支持向量机优化问题中，它代表了支持向量之间的相互关系以及对决策边界的影响。

• 第二部分： ${\sum }_{i=1}^N{\alpha }_i$

  • 这是一个线性项，是所有拉格朗日乘子的加和。
  • 它的存在是为了调节整体优化过程，使得我们不会无限制地增加 ${\alpha }_i$ 的值。

最大化问题的含义：

• 最大化这个目标函数意味着我们希望找到最优的拉格朗日乘子 ${\alpha }_i$，使得目标函数达到最大值。
• 在这个最大化过程中，只有那些 ${\alpha }_i>0$ 的点（即支持向量）才对分类边界产生影响，其他 ${\alpha }_i=0$ 的点不会对分类结果产生作用。

2. 约束条件解释

约束条件 1：${\sum }_{i=1}^N{\alpha }_i{y}_i=0$

这个约束条件表示拉格朗日乘子 ${\alpha }_i$ 和类别标签 $y_i$ 的加权和必须等于零。

原因：

• 这个约束是从对 $b$ 求导得到的结果（见公式 9-19）。
• 它的物理意义是确保分类器的平衡，即在最优分类超平面上，正类样本和负类样本的权重达到某种平衡。
• 通过这种平衡，我们确保超平面不会偏向任何一类，正类和负类的误分类率保持对称。

几何解释：

这个约束条件实际上反映了一个超平面平衡的问题。在支持向量机的优化过程中，正类和负类样本对分类器的贡献通过 ${\alpha }_i$ 和 $y_i$ 的乘积来体现。当 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 时，正负类别对分类边界的影响处于平衡状态。

约束条件 2：${\alpha }_i\ge 0,i=1,2,\dots ,N$

这个条件要求每个拉格朗日乘子 ${\alpha }_i$ 必须为非负值。

原因：

• 根据拉格朗日乘子法的理论，对于不等式约束（即 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$），拉格朗日乘子 ${\alpha }_i$ 必须为非负。
• 当 ${\alpha }_i=0$ 时，表示对应的样本点 ${\mathbf{x}}_i$ 对超平面没有贡献，即这些点并不影响分类器的构建。
• 当 ${\alpha }_i>0$ 时，表示对应的样本点 ${\mathbf{x}}_i$ 是一个支持向量，对分类边界的构造起关键作用。

几何解释：

支持向量是那些距离分类超平面最近的样本点，它们对最终的分类边界产生了实际影响。这个约束确保了只有那些在超平面上或附近的样本点（即支持向量）才会对分类超平面有影响，而其他远离分类边界的样本点不会影响优化结果。

3. 公式 9-23 的整体意义

公式 9-23 的目标函数是通过拉格朗日乘子 ${\alpha }_i$ 表示的对偶问题，目标是最大化一个与支持向量相关的函数，同时需要满足两个约束条件。这一过程是 SVM 中通过拉格朗日乘子法将原始问题（即最小化 $\Vert \mathbf{w}{\Vert }^2$ 的问题）转化为一个可以更高效求解的对偶问题。

• 目标函数描述了支持向量之间的相互作用及其对分类边界的影响，最大化目标函数意味着找到最优的支持向量组合。
• 第一个约束条件确保分类超平面的平衡，使得正负类样本对分类边界的影响保持均衡。
• 第二个约束条件确保每个拉格朗日乘子 ${\alpha }_i$ 非负，只有那些 ${\alpha }_i>0$ 的样本点（即支持向量）才对最终的分类边界有影响。

总结

公式 9-23 是支持向量机优化的核心之一，通过最大化拉格朗日对偶问题中的目标函数并满足约束条件，我们可以找到支持向量并确定分类器的最优超平面。这个过程不仅有效地简化了原始问题的求解，还通过对偶问题的形式为进一步的扩展（如核方法）提供了基础。