机器学习

发布日期: 2017-11-27

文章字数: 4.8k

我关于SVM的一点理解

前言

最近两天因为要用到SVM所以比较深入的了解了一下这个算法，查阅了很多资料，发现很多大牛的作品，比如pluskid的支持向量机系列（听说他后来去了MIT），还有邵正将的SVM系列，台大林轩田老师的机器学习基石（之前就学习过又把它复习了一遍）以及Andrew Ng的cs229 lecture notes 3，加深了我对于SVM的理解，以及了解到我跟这些大牛之间的差距是那么那么那么的大，我对于机器学习的认识是那么那么那么的浅薄，未来的路还很漫长，希望自己能够静下心去求索。

其实之前在林轩田老师的机器学习基石中就已经学习过SVM，但是并没有讲到如何求解SVM，因为自己的一个科研项目需要手撸出SVM，所以就更为深入的学习了一波，掌握了针对SVM问题求解的SMO(Sequential Minimal Optimization)算法，并且参照机器学习实战动手把代码撸了出来，好了废话不多说，接下来进入正题。

1.SVM基础

SVM(support vector machine),中文翻译过来叫支持向量机，一开始听到这个名字我就纳闷啥叫支持向量，又是个什么机器呢？且听我慢慢道来，这个名字的命名是有原因的。

试想一个二分类问题：

上面哪个是更好的分类线？首先我们要明确什么是一个好的分类线：
1.可以容忍更多的噪音。
2.更健壮，不易于过拟合。
综合来说，第三个图上的分类线是更好的分类线，因为离这条线最近的x和o点的距离相对于其他两条线是更大的，这就可以容纳更多的噪音同时模型也更加健壮。

这一节我们考虑的都是二分类问题，只有两个label,为了方便处理，我们将这两个label设置为1和-1（为什么要这样设置将在下面解释）。我们考虑的也是多维的非线性模型，可能这刚上来就整一个多维的非线性模型会使人感到害怕，但其实并不可怕，因为非线性可以转化为线性，而多维只不过就多了几个维度而已，所有的推导过程都是一样的。

比如说二维空间上的点:$(x_1,x_2)$, 在二维线性空间上进行二分类，也就是寻找$y=w_1x_1+w_2x_2+b$中的$w_1,w_2,b$使得对于任意一点代入这个模型求出的$y$和它的label是同正负的，也就是$y_i(\vec{w} \cdot \vec{x_i}+b)\geq 0 \ (i=1,2…..n)$。那么如何在二维空间上进行构造非线性模型呢？我们可以将二维升维:$(x_1,x_2,x_1x_2,x_1^2,x_2^2)$,这样就是一个五维空间，现在就在这个五维空间构建线性模型就ok了。

上面只是考虑建立一个二分类模型，那么如何在此之上建立二分类的SVM模型呢？SVM模型的目标是在分类正确的基础之上，最大化距离分类线最近的正负类点到分类线的距离。那么如何求解多维空间上点到面的距离？根据线性代数中所学的知识，任意一点$\rm{x_i}$到超平面$\vec{w} \cdot \vec{x}+b=0$的y的有向距离$d$为$$d = \frac{ \vec{w} \cdot \rm{x_i}+b }{\mid\mid\vec{w}\mid\mid}$$

那么我们的目标就是使$$\frac{y_i ( \vec{w} \cdot \rm{x_i}+b )} {\mid\mid\vec{w}\mid\mid} \ \ (i=1,2,3,…n) \geq 0$$即每个点的标签和这个点到超平面的有向距离是同号的。

令$$margin(b,\vec{w}) = \min_{i=1,2..n} \frac{y_i ( \vec{w} \cdot \rm{x_i}+b )} {\mid\mid\vec{w}\mid\mid}$$

我们的目标就是 $$max \ margin(b,\vec{w})$$并且对任意 $i$ 满足$$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 0$$

我们可以改变 $\vec{w}$ 和 $b$ 的倍数使得 $ \vec{w} \cdot \rm{x_i}+b$ 取到任意的值但是有向距离并不变化，出于对问题的简化，不管怎样我们可以找到一个$\vec{w}$ 和 $b$ 使得 $$\min_{i=1,2..n} \ y_i ( \vec{w} \cdot \rm{x_i}+b)= 1$$ 所以就有$$margin=\frac{1}{\mid\mid\vec{w}\mid\mid}$$

