CS229 Lesson 8 顺序最小优化算法

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了核方法以及SMO算法。

7.核方法

回到我们对线性回归的讨论中，我们遇到了一个问题，其中输入$x$是房子的生活区域，我们考虑使用特征$x$，$x^2$和$x^3$进行回归以获得三次函数。 为了区分这两组变量，我们将“原始”输入值称为问题的输入属性（在本例中为$x$，生活区域）。当它被映射到一组新的量然后传递给学习算法时，我们将这些新的量称为输入特征。（不幸的是，不同的作者使用不同的术语来描述这两件事，但是我们将尝试在这份讲义中一致地使用这个术语。）我们还将$\phi$表示特征映射，它将属性映射到特征。 例如，在我们的例子中，我们有

$$\phi(x) =\left[ \begin{matrix} x \\ x^2 \\ x^3 \end{matrix} \right]$$

​ 我们可能想使用某些特征$\phi(x)$来学习，而不是使用原始输入属性$x$来使用SVM。 要做到这一点，我们只需要检查我们之前的算法，并用$\phi(x)$替换其中的$x$。

​ 由于算法可以完全根据内积$\langle x,z \rangle$编写，这意味着我们将用$\langle \phi(x),\phi(z) \rangle$替换所有这些内积。特别地，给定特征映射$\phi $，我们将相应的核定义为

$$K(x,z) = \phi(x)^T \phi(z)$$

然后，在我们之前在我们的算法中有$\langle x,z \rangle$的地方，我们可以简单地用$K(x,z)$替换它，我们的算法现在将使用特征$\phi $来学习。

​ 现在，给定$\phi$，我们可以通过计算$\phi(x)$和$\phi(z)$并求其内积来轻松计算$K(x,z) $。 但更有趣的是，通常，$K(x,z) $的计算成本可能非常低廉，即使$\phi(x) $本身的计算成本非常高（可能因为它是一个维数很高的向量）。在这样的假定下，通过使用高效算法计算$K(x,z) $，我们可以使SVM在$\phi $给出的高维特征空间中学习，但同时不需要显式的计算$\phi (x)$。

​ 来看一个例子。 假设$x, z\in \mathbb R^n $，并考虑

$$K(x,z)=(x^T z)^2$$

上式也可以写为

$$\begin{aligned} K(x,z)&= \Big(\sum_{i=1}^n x_i z_i \Big) \Big(\sum_{j=1}^n x_j z_j \Big) \\ &=\sum_{i=1}^n \sum_{j=1}^n x_i x_j z_i z_j\\ &= \sum_{i,j=1}^n (x_i x_j)(z_i z_j) \end{aligned}$$

因此，我们看到$K(x,z) = \phi(x)^T \phi(z)$，其中特征映射$\phi $（此处针对$n = 3$的情况给出）

$$\phi (x) = \left[ \begin{matrix} x_1x_1 \\ x_1 x_2 \\ x_1 x_3 \\ x_2 x_1 \\ x_2 x_2 \\ x_2 x_3 \\ x_3 x_1 \\ x_3 x_2 \\ x_3 x_3 \end{matrix} \right]$$

注意，虽然计算$\phi (x )$需要$O(n^2)$的时间，但是计算$K(x,z)$只需要$O(n)$时间——和输入属性的维度呈线性关系。

​ 对于相关的核，考虑

$$\begin{aligned} K(x,z)&=(x^T z+c)^2 \\ &= (\sum_{i=1}^n x_i z_i+c)^2 \\ &= \sum_{i,j=1}^n (x_i x_j)(z_i z_j) + \sum_{i=1}^n (\sqrt{2c} x_i) (\sqrt{2c} z_i) +c^2 \end{aligned}$$

相应的特征映射为（再次给出$n=3$的情形）

