SVM系列终于要告一段落了，前面讲解了SVM的硬软边界，以及对偶问题。
现在讲解如何高效的对对偶问题进行求解。
包括
- 坐标下降法
- SMO
- Pegasos (以后更新)
坐标下降法
我们常用“梯度下降法” 来求解无约束优化问题，今天介绍另一种称为坐标下降法。
坐标下降法也是一种优化方法，它在每步迭代中固定一个坐标方向，通过不断循环使用不同的坐标方向来达到目标函数的局部极小值。
假设求解函数\(f({\bf x})\)的极小值，其中\({\bf x} = (x_1,x_2,\cdots,x_d)\)是一个d维向量，坐标下降法的步骤如下：
- 选择一个分量如 \(x_0\)，固定除\(x_0\)以外的其他维度, 以 \(x_0\)为自变量，求使得 f 取得最小值的 \(x_0\)
- 循环执行步骤1，直到f的值不再变化或变化很小
与梯度下降法类似，通过迭代执行，最后会收敛到期望的局部极小值点或驻点(stationary point)。
例如，\(f(x ,y) = 5x^2 - 6xy+5y^2\)，这里我们利用坐标下降求解。
- 假设首先首先位于固定x， 初始点于(-1,-1)，可以求解一元二次方程：求导得\(\frac{\partial f}{y} = -6x + 10y = 0 \Rightarrow y=\frac{6}{10}x\)，因此新的坐标为(-1, -0.6)
- 固定y，求导得\(\frac{\partial f}{y} = 10x - 6y = 0 \Rightarrow x=\frac{6}{10}y\)，因此新坐标为(-0.36, -0.6)
下图为坐标下降的过程：
可以看出，因为每次只优化一个变量，每次迭代的方向都是沿着坐标轴方向。
坐标下降法不需要计算梯度，每步迭代中仅需求解一维搜索问题，对于某些复杂问题计算较为简便。但若目标函数不光滑，则坐标下降法可能陷入非驻点(non-stationary point)。
与梯度下降法对比
- 一次更新:\(w^{t+1} \leftarrow w^t + \Delta w^t\)
- 梯度下降：沿梯度最大的的方向同时更新\(w_1\)和\(w_2\)
- 坐标轴下降：选择一个变量，沿坐标轴方向更新\(w_1\)或\(w_2\)
- 坐标轴下降将一个多变量优化问题转化为一系列单变量优化问题
SMO
回顾一下软间隔+核函数SVM问题： \[ \begin{align*} \max_{ {\boldsymbol \alpha} }\hspace{2ex}& \sum_{i=1}^n\alpha_i - \frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK( \bf{x_i, x_j}) \tag{2-1}\\ {\rm s.t.} \hspace{2ex} & \sum_{i=1}^n\alpha_iy_i =0\\ \hspace{2ex} & 0 \le \alpha_i \le C, \hspace{2ex} i=1,2,\cdots m \end{align*} \] 而对样本x的预测为： \(f(x) = \sum_{i=1}^{n}\alpha_{i}y_{i} K(x_{i}, x) + b\)
前面提到过，对偶问题有n个变量，因为每个样本都有一个\(\alpha_i\)。当数据量很大的时候，求解效率不高。
这也是SMO算法提出的动机。SMO全名为Sequential minimal optimization，翻译为中文就是序列最小化。SMO算法由Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。
SMO的原理是: 如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件[Osuna et al 1997].。因此，SMO中，每次选取的为一对变量\((\alpha_i,\alpha_j)\), 而其它变量固定。这样，参数初始化后，SMO不断执行如下两个步骤直到收敛：
- 选取一对需要更新的变量\(\alpha_i\)和\(\alpha_j\)
- 固定\(\alpha_i\)和\(\alpha_j\)外的参数，求解2-1获得更新后的\(\alpha_i\)和\(\alpha_j\)
可以看出，SMO算法的做法和坐标下降法类似，只不过SMO中，每次选取的为一对变量\((\alpha_i,\alpha_j)\), 而坐标下降为一个。因为SVM中，\(\alpha\)并非完全独立，而是有约束的（\(\sum_{i=1}^n\alpha_iy_i =0\) ），因此若一个\(\alpha\)改变，另一个也要随之变化以满足约束条件。
直观上看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。因此第一个变量选择违背KKT条件程度最大的变量，第二个变量则选择使目标函数减少最快的变量。具体的过程之后再讲。现在先讲假设已经选择了变量，然后我们来看看接下来怎么做。
获得未修剪的原始解
假设选择两个变量为\(\alpha_1\)和\(\alpha_2\)，其余变量\(\alpha_3, \alpha_4,\cdots,\alpha_n\)均固定（当作常数），于是式2-1的子问题可以写成： \[ \begin{align*} \max_{ {\boldsymbol \alpha} }\hspace{2ex}& \alpha_1 + \alpha_2 - \frac{1}{2}\alpha_1^2K_{11} - \frac{1}{2}\alpha_2^2K_{22}-\alpha_1\alpha_2y_1y_2K_{12} - \alpha_1y_1\sum_{i=3}^n\alpha_iy_iK_{i1}-\alpha_2y_2 \sum_{i=3}^n\alpha_iy_iK_{i2}\tag{2-2}\\ {\rm s.t.} \hspace{2ex} &\alpha_{1}y_{1} + \alpha_{2}y_{2} = -\sum_{i=3}^{n}\alpha_{i}y_{i} = \zeta\\ \hspace{2ex} & 0 \le \alpha_i \le C, \hspace{2ex} i=1,2 \end{align*} \]
- 上面的目标函数中，就是展开包含\(\alpha_1, \alpha_2\)的项，把其余不包括\(\alpha_1, \alpha_2\)的可以看成常数项的去掉得到的。并对\(y_iy_i = 1\)进行了化简。另外简写核函数\(K_{ij} = K({\bf x_i, x_j})\)
- 第一个约束条件就是进行移项，\(\alpha_1y_1 + \alpha_2y_2\)等于常数\(\zeta\)
- 由于我们只考虑\(\alpha_1\)和\(\alpha_2\)，因此第二个限制条件i只取1或2。
接着我们来做一些推导， 引进记号 \[ v_{i} = \sum_{j=3}^{n}\alpha_{j}y_{j}K_{ij} = f(x_{i}) - \sum_{j=1}^{2}\alpha_{j}y_{j}K_{ij} - b, \hspace{2ex} i=1,2\tag{2-3} \]
将2-3带入2-2的目标函数，则目标函数可以写成 \[ W(\alpha_1,\alpha_2) =\alpha_1 + \alpha_2 - \frac{1}{2}\alpha_1^2K_{11} - \frac{1}{2}\alpha_2^2K_{22}-\alpha_1\alpha_2y_1y_2K_{12} - \alpha_1y_1v_1-\alpha_2y_2 v_2\tag{2-4} \] 另外看看第一个约束条件： \[ \begin{align*} \alpha_{1}y_{1} & = \zeta - \alpha_{2}y_{2} \\ \alpha_{1} & = \zeta y_{1} - \alpha_{2}y_{2}y_{1} \hspace{2ex} 两边同时乘以y_1\tag{2-5} \end{align*} \] 将2-5带入2-4，就消去了\(\alpha_1\)，得到\(\alpha_2\)的目标函数: \[ \begin{align*} W(\alpha_2) =&\zeta y_{1} - \alpha_{2}y_{2}y_{1} + \alpha_2 - \frac{1}{2}(\zeta y_{1} - \alpha_{2}y_{2}y_{1})^2K_{11} - \frac{1}{2}\alpha_2^2K_{22} - (\zeta y_{1} - \alpha_{2}y_{2}y_{1})\alpha_2y_1y_2K_{12} \\& - (\zeta y_{1} - \alpha_{2}y_{2}y_{1})y_1v_1-\alpha_2y_2 v_2 \\=&(\zeta- \alpha_{2}y_{2} )y_1 + \alpha_2 -\frac{1}{2}K_{11}(\zeta - \alpha_{2}y_{2})^2 - \frac{1}{2}K_{22}\alpha_2^2 - y_2K_{12}(\zeta - \alpha_{2}y_{2})\alpha_2 \\& - v_1(\zeta - \alpha_{2}y_{2}) - y_2 v_2\alpha_2\tag{2-4} \end{align*} \] 对\(\alpha_2\)求导数，得： \[ \begin{align*} \frac{\partial w}{\partial \alpha_2} &= -y_1y_2+1 + (\zeta - \alpha_{2}y_{2})y_2K_{11} - K_{22}\alpha_2 - y_2K_{12} (\zeta - \alpha_{2}y_{2})+ y_2y_2K_{12}\alpha_2 +y_2v_1 - y_2v_2 \\& = -y_1y_2 + 1 +y_2\zeta K_{11} - K_{11}\alpha_2 - K_{22}\alpha_2-y_2K_{12}\zeta+2K_{12}\alpha_2 + y_2v_1 - y_2v_2 \end{align*} \] 令其为0，整理得到 \[ \begin{align*} (K_{11} + K_{22} -2K_{12})\alpha_2 &= -y_1y_2 + 1 +y_2\zeta K_{11} -y_2K_{12}\zeta+ y_2v_1 - y_2v_2\\ &=y_2(-y_1 + y_2 +\zeta K_{11} -\zeta K_{12}+ v_1 - v_2)\tag{2-5} \end{align*} \] 此外，将\(\alpha_{1}^{old} = \zeta y_{1} - \alpha_{2}^{old} y_{2}y_{1}\)代入\(v_1 - v_2\)，得到 \[ \begin{align*} v_1 - v_2 &= \left( f(x_{1}) - \sum_{j=1}^{2}\alpha_{j}y_{j}K_{1j} - b\right) - \left( f(x_{2}) - \sum_{j=1}^{2}\alpha_{j}y_{j}K_{2j} - b\right)\\ &= f(x_{1}) - f(x_{2}) - \sum_{j=1}^{2}\alpha_{j}y_{j}K_{1j} +\sum_{j=1}^{2}\alpha_{j}y_{j}K_{2j} \\ &= f(x_{1}) - f(x_{2}) - (\zeta - \alpha_2^{old}y_2)K_{11} - \alpha_2^{old}y_2K_{12} + (\zeta-\alpha_2^{old}y_2)K_{12} +\alpha_2^{old}y_2K_{22} \\ &= f(x_{1}) - f(x_{2}) - \zeta K_{11}+ \alpha_2^{old}y_2K_{11} -2 \alpha_2^{old}y_2K_{12} + \zeta K_{12}+\alpha_2^{old}y_2K_{22} \tag{2-6} \end{align*} \] 将2-6带入2-5, 并令\(E_i = f(x_i) - y_i\)表示SVM预测值与真实值误差： \[ \begin{align*} (K_{11} + K_{22} -2K_{12})\alpha_2^{\rm new, unclipped} = &y_2(-y_1 + y_2 +\zeta K_{11} -\zeta K_{12} \\&+ f(x_{1}) - f(x_{2}) - \zeta K_{11} + \alpha_2^{old}y_2K_{11} -2 \alpha_2^{old}y_2K_{12} + \zeta K_{12}+\alpha_2^{old}y_2K_{22}) \\ =&\ y_2(-y_1 + y_2 + f(x_{1}) - f(x_{2}) + \alpha_2^{old}y_2K_{11} -2 \alpha_2^{old}y_2K_{12}+\alpha_2^{old}y_2K_{22}) \\ =&\ y_2(-y_1 + y_2 + f(x_{1}) - f(x_{2})) + \alpha_2^{old}K_{11} -2 \alpha_2^{old}K_{12}+\alpha_2^{old}K_{22} \\ =&\ y_2(-y_1 + y_2 + f(x_{1}) - f(x_{2}) ) + (K_{11}+K_{22} -2 K_{12}) \alpha_2^{old}\\ =&\ y_2(E_1 - E_2) + (K_{11}+K_{22} -2 K_{12}) \alpha_2^{old} \end{align*} \] 令\(\eta = K_{1 1} + K_{22} - 2K_{12}\)得： \[ \begin{align*} \alpha_2^{\rm new, unclipped} =& \alpha_2^{old}+ \frac{y_2(E_1 - E_2) }{(K_{11} + K_{22} -2K_{12})}\\ =& \alpha_2^{old}+ \frac{y_2(E_1 - E_2) }{\eta}\tag{2-7} \end{align*} \]
修剪原始解
上面我们得到了未经修剪的原始解: \[ \begin{align*} \alpha_2^{\rm new, unclipped} = \alpha_2^{old}+ \frac{y_2(E_1 - E_2) }{\eta} \end{align*} \] 但是在SVM中需要满足限制条件: \[ \alpha_{1}y_{1} + \alpha_{2}y_{2} = -\sum_{i=3}^{n}\alpha_{i}y_{i} = \zeta\\ 0 \le \alpha_i \le C, \hspace{2ex} i=1,2 \] 第二个限制条件将其限制在正方形区域中，而第一个限制条件则为一条直线。根据\(y_1\)是否等于\(y_2\)的关系可以得到下图：
以左边的图为例，当\(y_1\ne y_2\)时，\(\alpha_1^{old} -\alpha_2^{old} = \zeta y_1 = k\), 可以看出-k为截距，因此下界L和上界H可以表示为： \[ \begin{align*} L = &\max(0, \alpha_2^{old} - \alpha_1^{old})\\ H = &\min(C, C + \alpha_2^{old} - \alpha_1^{old}) \end{align*} \] 右边的类似，当\(y_1= y_2\)时，\(\alpha_1^{old} +\alpha_2^{old} = \zeta y_1 = k\), 可以看出k为截距，因此下界L和上界H可以表示为： \[ \begin{align*} L = & \max(0, \alpha_1 ^{old}+ \alpha_2^{old} - C )\\ H = &\min(C, \alpha_1^{old} + \alpha_2^{old} ) \end{align*} \] 通过上下界，就可以得到修剪后的\(\alpha_2^{\rm new}\) \[ \alpha_{2}^{\rm new} = \begin{cases} H & \alpha_{2}^{\rm new, unclipped}> H \\ \alpha_{2}^{\rm new, unclipped} & L \le \alpha_{2}^{\rm new, unclipped} \le H \\ L & \alpha_{2}^{\rm new, unclipped} < L \end{cases}\tag{2-8} \] 得到了\(\alpha_2^{\rm new}\)后就可以根据\(\alpha_{1}^{\rm old}y_{1} + \alpha_{2}^{\rm old}y_{2} = \alpha_{1}^{\rm new}y_{1} + \alpha_{2}^{\rm new}y_{2}\)得到\(\alpha_1^{\rm new}\) \[ \alpha_{1}^{\rm new} = \alpha_{1}^{\rm old} + y_{1}y_{2}(\alpha_{2}^{\rm old} - \alpha_{2}^{\rm new}) \tag{2-9} \]
b值更新
当完成一对\(\alpha_i, \alpha_j\)更新之后需要重新计算参数b，因为b关系到我们f(x)的计算，进而关系到之后计算误差E。
前面提到过，当\(0 \lt \alpha_1^{\rm new} \lt C\)时，此时为支持向量， 有\(y_1({\bf w^Tx_1}+b) = 1\)，两边同时乘上\(y_1\)可以得到： \[ \begin{align*} b_1^{\rm new} &= y_1 - {\bf w^Tx_1}\\ &= y_1 - \sum_{i=1}^n\alpha_iy_iK_{i1}\\ &= y_1 - \sum_{i=3}^n\alpha_iy_iK_{i1} - \alpha_1^{\rm new}y_1K_{11} - \alpha_2^{\rm new}y_2K_{21} \tag{2-10} \end{align*} \] 又因为 \[ \begin{align*} E_1 &= f(x_1) - y_1 \\ &= {\bf w^Tx_1}+b^{\rm old} - y_1 \\ & =\sum_{i=1}^n\alpha_iy_iK_{i1} +b^{\rm old} - y_1 \\ &= \alpha_1^{\rm old}y_1K_{11} + \alpha_2^{\rm old}y_2K_{21} + \sum_{i=3}^n\alpha_iy_iK({\bf x_i},{\bf x_1}) +b^{\rm old}- y_1 \end{align*} \] 于是2-10前两项可以写为： \[ y_1 - \sum_{i=3}^n\alpha_iy_iK({\bf x_i},{\bf x_1}) = \alpha_1^{\rm old}y_1K_{11} + \alpha_2^{\rm old}y_2K_{21} +b^{\rm old}- E_1 \]
带入2-10得： \[ \begin{align*} b_1^{\rm new} &= \alpha_1^{\rm old}y_1K_{11} + \alpha_2^{\rm old}y_2K_{21} +b^{\rm old}- E_1- \alpha_1^{\rm new}y_1K_{11} - \alpha_2^{\rm new}y_2K_{21} \\ &= (\alpha_1^{\rm old} - \alpha_1^{\rm new})y_1K_{11} + (\alpha_2^{\rm old} - \alpha_2^{\rm new})y_2K_{21} + b^{\rm old} -E_1\tag{2-11} \end{align*} \]
同样，若\(0 \lt \alpha_2^{\rm new} \lt C\)，有： \[ \begin{align*} b_2^{\rm new} &= (\alpha_1^{\rm old} - \alpha_1^{\rm new})y_1K_{12} + (\alpha_2^{\rm old} - \alpha_2^{\rm new})y_2K_{22} + b^{\rm old} -E_2\tag{2-12} \end{align*} \]
- 如果\(\alpha_1^{\rm new},\alpha_2^{\rm new}\)同时满足\(0 \lt \alpha_1^{\rm new} \lt C ;\ 0 \lt \alpha_2^{\rm new} \lt C\)，则\(b_1^{\rm new} = b_2^{\rm new}\)
- 如果\(\alpha_1^{\rm new},\alpha_2^{\rm new}\)为0或者C,那么\(b_1\)和\(b_2\)以及它们之间的数都是满足KKT条件的阈值，这时候选它们的中点作为\(b^{\rm new} = \frac{1}{2} (b_1^{\rm new} + b_2^{\rm new})\)
更新完b之后，可以容易的得到\(E_i\)的值 \[ E_i^{\rm new} = \sum_{s\in support\ vector}\alpha_sy_sK_{si} +b^{\rm new} - y_i \tag{2-13} \] 可以看到，SMO算法计算中，主要是2-7, 2-8, 2-9 , 2-11, 2-12, 2-13，并不依赖于数据量n，效率极高。
选取更新变量\(\alpha\)
OK，现在来讨论如何选择\(\alpha\)更加细节的部分。
首先要明确的是： SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
第1个变量的选择
SMO称选择第1个变量的过程为外层循环。
具体的，外层循环首先遍历所有满足条件\(0 \lt \alpha_i \lt C\) 的样本点（即自由支持向量），检验其是否满足KKT条件，如果满足，那么遍历整个训练集，检验它们是否满足KKT条件。
这里优先遍历满足条件\(0 \lt \alpha_i \lt C\) 的样本点，因为这些样本点更容易违反KKT条件。为什么呢？因为非支持向量(\(\alpha_i = 0\))和受限支持向量(\(\alpha_i = C\))对应的系数\(\alpha_i\)一般不会更改。
如何判断满足KKT条件呢？就是根据互补松弛性\(\alpha_i(1 - \xi_i - y_i({\bf w^Tx_i}+b)) = 0; \hspace{2ex} \beta_i\xi_i = 0\)得出的下面几个判别式： \[ \begin{align*} \alpha_i = 0 & \Leftrightarrow y_if(x_i) \ge1 \\ 0 \lt \alpha_i \lt C &\Leftrightarrow y_if(x_i) = 1 \\ \alpha_i = C & \Leftrightarrow y_if(x_i) \le 1 \end{align*} \] 以第2个为例，此时\(0 \lt\alpha_i \lt C\) 可以根据 \(C - \alpha_i - \beta_i = 0\) 推出\(\beta_i \gt 0 \Rightarrow \xi_i = 0\)，因此\(y_if(x_i) = 1\)。
第2个变量选择
SMO称选择第2个变量为内层循环。假设在外层循环中已经找到第1个变量\(\alpha_1\),现在要在内层循环中寻找第2个变量\(\alpha_2\)。第2个变量选择的标准是希望能使\(\alpha_2\)有尽可能大的变化。
式2-7\(\alpha_2^{\rm new, unclipped} = \alpha_2^{old}+ \frac{y_2(E_1 - E_2) }{\eta}\)和式2-8告诉我们，是\(\alpha_2^{\rm new}\) 依赖于\(|E_1 - E_2|\)的。为了加快计算速度，一种简单的做法是选择\(\alpha_2\)，使其对应的\(|E_1 - E_2|\)最大。为了节省计算时间，将所有\(E_i\)的值保存在一个列表中。
- 如果\(E_1\)是正的，选最小的\(E_i\)作为\(E_2\)
- 如果\(E_1\)是负的，选最大的\(E_i\)作为\(E_2\)
特殊情况下，比如\(\eta = K_{11} + k_{22} - 2k_{12} = 0\)也就是两个样本的特征完全相同时，这样就有问题，因为分母为0。此时采用如下启发式规则继续选择\(\alpha_2\)：
- 在自由支持向量(\(0 \lt \alpha_i \lt C\))上遍历，依次将其对应的变量作为\(\alpha_2\)试用，直到找到\(\eta \ne0\)的变量
- 若1找不到合适的\(\alpha_2\)，那么遍历训练数据集继续寻找
注意这里要随机选择位置，这是因为每次都从头开始遍历的话算法就会偏向靠前的变量。
极端情况下，若仍找不到合适的\(\alpha_2\)，则放弃第1个\(\alpha_1\)，再通过外层循环另求\(\alpha_1\)
小结
关于SMO，西瓜书只有几句话的介绍，读起来一知半解，而李航老师的推导有些跳跃，新手难以看懂，因此决定总结一下。此外可以看看SMO原论文中的伪代码，这样会对过程更加了解。
除了SMO之外，还有直接在原问题上进行优化的算法（如Pegasos 以后在做介绍）。
SVM系列的介绍就告一段落啦。回想自己一开始的时候对SVM只停留在表面，原始问题知道了，不知道为啥要搞对偶问题，为什么能写出拉格朗日对偶等等，可谓菜的一比。
现在看来SVM思想也很简单，就是找间隔最大的超平面来划分数据，这样鲁棒性好。之后的一系列很多数学的推导都是为了最优化二次规划算法。包括写出拉格朗日对偶，将min max转化为 max min问题。然后在拉格朗日对偶中，我们发现w可以被线性的表示，这样更加凸显了支持向量的意义——只需要保存支持向量这些样本。此外，w可以被线性表示，进而我们使用核函数，将原本需要在高维空间的计算转化为低维空间中的计算，大大提高了效率。之后，由于样本可能有噪声数据等，盲目用核函数进行空间变换不一定是最好的，我们放宽条件，引入惩罚因子\(\xi_i\)进而允许一些样本分错，令人惊奇的是惩罚因子最后并没有出现在拉格朗日对偶的目标函数中，而仅仅是要求\(\alpha_i \lt C\)。之后，我们用类似的思想用于回归问题上，类似于软边距SVM，引入管道间隔得到了SVR，然后本篇把SMO这个高效的求解方法介绍了。不得不赞叹SVM理论优美，确实一步步设计太好了。
整理完这个系列，感觉水平进步了很多，基本上常见的最优化方法都涉猎了一遍，今后打算有空实现一下SVM。
在此感谢林轩田老师的《机器学习技法》，里面讲解SVM十分详细，值得一看。
以及李航老师《统计学习方法》对于推导也十分详细，但比较晦涩，适合有一定基础的同学看。
此外还有周志华老师的《机器学习》，公式较少，对于新手可能看完不知SVM推导的来龙去脉，推荐可以先看看原理，公式推导可以看本博客的深入理解SVM系列，以及林轩田老师的课程。
参考资料
- 《统计学习方法》 - 李航
- 支持向量机（五）SMO算法
- SMO算法总结