现在问题转化为 $$max = \frac{1}{\mid\mid\vec{w}\mid\mid}$$并且对任意 $i$ 满足 $$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1$$

为了求解的方便进一步转化这个问题：$$min \ \frac{1}{2} {\mid\mid\vec{w}\mid\mid}^2$$ 并且对任意 $i$ 满足 $$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1$$

2.SVM对偶问题

上面问题的求解看起来比较麻烦，我们要寻找对于任意 $i$ 在满足 $y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1$ 情况下 $\ \frac{1}{2} {\mid\mid\vec{w}\mid\mid}^2$ 的最小值，这是有不等式约束条件下的最值问题，我们可以将其转化为Lagrange函数求解

令 $$L(\vec{\alpha},\vec{w},b) = \frac{1}{2} {\mid\mid\vec{w}\mid\mid}^2\ + \sum_{i=1}^n {\alpha}_i [1- y_i ( \vec{w} \cdot \rm{x_i}+b ) ]$$
其中 $$\forall \ {\alpha}_i \ (i=1,2…n), {\alpha}_i \geq 0 $$

原问题转化为：寻找 ${\alpha}_i (i=1,2…n)$使得：$$\min \limits_{b,\vec{w}} \ \max \limits_{\vec{\alpha}} L(\vec{\alpha},\vec{w},b) $$
subject to $$\forall \ {\alpha}_i \ (i=1,2…n), {\alpha}_i \geq 0 $$

为什么原问题可以转化成这样？似乎那个令人烦恼的不等式条件不需要了？仔细想想，发现不等式条件其实隐藏在这个 $$\min \limits_{b,\vec{w}} \ \max \limits_{\vec{\alpha}} L(\vec{\alpha},\vec{w},b) $$条件中了，假设存在一个 $i$ 使得 $1 - y_i ( \vec{w} \cdot \rm{x_i}+b) \geq 0$，那么为了使 $L(\vec{\alpha},\vec{w},b)$ 最大，${\alpha}_i$ 可以趋于无限大整个式子也会趋于正无穷，这样就无法求出$$\min \limits_{b,\vec{w}} \ \max \limits_{\vec{\alpha}} L(\vec{\alpha},\vec{w},b) $$所以为了使得该式能够求出最小值，$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1$ 必然满足

假设我们最终求出了这样一组 ${\alpha}_i$
若对于其中一个 $i$, ${\alpha}_i >0$ ,则有 $1- y_i ( \vec{w} \cdot \rm{x_i}+b ) = 0$ ,所以这个$\rm{x_i}$ 是支持向量
若对于其中一个 $i$, ${\alpha}_i =0$ ,这个$\rm{x_i}$就不是支持向量

然而问题转化到了这一步看起来还是不容易求解，我们可以换个思路，转化为它的对偶问题，用对偶问题的最优解来代替原问题的最优解（实际上这两个解是相等的，因为我们求解的这个 $L$ 和 $1- y_i ( \vec{w} \cdot \rm{x_i}+b )$ 是凸函数而且由于这个是线性可分的情况所以函数必有最优解）。

那么问题转化为：$$ \max \limits_{\vec{\alpha}} \min \limits_{b,\vec{w}} \ L(\vec{\alpha},\vec{w},b) $$ subject to $$\forall \ {\alpha}_i \ (i=1,2…n), {\alpha}_i \geq 0 $$

这个问题就完全ojbk了，分别对 $b$ 和 $ \vec{w}$ 求偏导:$$\frac{\partial{L}}{\partial{b}}=0 \implies \sum_{i=1}^n {\alpha}_i y_i=0$$ $$\frac{\partial{L}}{\partial{\vec{w}}}=\vec{0} \implies \vec{w}= \sum_{i=1}^n {\alpha}_i y_i \vec{x_i}$$

$$\min_{b,\vec{w}} \ L(b,\vec{w},\vec{\alpha}) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j \vec{x_i} \cdot \vec{x_j}$$

最终问题转化为：$$\max_{\vec{\alpha}}\sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j \vec{x_i} \cdot \vec{x_j}$$
subject to $$\forall \ {\alpha}_i \ (i=1,2…n), {\alpha}_i \geq 0 $$

3.SVM软间隔

然而并非所有的数据都是线性可分的：

对于上述的数据点，永远无法找到一维线性模型完全将其分开。也许你会想一维不可以，我们完全可以通过升高维度来分开这些数据点嘛，但是这样做会有过拟合的风险，因为我们的数据看上去就是线性可分的，少数几个点只是噪音(outliners)。我们想忽略这几个噪音，尽量用最简单的模型去分类。

