查看“︁序列最小优化算法”︁的源代码

{{Infobox Algorithm
|image=
|class=训练支持向量机的[[最优化|优化算法]]
|data=
|time=O(''n''³)
|space=
}}
'''序列最小优化算法'''（{{lang en|Sequential minimal optimization}}, SMO）是一种用于解决[[支持向量机]]训练过程中所产生优化问题的算法。SMO由[[微软研究院]]的{{link-en|约翰·普莱特|John Platt}}于1998年发明<ref name="platt">{{Citation
 | last = Platt
 | first = John
 | year = 1998
 | title = Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.4376&rep=rep1&type=pdf
 | accessdate = 2010-12-03
 | archive-date = 2012-10-15
 | archive-url = https://web.archive.org/web/20121015044809/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.4376&rep=rep1&type=pdf
 | dead-url = no
 }}</ref>，目前被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。<ref>Chih-Chung Chang and Chih-Jen Lin (2001). ''[http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf LIBSVM: a Library for Support Vector Machines] {{Wayback|url=http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf |date=20110314220631 }}''.</ref><ref>Luca Zanni (2006). ''[http://jmlr.csail.mit.edu/papers/volume7/zanni06a/zanni06a.pdf Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems] {{Wayback|url=http://jmlr.csail.mit.edu/papers/volume7/zanni06a/zanni06a.pdf |date=20110718065219 }}''.</ref> 1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方[[二次规划]]工具。而SMO算法较好地避免了这一问题。<ref>{{Citation
 | last = Rifkin
 | first = Ryan
 | year = 2002
 | url = http://dspace.mit.edu/handle/1721.1/17549
 | title = Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning
 | journal = Ph.D. thesis
 | pages = 18
 | accessdate = 2010-12-04
 | archive-date = 2012-03-14
 | archive-url = https://web.archive.org/web/20120314015029/http://dspace.mit.edu/handle/1721.1/17549
 | dead-url = no
 }}</ref>

== 问题定义 ==
{{main|支持向量机#原型}}
SMO算法主要用于解决支持向量机目标函数的最优化问题。考虑数据集<math>(\mathbf{x_1}, y_1), \ldots , (\mathbf{x_n}, y_n)</math>的二分类问题，其中<math>\mathbf{x_i}</math>是输入向量，<math>y_i \in \{-1, 1\}</math>是向量的类别标签，只允许取两个值。一个软间隔[[支持向量机]]的目标函数最优化等价于求解以下二次规划问题的最大值：

:<math>W=\max_{\alpha} \sum_{i=1}^n \alpha_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(x_i, x_j) \alpha_i \alpha_j,</math>
:满足：
::<math>0 \leq \alpha_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,</math>
::<math>\sum_{i=1}^n y_i \alpha_i = 0,</math>

其中，<math>C</math>是SVM的参数，而<math>K(\mathbf{x_i}, \mathbf{x_j})</math>是[[核函数]]。这两个参数都需要使用者制定。

== 算法 ==
SMO是一种解决此类支持向量机优化问题的迭代算法。由于目标函数为[[凸函数]]，一般的优化算法都通过梯度方法一次优化一个变量求解二次规划问题的最大值，但是，对于以上问题，由于限制条件<math>\sum_{i=1}^n y_i \alpha_i = 0</math>存在，当某个<math>\alpha_i \,</math>从<math>\alpha_i^{old}</math>更新到<math>\alpha_i^{new}</math>时，上述限制条件即被打破。为了克服以上的困难，SMO采用一次更新两个变量的方法。

=== 数学推导 ===
假设算法在某次更新时更新的变量为<math>\alpha_1 \,</math>和<math>\alpha_2\,</math>，则其余变量都可以视为常量。为了描述方便，规定

::<math>K_{ij}=K(\mathbf{x_i}, \mathbf{x_j}), f(\mathbf{x_i})=\sum_{j=1}^n y_j \alpha_j K_{ij} + b,</math>
::<math>v_i=f(\mathbf{x_i})-\sum_{j=1}^2 y_j \alpha_j K_{ij} - b</math>

因而，二次规划目标值可以写成

::<math>\begin{array}{lcl}
W(\alpha_1,\alpha_2) &=&\sum_{i=1}^n \alpha_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(x_i, x_j) \alpha_i \alpha_j \\
            &=&\alpha_1+\alpha_2-\frac12 K_{11} \alpha_1^2 - \frac12 K_{22} \alpha_2^2 - y_1 y_2 K_{12} \alpha_1 \alpha_2 \\
            & & - y_1 \alpha_1 v_1 - y_2 \alpha_2 v_2 + \text{constant} \,
\end{array}
</math>

由于限制条件<math>\sum_{i=1}^n y_i \alpha_i = 0</math>存在，将<math>\alpha_3, \ldots, \alpha_n, y_3, \ldots, y_n</math>看作常数，则有<math>\alpha_1 y_1 + \alpha_2 y_2 = C \,</math>成立（<math>C \,</math>为常数）。由于<math>y_i \in \{-1, 1\} \,</math>，从而<math>\alpha_1 = \gamma - s \alpha_2 \,</math>（<math>\gamma \,</math>为变量<math>y_1C</math>，<math>s = y_1 y_2 \,</math>）。取<math>\alpha_2 \,</math>为优化变量，则上式又可写成

::<math>\begin{array}{lcl}
W(\alpha_2) &=&\gamma - s \alpha_2 + \alpha_2 - \frac12 K_{11} (\gamma - s \alpha_2)^2 - \frac12 K_{22} \alpha_2^2 \\
 & &- s K_{12} (\gamma - s \alpha_2)\alpha_2 - y_1(\gamma - s \alpha_2)v_1 - y_2 \alpha_2 v_2 + \text{constant} \end{array}
</math>

对<math>\alpha_2 \,</math>求[[偏导数|偏导]]以求得最大值，有

::<math>
\begin{array}{lcl}
\frac{\partial W(\alpha_2)}{\partial \alpha_2} &=& -s + 1 + s K_{11} \gamma - K_{11} \alpha_2 - K_{22}\alpha_2 + 2K_{12}\alpha_2 -s K_{12} \gamma\\& & + y_2v_1 - y_2 v_2 = 0
\end{array}
</math>

因此，可以得到

::<math>\alpha_2^{new} = \frac{y_2(y_2 - y_1 + y_1 \gamma (K_{11}-K_{12})+v_1-v_2)}{K_{11}+K_{22}-2K_{12}}</math>

规定误差项<math>E_i = f(\mathbf{x}_i) - y_i</math>，取<math>\gamma = \alpha_1^{old} +s \alpha_2^{old}</math>，并规定<math>K = K_{11}+K_{22}-2K_{12} \,</math>，上述结果可以化简为

::<math>\alpha_2^{new} = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K}</math>

再考虑限制条件<math>0 \leqslant \alpha_i \leqslant C</math>，<math>(\alpha_1, \alpha_2) \,</math>的取值只能为直线<math>\alpha_1 y_1 + \alpha_2 y_2 = \gamma \,</math>落在<math>[0, C] \times [0, C]</math>矩形中的部分。因此，具体的SMO算法需要检查<math>\alpha_2^{new}</math>的值以确认这个值落在约束区间之内。<ref name="platt" /><ref name="fast">{{Citation
 | last = Tsang
 | first = I. W.
 | last2 = Kwok
 | first2 = J. T.
 | last3 = Cheung
 | first3 = P. M.
 | year = 2005
 | title = Core Vector Machines: Fast SVM Training on Very Large Data Sets
 | periodical = Journal of Machine Learning Research
 | issue = 6
 | pages = 363–392
 | url = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.9158&rep=rep1&type=pdf
 | accessdate = 2010-12-06
 | archive-date = 2016-03-05
 | archive-url = https://web.archive.org/web/20160305012621/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.9158&rep=rep1&type=pdf
 | dead-url = no
 }}</ref>

=== 算法框架 ===
SMO算法是一个迭代优化算法。在每一个迭代步骤中，算法首先选取两个待更新的向量，此后分别计算它们的误差项，并根据上述结果计算出<math>\alpha_2^{new}</math>和<math>\alpha_1^{new}</math>。最后再根据SVM的定义计算出偏移量<math>\mathbf{b}</math>。对于误差项而言，可以根据<math>\alpha_1^{new}</math>、<math>\alpha_2^{new}</math>和<math>b</math>的增量进行调整，而无需每次重新计算。具体的算法如下：

 1 随机数初始化向量权重<math>\alpha_i \,</math>，并计算偏移<math>b</math>
 2 初始化误差项<math>E_i \,</math>
 3 选取两个向量作为需要调整的点
 4 令<math>\alpha_2^{new} = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K}</math>
 5 如果<math>\alpha_2^{new} > V</math>
 6     令<math>\alpha_2^{new} = V</math>
 7 如果<math>\alpha_2^{new} < U</math>
 8     令<math>\alpha_2^{new} = U</math>
 9 令<math>\alpha_1^{new} = \alpha_1^{old}+y_1 y_2 (\alpha_2^{old} - \alpha_2^{new})</math>
 10 利用更新的<math>\alpha_1^{new}</math>和<math>\alpha_2^{new}</math>修改<math>E_i \,</math>和<math>b</math>的值
 11 如果达到终止条件，则停止算法，否则转3

