序列最小优化算法

序列最小优化算法（英语：Sequential minimal optimization, SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的约翰·普莱特（英语：John Platt）于1998年发明^[1]，目前被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。^[2][3] 1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方二次规划工具。而SMO算法较好地避免了这一问题。^[4]

序列最小优化算法
概况
类别	训练支持向量机的优化算法
复杂度
最坏时间复杂度	O(n³)
相关变量的定义

问题定义

主条目：支持向量机 § 原型

SMO算法主要用于解决支持向量机目标函数的最优化问题。考虑数据集${\displaystyle (\mathbf {x_{1}} ,y_{1}),\ldots ,(\mathbf {x_{n}} ,y_{n})}$的二分类问题，其中${\displaystyle \mathbf {x_{i}} }$是输入向量，${\displaystyle y_{i}\in \{-1,1\}}$是向量的类别标签，只允许取两个值。一个软间隔支持向量机的目标函数最优化等价于求解以下二次规划问题的最大值：

${\displaystyle W=\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},}$

满足：

${\displaystyle 0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,}$

${\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0,}$

其中，${\displaystyle C}$是SVM的参数，而${\displaystyle K(\mathbf {x_{i}} ,\mathbf {x_{j}} )}$是核函数。这两个参数都需要使用者制定。

算法

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

数学推导

假设算法在某次更新时更新的变量为${\displaystyle \alpha _{1}\,}$和${\displaystyle \alpha _{2}\,}$，则其余变量都可以视为常量。为了描述方便，规定

${\displaystyle K_{ij}=K(\mathbf {x_{i}} ,\mathbf {x_{j}} ),f(\mathbf {x_{i}} )=\sum _{j=1}^{n}y_{j}\alpha _{j}K_{ij}+b,}$

${\displaystyle v_{i}=f(\mathbf {x_{i}} )-\sum _{j=1}^{2}y_{j}\alpha _{j}K_{ij}-b}$

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

${\displaystyle {\begin{array}{lcl}W(\alpha _{1},\alpha _{2})&=&\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\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}-{\frac {1}{2}}K_{11}\alpha _{1}^{2}-{\frac {1}{2}}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}}}$

由于限制条件${\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0}$存在，将${\displaystyle \alpha _{3},\ldots ,\alpha _{n},y_{3},\ldots ,y_{n}}$看作常数，则有${\displaystyle \alpha _{1}y_{1}+\alpha _{2}y_{2}=C\,}$成立（${\displaystyle C\,}$为常数）。由于${\displaystyle y_{i}\in \{-1,1\}\,}$，从而${\displaystyle \alpha _{1}=\gamma -s\alpha _{2}\,}$（${\displaystyle \gamma \,}$为变量${\displaystyle y_{1}C}$，${\displaystyle s=y_{1}y_{2}\,}$）。取${\displaystyle \alpha _{2}\,}$为优化变量，则上式又可写成

${\displaystyle {\begin{array}{lcl}W(\alpha _{2})&=&\gamma -s\alpha _{2}+\alpha _{2}-{\frac {1}{2}}K_{11}(\gamma -s\alpha _{2})^{2}-{\frac {1}{2}}K_{22}\alpha _{2}^{2}\\&&-sK_{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}}}$

对${\displaystyle \alpha _{2}\,}$求偏导以求得最大值，有

${\displaystyle {\begin{array}{lcl}{\frac {\partial W(\alpha _{2})}{\partial \alpha _{2}}}&=&-s+1+sK_{11}\gamma -K_{11}\alpha _{2}-K_{22}\alpha _{2}+2K_{12}\alpha _{2}-sK_{12}\gamma \\&&+y_{2}v_{1}-y_{2}v_{2}=0\end{array}}}$

因此，可以得到

${\displaystyle \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}}}}$

规定误差项${\displaystyle E_{i}=f(\mathbf {x} _{i})-y_{i}}$，取${\displaystyle \gamma =\alpha _{1}^{old}+s\alpha _{2}^{old}}$，并规定${\displaystyle K=K_{11}+K_{22}-2K_{12}\,}$，上述结果可以化简为

${\displaystyle \alpha _{2}^{new}=\alpha _{2}^{old}+{\frac {y_{2}(E_{1}-E_{2})}{K}}}$

再考虑限制条件${\displaystyle 0\leqslant \alpha _{i}\leqslant C}$，${\displaystyle (\alpha _{1},\alpha _{2})\,}$的取值只能为直线${\displaystyle \alpha _{1}y_{1}+\alpha _{2}y_{2}=\gamma \,}$落在${\displaystyle [0,C]\times [0,C]}$矩形中的部分。因此，具体的SMO算法需要检查${\displaystyle \alpha _{2}^{new}}$的值以确认这个值落在约束区间之内。^[1][5]

算法框架

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

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

其中，${\displaystyle U}$和${\displaystyle V}$为${\displaystyle \alpha _{2}^{new}}$的下界和上界。特别地，有

${\displaystyle U={\begin{cases}\max {\left\{0,\alpha _{2}^{old}-\alpha _{1}^{old}\right\}}&y_{1}y_{2}=-1\\\max {\left\{0,\alpha _{1}^{old}+\alpha _{2}^{old}-C\right\}}&y_{1}y_{2}=1\end{cases}},V={\begin{cases}\min {\left\{C,C+\alpha _{2}^{old}-\alpha _{1}^{old}\right\}}&y_{1}y_{2}=-1\\\min {\left\{C,\alpha _{2}^{old}+\alpha _{1}^{old}\right\}}&y_{1}y_{2}=1\end{cases}}}$

这一约束的意义在于使得${\displaystyle \alpha _{1}^{new}}$和${\displaystyle \alpha _{2}^{new}}$均位于矩形域${\displaystyle [0,C]\times [0,C]}$中。^[5]

优化向量选择方法

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

${\displaystyle y_{i}f(\mathbf {x} _{i}){\begin{cases}>1&\alpha _{i}=0\\=1&0<\alpha _{1}<C\\<1&\alpha _{i}=C\end{cases}}}$

的向量。而第二个向量可以选择使得${\displaystyle |E_{1}-E_{2}|\,}$最大的向量。^[5]

终止条件

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

${\displaystyle {\frac {W(\alpha ^{t+1})-W(\alpha ^{t})}{W(\alpha ^{t})}}<T}$^[5]

参考资料

1. Platt, John, Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines, 1998 [2010-12-03], （原始内容存档于2012-10-15）
2. Chih-Chung Chang and Chih-Jen Lin (2001). LIBSVM: a Library for Support Vector Machines （页面存档备份，存于互联网档案馆）.
3. Luca Zanni (2006). Parallel Software for Training Large Scale Support Vector Machines on Multiprocessor Systems （页面存档备份，存于互联网档案馆）.
4. Rifkin, Ryan, Everything Old is New Again: a Fresh Look at Historical Approaches in Machine Learning, Ph.D. thesis, 2002: 18 [2010-12-04], （原始内容存档于2012-03-14）
5. Tsang, I. W.; Kwok, J. T.; Cheung, P. M., Core Vector Machines: Fast SVM Training on Very Large Data Sets, Journal of Machine Learning Research (6), 2005, (6): 363–392 [2010-12-06], （原始内容存档于2016-03-05）

参见

• 支持向量机
• 核机器（英语：Kernel machines）
• 费希尔核（英语：Fisher kernel）
• 多项式核函数（英语：Polynomial kernel）
• 预测分析