那么问题来了，我们怎么处理这些outliners呢？
我们可以引入松弛变量 ${\xi}_i \geq 0$ ,允许有间隔小于1的点存在:
$$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1-{\xi}_i \ \ (i=1,2…n)$$
同时我们也需要限制 ${\xi}_i$ 的大小，防止我们划分的太宽泛。

问题转化为：$$\min_{\vec{w}, \vec{\xi}} \left[ \frac{1}{2} {\mid\mid\vec{w}\mid\mid}^2 + C\sum_{i=1}^n\xi_i \right] \ \ \ \ \ \ \ \ (3.1)$$
subject to $$y_i ( \vec{w} \cdot \rm{x_i}+b ) \geq 1-{\xi}_i \ \ (i=1,2…n)$$

$${\xi}_i \geq 0$$

C是一个可调节大小的参数（初始时固定）,那么定性的考虑一下：

当C设置的比较大时，为了使3.1式最小 $\xi_i$ 要尽可能小一点，这样在margin外的点到margin的距离也会减小，所以会使得margin比较窄，尽可能分类正确更多的点。
当C设置的比较小时，这样 $\xi_i$ 会比较大，$1-\xi_i$ 会是一个很小的负数，容错性好

这也是一个带有不等式约束条件的问题，仿照上面的做法，引入$L(\vec{w},b,\vec{\alpha}, \vec{\beta},\vec{\xi})$：
$$L(\vec{w},b,\vec{\alpha}, \vec{\beta},\vec{\xi}) = \frac{1}{2} {\mid\mid\vec{w}\mid\mid}^2 + C\sum_{i=1}^n\xi_i + \sum_{i=1}^n {\alpha}_i [1- \xi_i-y_i ( \vec{w} \cdot \rm{x_i}+b )] + \sum_{i=1}^n \beta_i(-\xi_i)$$

$$\forall \ {\alpha}_i,{\beta}_i, {\xi}_i \ (i=1,2…n), {\alpha}_i,{\beta}_i, {\xi}_i \geq 0 $$

现在的问题是求解$$\min \limits_{b,\vec{w},\vec{\xi}} \ \max \limits_{\vec{\alpha} ,\vec{\beta}} L(\vec{w},b，\vec{\alpha},\vec{\beta},\vec{\xi}) $$
subject to $$\forall \ {\alpha}_i,{\beta}_i, {\xi}_i \ (i=1,2…n), {\alpha}_i,{\beta}_i, {\xi}_i \geq 0 $$

同样的，可以将其转化为它的对偶问题求解：
$$\min \limits_{b,\vec{w},\vec{\xi}} \ \max \limits_{\vec{\alpha} ,\vec{\beta}} L(\vec{w},b，\vec{\alpha},\vec{\beta},\vec{\xi}) \implies \ \max \limits_{\vec{\alpha} ,\vec{\beta}}\min \limits_{b,\vec{w},\vec{\xi}} L(\vec{w},b，\vec{\alpha},\vec{\beta},\vec{\xi})$$

然后再分别对$b$ , $\vec{w}$ 和 $\vec{\xi}$ 求偏导:
$$\frac{\partial{L}}{\partial{b}}=0 \implies \sum_{i=1}^n {\alpha}_i y_i=0$$
$$\frac{\partial{L}}{\partial{\vec{w}}}=\vec{0} \implies \vec{w}= \sum_{i=1}^n {\alpha}_i y_i \vec{x_i}$$
$$\frac{\partial{L}}{\partial{\vec{\xi}}}=\vec{0} \implies \vec{C}-\vec{\alpha}-\vec{\beta}=\vec{0} \implies \beta_i = C-\alpha_i \ \ (i=1,2…n) \implies 0 \leq \alpha_i \leq C \ \ (i=1,2…n)$$

将上面求出的关系式代入:
$$\min \limits_{b,\vec{w},\vec{\xi}} L(\vec{w},b，\vec{\alpha},\vec{\beta},\vec{\xi}) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j \vec{x_i} \cdot \vec{x_j}$$

令$$W(\vec{\alpha} ) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j \vec{x_i} \cdot \vec{x_j}$$

原问题变成求解:
$$\max_{\vec{\alpha}} W(\vec{\alpha})$$
subject to
$$0 \leq \alpha_i \leq C \ \ \ \ (i=1,2…n)$$

