10.9 SMO算法求解SVM#
在10.7节内容中，我们分别就SVM中硬间隔与软间隔目标函数的求解过程进行了介绍，但是在实际应用过程中，从效率的角度来讲那样的做法显然是不可取的，尤其是在大规模数据样本和稀疏数据中[6]。在接下来的这节内容中，我们将介绍一种新的求解算法，即序列最小化优化算法来解决这一问题。
序列最小优化算法（Sequential Minimal Optimization,SMO）于1998年由John Platt所提出，并且SMO算法初次提出的目的就是为了解决SVM的优化问题[7]。SMO算法是一种启发式的算法，它在求解过程中通过以分析的方式来定位最优解可能存在的位置，从而避免了传统方法在求解中所遭遇的大量数值计算问题，并且最终以迭代的方式来求得最优解。在正式介绍SMO算法之前，我们将先介绍SMO算法的基本原理——坐标上升算法（Coordinate Ascent）。
10.9.1 坐标上升算法#
在2.5节内容中，我们详细地介绍了什么是梯度下降算法及梯度下降算法的作用。对于一个待优化的目标函数来讲，在初始化一个起始位置后，便可以以该点为基础每次沿着该点梯度的反方向向前移动一小步，以此来迭代求解，以便得到目标函数的全局（局部）最优解，而所谓的坐标上升（下降）算法可以看作初始位置只沿着其中的一个（或几个）方向移动来求解得到目标函数的全局（局部）最优解[8]，如图10-15所示。
在图10-15中，曲线为目标函数$J({{w}_{1}},{{w}_{2}})=-0.5{{({{w}_{1}}-1)}^{2}}-{{(2{{w}_{2}}+1)}^{2}}-0.5{{({{w}_{1}}-{{w}_{2}})}^{2}}$的等高线，黑色箭头曲线为梯度上升算法最大化目标函数$J(w_1,w_2)$的求解过程，而黑色箭头折线为坐标上升算法最大化目标函数的求解过程。
具体地，对于待求解目标函数$J({{w}_{1}},{{w}_{2}},...,{{w}_{n}})$来讲可以通过如下步骤进行求解。
(1) 随机将向量$w=({{w}_{1}},{{w}_{2}},...,{{w}_{n}})$初始化为初始参数值。
(2) 在${{w}_{1}},{{w}_{2}},...,{{w}_{n}}$中依次将${{w}_{i}},i=1,2,...,n$选择为变量并将其他参数固定为常量，然后求目标函数关于$w_i$的导数并令其为0求得$w_i$。
(3) 重复执行步骤(2)直到目标函数收敛或者误差小于某一阈值结束。
例如在上面这个示例中$w_1$和$w_2$的求解表达式分别为
$$ \begin{aligned} & w_{1}^{\text{new}}=-2w_{1}^{\text{old}}+w_2^{\text{old}}+1 \\[1ex] & w_{2}^{\text{new}}=-9w_{2}^{\text{old}}+w_1^{\text{new}}-4 \end{aligned}\tag{10-131} $$那么在初始化一组$w_{1}^{\text{old}}$和$w_{2}^{\text{old}}$后，便可以通过式(10-131)来迭代以便求解得到$w_1$和$w_2$的解。
同时，上述步骤(2)对于$w_i$顺序的选择这里采用了最为简单的按顺序依次进行，一种更优的做法便是每次选择余下常量中能够使目标函数产生最大增量的参数作为优化对象。
10.9.2 SMO算法原理#
根据10.7.3节中式(10-106)可知，SVM软间隔最终需要求解的目标函数为
$$ \begin{aligned}& \underset{\alpha }{\mathop{\max }}\sum_{i=1}^m{{\alpha }_{i}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}}{{({{x}^{(i)}})}^{T}}{{x}^{(j)}} \\[1ex]\text{s}.\text{t}.\ \ &0\le {{\alpha }_{i}}\le C,\ i=1,2,...,m\\[2ex]&\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \\\end{aligned}\tag{10-132} $$假设随机初始化后的$\alpha_i$均满足式(10-132)中的约束条件，现在通过坐标上升算法来求解$\alpha$。如果此时将${{\alpha }_{2}},...,{{\alpha }_{m}}$固定为常量，将$\alpha_1$ 固定为变量来求解$\alpha_1$ ，则能求解得到$\alpha_1$吗？答案是不能[2]。因为根据式(10-132)中第2个约束条件有
$$ \alpha_1y^{(1)}=-\sum_{i=2}^m\alpha_iy^{(i)}\tag{10-133} $$进一步，在式(10-133)两边同时乘上${{y}^{(1)}}$有
$$ \alpha_1=-y^{(1)}\sum_{i=2}^m\alpha_iy^{(i)}\tag{10-134} $$根据式(10-134)可知，${{\alpha }_{1}}$完全取决于${{\alpha }_{2}},...,{{\alpha }_{m}}$，如果${{\alpha }_{2}},...,{{\alpha }_{m}}$固定，也就意味着${{\alpha }_{1}}$也是固定的，因此，在这样的情况下每次至少需要同时选择两个参数为变量，同时再固定其他参数为常量，才能够最终求得所有参数。
此时，假设固定${{\alpha }_{3}},...,{{\alpha }_{m}}$不变来求解参数${{\alpha }_{1}}$和${{\alpha }_{2}}$。根据式(10-132)中的约束条件有
$$ {{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=-\sum\limits_{i=3}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}\tag{10-135} $$由于此时式(10-135)右边是固定的，因此可以用一个常数$\zeta$来表示
$$ {{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=\zeta \tag{10-136} $$进一步，可以将${{\alpha }_{1}}$表示为
$$ {{\alpha }_{1}}=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}\tag{10-137} $$此时，式(10-132)中的目标函数便可以改写为
$$ W({{\alpha }_{1}},{{\alpha }_{2}},...,{{\alpha }_{m}})=W((\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}},{{\alpha }_{2}},...,{{\alpha }_{m}})\tag{10-138} $$在式(10-138)中，由于此时将${{\alpha }_{3}},...,{{\alpha }_{m}}$固定为常数，因此其可以简单地表示为一个关于$\alpha_2$的一元二次 多项式，这一点也可以从式(10-84)中看出。
$$ a\alpha _{2}^{2}+b{{\alpha }_{2}}+c\tag{10-139} $$接着，对于多项式(10-139)来讲通过令${{\alpha }_{2}}$的导数为0便可以轻易求得${{\alpha }_{2}}$的取值，然后将${{\alpha }_{2}}$代入式(10-136)即可得到${{\alpha }_{1}}$的值。进一步，按照相同的过程便可求得${{\alpha }_{3}},...,{{\alpha }_{m}}$的值，最后重复执行上述整个过程便可以迭代求解得到$\alpha_1,\alpha_2,...,\alpha_m$的值。
以上就是SMO算法求解的主要思想。虽然看起来不太复杂，但是里面仍旧有很多值得深究的内容，下面开始正式介绍SMO算法的原理。
10.9.3 SMO算法求解SVM原理#
为了更加广义地表示SVM软间隔中的优化问题，可以通过如下形式来表示待求解的优化问题
$$ \begin{aligned}& \underset{\alpha }{\mathop{\max }}\sum_{i=1}^m{{\alpha }_{i}}-\frac{1}{2}\sum\limits_{i,j=1}^{m}{{{y}^{(i)}}{{y}^{(j)}}{{\alpha }_{i}}{{\alpha }_{j}}}K({{x}^{(i)}},{{x}^{(j)}}) \\[1ex]\text{s}.\text{t}.\ \ &0\le {{\alpha }_{i}}\le C,\ i=1,2,...,m \\[2ex]& \sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=0 \\\end{aligned}\tag{10-140} $$其中$K(\cdot)$为任意核函数。
进一步，不失一般性，这里假设首先将参数${{\alpha }_{1}}$和${{\alpha }_{2}}$选择为变量，将其他参数固定为常量。于是式(10-140)便可以改写成如下形式[6]
$$ \begin{aligned}& \underset{{\alpha_1},{\alpha_2}}{\mathop{\max }}\,{{\alpha}_{1}}+{{\alpha}_{2}}-\frac{1}{2}\alpha _{1}^{2}{{K}_{11}}-{{\alpha }_{1}}{{\alpha }_{2}}{{y}^{(1)}}{{y}^{(2)}}{{K}_{12}}-{{\alpha }_{1}}{{y}^{(1)}}\sum_{i=3}^m{{\alpha }_{i}}{{y}^{(i)}}{{K}_{1i}} \\[1ex]&\;\;\;\;\;\;\;\; -\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}\sum_{i=3}^m{{\alpha }_{i}}{{y}^{(i)}}{{K}_{2i}}+{{\Psi }_{\text{constant}}} \\[1ex]& \text{s}.\text{t}.\ \ 0\le {{\alpha }_{i}}\le C,\ i=1,2 \\[1ex]& {{\alpha }_{1}}{{y}^{(1)}}+{{\alpha }_{2}}{{y}^{(2)}}=-\sum\limits_{i=3}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}=\zeta\end{aligned}\tag{10-141} $$其中${{K}_{ij}}=K({{x}^{(i)}},{{x}^{(j)}})$，${{\Psi }_{\text{constant}}}$表示与$\alpha_1$和$\alpha_2$无关的常量。
同时，记
$$ \begin{aligned}& g(x)=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}K(x,{{x}^{(i)}})+b \\& {{v}_{i}}=\sum\limits_{j=3}^{m}{{{\alpha }_{j}}}{{y}^{(j)}}K({{x}^{(i)}},{{x}^{(j)}})=g({{x}^{(i)}})-\sum_{j=1}^2{{\alpha }_{j}}{{y}^{(j)}}K({{x}^{(i)}},{{x}^{(j)}})-b,\ \ i=1,2 \\\end{aligned}\tag{10-142} $$则目标函数(10-141)可以改写为
$$ \begin{aligned} & W({{\alpha }_{1}},{{\alpha }_{2}})={{\alpha }_{1}}+{{\alpha }_{2}}-\frac{1}{2}\alpha _{1}^{2}{{K}_{11}}-{{\alpha }_{1}}{{\alpha }_{2}}{{y}^{(1)}}{{y}^{(2)}}{{K}_{12}}-{{\alpha }_{1}}{{y}^{(1)}}{{v}_{1}} \\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; -\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}{{v}_{2}}+{{\Psi }_{\text{constant}}} \\[1ex] \end{aligned}\tag{10-143} $$将${{\alpha }_{1}}=(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}$代入式(10-143)便可以得到一个只含有变量$\alpha_2$的目标函数
$$ \begin{aligned} W({{\alpha }_{2}}) & =(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{y}^{(1)}}+{{\alpha }_{2}}-\frac{1}{2}{{(\zeta -{{\alpha }_{2}}{{y}^{(2)}})}^{2}}{{K}_{11}} \\[1ex] & -(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{\alpha }_{2}}{{y}^{(2)}}{{K}_{12}}-(\zeta -{{\alpha }_{2}}{{y}^{(2)}}){{v}_{1}}-\frac{1}{2}\alpha _{2}^{2}{{K}_{22}}-{{\alpha }_{2}}{{y}^{(2)}}{{v}_{2}} \end{aligned}\tag{10-144} $$进一步，式(10-144)关于$\alpha_2$的导数为
$$ \begin{aligned} \frac{\partial W}{\partial {{\alpha }_{2}}} & =-{{y}^{(1)}}{{y}^{(2)}}+1+\zeta {{y}^{(2)}}{{K}_{11}}-{{\alpha }_{2}}{{K}_{11}}+2{{\alpha }_{2}}{{K}_{12}} \\[1ex] & -\zeta {{y}^{(2)}}{{K}_{12}}+{{v}_{1}}{{y}^{(2)}}-{{\alpha }_{2}}{{K}_{22}}-{{y}^{(2)}}{{v}_{2}} \end{aligned}\tag{10-145} $$令式(10-145)为0，可以得到
$$ {{\alpha }_{2}}=\frac{{{y}^{(2)}}\left( {{y}^{(2)}}-{{y}^{(1)}}+\zeta {{\text{K}}_{11}}-\zeta {{\text{K}}_{12}}+{{v}_{1}}-{{v}_{2}} \right)}{{{K}_{11}}-2{{K}_{12}}+{{K}_{22}}}\tag{10-146} $$此时，记
$$ \begin{aligned} & \eta ={{K}_{11}}-2{{K}_{12}}+{{K}_{22}} \\[1ex] & {{E}_{i}}=g({{x}^{(i)}})-{{y}^{(i)}}=\left( \sum\limits_{j=1}^{m}{{{\alpha }_{j}}}{{y}^{(j)}}K({{x}^{(i)}},{{x}^{(j)}})+b \right)-{{y}^{(i)}},\ \ i=1,2 \\ \end{aligned}\tag{10-147} $$那么在初始化一组$\alpha _{1}^{\text{old}}$和$\alpha _{2}^{\text{old}}$后，将式(10-147)和$\zeta =\alpha _{1}^{\text{old}}{{y}^{(1)}}+\alpha _{2}^{\text{old}}{{y}^{(2)}}$代入式(10-146)有
$$ \begin{aligned} \alpha _{2}^{\text{new}}=&\frac{{{y}^{(2)}}}{\eta }[{{y}^{(2)}}-{{y}^{(1)}}+\left( \alpha _{1}^{\text{old}}{{y}^{(1)}}+\alpha _{2}^{\text{old}}{{y}^{(2)}} \right){{K}_{11}}-\\[1ex] &( \alpha _{1}^{\text{old}}{{y}^{(1)}}+\alpha _{2}^{\text{old}}{{y}^{(2)}} ){{K}_{12}}+g({{x}_{1}})-\sum\limits_{j=1}^{2}{\alpha _{j}^{\text{old}}}{{y}^{(j)}}{{K}_{1j}}-\\[1ex] &b-g({{x}_{2}})+\sum\limits_{j=1}^{2}{\alpha _{j}^{\text{old}}}{{y}^{(j)}}{{K}_{2j}}+b ] \end{aligned}\tag{10-148} $$将式(10-148)进一步化简后可得
$$ \alpha_2^{\text{new}}=\alpha_2^{\text{old}}+\frac{y^{(2)}(E_1-E_2)}{\eta}\tag{10-149} $$至此，便初步求得了$\alpha_2$的求解表达式。为什么是初步呢？因为此时求得的$\alpha_2$还没有经过约束条件裁剪。
由式(10-141)中的第1个约束条件可知，$\alpha_1$和$\alpha_2$的解只能位于$[0,C]\times[0,C]$这个正方形盒子中。进一步，由式(10-141)中的第2个约束条件可知，$\alpha_1$和$\alpha_2$还必须位于平行于盒子对角线的线段上，如图10-16所示。
如图10-16所示，$\alpha_1$和$\alpha_2$的解只能位于盒子内部的线段上，因此还需要使$\alpha _{2}^{\text{new}}$满足
$$ L\le \alpha _{2}^{\text{new}}\le H\tag{10-150} $$其中，$L$与$H$是图10-16中线段的两个端点，即下界和上界。
从图10-16可以看出，如果${{y}^{(1)}}\ne {{y}^{(2)}}$时两种情况：
① 当 $y^{(1)}=1,y^{(2)}=-1$时有 $\alpha_1-\alpha_2=k$，此时线段与 $\alpha_2=0$ 相交处为 $L=0$ ，与 $\alpha_1=C$ 相交处为 $H=C+\alpha _{2}^{\text{old}}-\alpha _{1}^{\text{old}}$ ；
② 当 $y^{(1)}= -1,y^{(2)}=1$时有 $\alpha_2-\alpha_1=k$，此时线段与 $\alpha_1=0$ 相交处为 $L=\alpha _{2}^{\text{old}}-\alpha _{1}^{\text{old}}$ , 与 $\alpha_2=C$ 相交处为 $H=C$ 。
因为 $L$ 和 $H$ 分别为线段的下界和上界，所以有