$$\phi (x) = \left[ \begin{matrix} x_1x_1 \\ x_1 x_2 \\ x_1 x_3 \\ x_2 x_1 \\ x_2 x_2 \\ x_2 x_3 \\ x_3 x_1 \\ x_3 x_2 \\ x_3 x_3 \\ \sqrt{2c} x_1\\ \sqrt{2c} x_2\\ \sqrt{2c} x_3\\ c \end{matrix} \right]$$

参数$c$控制$x_i$（一阶）和$x_ix_j$（二阶）项之间的相对权重。

​ 进一步推广，核$K(x,z)= (x^T z+c)^d$对应于映射到$\binom {n+d} d$维特征空间的特征映射，对应于形式为$x_{i_1}x_{i_2}…x_{i_k}$的所有次数最多为$d$的单项式。 然而，尽管在这个$O(n^d)$维空间，计算$K(x,z)$仍然只需要$O(n)$的时间，因此我们永远不需要在这个非常高维的特征空间中明确地表示特征向量。

​ 现在，让我们从不同的角度谈论核。 直观地，如果$\phi (x) $和$\phi (z) $靠得很近，那么我们可以期望$K(x,z) = \phi(x)^T \phi(z)$很大。 相反，如果$\phi (x) $和$\phi (z) $相距很远，比如几乎彼此正交，则$K(x,z) = \phi(x)^T \phi(z)$将很小。 因此，我们可以将$K(z,x)$视为对$\phi (x) $和$\phi (z) $或者$x$和$z$有多相似的度量。

​ 鉴于这种直觉，假设对于你正在研究的一些学习问题，你已经提出了某个函数$K(x,z) $，你认为它可能是$x$和$z$相似程度的合理量度。 例如，也许你选择了

$$K(x,z) =\exp \Big( -\frac{||x-z||^2}{2\sigma^2} \Big)$$

这是$x$和$z$相似性的合理度量，当$x$和$z$接近时，上式接近$1$，当$x$和$z$相距很远时上式接近$0$。 我们可以将这个$K$用作SVM中的核吗？ 在这个特定的例子中，答案是肯定的。 （这个内核称为高斯核，对应于无限维特征映射$\phi $。）但更广泛地说，给定某个函数$K$，我们如何判断它是否是一个有效的核；即，我们如何判断是否存在某些特征映射$ \phi $，使得对于所有$x,z$，$K(x,z) = \phi(x)^T \phi(z)$。

​ 现在假设$K$确实是对应于某个特征映射$\phi $的有效核。 现在，考虑有限的$m$点（不一定是训练集）$\{x^{(1)} ,…,x^{(m)}\}$，并且定义$m×m$矩阵$K$，使得其第$(i,j)$个元素为$K(x^{(i)},x^{(j)})$。 该矩阵称为核矩阵。 请注意，由于核函数$K(x,z)$和核矩阵$K$之间存在明显的密切关系，我们已经重载了符号并使用$K$来表示核函数$K(x,z)$和核矩阵$K$。

​ 现在，如果$K$是有效的核，则

$$K_{ij}=K(x^{(i)},x^{(j)}) = \phi(x^{(i)})^T \phi(x^{(j)}) = \phi(x^{(j)}) ^T \phi(x^{(i)}) =K(x^{(j)},x^{(i)}) =K_{ji}$$

因此$K$是对称矩阵。 更重要的是，让$\phi _k(x)$表示向量$\phi(x )$的第$k$个坐标，我们发现对于任何向量$z$，我们都有

$$\begin{aligned} z^T Kz &=\sum_i \sum_j z_i K_{ij}z_j \\ &=\sum_i \sum_j z_i\phi(x^{(i)})^T \phi(x^{(j)})z_j \\ &=\sum_i \sum_j z_i \sum_k\phi_k(x^{(i)}) \phi_k(x^{(j)})z_j \\ &=\sum_k \sum_i \sum_j z_i \phi_k(x^{(i)}) \phi_k(x^{(j)})z_j \\ &=\sum_k \Big( \sum_i z_i \phi_k(x^{(i)}) \Big)^2 \\ &\ge 0 \end{aligned}$$

由于$z$是任意值，这表明$K$是正半正定的（$K≥0$）。