$$\sum_{i=1}^n {\alpha}_i y_i=0$$

4.SVM核函数

现在来思考这样一个问题：
对于一个 $d$ 维空间上的点 $\vec{x}=(x_1,x_2,…x_d)$ ,将它转换为二次SVM，变成 $\hat{d}$ 维:
$$\Phi_2(\vec{x})=(x_1,x_2,…x_d,x_1x_2,…x_1x_d,…,x_1^2,x_2^2,…x_d^2)$$

如果按照之前的步骤直接求下去最终会在 $W(\vec{\alpha})$ 中遇到计算 ${\Phi_2(\vec{x_i})} \cdot \Phi_2(\vec{x_j})$，计算这个式子比较复杂，有没有什么简单的办法？

观察一下可以计算出
$${\Phi_2(\vec{x_i})} \cdot \Phi_2(\vec{x_j}) = 1+ \sum_{m=1}^d x_{im} x_{jm} + \sum_{m=1}^d \sum_{n=1}^d x_{im} x_{in} x_{jm} x_{jn} \\ = 1 + {\vec{x_i}}^\top \cdot \vec{x_j} + ({\vec{x_i}} \cdot \vec{x_j})({\vec{x_i}} \cdot \vec{x_j})$$

这个结果很激动人心了，我们将原来是 $\hat{d}$ 维相乘的问题转化成了 $d$ 维相乘，只要求出 ${\vec{x_i}} \cdot \vec{x_j}$ 计算 ${\Phi_2(\vec{x_i})} \cdot \Phi_2(\vec{x_j})$ 就轻而易举了。

令 $$K_{\Phi_2}({\vec{x_i},\vec{x_j}}) = 1 + {\vec{x_i}} \cdot \vec{x_j} + ({\vec{x_i}} \cdot \vec{x_j})({\vec{x_i}} \cdot \vec{x_j})$$

这里的 $K_{\Phi_2}({\vec{x_i},\vec{x_j}})$ 就叫做核函数(kernel function) ,将原来的一个复杂的 $\hat{d}$维内积变成 $d$ 维内积 ,有了这个kernel function 计算复杂度大大降低，同样的我们也可以将它推广到n次SVM，都是有类似的kernel存在的

这里再提一下高斯核(Gaussian Kernel):
$$K_G(\vec{x_i},\vec{x_j})={\rm{e}}^{-\gamma\mid\mid\vec{x_i}-\vec{x_j}\mid\mid} \ \ \ \ (\gamma > 0)$$
如何理解这个kernel?它相当于是 $d$ 维上的无穷次SVM问题

5.SMO算法求解SVM问题

回到我们的SVM问题上:
$$\max_{\vec{\alpha}} W(\vec{\alpha})$$
subject to
$$0 \leq \alpha_i \leq C \ \ \ \ (i=1,2…n)$$

$$\sum_{i=1}^n {\alpha}_i y_i=0$$

如何求解这个问题？platt在1996年提出了一个叫做SMO(Sequential Minimal Optimization)的算法，翻译过来就是序列最小化，SMO算法是将一个大的优化问题(需要优化 $\alpha_1,\alpha_2,…,\alpha_n$ 这n个参数)分解为多个小优化问题进行求解的(每次只优化两个不同的 $\alpha$)，这些小优化问题求解起来就简单多了，而且可以证明将它进行多次小优化的结果和作为整体优化的结果是完全一致的。

为什么整体优化和小优化最终殊途同归了？我们可以简单地定性地证明一下：
考虑这样一个问题，求 $$\max_{\vec{x}} f(x_1,x_2,…x_n)$$

对于这个问题，我们当然可以对每个 $x_i$ 求偏导得出它的梯度，然后从任意一点沿着梯度方向移动，最终会走到梯度为0的那一点，也就是最大值点。
但是傲娇的我并不想每次都对全部的这些 $x_i$ 求偏导呢？我们就可以固定任意除 $x_i$ 之外n-1个维度上的坐标，对 $x_i$ 求偏导，我们可以得到在给定除 $x_i$ 之外n-1个维度上的坐标值的情况下的 $f(\vec{x})$ 的最大值，然后继续按照这个步骤，每次只优化任意一个 $x_i$ 而固定其他值，最终我们也可以得到在n维上 $f(\vec{x})$ 的最大值

