5.2.3 对偶优化问题

为了推导约束 优化问题 (5.7) 的对偶形式，我们将 $\mathbf{w}$ 的定义代入拉格朗日函数，该定义涉及对偶变量，如(5.9)所示，并应用约束(5.10)。这得到

$$\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.12)}$$

这简化为

$$\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.13)}$$

这导致以下可分情况下SVM的对偶优化问题:

对偶优化问题 (5.14)

$$\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.14)}$$

subject to:

$${\alpha }_i\ge 0\wedge \sum _{i=1}^m{\alpha }_i{y}_i=0,\forall i\in \left[m\right]\text{.}$$

目标函数 $G:\alpha \mapsto \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)$是无限可微的。 其Hessian矩阵由 ${\nabla }^{2}G=-\mathbf{A}$ 给出，其中 $\mathbf{A}={\left(y_i{\mathbf{x}}_i\cdot y_j{\mathbf{x}}_j\right)}_{ij}$ 。 $\mathbf{A}$ 是与向量 $y_1{\mathbf{x}}_1,\dots ,y_m{\mathbf{x}}_m$ 相关的格拉姆矩阵，因此是半正定的(参见第A.2.3节)，这表明 ${\nabla }^{2}G\preccurlyeq 0$ 且 $G$ 是一个凹函数。 由于约束是仿射的和凸的，对偶优化问题 (5.14) 是一个凸优化问题。 由于 $G$ 是 $\alpha$ 的二次函数，这个对偶优化问题也是一个二次规划问题，正如原优化问题一样，再次可以使用通用和专门的二次规划求解器来获得解 (参见练习5.4，了解关于SMO算法的详细信息，该算法通常用于在更一般的非可分设置中解决SVM问题的对偶形式)。

此外，由于约束是仿射的，它们是合格的，强对偶性成立(见附录B)。 因此，原问题和对偶问题是等价的，即对偶问题(5.14)的解 $\alpha$ 可以直接用来通过方程(5.9)确定SVM返回的假设:

$$\begin{array}{rl}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).\end{array}\text{\hspace{1em}(5.15)}$$

由于支持向量位于边缘超平面上，对于任意支持向量 ${\mathbf{x}}_i$ , $\mathbf{w}\cdot {\mathbf{x}}_i+b=y_i$ ，因此 $b$ 可以通过以下方式获得:

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

对偶优化问题(5.14)以及表达式(5.15)和(5.16)揭示了SVM的一个重要性质:

假设解只依赖于向量之间的内积，而不是直接依赖于向量本身。

这个观察是关键，其重要性将在第6章中变得清晰，在那里我们引入了核方法。

方程(5.16)现在可以用来推导几何边缘 $\rho$ 关于 $\alpha$ 的简单表达式。 由于(5.16)对于所有 $i$ 成立，且 ${\alpha }_i\ne 0$ ，将两边乘以 ${\alpha }_i{y}_i$ 并求和得到:

$$\sum _{i=1}^m{\alpha }_i{y}_{i}b=\sum _{i=1}^m{\alpha }_i{y}_i^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.17)}$$

利用 $y_i^2=1$ 的事实以及方程(5.9)，然后得到:

$$0=\sum _{i=1}^m{\alpha }_i-\parallel \mathbf{w}{\parallel }^2\text{\hspace{1em}(5.18)}$$

注意到 ${\alpha }_i\ge 0$ ，我们得到边缘 $\rho$ 关于以下表达式的关于 $\alpha$ 的 $L_1$ 范数形式

$${\rho }^2=\frac{1}{\parallel \mathbf{w}{\parallel }_2^2}=\frac{1}{\sum _{i=1}^m{\alpha }_i}=\frac{1}{\parallel \alpha {\parallel }_1}.\text{\hspace{1em}(5.19)}$$