其中，<math>U</math>和<math>V</math>为<math>\alpha_2^{new}</math>的下界和上界。特别地，有

::<math>U=
\begin{cases}
\max{\left\{0, \alpha_2^{old} - \alpha_1^{old}\right\}} & y_1y_2 = -1 \\
\max{\left\{0, \alpha_1^{old} + \alpha_2^{old} - C \right\}} & y_1y_2 = 1
\end{cases},
V=
\begin{cases}
\min{\left\{C, C + \alpha_2^{old} - \alpha_1^{old}\right\}} & y_1y_2 = -1 \\
\min{\left\{C, \alpha_2^{old} + \alpha_1^{old}\right\}} & y_1y_2 = 1
\end{cases}
</math>

这一约束的意义在于使得<math>\alpha_1^{new}</math>和<math>\alpha_2^{new}</math>均位于矩形域<math>[0, C] \times [0, C]</math>中。<ref name="fast" />

=== 优化向量选择方法 ===
可以采用启发式的方法选择每次迭代中需要优化的向量。第一个向量可以选取不满足[[支持向量机]]KKT条件的向量，亦即不满足

::<math>y_if(\mathbf{x}_i)\begin{cases}
>1 & \alpha_i = 0 \\
=1 & 0 < \alpha_1 < C \\
<1 & \alpha_i = C
\end{cases}
</math>

的向量。而第二个向量可以选择使得<math>|E_1-E_2| \,</math>最大的向量。<ref name="fast" />

=== 终止条件 ===
SMO算法的终止条件可以为KKT条件对所有向量均满足，或者目标函数<math>W(\alpha) \,</math>增长率小于某个阈值，即

::<math>\frac{W(\alpha^{t+1})-W(\alpha^t)}{W(\alpha^t)}<T</math><ref name="fast" />

== 参考资料 ==
{{reflist|2}}

== 参见 ==
* [[支持向量机]]
* [[核方法]]
* {{le|费希尔核|Fisher kernel}}
* {{le|多项式核函数|Polynomial kernel}}
* [[预测分析]]

[[Category:最优化算法]]
[[Category:机器学习]]
[[Category:支持向量機]]