第五部分：支持向量机

本部分详述支持向量机的算法。支持向量机是最好的（许多人相信是最好的）“现成的”监督学习算法之一。为了讲述SVM的故事，我们需要首先讨论边缘空白以及用大的“间隔”分离数据的想法。接下来，我们将讨论最优边距分类器，它将要求我们先了解拉格朗日对偶。我们还将看到核，它提供了一种在非常高维（如无穷维）的特征空间中有效地应用SVM的方法，最后，我们将用SMO算法结束故事，它给出了SVM的有效实现。

边缘空白：直觉

我们将通过谈论边缘空白来开始我们关于SVM的故事。本节将给出关于边缘空白和对我们预测的“信心”的直观理解；这些想法将在第3节正式提出。

考虑对数几率回归，p(y = 1|x;θ)由h(x)=g(θ'x)建模得出。如果h(x)大于等于0.5，将预测为正例1，或者等价的，仅仅当θ'x大于等于0时。对于一个正例训练样本，θ'x越大，h(x)也会越大，这样我们的预测“信心”程度越高，标签就是1正例。因此，非正式地，我们可以认为我们的预测是非常有信心的，如果θ'x远大于0，y=1；反之亦然。给定一个训练集，同样非正式地，如果我们能够找到θ，使得对于所有的正例y=1,θ'x远大于0；使得对于所有的负例y=0,θ'x远小于0，这样的拟合是非常好的，因为对于所有的训练实例这将反映一个非常自信的分类器。这似乎是一个不错的目标，我们很快将使用边缘空白的概念将这一想法正式化。

对于不同类型的直观感受，考虑下图，其中x表示正训练实例，o表示负训练实例，还显示了判定边界（这是方程θ'x=0给出的直线，也称为分离超平面），以及被标记为A、B和C三点。

注意到点A距离决策边界最远。如果我们被要求对A处的y值进行预测，那么我们似乎应该很有信心预测y=1。相反地，点C非常接近决策边界，虽然它位于我们可以预测y=1的决策边界一侧，但是似乎只要对决策边界稍作改变就可能很容易导致预测为y=0。因此，我们对A点的预测比C点的预测更有信心。点B介于这两种情况之间，更广泛地说，我们看到如果一个点远离分离超平面，那么我们的预测可能明显更有信心。同样，非正式地，我们认为，如果给定一个训练集，我们能够找到一个决策边界，它允许我们在训练示例上做出所有正确和有信心（意味着远离决策边界）的预测，那将是不错的。稍后我们将使用几何边距的概念将其正式化。

符号

为了使我们对SVM的讨论更容易，我们首先需要引入一个新的符号来讨论分类。我们将考虑使用带有标签y和特征x的二元分类问题的线性分类器。从现在开始，我们将使用y∈{-1,1}（而不是{0,1}）来表示类标签。另外，我们不是用向量θ参数化我们的线性分类器，而是使用参数w、b，并将我们的分类器表示为:

如果z大于等于零，g(z)等于1；否则g(z)等于-1。这种[w，b]符号表示允许我们明确地将截距项b与其他参数分开处理。(我们也放弃了以前让x0 = 1为输入特征向量中的额外坐标的约定。)因此，b扮演先前θ0的角色，w扮演[θ1,...,θn] '的角色。

还要注意，根据我们上面对g的定义，我们的分类器将直接预测1或-1(参见感知器算法)，而不首先通过估计y为1的概率的中间步骤(这是对数几率回归所做的)。

函数间隔和几何间隔

让我们先介绍函数间隔和几何间隔的概念。给定一个训练样本(x(i),y(i))，我们根据训练样本定义(w，b)的函数间隔：

注意，如果y(i)= 1，那么为了使函数间隔变大(即，为了使我们的预测有信心和正确)，我们需要(w'x + b)是一个大的正数。相反地，如果y(i)= -1，然后，为了使函数间隔变大，我们需要(w'x + b)为一个大的负数。此外，如果y(i)(w'x + b) > 0，那么我们对这个例子的预测是正确的。因此，大的函数间隔代表了自信和正确的预测。

对于上面给出的g选择的线性分类器(取{-1,1}中的值)，然而，函数间隔的一个属性使得它不是一个非常好的置信度量。关于我们选择的g函数，我们注意到如果我们用2w代替w而用2b替换b，那么因为g(w'x + b)= g(2w'x + 2b)，所以这根本不会改变最后的预测结果hw,b(x)。因为g仅仅依靠(w'x + b)的符号，而不是幅度。然而，用(2w,2b)代替(w,b)也会导致我们的函数间隔变为之前的两倍。因此，通过成倍放大w和b的值，我们可以使函数间隔任意大，而不会真正改变任何有意义的东西。直观地说，因此强加某种归一化条件可能是有意义的，例如||w||_2 = 1； 也就是说，我们可以用(w / || w ||_2，b / || w ||_2)代替(w，b)，而是考虑(w / || w ||_2，b / || w ||_2)的函数间隔。 我们稍后再回过头来看看。

对于给定训练集S = {(x(i)，y(i))；i = 1,...,m}，我们将(w，b)的函数间隔定义为各个训练样本中的最小函数间隔。如下所示：

接下来，我们将讨论几何间隔。考虑下面的图片：

上面显示了对应于(w，b)的决策边界以及向量w。请注意，w与分离超平面正交。考虑A处的点，其表示具有标签y(i) = 1的一些训练样本的输入x(i)。它与决策边界的距离γ(i)由线段AB给出。

我们怎样才能找到γ(i)的值？w / || w || 是指向与w相同方向的单位长度向量。由于A表示成x(i)，因此我们发现点B由x(i)-γ(i)·w / || w ||给出。但这一点位于决策边界上，决策边界上的所有点x都满足方程w'x + b = 0。因此：

进一步可得：

这是针对图中A的正训练样本的情况得出的，其中处于决策边界的“正”侧是好的。更一般地，我们将训练样本(x(i)，y(i))的(w，b)的几何间隔定义为：

请注意，如果|| w || = 1，那么函数间隔等于几何间隔 - 这就为我们提供了一种方法来联系这两种不同的间隔概念。此外，几何间隔对于重新缩放参数是不变的; 即，如果我们用2w代替w，用2b代替b，则几何间隔不会改变。事实上，这将在以后派上用场。具体来说，由于参数缩放的这种不变性，当试图将w和b拟合到训练数据时，我们可以对w施加任意缩放约束而不改变任何重要的东西。

最后，给定训练集S = {(x(i)，y(i))；i = 1,...,m}，我们还将(w，b)相对于S的几何间隔定义为各个训练样本中几何间隔中的最小值：

最优间隔分类器

给定一个训练集，从我们之前的讨论中可以看出，一个自然的需求是试图找到一个最大化(几何)间隔的决策边界，因为这将反映出对训练集的一个非常有信心的预测和一个良好的“拟合” “对训练数据。具体而言，这将导致分类器用“间隙”(几何间隔)将正和负训练样本分开。

现在，我们假设我们得到一个可线性分离的训练集；即，可以使用一些分离超平面分离正例和负例。 我们如何找到达到最大几何间隔的那个？ 我们可以提出以下优化问题：

我们希望最大化γ，其中每个训练样本具有至少γ大小的函数间隔。||w|| = 1约束还确保函数间隔等于几何间隔，因此我们也保证所有几何间隔至少为γ。 因此，解决该问题将导致(w，b)相对于训练集具有最大可能的几何间隔。

如果我们能解决上面的优化问题，我们就完成了。 但是“||w|| = 1“约束是一个讨厌的(非凸的)，这个问题肯定不是我们可以插入标准优化软件来解决的任何格式。所以，让我们尝试将问题转化为更好的问题。考虑：

在这里，我们将最大化γ / || w ||，但函数间隔都至少为γ，这将给出我们想要的答案。而且，我们已经摆脱了我们不喜欢的约束 || w || = 1。缺点是我们现在有一个讨厌的(再次，非凸)目标函数；而且，我们仍然没有任何可以解决这种形式的优化问题的现成软件。

我们继续吧。 回想一下我们之前的讨论，我们可以在w和b上添加任意缩放约束而不改变任何东西。 这是我们现在使用的关键想法。 我们将引入缩放约束即w，b相对于训练集的函数间隔必须为1：

由于将w和b乘以某个常数导致函数间隔乘以相同的常数，这确实是缩放约束，并且可以通过重新缩放w，b来满足。将其插入上述问题，并注意到最大化γ/ || w || = 1 / ||w||与最小化||w||^2相同，我们现在有以下优化问题：

我们现在已经将问题转化为可以有效解决的形式。 以上是具有凸二次目标和仅线性约束的优化问题。 它的解决方案为我们提供了最佳间隔分类器，可以使用商业二次规化代码来解决该优化问题。

虽然我们可以在这里解决问题，但我们要做的是做一个题外话来讨论拉格朗日对偶性。 这将导致我们的优化问题的双重形式，它将在允许我们使用内核获得最佳间隔分类器以在非常高维空间中有效工作方面发挥关键作用。 双重形式还将允许我们推导出一种有效的算法来解决上述优化问题，该算法通常比通用QP软件做得更好。

拉格朗日对偶

让我们暂时搁置SVM和最大间隔分类器，并讨论解决约束优化问题。

考虑以下形式的问题：

你们中的一些人可能还记得拉格朗日乘数的方法如何用来解决它。在这种方法中，我们将拉格朗日定义为：

在这儿，βi称为拉格朗日乘子。然后我们会找到并将偏导数设为零：

来解w和β。

在本节中，我们将此概括为约束优化问题，其中我们可能存在不等式以及等式约束。 由于时间限制，我们不能真正在本节课中详细的研究拉格朗日对偶理论，但我们将给出主要思想和结果，然后将应用于我们的最优间隔分类器的优化问题。

考虑以下内容，我们将其称为原始优化问题：

为了解决这个问题，我们首先定义广义拉格朗日量：

这儿，αi’、βi’是拉格朗日乘子。考虑下面等式：

这里，“P”下标代表“原始”。让我们给一些w， 如果w违反任何原始约束(即，对于某些 i，gi(w)> 0或hi(w)不等于0)，那么你应该能够验证：

相反，如果对于特定的w值确实满足约束，则θP(w)= f(w)。因此:

因此，对于满足原始约束的所有w，θP与我们的问题中的目标具有相同的值，并且如果违反约束则为正无穷大。因此，如果我们考虑最小化问题：

我们看到它与我们原始问题是同一个问题，并且具有相同的解决方案。为了以后的使用，我们还将目标的最优值定义为:

我们称之为原始问题的解。

现在我们再来看一个稍微不同的问题，我们定义：

这儿D下标代表对偶问题。还要注意，在θP的定义中，我们对α、β进行了优化(最大化)，在这里我们相对于w做最小化。
我们现在可以提出对偶优化问题：

这与上面所述的原始问题完全相同，只是现在交换了“max”和“min”的顺序。我们还定义了对偶问题的最优值：

原始和对偶问题是如何相关的？ 很容易证明这一点：

但是，在某些条件下，我们会有:

这样我们就可以解决对偶问题来代替原始问题，让我们看看这些条件是什么。

假设f和gi是凸的，hi是仿射的。进一步假设约束gi是(严格地)可行的；这意味着存在一些w使得所有i的gi(w)<0。

在我们的上述假设下，肯定存在w*、α*、β*，使得w*是原始问题的解，α*、β*是对偶问题的解，而且p* = d* = L (w*，α*，β*)。 此外，w*、α*和β*满足Karush-Kuhn-Tucker(KKT)条件，如下：

此外，如果某些w*、α*、β*满足KKT条件，那么它也是原始和对偶问题的解决方案。

我们请注意等式(5)，这被称为KKT对偶互补条件。具体来说，它暗示如果αi*> 0，那么gi(w*)= 0。(即，“gi(w)≤0”约束是有效的，这意味着它保持平等而不是不等式。)稍后 ，这将是证明SVM只有少量“支持向量”的关键；当我们讨论SMO算法时，KKT对偶互补条件也将为我们提供收敛性测试。

最优间隔分类器

以前，我们提出了以下(原始)优化问题来找到最优间隔分类器：

我们可以将约束写成：

我们对每个训练样本都有一个这样的约束。 请注意KKT对偶互补条件，我们将只有 αi>0 用于函数间隔恰好等于1的训练样例。考虑下图，其中分离超平面的最大间隔为用实线表示。

间隔最小的点恰好是最接近决策边界的点；这里，这些是位于与决策边界平行的虚线上的三个点（一个负面和两个正面示例）。 因此，在我们的优化问题的最优解决方案中，只有三个αi，即对应于这三个训练样本的αi将是非零的。 这三个点在这个问题中被称为支持向量，支持向量的数量可以比训练集的数量小得多的事实将在以后有用。

让我们继续， 展望未来，当我们开发问题的对偶形式时，需要注意的一个关键想法是我们将尝试仅根据输入特征空间中各点之间的内积<x(i),x(j)>来编写算法。 当我们应用内核技巧时，根据这些内积表达我们的算法这一事实将是关键。

当我们为优化问题构造拉格朗日时，我们得到：

注意，只有“αi”但没有“βi”拉格朗日乘子，因为问题只有不等式约束。

让我们找到问题的对偶形式。 要做到这一点，我们需要首先最小化L(w，b，α)相对于w和b(对于固定α)，得到对偶形式，我们将对L求导(相对于w和b)，然后令导数为零。 我们有：

进一步可得：

对b求导：

如果我们在等式(9)中采用w的定义并将其插回拉格朗日(等式8)，并简化，我们得到:

但是根据公式(10)，最后一项必须为零，因此我们得到:

回想一下，我们通过最小化L相对于w和b来得到上面的等式。将这与约束αi≥0(我们一直有)和约束(10)放在一起，我们得到以下对偶优化问题：

你还应该能够验证在我们的优化问题中确实满足p* = d*和KKT条件(等式3~7)所需的条件。 因此，我们可以解决对偶问题代替解决原始问题。 具体来说，在上面的对偶问题中，我们有一个最大化问题，其中参数是αi。 我们稍后将讨论我们将用于解决对偶问题的特定算法，但是如果我们确实能够解决它(即，找到最大化受到约束的W(α)的α)，那么我们可以使用等式(9)返回并找到作为α的函数的最优w。找到w*后，通过考虑原始问题，找到截距项b的最优值也是很容易的：

在继续之前，让我们更仔细地看一下等式(9)，它给出了w的最佳值(α的最佳值)。 假设我们将模型的参数拟合到训练集，现在希望在新点x进行预测。 然后，我们将计算w'x + b，并且当且仅当大于零时，预测y = 1。 但是使用(9)，这个数量也可以写成：

因此，如果我们找到αi，为了进行预测，我们必须计算仅依赖于x和训练集中的点之间的内积的量。 此外，我们之前看到除了支持向量之外，αi都将为零。 因此，上面总和中的许多式子将为零，我们确实只需要找到x和支持向量之间的内积(其中通常只有一小部分)，以便计算(13)并做预测。

通过检查优化问题的对偶形式，我们获得了对问题结构的重要洞察，并且还能够仅根据输入特征向量之间的内积来编写整个算法。 在下一节中，我们将利用此属性将内核应用于我们的分类问题。 由此产生的算法，支持向量机，将能够在高维空间中有效地学习。

核

回到我们对线性回归的讨论中，我们遇到了一个问题，其中输入x是房子的居住面积，我们考虑使用特征x、x^2和x^3进行回归以获得立方函数。 为了区分这两组变量，我们将“原始”输入值称为问题的输入属性attributes(在本例中为x，居住面积)。当它被映射到一组新的集合然后传递给学习算法时，我们将这些新集称为输入特征features。(不幸的是，不同的作者使用不同的术语来描述这两件事，但我们会尝试在这些注释中使用这个术语。)我们还将φ表示特征features映射，该映射从属性attributes映射到特征features。 例如，在我们的例子中，我们有：

我们可能不想使用使用原始输入属性attributesx来应用SVM，而是使用某些特征features φ(x)来学习。 为此，我们只需要检查我们之前的算法，并用φ(x)替换其中的x。

由于算法可以完全根据内积<x，z>编写，这意味着我们将用<φ(x)，φ(z)>替换所有这些内积。 具体来说，给定特征映射φ，我们定义相应的内核：

然后，之前在我们的算法中有<x，z>的地方，我们可以简单地用K(x，z)替换它，我们的算法现在将使用特征φ学习。

现在，给定φ，我们可以通过找到φ(x)和φ(z)并取其内积来轻松计算K(x，z)。 但更有趣的是，通常，K(x，z)的计算成本可能非常低廉，即使φ(x)本身的计算成本非常高(可能因为它是一个极高的维度向量)。在这样的设置中，通过在我们的算法中使用计算K(x，z)的有效方法，我们可以得到SVM在φ给出的高维特征空间中学习，但是不必明确地找到或表示向量φ(x)。
我们来看一个例子吧。 假设x,z∈Rn，并考虑：

我们也可以这样写：

因此，我们看到K(x，z)=φ(x)'φ(z)，其中给出了特征映射φ(此处针对n = 3的情况)：

注意，虽然计算高维φ(x)需要O(n^2)时间，但是计算K(x，z)仅需要O(n)时间，n为输入属性的维度。

对于内核，也要考虑：

这对应于特征映射，并且参数c控制xi(一次项)和xixj(二次项)项之间的相对加权。n==3特征映射如下所示：

更广泛的说，内核：

对应于映射到特征空间(n+d,d)的特征。然而，尽管在这个O(n^d)维空间中工作，计算K(x，z)仍然只需要O(n)时间，因此我们永远不需要在这个非常高维的特征空间中明确地表示特征向量。

现在，让我们谈谈内核略有不同的观点。 直观地，(并且这种直觉有问题但是没有关系)，如果φ(x)和φ(z)靠得很近，那么我们可能期望K(x，z)=φ(x)'φ(z)很大。 相反，如果φ(x)和φ(z)相距很远 - 比如几乎彼此正交 - 则K(x，z)=φ(x)'φ(z)将很小。 因此，我们可以将K(x，z)视为对φ(x)和φ(z)有多相似的一些测量，或者x和z有多相似。

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

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

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

现在，如果K是有效的核，则Kij = K(x(i)，x(j))=φ(x(i))'φ(x(j))=φ(x(j))'φ(x (i))= K(x(j)，x(i))= Kji，因此K必须是对称的。 让φ_k(x)表示向量φ(x)的第k个坐标，我们发现对于任何向量z，我们都有：

上面倒数第二步使用了与问题集1 -- Q1中相同的技巧。 由于z是任意的，这表明K是半正定(K≥0)的。

因此，我们已经证明，如果K是有效内核(即，如果它对应于某些特征映射φ)，则相应的核矩阵K∈Rm×m是对称的半正定。 更一般地说，这不仅是K成为有效内核(也称为Mercer内核)的必要条件，也是充分条件。 以下结果归功于Mercer。

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

在课堂上，我们还简要介绍了其他几个内核示例。 例如，考虑数字识别问题，其中给定手写数字(0-9)的图像(16×16像素)，我们必须弄清楚它是哪个数字。使用简单的多项式核K(x，z)=(x'z)^d或高斯核，SVM能够在这个问题上获得极好的性能。这是特别令人惊讶的，因为输入属性x仅是图像像素强度值的256维向量，并且系统没有关于视觉的先验知识，或者甚至关于哪些像素与哪些像素相邻。

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

正规化和线性不可分的情况

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

为了使算法适用于非线性可分离数据集以及对异常值不太敏感，我们重新配置我们的优化(使用ℓ1正则化)，如下所示：

因此，现在允许样本具有小于1的函数间隔，并且如果样本具有函数间隔1-ξi(ξ> 0)，则我们将目标函数的成本增加Cξi。参数C控制了使||w||^2变小(我们之前看到的使边距变大)和确保大多数示例具有至少1的功能边界的双重目标之间的相对权重。

和以前一样，我们可以形成拉格朗日：

这里，αi和ri是我们的拉格朗日乘数(约束为≥0)。 我们不会再详细讨论对偶的推导，但是在将w和b的导数设置为零之后，将它们替换回来并简化，我们得到以下问题的对偶形式：

和以前一样，我们也可以用公式(9)中给出的αi表示w，这样在求解对偶问题后，我们可以继续使用公式(13)来进行预测。 注意，有点令人惊讶的是，在加上l1正则化时，对偶问题的唯一变化是原来的约束0≤αi现在变为0≤αi≤C。b*的计算也必须修改(方程式11不再有效)；请参阅下一节。

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

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

SMO算法

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

坐标上升算法

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

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

因此，在该算法的最内层循环中，除了αi其余的参数都看成定值，并且仅针对参数αi重新优化W。在这里给出的这个方法的版本中，内循环以α1、α2、...αm、α1、α2、...的顺序重新优化变量(一个更复杂的版本可能会选择其他排序；例如，我们可以根据在W(α)中获得最大增长的来选择下一个变量更新。)

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

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

SMO

我们通过SMO算法的推导来结束对SVM的讨论。 一些细节将留给作业，而对于其他人，可以参考课堂上发表的论文摘录。

这是我们想要解决的(对偶)优化问题：

假设我们有一组满足约束条件的αi(18-19)。 现在，假设我们想要(α2,...,αm)固定，并采取坐标上升步骤，并相对于α1重新优化目标。 我们可以取得任何进展吗? 答案是否定的，因为约束(19)确保了这一点:

或者，通过将两边乘以y(1)，我们等效地具有:

(这一步使用了y(1)∈{-1,1}，因此(y(1))^2 = 1的事实。)因此，α1完全由其他αi确定，如果我们要保持α2,...,αm固定，那么我们就不能在不违反优化问题中的约束(19)的情况下对α1进行任何改变。

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

为了测试该算法的收敛性，我们可以检查KKT条件(方程14-16)是否满足于某个tol。 这里，tol是收敛容差参数，并且通常设置为约0.01至0.001。

SMO是一种有效算法的关键原因是可以非常有效地计算对αi、αj的更新。 现在让我们简要概述一下推导有效更新的主要思路。

假设我们目前有一些αi的设置满足约束条件(18-19)，并假设我们决定保持α3,...,αm固定，并且想要相对于α1和α2重新优化W(α1,α2,...,αm)(受约束条件限制)。 从(19)开始，我们要求:

由于右侧是固定的(因为我们已经固定了α3,...,αm)，我们可以让它用常数ζ表示：

因此，我们可以如下描述对α1和α2的约束：

根据约束(18)，我们知道α1和α2必须位于所示的框[0，C]×[0，C]内。 还绘制了线α1y(1)+α2y(2)=ζ，我们知道α1和α2必须位于其上。还要注意，从这些约束中，我们知道L≤α2≤H；否则，(α1，α2)不能同时满足框和直线约束。在这个例子中，L = 0。但是根据线α1y(1)+α2y(2)=ζ的样子，这并不一定是这种情况；但更一般地说，在α2的允许值上会有一些下限L和一些上限H，这将确保α1，α2位于框[0，C]×[0，C]内。

使用等式(20)，我们也可以将α1写为α2的函数：

(自己检查这个推导；我们再次使用y(1)∈{-1,1}这样的事实，使得(y(1))^2 = 1。)因此，可以写出目标W(α):

将α3,...,αm看作常数，你应该能够验证这只是α2中的一些二次函数。对于某些适当的a、b和c，这也可以以aα2^2+bα2+ c的形式表示。如果我们忽略“框”约束(18)(或等效地，L≤α2≤H)，那么我们可以通过将其导数设置为零并求解来轻松地最大化该二次函数。我们将

并将其在[L，H]中“剪切”来找到所得到的最优值。

最后，找到了α_new2，我们可以使用等式(20)返回并找到α_new1的最佳值。

还有一些非常简单的细节，但我们将让你在Platt的论文中了解：一个是用于选择下一个αi，αj进行更新的启发式选择；另一种是在运行SMO算法时如何更新b。