SMO论文中文翻译

John C. Platt
Microsoft Research
jplatt@microsoft.com
Technical Report MSR-TR-98-14
April 21, 1998
© 1998 John Platt

摘要（ABSTRACT）

本文提出了一种新的支持向量机（Support Vector Machines）算法：序列最小优化算法(Sequential Minimal Optimization，SMO)。训练支持向量机需要解决一个非常大的二次规划（Quadratic Programming，QP）优化问题。SMO将这个非常大的QP问题分成了一系列尽可能少的QP问题。对这些小的QP问题使用解析解，避免使用耗时间的数值型QP优化问题作为内部循环。SMO所需的内存量在训练集大小上是线性的，这允许SMO处理非常大的训练集。由于避免了矩阵计算，对于各种测试问题，SMO在训练集大小上的缩放在线性和二次之间，而标准的分块SVM算法在训练集大小上的缩放在线性和三次之间。SMO算法的计算时间主要受SVM算法计算时间的影响，因此对于线性支持向量机和稀疏数据集，SMO算法的计算速度最快。在真实世界的稀疏数据集上，SMO算法可以比分块算法快1000倍以上。

在过去的几年里，人们对支持向量机(SVMs)的兴趣激增[1] [2] [3]。经验表明，支持向量机在各种各样的问题上都具有良好的泛化性能，如手写字符识别[4]、人脸检测[5]、行人检测[6]和文本分类[7]。

然而，支持向量机的使用仍然局限于一小部分研究人员。一个可能的原因是支持向量机的训练算法很慢，特别是对于大问题。另一种解释是，SVM训练算法复杂、精细，一般工程师难以实现。

本文描述了一种新的支持向量机学习算法，该算法概念简单，易于实现，通常速度更快，与标准的支持向量机训练算法相比，对困难的支持向量机问题具有更好的缩放特性。新的SVM学习算法被称为SMO。与以前使用数值QP作为内环的SVM学习算法不同，SMO使用解析QP步骤。

本文首先对支持向量机进行了概述，并对现有的支持向量机训练算法进行了综述。然后详细介绍了SMO算法，包括，解析QP步骤的求解，选择内环优化变量的启发式算法，如何设置SVM的阈值，一些特殊情况下的优化，算法的伪代码，以及SMO与其他算法的关系。

SMO已经在两个真实数据集和两个人工数据集上进行了测试。本文给出了这些数据集定时SMO与标准”分块”算法的对比结果，并给出了基于这些定时的结论。最后，有一个附录，描述了解析优化的推导。

图1 线性支持向量机

Vladimir Vapnik在1979年发明了支持向量机[1:1]。在最简单的线性形式中,支持向量机是一种超平面，它将一组正例与一组反例分隔开，并具有最大的边界(见图1)。在线性情况下，边界(m)由超平面到最近的正例和反例的距离定义。线性支持向量机的输出公式为

[u=\vec{w} \cdot \vec{x} – b \tag{1} ]

其中(w)为超平面的法向量， (x)为输入向量。分离超平面是平面 (u=0)。最近的点位于(u =±1)平面上。边界(m)是这样的

[m=\frac{1}{||\vec{w}||^2}\tag{2} ]

边界最大化可以通过以下优化问题[3:1]表示:

[\begin{align} \min_{\vec{w},b} \quad &\frac{||\vec{w}||^2}{2} ,\ s.t \quad &\ y_i(\vec{w} \cdot x_i-b)\geq 1,\forall i \tag{3} \end{align} ]

式中，(x_i)为第(i)个训练示例，(y_i)为第(i)个训练示例的SVM正确输出。(y_i)的值对于类中的正例子是+1，对于反例子是-1。

使用拉格朗日量，这个优化问题可以转换成对偶形式，这是一个QP问题，其中目标函数(Ψ)单独依赖于一组拉格朗日乘子(α_i)，

[\min_{\vec{α}}Ψ(\vec{α})=\min_{\vec{α}}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j(\vec{x_i} \cdot \vec{x_j})α_iα_j-\sum_{i=1}^{N}α_i \tag{4} ]

(N为训练例数)，受不等式约束,

[α_i\geq 0,\forall i \tag{5} ]

一个线性等式约束，

[\sum_{i=1}^N y_iα_i =0 \tag{6} ]

在每个拉格朗日乘数和每个训练示例之间有一个一对一的关系。一旦确定了拉格朗日乘子，就可以由拉格朗日乘子求出法向量 (\vec{w}) 和阈值 (b):

[\vec{w}=\sum_{i=1}^{N}y_iα_i\vec{x_i} ,\\ b=\vec{w}\cdot\vec{x_k}-y_k\ for \ some \ α_k > 0 \tag{7} ]

因为(\vec{w}) 在使用之前可以通过公式(7)从训练数据中计算出来，所以评估一个线性支持向量机所需的计算量在非零支持向量的数量上是恒定的。

当然，不是所有的数据集都是线性可分的。可能没有超平面把正面的例子和负面的例子分开。在上面的公式中，不可分离的情况将对应一个无穷解。然而，在1995年，Cortes & Vapnik [8]建议对原始优化语句(3)进行修改，对未能达到正确的边界进行惩罚。修改成:

[\begin{align} \min_{\vec{w},b,\vec{ξ} }& \quad \frac{1}{2}||\vec{w}||^2+C\sum_{i=1}^{N}ξ_i \ s.t. & \quad y_i(\vec{w}\cdot\vec{x_i}-b)\geq1-ξ_i,\forall i,\tag{8} \end{align} ]

其中(ξ_i)是松弛变量，允许边界失效，而(C)是一个参数，它权衡了大范围边界与少量边界失效之间的关系。当这个新的优化问题转化为对偶形式时，只需将约束(5)变为框约束:

[0\leq α\leq C,\forall i \tag{9} ]

变量(ξ_i)在对偶公式中根本没有出现。

支持向量机甚至可以进一步推广到非线性分类器[9]。非线性的输出
SVM由拉格朗日乘数显式计算:

[u=\sum_{j=i}^{N}y_iα_jK(\vec{x_j},\vec{x})-b \tag{10} ]

其中(K)是核函数，用于度量输入向量(\vec{x})和存储的训练向量(\vec{x_j})之间的相似度或距离。(K)的例子包括高斯、多项式和神经网络非线性[3:2]。如果(K)是线性的，则恢复线性支持向量机(1)的方程。

拉格朗日乘子(α_i)仍然通过二次程序计算。非线性改变了二次形式，但对偶目标函数(Ψ)在(α)中仍然是二次的:

[\begin{align} \min_{\vec{α}}Ψ(\vec{α})=&\min_{\vec{α}}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_jK(\vec{x_i} \cdot \vec{x_j})α_iα_j-\sum_{i=1}^{N}α_i \ &0\leq α\leq C,\forall i \ &\sum_{i=1}^N y_iα_i =0 \tag{11} \end{align} ]

上式(11)中的QP问题就是SMO算法要解决的QP问题。为了使上述QP问题是正定的，核函数K必须服从Mercer条件[3:3]。
KKT(Karush-Kuhn-Tucker)条件是正定QP问题最优点的充分必要条件。QP问题(11)的KKT条件特别简单。当对于所有i:

[\begin{align*} α_i=0 \Leftrightarrow y_iu_i\geq 1 \ 0

式中，(u_i)是第(i)个训练例的SVM输出。注意，KKT条件可以一次在一个示例上求值，这在构建SMO算法时很有用。

由于其巨大的规模，支持向量机产生的QP问题(11)不能轻易地通过标准的QP技术来解决。(11)中的二次形式涉及到一个矩阵，其元素的数量等于训练示例数量的平方。这个矩阵不能容纳,如果有超过4000个训练示例，则为128兆字节。

Vapnik [1:2]描述了一种解决SVM QP的方法，自此被称为”分块”。分块算法利用了这样一个事实:如果去掉拉格朗日乘子为0的矩阵的行和列，那么二次型矩阵的值是相同的。因此，大的QP问题可以分解为一系列小的QP问题，这些小问题的最终目标是识别所有非零的拉格朗日乘数，并丢弃所有的零，拉格朗日乘数法。在每个步骤中，分块解决由以下内容组成的QP问题，示例:上一步的每个非零拉格朗日乘子，以及M个违反KKT条件的最差示例(12) [3:4]，对于M的某个值(参见图2)。如果在某一步中违反KKT条件的示例少于M个，则添加所有违反KKT条件的示例。每个QP子问题都使用前一个子问题的结果进行初始化。最后一步确定了整个非零拉格朗日乘子集合，从而解决了大型QP问题。

分块严重地将矩阵的大小从训练样本数量的平方降低到近似于非零拉格朗日乘子数量的平方。然而，分块仍然无法处理大规模训练问题，因为即使是这个简化矩阵也无法装入内存。

图2。训练支持向量机的三种替代方法:分块、Osuna算法和SMO。对于每种方法，说明了三个步骤。每一步的水平细线代表训练集，而厚框代表在这一步优化的拉格朗日乘数。对于分块，每一步添加固定数量的示例，而每一步丢弃零拉格朗日乘数。因此，每一步训练的例子数量趋于增长。对于Osuna的算法，每一步优化固定数量的示例:添加相同数量的示例

1997年，Osuna等人[10]证明了一个定理，提出了一套新的支持向量机QP算法。该定理证明了大QP问题可以分解为一系列小QP子问题。只要在前一个子问题的样例中添加至少一个违反KKT条件的样例，每一步都会降低总体目标函数，并保持一个满足所有约束条件的可行点。因此，一个序列如果QP子问题中总添加至少一个违例者，则保证收敛。注意，分块算法服从定理的条件，因此会收敛。

Osuna等人建议为每个QP子问题保持一个固定大小的矩阵，这意味着在每一步[10:1]添加和删除相同数量的示例(见图2)。使用固定大小的矩阵将允许在任意大小的数据集上进行训练。Osuna的论文[10:2]中给出的算法建议每一步增加一个示例并减去一个示例。显然，这是低效的，因为它将使用整个数值QP优化步骤来使一个训练示例遵守KKT条件。在实践中，研究人员根据未发表的启发式算法[11]对多个实例进行加减运算。无论如何，所有这些方法都需要一个数值QP求解器。众所周知，QP数值很难正确计算;有许多数值精度问题需要解决。

序列最小优化(SMO)是一种简单的算法，可以快速求解SVM QP问题，不需要任何额外的矩阵存储，也完全不需要使用数值QP优化步骤。SMO将整个QP问题分解为QP子问题，利用Osuna定理保证算法的收敛性。

与以往方法不同，SMO在每一步都选择解决尽可能小的优化问题。对于标准的SVM QP问题，最小可能的优化问题包含两个拉格朗日乘子，因为拉格朗日乘子必须服从一个线性等式约束。在每一步，SMO选择两个拉格朗日乘子进行联合优化，找到这些乘子的最优值，并更新SVM以反映新的最优值(见图2)。

SMO的优点在于可以解析地求解两个拉格朗日乘子。因此，完全避免了数值QP优化。算法的内部循环可以用少量的C代码来表示，而不是调用整个QP库例程。即使在算法的过程中解决了更多的优化子问题，但每个子问题的速度都非常快，从而快速地解决了整个QP问题。

此外，SMO完全不需要额外的矩阵存储。因此，非常大的SVM训练问题可以放在普通个人计算机或工作站的内存中。由于SMO算法没有使用矩阵算法，因此不易受到数值精度问题的影响。

SMO有两个组成部分:用于求解两个拉格朗日乘子的解析方法，以及用于选择优化哪些乘子的启发式方法。

图3所示。两个拉格朗日乘数必须满足整个问题的所有约束条件。不等式约束导致拉格朗日乘数在方框中。线性等式约束使它们位于一条对角线上。因此，SMO算法的第一步必须在对角线上找到目标函数的最优解。

为了求解这两个拉格朗日乘子，SMO首先计算对这两个乘子的约束，然后求解约束最小值。为了方便起见，所有指向第一个乘数的量的下标都是1，而指向第二个乘数的量的下标都是2。因为只有两个乘数，约束可以很容易地在二维中显示(参见图3)。边界约束(9)导致拉格朗日乘子位于方框中，而线性等式约束(6)使得拉格朗日乘子位于对角线上。因此，目标函数的约束最小值必须位于对角线段上(如图3所示)。这个约束解释了为什么可以优化的拉格朗日乘子的最小数量是2:如果SMO只优化一个乘子，它就不能在每一步都满足线性等式约束。

对角线段的端点可以很简单地表示出来。该算法在不失一般性的前提下，首先计算第二个拉格朗日乘子(α_2)，然后根据(α_2)计算对角线段的端点。如果目标(y_1)不等于目标(y_2)，则适用于(α_2):

[L=max(0,α_2-α_1),\qquad H=min(C,C+α_2-α_1) \tag{13} ]

如果目标(y_1)等于目标(y_2)，那么下面的边界适用于(α_2):

[L=max(0,α_2+α_1-C),\qquad H=min(C,α_2+α_1) \tag{14} ]

目标函数沿对角线的二阶导数可以表示为:

[η=K(\vec{x_1} \cdot \vec{x_1})+K(\vec{x_2} \cdot \vec{x_2})-2K(\vec{x_1} \cdot \vec{x_2}) \tag{15} ]

通常情况下，目标函数是正定的，沿着线性等式约束的方向会有一个最小值，(η)会大于零。在这种情况下，SMO会计算约束方向上的最小值:

[α_2^{new}=α_2+\frac{y_2(E_1-E_2)}{η} \tag{16} ]

其中(E_i=u_i-y_i)为第(i)个训练样本的误差。下一步，通过将无约束最小值裁剪到线段的末端来找到有约束的最小值:

[α_2^{new,clipped}= \begin{cases} H \quad \ \ \ \ if\quad α_2^{new}\geq H \ α_2^{new} \quad if \quad L

现在令(s=y_1y_2)。(α_1)的值是根据裁剪后的新(α_2)计算得到的:

[α_1^{new}=α_1+s(α_2^{new}-α_2^{new,clipped}) \tag{18} ]

在不寻常的情况下，(η)不会是正的。如果核函数(K)不符合Mercer条件，则η为负，从而导致目标函数变得不确定。即使有一个正确的内核，如果多个训练示例具有相同的输入向量(x)， (η)也可以为零。在任何情况下，即使(η)不是正的，SMO也将工作，在这种情况下，目标函数(Ψ)应该在线段的每个端点进行评估:

[\begin{align} f_1 &= y_1(E_1+b)-α_1K(\vec{x_1} \cdot \vec{x_1})-sα_2K(\vec{x_1} \cdot \vec{x_2})\ f_2 &= y_2(E_2+b)-sα_1K(\vec{x_1} \cdot \vec{x_2})-α_2K(\vec{x_2} \cdot \vec{x_2})\ L_1 &= α_1+s(α_2-L)\ H_1 &= α_1+s(α_2-H)\ Ψ_L &= L_1f_1+Lf_2+\frac{1}{2}L_1^2K(\vec{x_1} \cdot \vec{x_1})+\frac{1}{2}L^2K(\vec{x_1} \cdot \vec{x_2})+sLL_1K(\vec{x_1} \cdot \vec{x_2}) \ Ψ_H &= H_1f_1+Hf_2+\frac{1}{2}H_1^2K(\vec{x_1} \cdot \vec{x_1})+\frac{1}{2}H^2K(\vec{x_1} \cdot \vec{x_2})+sHH_1K(\vec{x_1} \cdot \vec{x_2}) \tag{19} \end{align} ]

SMO将拉格朗日乘子移动到目标函数值最小的端点。如果两端的目标函数相同(四舍五入误差在一个很小的(ε)内)，且核函数符合Mercer条件，则联合最小化无法取得进展。该场景描述如下。

只要SMO总是在每一步优化和改变2个拉格朗日乘子，并且至少有一个拉格朗日乘子在这一步之前违反了KKT条件，那么每一步都会根据Osuna [10:3]定理减小目标函数。因此收敛性得到了保证。为了加快收敛速度，SMO使用启发式方法选择两个拉格朗日乘子进行联合优化。

有两个独立的选择启发式算法:一个用于第一个拉格朗日乘子，另一个用于第二个。SMO算法的外循环由第一种启发式算法构成。外循环首先遍历整个训练集，确定每个样本是否违反KKT条件(12)。如果一个例子违反了KKT条件，那么它就有资格进行优化。在遍历整个训练集之后，外循环迭代拉格朗乘子既不为0也不为C的所有示例(非边界示例)。同样，每个示例都根据KKT条件进行检查，违反条件的示例有资格进行优化。外循环对非边界样本进行重复遍历，直到所有的非边界样本都满足(ε)内的KKT条件。然后，外循环返回并遍历整个训练集。外循环在对整个训练集的单遍遍历和对非边界子集的多遍遍历之间交替进行，直到整个训练集服从(ε)内的KKT条件，此时算法终止。

第一选择启发式算法将CPU时间集中在最可能违反KKT条件的例子上:非边界子集。随着SMO算法的进行，在边界处的样例很可能会停留在边界处，而不在边界处的样例会随着其他样例的优化而移动。因此，SMO算法将遍历非边界子集，直到该子集是自洽的，然后SMO算法将扫描整个数据集，寻找因优化非边界子集而违反KKT的边界样本。

注意，KKT条件被检查为满足ε。通常情况下，(ε)被设置为(10^{-3})。识别系统通常不需要满足高精度的KKT条件:对于正余量的例子，输出在0.999到1.001之间是可以接受的。如果需要产生非常高的精度输出，SMO算法(和其他SVM算法)将无法快速收敛。

一旦选择了第一个拉格朗日乘子，SMO就会选择第二个拉格朗日乘子来最大化联合优化过程中所采取的步长。现在，计算核函数(K)是耗时的，因此SMO用公式(16)中的分子的绝对值近似步长:(|E_1-E_2|)。SMO为训练集中的每个非边界样本保存一个缓存的误差值(E)，然后选择一个误差来近似最大化步长。如果(E_1)为正，SMO选择一个误差最小的样本(E_2)。当(E_1)为负时，SMO选择误差最大的(E_2)。

在特殊情况下，SMO无法使用上述第二选择启发式算法取得积极进展。例如，如果第一个和第二个训练样本共享相同的输入向量x，则无法取得积极的进展，这导致目标函数变得半定。在这种情况下，SMO使用一层第二选择启发式算法，直到找到一对可以取得积极进展的拉格朗日乘数。通过对两个拉格朗日乘子进行联合优化，使步长不为零，可以确定取得了积极进展。第二选择启发式的层次结构包括以下内容。如果上述启发式方法没有取得积极进展，那么SMO就开始迭代非边界样例，寻找第二个可以取得积极进展的样例。如果没有一个非边界样本取得正进展，那么SMO开始迭代整个训练集，直到找到一个取得正进展的样本。对非边界样本的迭代和对整个训练集的迭代都是从随机位置开始的，以便使SMO不偏向训练集开始时的样本。在极端堕落的情况下，没有一个例子可以作为第二个例子。当发生这种情况时，第一个示例将被跳过，SMO将继续使用另一个选择的第一个示例。

每一步后重新计算阈值(b)，以便两个优化示例都满足KKT条件。当新的(α_1)不在边界处时，下面的阈值(b_1)是有效的，因为当输入为(x_1)时，它强制SVM的输出为(y_1):

[b_1=E_1+y_1(α_1^{new}-α_1)K(\vec{x_1} \cdot \vec{x_1})+y_2(α_2^{new,clipped}-α_2)K(\vec{x_1} \cdot \vec{x_2})+b \tag{20} ]

当新的(α_2)不在边界处时，下面的阈值(b_2)是有效的，因为当输入为(x_2)时，它强制SVM的输出为(y_2):

[b_2=E_2+y_1(α_1^{new}-α_1)K(\vec{x_1} \cdot \vec{x_2})+y_2(α_2^{new,clipped}-α_2)K(\vec{x_2} \cdot \vec{x_2})+b \tag{21} ]

当(b_1)和(b_2)都有效时，它们是相等的。当新的拉格朗日乘子都有界且(L)不等于(H)时，(b_1)和(b_2)之间的区间都是符合KKT条件的阈值。SMO选择阈值在(b_1)和(b_2)之间。

要计算一个线性SVM，只需要存储一个权重向量(\vec{w})，而不是对应于非零拉格朗日乘子的所有训练样本。如果联合优化成功，则需要更新存储的权重向量以反映新的拉格朗日乘子值。由于SVM是线性的，权重向量的更新很容易:

[\vec{w^{new} }=\vec{w}+y_1(α_1^{new}-α_1)\vec{x_1}+y_2(α_2^{new}-α_2)\vec{x_2} \tag{22} ]

下面的伪代码描述了整个SMO算法:

target = desired output vector
point = training point matrix

procedure takeStep(i1,i2)
    if (i1 == i2) return 0
    alph1 = Lagrange multiplier for i1
    y1 = target[i1]
    E1 = SVM output on point[i1] – y1 (check in error cache)
    s = y1*y2
    Compute L, H via equations (13) and (14)
    if (L == H)
        return 0
    k11 = kernel(point[i1],point[i1])
    k12 = kernel(point[i1],point[i2])
    k22 = kernel(point[i2],point[i2])
    eta = k11+k22-2*k12
    if (eta > 0)
    {
        a2 = alph2 + y2*(E1-E2)/eta
        if (a2 < L) a2 = L
        else if (a2 > H) a2 = H
    }
    else
    {
        Lobj = objective function at a2=L
        Hobj = objective function at a2=H
        if (Lobj < Hobj-eps)
            a2 = L
        else if (Lobj > Hobj+eps)
            a2 = H
        else
            a2 = alph2
    }
    if (|a2-alph2| < eps*(a2+alph2+eps))
        return 0
    a1 = alph1+s*(alph2-a2)
    Update threshold to reflect change in Lagrange multipliers
    Update weight vector to reflect change in a1 & a2, if SVM is linear
    Update error cache using new Lagrange multipliers
    Store a1 in the alpha array
    Store a2 in the alpha array
    return 1
endprocedure

procedure examineExample(i2)
    y2 = target[i2]
    alph2 = Lagrange multiplier for i2
    E2 = SVM output on point[i2] &#x2013; y2 (check in error cache)
    r2 = E2*y2
    if ((r2 < -tol && alph2 < C) || (r2 > tol && alph2 > 0))
    {
    if (number of non-zero & non-C alpha > 1)
    {
        i1 = result of second choice heuristic (section 2.2)
        if takeStep(i1,i2)
            return 1
    }
    loop over all non-zero and non-C alpha, starting at a random point
    {
        i1 = identity of current alpha
        if takeStep(i1,i2)
            return 1
    }
    loop over all possible i1, starting at a random point
    {
        i1 = loop variable
        if takeStep(i1,i2)
            return 1
    }
    }
    return 0
endprocedure

main routine:
    numChanged = 0;
    examineAll = 1;
    while (numChanged > 0 | examineAll)
    {
    numChanged = 0;
    if (examineAll)
        loop I over all training examples
            numChanged += examineExample(I)
    else
        loop I over examples where alpha is not 0 & not C
            numChanged += examineExample(I)
    if (examineAll == 1)
        examineAll = 0
    else if (numChanged == 0)
        examineAll = 1
    }

SMO算法既与以往的SVM算法有关，也与优化算法有关。SMO算法可以被认为是Osuna算法的一个特殊情况，其中优化规模为2,Lagrange乘子在每一步都被通过良好的启发式选择的新乘子替换。

SMO算法与一系列优化算法密切相关，这些算法被称为Bregman方法[12]或row-action方法[13]。这些方法用于求解具有线性约束的凸规划问题。它们是迭代方法，其中每个步骤都将当前原始点投影到每个约束上。未修改的Bregman方法不能直接解决QP问题(11)，因为SVM中的阈值在对偶问题中产生了线性等式约束。如果每一步只投影一个约束，就会违反线性等式约束。用更专业的术语来说，在具有阈值b的所有可能权重向量(\vec{w})的组合空间上最小化权重向量(\vec{w})的范数的原始问题产生了一个Bregman-D投影，该投影没有唯一的最小[12:1] [14]。

有趣的是，考虑一个SVM，其阈值b固定为零，而不是被求解。固定阈值的SVM不具有线性等式约束(6)。因此，一次只需要更新一个拉格朗日乘子，可以使用行动作方法。然而，由于等式(8)中有松弛变量(ξ_i)，传统的Bregman方法仍然不能适用于这类支持向量机。由于松弛变量(ξ_i)的存在，使得Bregman-D投影在权向量(\vec{w})和松弛变量(ξ_i)的组合空间中变得非唯一

幸运的是，SMO可以被修改以解决固定阈值的SVM。SMO将每个拉格朗日乘子更新为对应维度上Ψ的最小值。更新规则为:

[α_1^{new} = α_1 + \frac{y_1E_1}{K(\vec{x_1} \cdot \vec{x_1})} \tag{23} ]

这个更新方程强制SVM的输出为(y_1)(类似于Bregman方法或Hildreth的QP方法[15])。在计算出新的(α)后，它会被裁剪到([0,C])区间(与之前的方法不同)。选择优化拉格朗日乘子的方法与2.2节中描述的第一种启发式方法相同。

线性SVM的固定阈值SMO在概念上类似于感知器放松规则[16]，其中感知器的输出在出现错误时进行调整，以便输出准确地位于边界上。然而，固定阈值的SMO算法有时会减少训练输入在权重向量中的比例，以最大化间隔。松弛规则不断增加权重向量中的训练输入量，因此不是最大间隔。高斯核的固定阈值SMO也与资源分配网络(resource allocating network，RAN [17])算法有关。当RAN检测到某些类型的错误时，它将分配一个内核来精确地修复错误。SMO的表现类似。然而，SMO/SVM将调整核的高度以最大化特征空间中的间隔，而RAN将简单地使用LMS来调整核的高度和权重。

将SMO算法与标准的分块SVM学习算法在一系列基准上进行了测试。这两个算法都是用c++编写的，使用的是微软的Visual c++ 5.0编译器。两种算法都在一个未加载的266mhz Pentium II处理器上运行，该处理器运行Windows NT 4。

两种算法都利用了输入向量的稀疏性。更具体地说，内核函数在内部循环中依赖于点积。如果输入是稀疏向量，那么输入可以存储为稀疏数组，并且点积只会迭代非零输入，将非零输入乘以相应的权重累加。如果输入是一个稀疏的二进制向量，那么可以存储输入中”1″的位置，并且点积将对输入中”1″的位置对应的权重求和。

chunking算法采用Burges [3:5]提出的投影共轭梯度算法[18]作为QP求解器。为了确保分块算法是一个公平的基准，Burges比较了他在运行Solaris的200mhz Pentium II上分块代码的速度和基准分块代码的速度(关闭稀疏点积代码)。测试结果表明，测试速度相当，表明分块代码是一个合理的基准测试。

要确保分块代码和SMO代码具有相同的精度，需要一定的注意。如果输出值与正确值或半空格的距离大于(10^{-3})，则SMO代码和分块代码都将判定该示例违反了KKT条件。在分类任务中，阈值(10^{-3})被选择为一个微不足道的错误。投影共轭梯度码有一个停止阈值，它描述了目标函数在每一步的最小相对改进[3:6]。如果投影的共轭梯度的改进值小于这个最小值，则共轭梯度码终止，并进行另一个分块步骤。Burges [3:7]建议使用常数(10^{-10})作为这个最小值。

在下面的实验中，在精度为(10^{-10})时停止投影的共轭梯度，通常会使KKT违例大于(10^{-3})，特别是对于非常大规模的问题。因此，基准分块算法使用以下启发式方法设置共轭梯度停止阈值。阈值从3x (10^{-10})开始。在每个分块步骤之后，计算拉格朗日乘子不受限制的所有示例的输出。计算这些输出是为了计算阈值(参见[3:8])。每个例子都表明了一个建议的阈值。如果最大的建议阈值比最小的建议阈值高2x (10^{-3})，那么在(10^{-3})内不可能满足KKT条件。因此，从下一个块开始，共轭梯度阈值减小了3倍。这种启发式方法将优化共轭梯度的速度:它只在最困难的问题上使用高精度。对于下面描述的大多数测试，阈值保持在3x (10^{-10})。使用的最小阈值为3.7x (10^{-12})，这发生在最大的网页分类问题分块的最后。

SMO算法在一个收入预测任务、一个网页分类任务和两个不同的人工数据集上进行了测试。所有表中列出的所有时间的单位都是CPU秒。

用于测试SMO速度的第一个数据集是UCI”adult”数据集，可以在 上找到。SVM从一个家庭的人口普查表格中得到14个属性。SVM的任务是预测该家庭的收入是否大于5万美元。在14个属性中，8个是类别属性，6个是连续属性。为了便于实验，将6个连续属性离散化为五分位数，总共产生123个二进制属性，其中14>个为真。在”adult”训练集中有32562个样本。在该问题上训练了两种不同的SVM:线性SVM和使用方差为10的高斯核的径向基函数SVM。选择这个方差是为了最小化验证集上的错误率。线性SVM的C极限值取0.05,RBF/SVM的C极限值取1。同样，选择这个限定值是为了最小化验证集上的错误。

在adult数据集上，SMO算法与线性SVM分块算法的时序性能对比如下表所示:

通过随机选取完整训练集的子集来改变训练集的大小。这些子集是嵌套的。分块时间列中的”N/A”项的矩阵太大，无法装入128兆字节，因此由于内存抖动而无法计时。通过SMO来确定非边界支持向量的数量和边界支持向量的数量:由于在KKT条件下对误差的容忍，分块结果会有少量的变化。

通过对训练时间与训练集大小的对数图拟合直线，可以推导出SMO和分块的经验尺度。SMO训练时间为~ (N^{1.9})，而块组训练时间为~ (N^{3.1})。因此，SMO将该问题的经验扩展提高了不止一阶。

使用高斯支持向量机进行SMO和分块的时序性能如下图所示:

SMO算法处理非线性支持向量机的速度要比线性支持向量机慢，因为时间主要取决于对支持向量机的评价。其中，SMO训练时间尺度为~ (N^{2.1})，而块组尺度为~ (N^{2.9})。同样，SMO的扩展速度大约比分块快一个订单。收益预测检验表明，对于在边界上有许多支持向量的真实稀疏问题，SMO比分块要快得多

SMO的第二个测试是文本分类:对网页是否属于某个类别进行分类。训练集由49749个网页组成，每个网页提取300个稀疏的二进制关键字属性。在这个问题上尝试了两种不同的支持向量机:线性支持向量机和非线性高斯支持向量机，其方差为10。线性支持向量机的C值取1，非线性支持向量机的C值取5。同样，选择这些参数是为了最大化验证集的性能。

SMO与线性支持向量机分块的时间如下表所示:

对于该数据集上的线性支持向量机，SMO训练时间尺度为~ (N^{1.6})，块集尺度为~ (N^{2.5})。这个实验是SMO在计算时间上优于分块的另一种情况。

SMO与非线性支持向量机分块的时间如下表所示:

对于该数据集上的非线性支持向量机，SMO训练时间尺度为~ (N^{1.7})，块集尺度为~ (N^{2.0})。在这种情况下，SMO的可伸缩性比分块要好:SMO比分块快2到6倍。非线性检验表明，当非定界支持向量数量较大且输入数据集稀疏时，SMO算法仍然比分块算法更快。

SMO还在人工生成的数据集上进行了测试，以探索SMO在极端场景下的性能。第一个人工数据集是完全线性可分的数据集。输入数据是随机的二元300维向量，输入”1″的比例为10%。在[-1,1]中随机生成一个300维的权重向量。如果权重与输入点的点积大于1，则该输入点被赋予一个正标签。如果点积小于-1，则赋一个负标签。如果点积的值在-1到1之间，则该点被丢弃。用线性SVM对该数据集进行拟合。

对于线性SVM来说，线性可分的数据集是最简单的问题。毫不奇怪，训练集大小的扩展对于SMO和分块都很好。运行时间如下表所示:

这里，SMO运行时间的尺度为~ (N)，略优于分块的尺度，分块的尺度为~ (N^{1.2})。因此，对于这个简单的稀疏问题，分块和SMO通常是可以比较的。两种算法都在C设置为100的情况下进行训练。用于分块的块大小设置为500。

在这个简单的数据集上，可以测量出SMO算法和分块算法由于稀疏点积编码而带来的加速。使用稀疏点积编码和不使用稀疏点积编码对相同的数据集进行了测试。对于非稀疏实验，每个输入点存储为一个300维的浮点向量。稀疏/非稀疏实验结果如下表所示:

对于SMO，使用稀疏数据结构可以使代码速度提高10倍以上，这表明SVM的评估时间完全支配SMO的计算时间。稀疏点积代码对分块计算的速度仅提高了1.1倍左右，这表明数值QP步骤的计算在分块计算中占主导地位。对于线性可分的情况，在有界处绝对没有拉格朗日乘子，这是SMO的最坏情况。因此，应该考虑到本实验中非稀疏SMO相对于非稀疏分块的性能较差

稀疏与非稀疏实验表明，SMO算法相对于分块算法的部分优势来自于对稀疏点积码的利用。幸运的是，许多现实世界的问题都有稀疏输入。除了3.1节和3.2节中描述的真实数据集之外，任何量化或模糊隶属编码问题都将是稀疏的。此外，光学字符识别[4:1]、手写字符识别[19]和自然图像[20] [6:1]的小波变换系数都倾向于自然地表达为稀疏数据。

第二个人工数据集与第一个简单数据集形成了鲜明的对比。第二组是由随机300维二进制输入点(10%”1″)和随机输出标签生成的。因此支持向量机是拟合纯噪声的。C值被设置为0.1，因为这个问题根本无法解决。将SMO和chunking应用于线性SVM的结果如下所示:

在第二个数据集上，SMO和分块的扩展性要高得多。这反映了问题的难度。SMO算法的计算时间为~ (N^{1.8})，而chunking算法的计算时间为~ (N^{3.2})。第二个数据集表明，当大多数支持向量都处于边界时，SMO的效果更好。因此，为了确定稀疏点积编码带来的速度提升，我们在没有稀疏点积编码的情况下测试了SMO和chunking:

在线性支持向量机的情况下，稀疏点积代码使SMO的速度提高了约6倍，而分块算法的速度只提高了最小。在这个实验中，即使对于非稀疏的数据，SMO也比分块更快。

第二个数据集也使用方差为10的高斯svm进行了测试。C值仍然被设置为0.1。高斯svm的结果如下表所示:

表10

当高斯SVM适合纯噪声时，SMO的计算时间约为~ (N^{2.2})，而chunking的计算时间约为~ (N^{3.4})。到目前为止，纯噪声情况下的扩展效果最差，但SMO比分块扩展效果好不止一个数量级。即使应用于非稀疏数据，SMO的总运行时间仍然优于分块。输入数据的稀疏性使得非线性情况下SMO的计算速度提高了约4倍，这表明对于非线性支持向量机而言，点积速度仍然是SMO计算速度的主要因素

SMO是一种改进的svm训练算法。与其他SVM训练算法一样，SMO将一个大的QP问题分解为一系列小的QP问题。与其他算法不同的是，SMO算法利用了尽可能小的QP问题，能够快速解析地求解，极大地提高了算法的可扩展性和计算时间。

SMO在现实问题和人工问题上都进行了测试。通过这些测试，可以得出以下结论:

• 当用户不容易访问二次编程包和/或不希望调整该QP包时，可以使用SMO。
• SMO在许多拉格朗日乘子有界的svm上表现非常好。
• SMO在线性SVM上表现良好，这是因为SMO的计算时间主要由SVM的计算时间决定，而线性SVM的计算可以表示为单个点积而不是线性核的和。
• SMO对于稀疏输入的svm表现良好，甚至对于非线性的svm，因为可以减少核计算时间，直接加快SMO的速度。由于分块的大部分时间都花在QP代码上，它不能利用SVM的线性和输入数据的稀疏性。
• SMO对于大型问题表现良好，因为对于迄今为止尝试过的所有测试问题，SMO随着训练集大小的扩展比分块要好。

对于不同的测试集，SMO的训练时间在 ~ (N) 到 ~ (N^{2.2})之间。组块分析的训练时间在 ~ (N^{1.2}) ，~ (N^{3.4}) 之间。SMO的扩展性可以比chunking好不止一个订单。对于真实世界的测试集，对于线性svm, SMO的速度可以提高1200倍，对于非线性svm可以提高15倍。

由于SMO易于使用，并且可以随着训练集的大小而更好地扩展，因此很有可能成为标准的SVM训练算法。在得出最终结论之前，还需要对其他QP技术和最佳Osuna启发式算法进行更多的基准实验。

感谢Lisa Heilbron协助编写案文。感谢Chris Burges使用他的投影共轭梯度代码运行了一个数据集。感谢Leonid Gurvits指出SMO与Bregman方法的相似性。

附录:两例最小化的推导

SMO的每一步都会优化两个拉格朗日乘子。不失一般性，这两个乘数是 (α_1) 和 (α_2) 。式(11)的目标函数 (Ψ) 可以写成:

[Ψ=\frac{1}{2}K_{11}α_1^2+\frac{1}{2}K_{22}α_2^2+sK_{12}α_1α_2+y_1α_1v_1+y_2α_2v_2-α_1-α_2+Ψ_{constant} \tag{24} ]

[\begin{align} K_{ij} =& K(\vec{x_i} \cdot \vec{x_j}),\ v_i =& \sum_{j=3}^Ny_jα_j^K_{ij}\ =&u_i+b^-y_1α_1^K_{1i}-y_2α_2^K_{2i}\tag{25} \end{align} ]

星号变量表示上一个迭代结束时的值。(Ψ_constant) 是不依赖于 (α_1) 或 (α_2) 的项。

每一步都要沿着线性等式约束(6)定义的直线找到最小值。该线性等式约束可以表示为

[α_1+sα_2=α_1^*=w \tag{26} ]

沿着线性等式约束的目标函数可以用 (α_2) 单独表示:

[\begin{align} Ψ=&\frac{1}{2}K_{11}(w-sα_2)^2+\frac{1}{2}K_{22}α_2^2+sK_{12}(w-sα_2)α_2 \ &+y_1(w-sα_2)v_1-w+sα_2+y_2α_2v_2-α_2+Ψ_{constant} \tag{27} \end{align} ]

目标函数的极值为

[\begin{align} \frac{dΨ}{dα_2}=&-sK_{11}(w-sα_2)+K_{22}α_2-K_{12}α_2+sK_{12}(w-sα_2) \ &-y_2v_1+s+y_2v_2-1=0 \tag{28} \end{align} ]

如果二阶导是正的，这是通常的情况，那么 (α_2) 的最小值可以表示为

[α_2(K_{11}+K_{22}-2K_{12})=s(K_{11}-K_{12})w+y_2(v_1-v_2)+1-s) \tag{29} ]

将 (w) 和 (v) 的方程展开

[α_2(K_{11}+K_{22}-2K_{12})=α_2^*(K_{11}+K_{22}-2K_{12})+y_2(u_1-u_2+y_2-y_1) \tag{30} ]

更多的代数运算得到方程(16)。

Original: https://www.cnblogs.com/FlourishingTree/p/16618374.html
Author: 好像没什么问题
Title: SMO论文中文翻译