5.3.2 支持向量

与可分离情况一样，约束是仿射的，因此是合格的。目标函数以及仿射约束是凸的且可微的。因此，定理B.30的假设成立，KKT条件在最优解处适用。我们使用这些条件来分析算法并展示其几个关键性质，并随后推导出与SVMs相关的对偶优化问题，在5.3.3节中。

我们引入拉格朗日变量 ${\alpha }_i\ge 0,i\in \left[m\right]$，与第一个 $m$ 约束相关，以及 ${\beta }_i\ge 0,i\in \left[m\right]$ 与松弛变量的非负约束相关。我们用 $\alpha$ 表示向量 ${\left({\alpha }_1,\dots ,{\alpha }_m\right)}^{\top }$，用 $\beta$ 表示向量 ${\left({\beta }_1,\dots ,{\beta }_m\right)}^{\top }$。拉格朗日函数可以定义为所有 $\mathbf{w}\in {\mathbb{R}}^N,b\in \mathbb{R}$ 和 $\xi ,\alpha ,\beta \in {\mathbb{R}}_{+}^m$ 的函数。

$$\mathcal{L}\left(\mathbf{w},b,\xi ,\alpha ,\beta \right)=\frac{1}{2}\parallel \mathbf{w}{\parallel }^2+C\sum _{i=1}^m{\xi }_i-\sum _{i=1}^m{\alpha }_i\left[y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)-1+{\xi }_i\right]-\sum _{i=1}^m{\beta }_i{\xi }_i.\text{\hspace{1em}(5.25)}$$

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

$${\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\text{\hspace{1em}(5.26)}$$ $${\nabla }_b\mathcal{L}=-\sum _{i=1}^m{\alpha }_i{y}_i=0\Rightarrow \sum _{i=1}^m{\alpha }_i{y}_i=0\text{\hspace{1em}(5.27)}$$ $${\nabla }_{{\xi }_i}\mathcal{L}=C-{\alpha }_i-{\beta }_i=0\Rightarrow {\alpha }_i+{\beta }_i=C\text{\hspace{1em}(5.28)}$$ $$\forall i,{\alpha }_i\left[y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)-1+{\xi }_i\right]=0\Rightarrow {\alpha }_i=0\vee y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)=1-{\xi }_i\text{\hspace{1em}(5.29)}$$ $$\forall i,{\beta }_i{\xi }_i=0\Rightarrow {\beta }_i=0\vee {\xi }_i=0.\text{\hspace{1em}(5.30)}$$

By equation (5.26), as in the separable case, the weight vector $\mathbf{w}$ at the solution of the SVM problem is a linear combination of the training set vectors ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$ . A vector ${\mathbf{x}}_i$ appears in that expansion iff ${\alpha }_i\ne 0$ . Such vectors are called support vectors. Here, there are two types of support vectors. By the complementarity condition (5.29), if ${\alpha }_i\ne 0$ , then $y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)=1-{\xi }_i$ . If ${\xi }_i=0$ , then $y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)=1$ and ${\mathbf{x}}_i$ lies on a marginal hyperplane, as in the separable case. Otherwise, ${\xi }_i\ne 0$ and ${\mathbf{x}}_i$ is an outlier. In this case,(5.30) implies ${\beta }_i=0$ and (5.28) then requires ${\alpha }_i=C$ . Thus, support vectors ${\mathbf{x}}_i$ are either outliers, in which case ${\alpha }_i=C$ , or vectors lying on the marginal hyperplanes. As in the separable case, note that while the weight vector $\mathbf{w}$ solution is unique, the support vectors are not.