​ 因此，我们已经证明，如果$K$是有效核（即，如果它对应于某些特征映射$ \phi $），则相应的核矩阵$K∈\mathbb R^{m×m}$是半正定对称矩阵。 更一般地说，这不仅是$K$成为有效核（也称为Mercer核）的必要条件，而且是充分条件。 以下结果归功于Mercer。

定理（Mercer）

设$K∈\mathbb R^{n} \times \mathbb R^{n} \to \mathbb R$。 那么$K$是有效（Mercer）核的充要条件是对任意$\{x^{(1)} ,…,x^{(m)}\}$，（$m<\infty$），相应的核矩阵是正半定对称矩阵。

​ 给定函数$K$，除了试图找到与其对应的特征映射$\phi $之外，该定理因此提供了另一种测试它是否是有效核的方法。

​ 核在支持向量机方面的应用应该已经很清楚了，所以我们不会在这里花太多时间。 但请记住，核的概念比SVM具有更广泛的适用性。 具体来说，如果你有任何学习算法只需要用输入属性向量之间的内积$\langle x,z \rangle$来编写，那么用$K(x,z)$替换它，其中$K$是一个核，你可以“神奇地”允许你的算法在对应于$K$的高维特征空间中有效地工作。例如，该核技巧可以与感知机一起应用以导出核感知机算法。 我们将在本课程后面看到的许多算法也适用于这种方法，后者被称为“核技巧”。

8.正则化和不可分的情形

到目前为止所呈现的SVM的推导都是假设数据是线性可分的。 虽然通过$\phi $将数据映射到高维特征空间通常会增加数据可分的可能性，但我们无法保证它始终如此。 此外，在某些情况下，我们不清楚找到分离超平面正是我们想要做的，因为这可能容易受到异常值的影响。 例如，下图左边显示了一个最佳间隔分类器，当在左上角区域（右图）中添加了一个异常值时，它会使决策边界产生戏剧性的摆动，并且得到的分类器的间隔要小的多。

​ 为了使算法适用于线性不可分数据集以及对异常值不太敏感，我们重新设置我们的优化问题（使用$ℓ_1$正则化），如下所示：

$$\begin{aligned} \min_{ \gamma, w, b}\ \ & \frac 1 2 ||w||^2 + C\sum_{i=1}^m \xi_i \\ \text{s.t}\ \ & y^{(i)}(w^T x^{(i)}+b)\ge 1-\xi_i ,i=1,...,m \\ & \xi_i \ge 0 ,i=1,...,m \end{aligned}$$

因此，现在允许样本具有小于$1$的（函数）间隔，并且如果样本具有函数间隔$1-ξ_i$（$ξ> 0$），则我们付出的代价为目标函数的成本增加$Cξ_ i$。 参数$C$控制了使$|| w ||^2$变小（我们之前看到的这项使间距变大）和确保大多数样本具有至少$1$的函数间隔的双重目标之间的相对权重。

​ 将上述条件修改为

$$1-\xi_i-y^{(i)}(w^T x^{(i)}+b)\le 0 ,i=1,...,m \\ -\xi_i \le 0 ,i=1,...,m$$

我们可以得到拉格朗日算子

$$\mathcal L(w,\beta,\xi,\alpha,r) = \frac 1 2||w||^2+C\sum_{i=1}^m \xi_i -\sum_{i=1}^m \alpha_i [y^{(i)} (w^T x^{(i)}+b) -1 +\xi_i] -\sum_{i=1}^m r_i \xi_i$$

这里，$α_i$和$r_i$是我们的拉格朗日乘子（约束为$≥0$），求偏导并令为$0$可得：

$$\begin{aligned} \nabla_w \mathcal L(w,\beta,\xi,\alpha,r)&= w- \sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}=0 \\ \nabla_b \mathcal L(w,\beta,\xi,\alpha,r)&= \sum_{i=1}^m \alpha_i y^{(i)}=0 \\ \nabla_{\xi_i}L(w,\beta,\xi,\alpha,r) &= C -\alpha_i -r_i =0 \end{aligned}$$

