在SVM的前三篇里，我们优化的目标函数最终都是一个关于 $α$ 向量的函数。而怎么极小化这个函数，求出对应的 $α$ 向量，进而求出分离超平面我们没有讲。本篇就对优化这个关于$α$ 向量的函数的SMO算法做一个总结。
1. 回顾SVM优化目标函数
优化目标函数：
\[\underbrace{ min }_{\alpha} \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum\limits_{i=1}^{m}\alpha_i\] \[s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0\] \[0 \leq \alpha_i \leq C\]解要满足的KKT条件的对偶互补条件为：
\[\alpha_{i}^{*}(y_i(w^Tx_i + b) - 1 + \xi_i^{*}) = 0\]根据这个KKT条件的对偶互补条件，我们有：
\[\alpha_{i}^{*} = 0 \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) \geq 1\] \[0 <\alpha_{i}^{*} < C \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) = 1\] \[\alpha_{i}^{*}= C \Rightarrow y_i(w^{*} \bullet \phi(x_i) + b) \leq 1\]由于 $w^{*} = \sum\limits_{j=1}^{m}\alpha_j^{*}y_j\phi(x_j)$ ,我们令 $g(x) = w^{*} \bullet \phi(x) + b =\sum\limits_{j=1}^{m}\alpha_j^{*}y_jK(x, x_j)+ b^{*}$ ，则有：
\[\alpha_{i}^{*} = 0 \Rightarrow y_ig(x_i) \geq 1\] \[0 < \alpha_{i}^{*} < C \Rightarrow y_ig(x_i) = 1\] \[\alpha_{i}^{*}= C \Rightarrow y_ig(x_i) \leq 1\]2. SMO算法的基本思想
上面这个优化式子比较复杂，里面有m个变量组成的向量 $α$ 需要在目标函数极小化的时候求出。直接优化时很难的。SMO 算法则采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。由于 $\sum\limits_{i=1}^{m}\alpha_iy_i = 0$ , 假如将 $\alpha_3, \alpha_4, …, \alpha_m$ 固定，那么 $\alpha_1, \alpha_2$ 之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。
为了后面表示方便，我们定义 $K_{ij} = \phi(x_i) \bullet \phi(x_j)$
由于 $\alpha_3, \alpha_4, …, \alpha_m$ 都成了常量，所有的常量我们都从目标函数去除，这样我们上一节的目标优化函数变成下式：
\[\begin{equation} \underbrace{\min _{\alpha_{1}, \alpha_{1}}} \frac{1}{2} K_{11} \alpha_{1}^{2}+\frac{1}{2} K_{22} \alpha_{2}^{2}+y_{1} y_{2} K_{12} \alpha_{2}-\left(\alpha_{1}+\alpha_{2}\right)+y_{1} \alpha_{1} \sum_{i=3}^{m} y_{i} \alpha_{i} K_{i 1}+y_{2} \alpha_{2} \sum_{i=3}^{m} y_{i} \alpha_{i} K_{i 2} \end{equation}\] \[\begin{equation} \text {s.t. } \quad \alpha_{1} y_{1}+\alpha_{2} y_{2}=-\sum_{i=3}^{m} y_{i} \alpha_{i}= \varsigma \end{equation}\] \[\begin{equation} 0 \leq \alpha_{i} \leq C \qquad i=1,2 \end{equation}\]3. SMO算法目标函数的优化
为了求解上面含有这两个变量的目标优化问题，我们首先分析约束条件，所有的 $\alpha_1, \alpha_2$ 都要满足约束条件，然后在约束条件下求最小。
根据上面的约束条件 $\alpha_1y_1 + \alpha_2y_2 = \varsigma\;\;0 \leq \alpha_i \leq C \;\; i =1,2$ ，又由于 $y_1,y_2$ 均只能取值1或者-1, 这样 $\alpha_1, \alpha_2$ 在 [0,C] 和 [0,C] 形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说 $\alpha_1, \alpha_2$ 的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：
由于 $\alpha_1, \alpha_2$ 的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是 $\alpha_2$ 的优化问题。由于我们采用的是启发式的迭代法，假设我们上一轮迭代得到的解是 $\alpha_1^{old}, \alpha_2^{old}$ ，假设沿着约束方向 $\alpha_2$ 未经剪辑的解是 $\alpha_2^{new,unc}$ .本轮迭代完成后的解为 $\alpha_1^{new}, \alpha_2^{new}$
未完 。。。。