5.2.2 支持向量

回到 优化问题 (5.7)，我们注意到约束是仿射的，因此是合格的。 目标函数以及仿射约束是凸的且可微的。 因此，定理B.30 Karush-Kuhn-Tucker定理 的要求成立，KKT条件在最优解处适用。 我们将使用这些条件来分析算法，并证明它的几个关键性质，然后推导出与 SVM 相关的对偶优化问题，在 5.2.3 对偶优化问题 中给出。

我们引入

• 拉格朗日变量 ${\alpha }_i\ge 0,i\in \left[m\right]$与 $m$ 约束相关，
• 并用 $\alpha$ 表示向量 ${\left({\alpha }_1,\dots ,{\alpha }_m\right)}^{\top }$。

拉格朗日函数

拉格朗日函数可以定义为所有 $\mathbf{w}\in {\mathbb{R}}^N,b\in \mathbb{R}$ 和 $\alpha \in {\mathbb{R}}_{+}^m$ 的函数

$$\begin{array}{rl}\mathcal{L}\left(\mathbf{w},b,\alpha \right):=& \frac{1}{2}\parallel \mathbf{w}{\parallel }^2\\ & -\sum _{i=1}^m{\alpha }_i\left[y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)-1\right].\end{array}\text{\hspace{1em}(5.8)}$$

KKT条件是通过将拉格朗日函数对原变量 $\mathbf{w}$ 和 $b$ 的梯度设为零，并写出互补条件得到的。

$$\begin{array}{rl}& {\nabla }_{\mathbf{w}}\mathcal{L}=\mathbf{w}-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i=0\\ & \Rightarrow \mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\end{array}\text{\hspace{1em}(5.9)}$$ $$\begin{array}{rl}& {\nabla }_b\mathcal{L}=-\sum _{i=1}^m{\alpha }_i{y}_i=0\\ & \Rightarrow \sum _{i=1}^m{\alpha }_i{y}_i=0\end{array}\text{\hspace{1em}(5.10)}$$ $$\begin{array}{rl}& \forall i,{\alpha }_i\left[y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)-1\right]=0\\ & \Rightarrow {\alpha }_i=0\vee y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)=1.\end{array}\text{\hspace{1em}(5.11)}$$

• 由方程(5.9)，在SVM问题解中的权重向量 $\mathbf{w}$ 是训练集向量的 ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$ 的线性组合。
  • 一个向量 ${\mathbf{x}}_i$ 出现在该展开中当且仅当 ${\alpha }_i\ne 0$。
  • 这样的向量被称为 支持向量。
• 由互补条件 (5.11)，如果 ${\alpha }_i\ne 0$，那么 $y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)=1$
  • 因此，支持向量位于边缘超平面上 $\mathbf{w}\cdot {\mathbf{x}}_i+b=\pm 1$

支持向量完全定义了最大间隔超平面或SVM解，这证明了该算法名称的合理性。 按照定义，不在边缘超平面上的向量不影响这些超平面的定义 - 在它们缺失的情况下，SVM问题的解仍然不变。

Remark

注意，尽管SVM问题的解 $\mathbf{w}$ 是唯一的，但支持向量不是。 在 $N,N+1$ 维度中，点足以定义一个超平面。因此，当超过 $N+1$ 个点位于边缘超平面上时，对于 $N+1$ 支持向量的选择是可能的。