化简第一个式子可得

$$w = \sum_{i=1}^m \alpha_i y^{(i)}x^{(i)}$$

带入原式可得

$$\begin{aligned} \mathcal L(w,\beta,\xi,\alpha,r) = \sum_{i=1}^m \alpha_i -\frac 1 2 \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} -b \sum_{i=1}^m \alpha_i y^{(i)} +\sum_{i=1}^m (C-\alpha_i-\xi_i) \xi_i \end{aligned}$$

注意到

$$\sum_{i=1}^m \alpha_i y^{(i)}=0 \\ \alpha_i +r_i = C$$

所以

$$\begin{aligned} \mathcal L(w,\beta,\xi,\alpha,r) = \sum_{i=1}^m \alpha_i -\frac 1 2 \sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} \end{aligned}$$

有$\xi_i \ge 0, \alpha_i \ge 0$可得

$$\xi_i =C- \alpha_i \ge 0 \\ 0\le \alpha_ i\le C$$

所以对偶问题为

$$\begin{aligned} \max_{ \alpha}\ \ & W(\alpha) = \sum_{i=1}^m \alpha_i -\frac 1 2\sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)}\rangle \\ \text{s.t}\ \ &0\le \alpha_i\le C ,i=1,...,m \\ & \sum_{i=1}^m \alpha_i y^{(i)}=0 \end{aligned}$$

​ 和以前一样，我们像公式$(9)$用$α_i$表示$w$，这样在求解对偶问题后，我们可以继续使用公式$(13)$来进行预测。 注意，有些令人惊讶的是，在添加$ℓ_1$正则化时，对偶问题的唯一变化是原来的约束$0≤α_i$现在变为$0≤α_i≤C$。注意此时$b’$的计算也必须修改。

​ 此外，KKT对偶互补条件（在下一节中将有助于测试SMO算法的收敛）是：

$$\begin{eqnarray*} \alpha_i = 0 &\Rightarrow y^{(i)}(w^T x^{(i)} +b )\ge 1 \tag{14} \\ \alpha_i = C &\Rightarrow y^{(i)}(w^T x^{(i)} +b )\le 1 \tag{15} \\ 0<\alpha_i<C &\Rightarrow y^{(i)}(w^T x^{(i)} +b )= 1 \tag{16} \end{eqnarray*}$$

上述等式的证明如下：

首先由上一讲的等式$(5),(6)$可得：

$$\alpha_i \big(1-\xi_i-y^{(i)}(w^T x^{(i)}+b)\big) =0 \\ 1-\xi_i-y^{(i)}(w^T x^{(i)}+b) \le 0 \\ -r_i\xi_i =0\\ -\xi_i \le 0$$

如果$\alpha _i =0$，那么由

$$\alpha_i +r_i = C$$

可得

$$r_i =C$$

所以

$$\xi_i =0 \\ 1-\xi_i-y^{(i)}(w^T x^{(i)}+b)=1-y^{(i)}(w^T x^{(i)}+b) \le 0 \\ y^{(i)}(w^T x^{(i)}+b) \ge 1$$

如果$\alpha _i =C$，那么

$$1-\xi_i-y^{(i)}(w^T x^{(i)}+b) =0$$

此时

$$r_i =C-\alpha _i = 0$$

所以无法判断$\xi_i$是否为$0$，但是肯定有

$$y^{(i)}(w^T x^{(i)}+b) = 1-\xi_i \le 1$$

如果$0<\alpha_ i<C$，那么

$$1-\xi_i-y^{(i)}(w^T x^{(i)}+b) =0 \\ y^{(i)}(w^T x^{(i)}+b) =1-\xi_i$$

注意到之前我们有

$$\alpha_i +r_i = C$$

所以

$$r_i \neq 0$$

这推出

$$\xi_i = 0$$

从而

$$y^{(i)}(w^T x^{(i)}+b) =1$$