继续回到SVM问题的求解，同样的，我们可以优化一个任意的 $\alpha_i$ 而固定其他值，但是眉头一皱发现事情并没有想象中的那么简单，我们是不是还有一个约束条件没考虑啊? $$\sum_{i=1}^n {\alpha}_i y_i=0$$

这个约束条件必须考虑进去，那么我们可以变化 $\alpha_1,\alpha_2$这两个值，固定 $\alpha_3,\alpha_4,…\alpha_n$

我们之前定义的 $W(\vec{\alpha})$:
$$W(\vec{\alpha} ) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j \vec{x_i} \cdot \vec{x_j}$$

现在我们考虑把kernel放进去，$$W(\vec{\alpha} ) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j K(\vec{x_i},\vec{x_j})$$
为了写起来方便，令$$K_{ij}=K(\vec{x_i},\vec{x_j})$$
可以发现 $K_{ij}=K_{ji}$
那么就有:
$$W(\vec{\alpha} ) = \sum_i^n \alpha_i - \frac{1}{2} \sum_i^n \sum_j^n \alpha_i \alpha_j y_i y_j K_{ij}$$

现在我们固定 $\alpha_3,\alpha_4,…\alpha_n$ 只变化 $\alpha_1,\alpha_2$这两个值:
$$W(\alpha_1,\alpha_2)= \alpha_1 + \alpha_2 - \frac{1}{2}K_{11}y_1^2{\alpha_1}^2 - \frac{1}{2}K_{22}y_2^2{\alpha_2}^2 - K_{12}y_1y_2\alpha_1\alpha_2 - y_1\alpha_1 \sum_{i=3}^n\alpha_iy_iK_{i1}- y_2\alpha_2 \sum_{i=3}^n\alpha_iy_iK_{i2} + C_1$$
这里的 $C_1$ 是与 $\alpha_1, \alpha_2$ 无关的常数项。

subject to :
$$\alpha_1y_1+\alpha_2y_2 = -\sum_{i=3}^n \alpha_iy_i $$
令$$-\sum_{i=3}^n \alpha_iy_i = \zeta$$

那么可以得到:
$$\alpha_1 = \zeta y_1-\alpha_2 y_1y_2$$

令
$$v_1 = -\sum_{i=3}^n \alpha_iy_i K_{i1}$$
$$v_2 = -\sum_{i=3}^n \alpha_iy_i K_{i2}$$
$$\implies W(\alpha_2) = -\frac{1}{2}K_{11}{(\zeta-\alpha_2y_2)}^2-\frac{1}{2}K_{22}{\alpha_2}^2-y_2(\zeta-\alpha_2y_2)\alpha_2K_{12} - v_1(\zeta-\alpha_2y_2)-v_2y_2\alpha_2+\alpha_1+\alpha_2 + C_1$$

$$\frac{\partial{W(\alpha_2)}}{\partial{\alpha_2}} = -(K_{11}+K_{22}-2K_{12})\alpha_2+(K_{11}-K_{12})(\zeta y_2) + v_1y_2-v_2y_2-y_1y_2+y_2^2=0$$

上面那个 $\zeta, v_1,v_2$ 求起来还是比较麻烦的，你需要求n-3项的和，但是我们有一种更简单的办法求上式。我们之前得出$$\vec{w}= \sum_{i=1}^n {\alpha}_i y_i \vec{x_i}$$
那么对于一个 $\vec{x}$:
$$y(\vec{x}) = \vec{w} \cdot \vec{x} + b = \sum_{i=1}^n \alpha_i y_i K(\vec{x_i},\vec{x}) + b$$
$$\implies v_1 = -\sum_{i=3}^n \alpha_iy_i K_{i1} = y(x_1)-\alpha_1y_1K_{11}-\alpha_2y_2K_{12}-b$$
$$\implies v_2 = -\sum_{i=3}^n \alpha_iy_i K_{i2} = y(x_2)-\alpha_1y_1K_{12}-\alpha_2y_2K_{22}-b$$

$$\implies v_1-v_2=y(x_1)-y(x_2)-(K_{11}-K_{12})\zeta + (K_{11}+K_{22}-2K_{12})\alpha_2^{old}y_2$$

$\implies \frac{\partial{W(\alpha_2)}}{\partial{\alpha_2}} = -(K_{11}+K_{22}-2K_{12})\alpha_2^{new} + (K_{11}+K_{22}-2K_{12})\alpha_2^{old} + y_2(y_2-y_1+y(x_1)-y(x_2))$

