SVM - 原理

机器学习

---

代码请移步：7 - SVM-SMO —— 代码

线性可分

首先对于线性可分的数据必然存在一个分离超平面$w^*\cdot x+b^*=0$能够把数据完全正确的分开，我们的目标就是要求该分离超平面的形式。前面的感知器通过最小化分错的点到超平面的距离

$$\begin{split} & \underset{w,b}{\min} - \sum_{x_i\in M}\frac{y_i(w\cdot x_i+b)}{\|w\|} \\ = & \underset{w,b}{\min} -\sum_{x_i\in M}yi(w\cdot x_i + b) \end{split}$$

$M$为所有被分离超平面$w\cdot x+b=0$错误分类的点的集合。上式中个人感觉因为上面的式子不好算所以用了下面的式子来代替，然后用迭代的方法更新$w,b$，但这时得到的解不是唯一的，有无穷多个，线性可分的SVM用间隔最大化来求解分离超平面，相当于在原始感知器的基础上加了一个间隔最大化的条件，使解是唯一的

对于超平面$(w,b)$样本点$(x_i,y_i)$的函数间隔为

$$\hat{\gamma}_i = y_i(w\cdot x_i + b)$$

但对于函数间隔来说，当$(w,b)$等比例变化$w=\lambda w,b=\lambda b$时表示的该超平面不变，但函数间隔$\hat{\gamma} = \lambda \gamma$变为原来的$\gamma$倍，故不能直接用函数间隔来表示

现有间隔表示几何上点$(x_i,y_i)$到超平面$w\cdot x +b=0$的距离

$$\begin{split} \gamma_i & = \frac{y_i(w\cdot x_i + b)}{\|w\|} \\ & = \frac{\hat{\gamma_i}}{\|w\|} \end{split}$$
相当于在函数间隔上对超平面加了一个约束$\|w\|=1$。

由此SVM表示为了最大化样本点中最小的几何间隔

$$\begin{split} & \underset{w,b}{\max} \left\{ \underset{i}{\min}\frac{y_i(w\cdot x_i+b)}{\|w\|} \right\} \\ = & \underset{w,b}{\max}\left\{ \frac{1}{\|w\|}\underset{i}{\min} y_i(w\cdot x_i + b) \right\} \\ = & \underset{w,b}{\max}\left\{ \underset{i}{\min} \gamma_i \right\} \\ = & \underset{w,b}{\max}\left\{\frac{1}{\|w\|} \underset{i}{\min} \hat{\gamma}_i \right\} \end{split}$$

由于当$w,b$成比例的变化$w = \lambda w, b = \lambda b$时函数距离$\hat{\gamma}_i = \lambda \hat{\gamma}_i$也成比例变化，但该超平面$w\cdot x + b = 0$不变，几何间隔$\gamma_i$也不变，故此时的函数间隔$\hat{\gamma}_i$可取任意值，现取$\underset{i}{\min}\hat{\gamma}_i=1$，也就是说样本点到超平面的最小函数距离设为$1$，故此时的优化问题变为