​ 现在，剩下的就是给出一个实际解决对偶问题的算法，我们将在下一节中介绍。

9.SMO算法

John Platt发明的SMO（序列最小优化）算法提供了一种有效的方法来解决由SVM的推导得到的对偶问题。 部分是为了激发SMO算法，部分是因为它本身很有趣，让我们首先讨论坐标上升算法。

9.1 坐标上升

考虑尝试解决无约束的优化问题

$$\max_{\alpha} W(\alpha_1,\alpha_2,...,\alpha_m)$$

在这里，我们将$W$视为参数$α_i$的某个函数，现在忽略此问题与SVM之间的任何关系。 我们已经看到了两种优化算法，梯度上升和牛顿方法。 我们将在这里考虑的新算法称为坐标上升：

• 迭代直至收敛{

  • 对$i=1,…,m$，{

    $$\alpha_i := \arg\max_{\hat \alpha_i} W(\alpha_1,...,\alpha_{i-1},\hat \alpha_{i},\alpha_{i+1},...,\alpha_m)$$

  • }

• }

​ 因此，在该算法的最内层循环中，除了一些固定的$α_i$之外，我们将保持所有变量，并且仅针对参数$α_i$重新优化$W$。 在这里给出的这个方法的版本中，内循环按$\alpha_1,\alpha_2,…,\alpha_m,\alpha_1,\alpha_2,…$的顺序重新优化变量，（一个更复杂的版本可能会选择其他顺序；例如，我们可以选择使$W(\alpha )$获得最大增长的变量。）

​ 当函数$W$碰巧具有内循环中的“$\arg \max$”可以有效地执行的形式时，那么坐标上升是相当有效的算法。 这是一张坐标上升的图片：

​ 图中的椭圆是我们想要优化的二次函数的等高线。 坐标上升法初始化为$(2, -2)$，并且图中还绘制了它到达全局最大值的路径。 请注意，在每个步骤中，坐标上升采用与其中一个轴平行的步长，因为一次只优化一个变量。

9.2 SMO

我们通过对SMO算法的简单推导来结束对SVM的讨论。

​ 这是我们想要解决的（对偶）优化问题：

$$\begin{eqnarray*} \max_{ \alpha}\ \ && W(\alpha) = \sum_{i=1}^m \alpha_i -\frac 1 2\sum_{i,j=1}^m y^{(i)}y^{(j)} \alpha_i \alpha_j \langle x^{(i)}, x^{(j)}\rangle \tag{17} \\ \text{s.t}\ \ &&0\le \alpha_i\le C ,i=1,...,m \tag{18} \\ && \sum_{i=1}^m \alpha_i y^{(i)}=0 \tag{19} \end{eqnarray*}$$

​ 假设我们有一组满足约束条件$(18-19)$的$\alpha_i $。 现在，假设我们想要保持$\alpha_2,…,\alpha_m$固定，并采取坐标上升法，并关于$α_1$重新优化目标。 我们可以取得任何进展吗？ 答案是否定的，因为约束$(19)$确保了

$$\alpha_1 y^{(1)}=-\sum_{i=2}^m \alpha_i y^{(i)}$$

或者，通过将两边乘以$y^{(1)}$，我们等价地有

$$\alpha_1 =- y^{(1)}\sum_{i=2}^m \alpha_i y^{(i)}$$

（这一步使用了$y^{(1)} ∈\{-1,1\}$）因此$(y^{(1)} )^2 =1$。所以如果我们保持保持$\alpha_2,…,\alpha_m$固定，那么$α_1$完全由其他$α_i$确定，那么我们就不能在不违反优化问题中的约束$(19)$的情况下对$α_1$进行任何改变。

​ 因此，如果我们想要更新$α_i$中某些项，我们必须同时更新它们中的至少两个以便保持满足约束。 这激发了SMO算法，它简单地执行以下操作：