令 $\eta$ $$\eta = K_{11}+K_{22}-2K_{12}$$
令 $E_i$ 为预测值和真实值之差：
$$E_i = y(\vec{x_i}-y_i)$$

$$\implies \frac{\partial{W(\alpha_2)}}{\partial{\alpha_2}} = -\eta \alpha_2^{new} + \eta \alpha_2^{old} +y_2(E_1-E_2)=0$$

解出$$\alpha_2^{new}=\alpha_2^{old}+\frac{y_2(E_1-E2)}{\eta}$$

这样问题是不是就结束了？咦，发现我们还有一个约束条件没有用到
$$0 \leq \alpha_i \leq C \ \ \ \ (i=1,2…n)$$
所有 $\alpha_i$ 都必须满足这约束条件

当 $y_1 \not= y_2$：综合考虑 $\alpha_1,\alpha_2$的约束得出：
$\alpha_2$ 的下界 L:$max(0,\alpha_2^{old}-\alpha_1^{new})$
上界H:$min(C,C+\alpha_2^{old}-\alpha_1^{old})$
当 $y_1 = y_2 $:
$\alpha_2$ 的下界 L: $\max(0,\alpha_1^{old}+\alpha_2^{old}-C) $
上界H:$min(C,\alpha_2^{old}+\alpha_1^{old})$

之前得出的 $\alpha_2^{new}$ 只是未经过约束条件修剪的，我们称之为 $\alpha_2^{new,unclipped}$
$$\alpha_2^{new,unclipped}=\alpha_2^{old}+\frac{y_2(E_1-E2)}{\eta}$$

结合上界L和下界H得出:
$$\alpha_2^{new}=\begin{cases} H, & \alpha_2^{new,unclipped}>H \\ \alpha_2^{new,unclipped} & L \leq \alpha_2^{new,unclipped}, \leq H \\ L, & \alpha_2^{new,unclipped}<L \end{cases}$$

$\alpha_2^{new}$ 求出后，根据 $\alpha_1^{old}y_1 + \alpha_2^{old}y_2=\alpha_1^{new}y_1+\alpha_2^{new}y_2$我们可以得到 $\alpha_1^{new}$:

$$\alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})$$

那么现在我们 $\alpha_1^{new},\alpha_2^{new},\vec{w}$ 都已经求出来了，想想还有啥没有求出来的，这个 $b$ 我们是不是一直对它不管不顾啊，那么现在我们就来求一下这个 $b$

我们分几种情况讨论:

$L < \alpha_1 < H$:
$$\implies \beta_i^{new}>0 \implies \xi_1 =0 , \ \ \ 1-\xi_1-y_1(\vec{w} \cdot \vec{x_1} + b)=0$$
$$\implies y_1(\vec{w} \cdot \vec{x_1} + b)=1$$
$$y_1 = \sum_{i=1}^n \alpha_iy_iK_{i1} +b \implies b_1^{new}=y_1-\sum_{i=3}^n \alpha_iy_iK_{i1}-\alpha_1^{new}y_1K_{11}-\alpha_2^{new}y_1K_{21}$$
$$\implies b_1^{new}=-E_1-y_1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{21}(\alpha_2^{new}-\alpha_2^{old}+b_1^{old})$$
$L < \alpha_2 < H$:同理可以得到
$$b_2^{new}=-E_2-y_1K_{12}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{22}(\alpha_2^{new}-\alpha_2^{old}+b_1^{old})$$
$L < \alpha_1 < H, L < \alpha_2 < H$ 同时满足:
$$b_1^{new}=b_2^{new}$$
$\alpha_1, \alpha_2$ 都在边界上:
$b$ 可以取在 $b_1^{new}$ 和 $b_2^{new}$ 之间的任意值，我们通常取
$$b^{new}=\frac{b_1^{new}+b_2^{new}}{2}$$

上面我们优化的是 $\alpha_1, \alpha_2$ 它们两个优化完之后，我们可以再随机选择两个 $\alpha$ ，一直到：
$$\forall i,j \ \ \ (i,j=1,2,…n) \ \ \ \ \alpha_i^{new}-\alpha_i^{old}=0, \alpha_j^{new}-\alpha_j^{old}=0 $$

那么现在整个求解的算法过程已经明确了，用代码实现就不再困难了，之前因为赶时间代码写的比较乱就先不贴出来了，等忙完这一阵子再优化优化贴上来。