$$\begin{split} & \underset{w,b}{\max} \frac{1}{\|w\|} \\ & s.t. \quad y_i(w\cdot x_i + b) \geq 1 \quad \text{//保证最小函数间隔为1} \end{split}$$

该优化问题等价于

$$\begin{split} & \underset{w,b}{\min} \frac{1}{2}\|w\|^2 \\ & s.t. \quad y_i(w\cdot x_i + b) \geq 1 \end{split}$$

这样就消去了上面的最小化间隔形式中的$\min$，转变成了一个单纯的二次优化问题，该优化问题存在不等式约束故需要用KKT条件，现插播一下KKT条件

KKT条件 —— 松弛变量法

KKT条件使用松弛变量法推出来的，现有优化问题

$$\begin{split} & \underset{x}{\min} f(x) \\ & s.t. \left\{\begin{matrix} h_i(x) = 0 & i = 1,\cdots,N_h \\ g_i(x) \le 0 & i = 1,\cdots, N_g \end{matrix}\right. \end{split}$$

用松弛变量使不等式约束转变为等式约束

$$g_i(x) + a_i^2 = 0$$

然后根据拉格朗日乘子法得到

$$\begin{split} L(x, \alpha, \beta, a) = f(x) + \sum_{i=1}^{N_h}\alpha_ih_i(x) + \sum_{i=1}^{N_g}\beta_i(g_i(x)+a_i^2) \end{split}$$

然后求偏导

$$\begin{split} \frac{\partial L}{\partial x} & = \nabla f + \sum_{i=1}^{N_h}\alpha_i\nabla h_i + \sum_{i=1}^{N_g}\beta_i \nabla_i g_i = 0 \\ \frac{\partial L}{\partial a_i} & = 2\beta_ia_i = 0 \end{split}$$

得到$\beta_ia_i = 0$，现在可分为两种情况

• $\beta_i = 0$：此时不等式约束$g_i(x) \le0$不起作用
• $a_i = 0,\beta_i>0$：此时不等式约束退化为等式约束$g_i(x) = 0$

所以等价于$\beta_i=0$或者$g_i(x)=0$也就消去了松弛变量$\beta_ig_i(x)=0$
故此时有

$$\begin{split} L(x,\alpha,\beta) & = f(x) + \sum_{i=1}^{N_h}\alpha_ih_i(x) + \sum_{i=1}^{N_g}\beta_ig_i(x) \end{split}$$

并且对应的KKT条件为

$$\left\{\begin{split} & \nabla f + \sum_{i=1}^{N_h} \alpha_i\nabla h_i + \sum_{i=1}^{N_g}\beta_ig_i = 0 \\ & h_i(x) = 0 \\ & g_i(x) \le 0 \\ & \beta_i g_i(x) = 0 \\ & \alpha_i \geq 0 \\ & \beta_i \geq 0 \end{split}\right.$$

对偶

由上一节可以得到

$$L(w,b,\alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b) + \sum_{i=1}^N \alpha_i$$
并且对应的KKT条件为
$$\left\{\begin{split} & \frac{\partial L}{\partial w} = w - \sum_{i=1}^N \alpha_iy_ix_i = 0 \\ & \frac{\partial L}{\partial b} = - \sum_{i=1}^N \alpha_iy_i = 0 \\ & \alpha_i(y_i(w\cdot x_i+b) - 1) = 0 \\ & y_i(w\cdot x_i +b) \geq 1 \\ & \alpha_i \geq 0 \\ \end{split}\right.$$

故现在优化问题变为一个极小极大问题

$$\underset{w,b}{\min}\underset{\alpha}{\max}L(w,b,\alpha)$$

其与一个极大极小问题对应

$$\underset{\alpha}{\max}\underset{w,b}{\min} L(w,b,\alpha)$$

由上面的KKT条件可以消去里面的$w = \sum_{i=1}^N \alpha_iy_ix_i,b$

$$\begin{split} L(\alpha) & = \frac{1}{2}\|w\|^2 - \sum_{i=1}^N \alpha_iy_i(w\cdot x_i + b) + \sum_{i=1}^N \alpha_i \\ & = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - b\sum_{i=1}^N\alpha_iy_i + \sum_{i=1}^N \alpha_i \\ & = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N\alpha_i \end{split}$$

故现在优化问题变为

$$\begin{split} & \underset{\alpha}{\max} L(\alpha) = \\ & \underset{\alpha}{\min}-L(\alpha) = \\ & \underset{\alpha}{\min} \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\ & s.t. \left\{\begin{split} & \sum_{i=1}^N \alpha_iy_i = 0 \\ & \alpha_i \geq 0 \end{split}\right. \end{split}$$

支持向量

关于支持向量的图示网上有很多这里就不再画一个了，只说下在优化的角度支持向量的解释

支持向量是那些在分割带边缘的点，也即满足最小化间隔的点，在上述的优化问题中就是满足$y_i(w\cdot x_i + b) = 1$的点，支持向量有一个性质，SVM的解只与支持向量有关，而非支持向量的变化不改变SVM求解的超平面，再由前面的KKT条件的$\beta_i g_i(x)=0$得到，支持向量需满足$\alpha_i>0$，这时改点构成的约束$y_i(w\cdot x_i +b)\geq 1$起作用，并且该约束退化为等式约束$y_i(w\cdot x_i +b) = 1$也同样表示了在分隔带边缘的点，而其他点满足约束$y_i(w\cdot x_i +b) > 1$而$\alpha_i=0$，此时对应的约束失效，同样表示为非支持变量的变化不影响最终优化的解

线性可分SVM学习机

解上面的对偶优化问题可以得到最优的$\alpha^*$，要得到最终的学习机的形式需要得到该超平面，由上面可以得到$w^* = \sum_{i=1}^N\alpha_i^*y_ix_i$，想要得到具体的学习机的形式还需要知道$b$的值，这里用的是支持向量的性质，由上面得到支持向量$(x_j,y_j)$满足等式$y_j(w^*\cdot x_j + b^*) = 1$得到

$$\begin{split} b^* & = \frac{1}{y_j} - w^* \cdot x_j \\ & = y_j - \sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j) \quad \text{// $y_j^2=1$} \end{split}$$

则分离超平面为

$$\sum_{i=1}^N \alpha_i^*y_i(x_i \cdot x) + b^* = 0$$

并且对应的决策函数为

$$f(x) = \mathrm{sign}\left\{ \sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x) + b^* \right\}$$

可以看到不管是对偶优化，还是分割平面和最终的决策函数都只与样本的$x$的内积有关

线性不可分 与 软间隔

SVM为了应对线性不可分的情况采取了一种软间隔策略，首先看下SVM如何看待线性不可分，其把线性不可分的数据看成了在线性可分基础上的一些少量离群点，线性可分的形式在最小间隔下所有的点需要满足$y_i(w\cdot x_i + b) \geq 1$，由于有少量离群点的存在，该间隔用松弛变量法成了一个软间隔的形式$y_i(w\cdot x_i + b)\geq 1 - \xi_i$

$\xi_i$可以看作是每一个点对应的与最小间隔边界的误分类的函数距离，而反过来$\xi_i$的存在也模糊化了该最小间隔的边界，此时优化目标函数加了一个该误分类距离的惩罚项，让该误分类距离尽量小，现在优化目标变为

$$\underset{w,b,\xi}{\min}\frac{1}{2}\|w\|^2 + C\sum_{i=1}^N \xi_i \\ s.t.\left\{\begin{split} & y_i(w\cdot x_i + b) \geq 1-\xi_i \\ & \xi_i \geq 0 \end{split}\right.$$

这里$C$表示对误分类距离的惩罚系数

由拉格朗日乘子法得

$$L(w,b,\xi,\alpha,\beta) = \frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i - \sum_{i=1}^N \alpha_iy_i(w\cdot x_i + b) +\sum_{i=1}^N \alpha_i - \sum_{i=1}^N \alpha_i\xi_i - \sum_{i=1}^N \beta_i\xi_i$$
然后求偏导得
$$\begin{split} \frac{\partial L}{\partial w} & = w - \sum_{i=1}^N \alpha_iy_ix_i = 0 \\ \frac{\partial L}{\partial b} & = - \sum_{i=1}^N \alpha_iy_i = 0 \\ \frac{\partial L}{\partial \xi_i} & = C - \alpha_i - \beta_i = 0 \\ & \alpha_i \geq 0\\ & \beta_i \geq 0 \end{split}$$

带入上式可得到

$$L(\alpha) = -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) + \sum_{i=1}^N \alpha_i$$

并且由$C-\alpha_i - \beta_i = 0$得到$\alpha_i = C- \beta_i$，由于$\beta_i\geq 0$故$0\le\alpha_i\le C$

最后由上面的极大极小转化为极小极大，最终优化问题变为

$$\begin{split} & \underset{\alpha}{\min} \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i\alpha_jy_iy_j (x_i\cdot x_j) - \sum_{i=1}^N\alpha_i \\ & s.t. \left\{\begin{split} & \sum_{i=1}^N \alpha_iy_i = 0 \\ & 0\le \alpha_i \le C \end{split}\right. \end{split}$$

---

分析一下对偶情况下样本点的约束情况，此时需要满足两个重要的KKT条件有

$$\alpha_i\big[y_i(w\cdot x_i+b) - 1 + \xi_i\big] = 0 \\ \beta_i\xi_i = 0 \\ \alpha_i + \beta_i = C \\ \alpha_i \geq 0\\ y_i(w\cdot x_i + b) - 1 + \xi_i \geq 0 \\ \beta_i \geq 0 \\ \xi_i \geq 0$$

故此时有：

• $\alpha_i = 0$，此时不等式约束$y_i(w\cdot x_i + b) \geq 1 - \xi_i$不起作用，也就是该点构成的约束不起作用，则该点在分离间隔外面，是非支持向量点
• $\alpha_i > 0$，因为$\alpha_i\big[y_i(w\cdot x_i+b) - 1 + \xi_i\big] = 0$有等式约束$y_i(w\cdot x_i + b) = 1 - \xi_i$起作用，此时点在分离间隔上或者内部，该点是支持向量点，此外由于有$\beta_i = C - \alpha_i$，这时根据$\beta_i$又分为两种情况
  
  • $0 < \alpha_i < C$此时$0 < \beta_i < C$，因为$\beta_i\xi_i = 0$，有不等式约束退化为等式约束$\xi_i=0$起作用，由于此时松弛变量$xi_i = 0$，故$\alpha_i$对应的等式约束变为$y_i(w\cdot x_i + b) = 1$，此时点正好在分离间隔的边界上也就是上图中虚线穿过的点
  • $\alpha_i = C$此时$\beta_i = 0$不等式约束$\xi_i \geq 0$不起作用，也就是不管该点松弛变量$\xi$的值如何都不影响最终的优化结果，由于此时$\xi_i\geq 0$，$\alpha_i$对应的等式约束为$y_i(w\cdot x_i + b) = 1 - \xi_i$，此时该点在分离间隔内部或者在另一侧（$\xi_i$为大于等于0的任意值）

最后看一下惩罚项$C$的影响，本身松弛因子是不影响最终优化结果的，但SVM在原始目标函数上加了一个包含松弛因子的正则化项，使得惩罚项$C$对应的松弛因子对最终的优化结果产生了影响。由上面可知$\alpha_i + \beta_i = C$，由于对偶因子$\alpha_i$和$\beta_i$代表了该等式约束在该优化问题中的影响力，当$0\le\alpha_i \le C,0\le \beta_i \le C$，两个等式约束项同时起作用，但$\alpha_i$越大$\beta_i$越小，故虽然此时点均在分离间隔边界上，但其仍然是不同的，其与$\alpha_i$的大小有关，$\alpha_i$越大该点在优化中越重要，但对应的松弛因子越“容易”变大，当$\alpha_i = C$时，松弛因子突破0，此时的松弛因子对应的等式约束不再起作用，表现在分类数据集上是两个不同的类点越靠近（越“杂糅”）$\alpha$越大，当到达一定程度松弛因子开始起作用，其使该“离群点”不影响最终的优化，从而达到该离群点不影响最终优化结果的目的。由后面的SMO优化过程可知，优化过程通过求解$\alpha_i$得到的，故当$C$比较大时，会有更多的点在分离间隔的边界上。

个人赶脚SVM作为统计模型还缺点啥，如果换成随机变量来分析会不会有不一样

核方法

关于核方法已经超出我现在理解的能力范围，只是拿来主义的说下核方法的形式

首先SVM划分了输入空间和特征空间，都是基于上面的内积（内积空间是数分里面的内容，我现在的理解还不够）的性质

为了能够解决非线性问题，SVM引入了核方法，通过把原始的输入空间映射为特征空间，使原始非线性的输入空间转变为线性可分的特征空间，并在特征空间进行线性分类。再由上面可知，SVM只与$x$的内积有关，此时的$x$在特征空间，而且只与当前所有样本点的特征向量的内积有关，故提出了一种核函数的方法

输入空间为$\mathcal{X}$，特征空间为$\mathcal{H}$，而SVM的输入是在特征空间中，原始输入空间非线性问题被映射为了一个特征空间成为一个线性可分问题，设映射为$\phi(x):\mathcal{X}\rightarrow \mathcal{H}$，然而特征空间有可能是非常高的维度或者是无穷维，故提出了一种核函数的方法能够用输入空间中的函数的形式来表示在特征空间中的内积

$$K(x,z) = <\phi(x), \phi(z)>$$

这样就能只需要显式的定义核函数$K$，而不需要显式的再定义具体的映射$\phi$，我们都知道SVM通过把样本映射到高维空间，使其变成一个线性可分，如果直接按照原始形式在高维特征空间进行求解，那么参数$w$的维度也很大，而对偶内积的形式所求解的参数数量只与样本量相等，相当于每一个样本构成了一个约束，而由特征空间内积引发的核函数使特征空间中的内积变成了一个输入空间中函数的形式，使得不必映射到高维空间也仍然能达到相同的效果。

但需要特别注意的一个问题是，SVM的核方法把输入样本映射为高维的特征空间，在高维空间中如何保证算法的有效性，如何分析其误差，这才是SVM真正的难点所在

那么优化问题就变为

$$\begin{split} & \underset{\alpha}{\min}\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^N\alpha_i \\ & s.t. \left\{\begin{split} & \sum_{i=1}^N \alpha_iy_i = 0 \\ & 0\le \alpha_i \le 0 \end{split}\right. \end{split}$$

核方法还是比较难，涉及到的理论也比较深，可扩展性很强，等我数分到达一定程度再来写核方法相关部分

SMO

现在就剩下如何对该对偶问题进行优化，这里用的是SMO（序列最小最优化算法），该方法是每次只选取两个变量进行优化，直至所有变量都满足约束条件（KKT条件）的时候即完成了优化，但这个方法需要证明收敛和等价，但好像都没有相关证明

每次只选择其中两个变量进行优化并固定其他变量，设这两个变量为$\alpha_1,\alpha_2$，根据$\sum_{i=1}^N \alpha_iy_i = 0$有

$$\alpha_1y_1 + \alpha_2y_2 = -\sum_{i=3}^N \alpha_iy_i = k \quad \text{// 其他变量固定，故$k$为常数} \\ a_1 = ky_1 - \alpha_2y_1y_2$$

那么这时该优化问题的子问题为

$$\begin{split} \underset{\alpha}{\min} W(\alpha_1,\alpha_2) & = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum_{i=1}^N\alpha_i \\ & \begin{split} = \frac{1}{2}\left\{ \sum_{i=1}^2\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) + \sum_{i=3}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) \right\} \\ -\left\{ \alpha_1 + \alpha_2 + \sum_{i=3}^Na_i \right\} \end{split} \\ & \begin{split} = \frac{1}{2}\left\{ \begin{split} \sum_{i=1}^2 & \sum_{j=1}^2\alpha_i\alpha_jy_iy_jK(x_i,x_j) + \sum_{i=1}^2\sum_{j=3}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) \\ & + \sum_{i=3}^N\sum_{j=1}^2\alpha_i\alpha_jy_iy_jK(x_i,x_j) + \sum_{i=3}^N\sum_{j=3}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j) \end{split} \right\} \\ -\left\{ \alpha_1 + \alpha_2 + \sum_{i=3}^Na_i \right\} \end{split} \\ & = \frac{1}{2}\left\{ \alpha_1^2K_{11} + \alpha_2^2K_{22} + 2\alpha_1\alpha_2y_1y_2K_{12} + 2\alpha_1y_1v_1 + 2\alpha_2y_2v_2 \right\} - \{\alpha_1+\alpha_2\} + Constant \\ & = \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_2v_2 - \alpha_1 - \alpha_2 + Constant \end{split}$$

这里有

$$v_1 = \sum_{j=3}^N\alpha_jy_jK_{1j} \\ v_2 = \sum_{j=3}^N\alpha_jy_jK_{2j}$$

把$\alpha_1 = ky_1 - \alpha_2y_1y_2$代入原式得

$$\begin{split} W(\alpha_2) & = \frac{1}{2} (ky_1 - \alpha_2y_1y_2)^2K_{11} + \frac{1}{2}\alpha_2^2K_{22} + (ky_1 - \alpha_2y_1y_2)\alpha_2y_1y_2K_{12} \\ & + (ky_1 - \alpha_2y_1y_2)y_1v_1 + \alpha_2y_2v_2 - (ky_1 - \alpha_2y_1y_2) - \alpha_2 + Constant \end{split}$$
求偏导
$$\begin{split} \frac{\partial W}{\partial \alpha_2} = \alpha_2K_{11} - ky_2K_{11} + \alpha_2K_{22} + ky_2K_{12} - 2\alpha_2K_{12} \\ + y_2v_1 + y_2v_2 + y_1y_2 - 1 = 0 \\ \end{split}$$
$$\begin{split} \alpha_2 & = \frac{1-y_1y_2 + ky_2K_{11} - ky_2K_{12} + y_2v_1 - y_2v_2}{K_{11}+K_{22}-2K_{12}} \\ & = \frac{y_2(y_2-y_1 + kK_{11} - kK_{12} + v_1 - v_2)}{K_{11}+K_{22}-2K_{12}} \end{split}$$

这里可以进一步化简，有

$$\begin{split} f(x_1) & = w\cdot x_1 + b \\ & = \sum_{i=1}^N\alpha_iy_iK_{1i} + b \\ & = \alpha_1y_1K_{11} + \alpha_2y_2K_{12} + \sum_{i=3}^N \alpha_iy_iK_{1i} + b \\ & = \alpha_1y_1K_{11} + \alpha_2y_2K_{12} + v_1 + b \\ & = (ky_1 - \alpha_2y_1y_2)y_1K_{11} + \alpha_2y_2K_{12} + v_1 + b \\ & = kK_{11} - \alpha_2y_2K_{11} + \alpha_2y_2K_{12} + v_1 + b\\ f(x_2) & = kK_{12} - \alpha_2y_2K_{12} + \alpha_2y_2K_{22} + v_2 + b \\ \end{split}$$
$$f(x_1) - f(x_2) = kK_{11} - kK_{12} - \alpha_2y_2(K_{11} + K_{22} - 2K_{12}) + v_1 - v_2$$
代入上式得
$$\begin{split} \alpha_2 & = \frac{y_2(y_2-y_1 + f(x_1) - f(x_2) + \alpha_2y_2(K_{11} + K_{22} - 2K_{12}))}{K_{11} + K_{22} - 2K_{12}} \\ & = \alpha_2^{old} + \frac{y_2(f(x_1)-y_1 - (f(x_2) - y_2))}{K_{11} + K_{22} - 2K_{12}} \\ & = \alpha_2^{old} + \frac{y_2(E_1-E_2)}{K_{11} + K_{22} - 2K_{12}} \quad //E_i = f(x_i) - y_i \end{split}$$
$E_i$表示的是函数值与真值的差值

根据约束裁剪$\alpha_2$

接下来是根据上文中的约束条件对上式求得的$\alpha_2$进行裁剪
有上文可知$\alpha_1,\alpha_2$需要满足的约束为

$$\left\{\begin{split} & \alpha_1y_1 + \alpha_2y_2 = k\\ & 0 \le \alpha_1,\alpha_2\le C \end{split}\right.$$

上式第一个约束条件把$\alpha_1,\alpha_2$约束在了平行于正方形对角线的一条线段上，这时分为两种情况

由图很容易得出

• $y_1 \neq y_2$： $$\left\{\begin{matrix} L = \max(0, \alpha_2^{old} - \alpha_1^{old}) \\ H = \min(C, \alpha_2^{old} - \alpha_1^{old} + C) \end{matrix}\right.$$
• $y_1 = y_2$： $$\left\{\begin{matrix} L = \max(0, \alpha_2^{old} + \alpha_1^{old} - C) \\ H = \min(C, \alpha_2^{old} + \alpha_1^{old}) \end{matrix}\right.$$

故经过裁剪后的$\alpha_2$为

$$\alpha_2^{new} = \left\{\begin{matrix} H & \alpha_2^{new,unc} > H \\ \alpha_2^{new,unc} & L\le \alpha_2^{new, unc}\le H \\ L & \alpha_2^{new, unc} < L \end{matrix}\right.$$

由此有

$$\begin{split} \alpha_1^{new} & = ky_1 - y_1y_2\alpha_2^{new} \\ & = (\alpha_1^{old}y_1 + \alpha_2^{old}y_2)y_1 - y_1y_2\alpha_2^{new} \\ & = \alpha_1^{old} + y_1y_2(\alpha_2^{old} - \alpha_2^{new}) \end{split}$$

接下来需要根据更新后的$\alpha_1, \alpha_2$的值更新$b$，前面提到，$b$更新依赖需要有一个位于决策边界的点才行，也就是说要有一个$\alpha_i$满足$0<\alpha<C$，故这时需要判断求得的$\alpha_1$和$\alpha_2$是否满足条件

当$0<\alpha_1<C$时，

$$\begin{split} y_1 & = w_1^*\cdot x_1 + b_1^* \\ & = \sum_{i=1}^N \alpha_i^{new}y_iK_{1i} + b_1^{new} \\ & = \alpha_1^{new}y_1K_{11} + \alpha_2^{new}y_2K_{12} + \sum_{i=3}^N\alpha_iy_iK_{1i} + b_1^{new} \\ b_1^{new} & = y_1 - \alpha_1^{new}y_1K_{11} - \alpha_2^{new}y_2K_{12} - \sum_{i=3}^N\alpha_iy_iK_{1i} \end{split}$$

由前面可知，$\alpha_i$的更新依赖于$E_i$，故$E$依赖于上次迭代的$\alpha$，故需要用$\alpha_1^{old}$和$b^{old}$

$$\begin{split} E_1 & = f(x_1) - y_1 \\ & = \sum_{i=1}^N \alpha_i^{old}y_iK_{1i} + b^{old} - y_1 \\ & = \alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{12} + \sum_{i=3}^N\alpha_iy_iK_{1i} + b^{old} - y_1 \end{split}$$

可得到

$$y_1 - \sum_{i=3}^N \alpha_iy_iK_{1i} = \alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{12} + b^{old} - E_1$$

代入上式得

$$\begin{split} b_1^{new} & = \alpha_1^{old}y_1K_{11} + \alpha_2^{old}y_2K_{12} + b^{old} - E_1 - \alpha_1^{new}y_1K_{11} - \alpha_2^{new}y_2K_{12} \\ & = y_1K_{11}(\alpha_1^{old} - \alpha_1^{new}) + y_2K_{12}(\alpha_2^{old} - \alpha_2^{new}) - E_1 + b^{old} \end{split}$$

当$0<\alpha_2<C$时，同理得

$$\begin{split} b_2^{new} = y_1K_{12}(\alpha_1^{old} - \alpha_1^{new}) + y_2K_{22}(\alpha_2^{old} - \alpha_2^{new}) - E_2 + b^{old} \end{split}$$

故当$\alpha_1$和$\alpha_2$同时满足$0<\alpha_i<C$时$b_1^{new} = b_2^{new}$，而当$\alpha_1$和$\alpha_2$同时取$0$或$C$时，书上说$b_1^{new}$和$b_2^{new}$都是符合KKT条件的阈值，这时选择他们的中点$b^{new} = \frac{b_1^{new} + b_2^{new}}{2}$，但不知道为啥

最后再更新E的值

$$E_i^{new} = \sum_{j=1}^N\alpha_j^{new}y_jK_{ij} + b^{new} - y_i$$

书上说这里用的是所有支持向量，但非支持向量的$\alpha_i=0$，故效果相同

终止条件

终止条件是让SVM不再变化并且尽量满足KKT条件，这里加了一个KKT条件的阈值，就是SVM中常见的$tol$，在判断KKT条件时只要满足$\varepsilon$范围内即可，其在一定程度上控制了SVM的最终精度和运行时间。另外一个常见的是eps，其控制每次$\alpha_2$的变化量的阈值？

这样迭代过程为，每次先找到一个不满足$\varepsilon$-KKT的变量，然后再找另外一个变量来执行子优化过程，当遍历完成一遍整个数据集，找不到这样的变量对时结束

过程如下

$i = \underset{i}{\arg\max}|E_i - E_j|$是为了让第二个变量$\alpha_i$能够有最大的变化，因为

$$\alpha_2^{new} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{K_{11} + K_{22} - 2K_{12}}$$

这个地方原始论文上说只让$|E_1-E_2|$最大，因为核$K$的计算需要花费时间，但这里我们预先把所有样本点的核矩阵保存起来了，这个地方个人认为可以改为

$$i = \underset{i}{\arg\max}\left|\frac{E_i - E_j}{K_{11} + K_{22} - 2K_{12}}\right|$$

---

SVM的原始思想还是非常简单的，但伴随其的数学方法却很有难度，其把一种很简单的思想转换成了一种数学问题一种求解优化问题，并完美的把核方法带入进去

最后的SVM另外重要的一块是其误差分析，和核方法的误差分析，这部分等我把统计学习理论搞懂了再来写:>

Reference

• Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines
• 《统计学习方法》
• Implementing a Support Vector Machine using Sequential Minimal Optimization and Python 3.5