• 重复直至收敛{
  • 1.选择一对$α_i$和$α_j$进行下一次更新（选择在全局最大值上取得最大增量的两个坐标）。
  • 2.关于$α_i$和$α_j$重新优化$W(\alpha )$，同时保持所有其他$\alpha_k (k\neq i,j)$固定。
• }

为了测试该算法的收敛性，我们可以检查KKT条件（公式$14-16$）是否在某个tol范围内满足。 这里，tol是收敛容差参数，并且通常设置为约$0.01$至$0.001$。（有关详细信息，请参论文和伪代码。）

​ SMO是一种有效算法的关键原因对$α_i,α_j$的更新可以有效的进行。 现在让我们简要推导高效更新的主要思路。

​ 假设我们目前有一些$α_i$满足约束条件$(18-19)$，并假设我们决定保持$\alpha_3,…,\alpha_m$固定，并且想要关于$α_1$和$α_2$（满足约束条件）重新优化$ W(\alpha_1,\alpha_2,…,\alpha_m)$。 由等式$(19)$，我们有

$$\alpha_1 y^{(1)}+\alpha_2 y^{(2)}=-\sum_{i=3}^m \alpha_i y^{(i)}$$

由于右侧是固定的（因为我们已经固定了$\alpha_3,…,\alpha_m$），我们可以用某个常数$ζ$表示这项：

$$\alpha_1 y^{(1)}+\alpha_2 y^{(2)}=\xi$$

因此，我们可以将对$α_1$和$α_2$的约束描述如下：

根据约束$(18)$，我们知道$α_1$和$α_2$必须位于所示的框$[0,C]×[0,C]$内。 还绘制了直线$\alpha_1 y^{(1)}+\alpha_2 y^{(2)}=\xi$，其中$α_1$和$α_2$必须在该直线上。 还要注意，从这些约束中，我们知道$L≤α_2≤H$；否则，$(\alpha_1,\alpha_2)$不能同时满足框和直线约束。 在这个例子中，$L = 0$。但是根据线$\alpha_1 y^{(1)}+\alpha_2 y^{(2)}=\xi$的样子，这不是必然的情况；但更一般地，在$α_2$的允许值上将存在某个下限$L$和某个上限$H$，这将确保$α_1,α_2$位于框$[0,C]×[0,C]$内。

​ 使用等式$(20)$，我们也可以将$α_1$写为$α_2$的函数：

$$\alpha_1 =(\xi-\alpha_2 y^{(2)})y^{(1)}$$

（我们再次使用$y^{(1)}∈\{-1,1\}$的事实，因此$(y^{(1)})^2 =1$。）因此，可以写出目标函数$W(\alpha )$

$$W(\alpha_1,\alpha_2,...,\alpha_m) = W((\xi-\alpha_2 y^{(2)})y^{(1)},\alpha_2,...,\alpha_m)$$

将$\alpha_3,…,\alpha_m$视为常数，可以验证这是关于$α_2$中的二次函数。 即，对于某些$a,b,c$，可以以$aα_2^2 +bα_2+ c$的形式表示。 如果我们忽略“框”约束$(18 )$（或等效地，$L≤α_2 ≤H$），那么我们可以通过将其导数设为零并求解来轻松地最大化该二次函数。 我们将$α_2 ^{new,unclipped}$表示$α_2$的结果值。如果我们想要相对于$α_2$最大化$W$但受制于框约束，我们可以得到（利用二次函数的性质）

$$\alpha_2 ^{new}=\begin{cases} H & 如果α_2 ^{new,unclipped} > H\\ α_2 ^{new,unclipped}& 如果L\le α_2 ^{new,unclipped} \le H \\ L&如果 α_2 ^{new,unclipped} < L \end{cases}$$

最后，找到了$\alpha_2 ^{new} $，我们可以使用公式$(20)$找到$\alpha_1 ^{new} $的最优值。

​ 还有一些非常简单的细节，可以Platt的论文中了解：一个是用于选择下一个$α_i,α_j$进行更新的启发式选择；另一个是在运行SMO算法时如何更新$b$。