序列最小优化算法

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

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

问题定义

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

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},

满足：

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

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

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

算法

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

数学推导

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

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

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

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

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

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

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

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

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

因此，可以得到

\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}}}

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

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

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

算法框架

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

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