5.3.3 对偶优化问题

To derive the dual form of the constrained optimization problem (5.24), we plug into the Lagrangian the definition of $\mathbf{w}$ in terms of the dual variables (5.26) and apply the constraint (5.27). This yields

$$\mathcal{L}=\underset{-\frac{1}{2}\sum _{i,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)}{\underbrace{\frac{1}{2}{\Vert \begin{array}{c}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i\end{array}\Vert }^2-\sum _{i,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)}}-\underset{0}{\underbrace{\sum _{i=1}^m{\alpha }_i{y}_{i}b}}+\sum _{i=1}^m{\alpha }_i.\text{\hspace{1em}(5.31)}$$

Remarkably, we find that the objective function is no different than in the separable

case:

$$\mathcal{L}=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)\text{\hspace{1em}(5.32)}$$

However, here, in addition to ${\alpha }_i\ge 0$ , we must impose the constraint on the Lagrange variables ${\beta }_i\ge 0$ . In view of (5.28), this is equivalent to ${\alpha }_i\le C$ . This leads to the following dual optimization problem for SVMs in the non-separable case, which only differs from that of the separable case (5.14) by the constraints ${\alpha }_i\le C$ :

$$\underset{\alpha }{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)\text{\hspace{1em}(5.33)}$$ $$\text{ subject to: }0\le {\alpha }_i\le C\wedge \sum _{i=1}^m{\alpha }_i{y}_i=0,i\in \left[m\right].$$

因此，我们之前关于优化问题(5.14)的评论也适用于(5.33)。特别是，目标函数是凹的且可无限次微分，(5.33)等价于一个凸二次规划问题。该问题等价于原问题(5.24)。

对偶问题(5.33)的解 $\alpha$ 可以直接用来确定 SVMs 返回的假设，使用方程(5.26):

$$h\left(\mathbf{x}\right)=\mathrm{sgn}\left(\mathbf{w}\cdot \mathbf{x}+b\right)=\mathrm{sgn}\left(\sum _{i=1}^m{\alpha }_i{y}_i\left({\mathbf{x}}_i\cdot \mathbf{x}\right)+b\right).\text{\hspace{1em}(5.34)}$$

此外，$b$ 可以从任意位于边缘超平面上的支持向量 ${\mathbf{x}}_i$ 中获得，即任意满足 $0<{\alpha }_i<C$ 的向量 ${\mathbf{x}}_i$ 。对于这样的支持向量，$\mathbf{w}\cdot {\mathbf{x}}_i+b=y_i$

因此

$$b=y_i-\sum _{j=1}^m{\alpha }_j{y}_j\left({\mathbf{x}}_j\cdot {\mathbf{x}}_i\right)\text{\hspace{1em}(5.35)}$$

与可分情况一样，对偶优化问题(5.33)以及表达式(5.34)和(5.35)显示了 SVMs 的一个重要性质:假设解仅依赖于向量之间的内积，而不是直接依赖于向量本身。这一事实可以用来将 SVMs 扩展到定义非线性决策边界，我们将在第6章中看到。