前言

最近看了Andrew Ng的机器学习视频中的支持向量机，视频的内容比较浅显，没有深入解释支持向量机中的数学原理。但是对于一个比较执着于知道为什么的人，笔者还是去网上查找了有关支持向量机原理以及实现的相关资料。在查找的过程中，笔者发现支持向量机的内容还是蛮多的，于是笔者根据自己的理解，并且参考了一些相关资料，最终写下了支持向量机的四篇博客。
机器学习：支持向量机(SVM)与Python实现第(一)篇——此篇主要介绍了分类间隔，引入SVM。
机器学习：支持向量机(SVM)与Python实现第(二)篇——此篇主要介绍了使用拉格朗日乘子来简化SVM问题的优化。
机器学习：支持向量机(SVM)与Python实现第(三)篇——此篇主要介绍非线性分类(核函数)以及松弛变量。
机器学习：支持向量机(SVM)与Python实现第(四)篇——此篇主要介绍SMO算法并用python实现了简单的SVM分类器。

核函数

前面我们介绍了很多东西，但一直都是基于数据是线性可分的。那么对于那些非线性的数据呢？

比如上面的图，数据显然不是线性可分的(事实上得用圆来作边界)。我们知道二次曲线方程(圆是特殊的二次曲线)一般可以写成：
$$\begin{aligned}w_1x_1^2+w_2x_2^2+w_3x_1x_2+w_4x_1+w_5x_2+w_6=0\end{aligned}$$ 在这里我们的特征变量可以写成：
$$\begin{aligned}\phi (x)=\begin{bmatrix}x_1^2\\ x_2^2\\ x_1x_2\\ x_1\\ x_2\end{bmatrix}\end{aligned}$$ 回顾以前的输入是向量x，现在由于是非线性的，所以我们的输入映射成$\phi(x)$，也就是为了使用之前博文说的算法，要把向量x替换成$\phi(x)$。

但是我们注意到一个问题，就是上一篇博文最后推导出来的式子中，x都是以内积的形式存在的，即$\left \langle x^{T},z \right \rangle$的形式。现在我们替换成了$\phi(x)$，就会变成$\left \langle \phi(x)^{T},\phi(z) \right \rangle$。具体一点，我们定义这个内积为:
$$K(x,z)=\left \langle \phi(x)^{T},\phi(z) \right \rangle$$ 所以上一篇博文最后推导出来的内积都可以用$K(x,z)$替换。也就是：
$$\begin{aligned}\underset{\alpha}{max}\ &W(\alpha)=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}y^{(i)}y^{(j)}\alpha_i\alpha_j \left \langle x^{T},x \right \rangle\\s.t\ \ &\alpha_i\geq 0,\ i=1,...,m\\&\sum_{i=1}^{m}\alpha_iy^{(i)}=0\end{aligned}$$
这个优化问题可以替换成：
$$\begin{aligned}\underset{\alpha}{max}\ &W(\alpha)=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}y^{(i)}y^{(j)}\alpha_i\alpha_j K(x,z)\\s.t\ \ &\alpha_i\geq 0,\ i=1,...,m\\&\sum_{i=1}^{m}\alpha_iy^{(i)}=0\end{aligned}$$ 这样问题好像解决了，一旦遇到非线性的分类，就去找一个映射，然后替换掉内积部分，就可以了。然而，这里有一个问题，就是维度呈指数型增长，上面二维空间就得映射成五维，三维空间就得映射成十九维。这样的话，计算量就会非常大。所以这样是行不通的。必须寻找另外的方法。

让我们来看一个例子，假设$x=(x_1,x_2),\ z=(z_1,z_2)$。考虑：
$$K(x,z) = (x^Tz)^2$$ 将其展开得到：
$$\begin{aligned}K(x,z) &=x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2\\&=\sum_{i,j=1}^{2}(x_ix_j)(z_iz_j)\end{aligned}$$ 而如果：
$$\begin{aligned}\phi(x)=\begin{bmatrix}x_1x_1\\ x_1x_2\\ x_2x_2\end{bmatrix}\end{aligned}$$ 那么，
$$K(x,z)=\left \langle \phi(x)^{T},\phi(z) \right \rangle =x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2$$
另外如果注意到：
$$K(x,z) = (x^Tz+1)^2==x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2+2x_1z_1+2x_2z_2+1$$ 同样，映射成：
$$\begin{aligned}\phi(x)=\begin{bmatrix}x_1x_1\\\sqrt{2}x_1\\ \sqrt{2}x_2\\ x_1x_2\\ x_2x_2\\1\end{bmatrix}\end{aligned}$$ 你会发现这与内积$\left \langle \phi(x)^{T},\phi(z) \right \rangle$的结果是一样的。也就是说，如果我们写成$K(x,z) = (x^Tz+1)^2$的形式，我们就不用映射成$\phi(x)$。这样就没有维度爆炸带来的后果了。

核函数的选择

现在我们来看两个直观的效果。核函数我们写成内积的形式：$K(x,z)=\left \langle \phi(x)^{T},\phi(z) \right \rangle$。如果内积之后的值很大，那么说明$\phi(x)与\phi(z)$的距离比较远，反过来，如果它们的内积很小，说明这两个向量接近于垂直。所以$K(x,z)$可以来衡量$\phi(x)与\phi(z)$有多接近，或者说x与z有多接近。所以我们要如何选择核函数？如果从这个角度看，或许高斯函数是一个不错的选择：
$$\begin{aligned}K(x,z)= exp(-\frac{\left \| x-z \right \|^2}{2\sigma ^2})\end{aligned}$$ 从高斯函数的表达式中可以看到，如果x与z很接近，那么$K(x,z)$的值就比较大(接近1)，反正就比较小(接近0)。这个就被称为高斯核。

从$K(x,z) = (x^Tz+1)^2$的形式也可以看出，$K(x,z)$的值是大于0的。另外核函数也要关于y轴对称。

松弛向量与软间隔最大化

另外一个问题是松弛变量的问题。我们之前一直谈论的分类是基于数据都比较优雅易于区分的。但是如果是这样的情况呢？

左图是理想的数据集，有图会发现有一个点比较偏离正常值。它也许是一个噪点，也许是人工标记的时候标错了。但在使用SVM分类时，却会因为这个点的存在而导致分类超平面是实线那个，但是一般来说，我们都知道虚线那个分类超平面是比较合理的。那么我们应该怎么做呢？

为了处理这种情况，我们允许数据点在一定程度上偏离超平面。

所以我们重新罗列出我们的优化问题：
$$\begin{aligned}& \underset{\gamma,w,b}{min} \ \frac{1}{2}\left \| w \right \|^2+C\sum_{i=1}^{m}\xi _i \\&s.t.\ \ y^{(i)}(w^{T}x^{(i)}+b)\geq 1-\xi _i,\ i=1,...,m\\&\xi _i\geq 0,\ i=1,...,m\end{aligned}$$ 这样我们就允许一些点的间距小于1了。并且如果有些点的间距为$1-\xi _i$，我们就会给目标函数一些惩罚，即增加了$C\xi _i$。于是我们重新写下新的拉格朗日函数：
$$\begin{aligned}L(w,b,\xi,\alpha,r)=\frac{1}{2}w^Tw+C\sum_{i=1}^{m}\xi _i-\sum_{i=1}^{m}\alpha_i[y^{(i)}(x^Tw+b)-1+\xi_i]-\sum_{i=1}^{m}r_i\xi_i\end{aligned}$$ 其中，$\alpha_i与r_i$是拉格朗日乘子(都大于0)。经过相同的推导，我们会得到：
$$\begin{aligned}\underset{\alpha}{max}\ &W(\alpha)=\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i,j=1}^{m}y^{(i)}y^{(j)}\alpha_i\alpha_j \left \langle x^{(i)}, x^{(j)}\right \rangle\\s.t\ \ & 0\leq \alpha_i\leq C,\ i=1,...,m\\&\sum_{i=1}^{m}\alpha_iy^{(i)}=0\end{aligned}$$ 所以现在，加上松弛变量，我们的问题就变成上面那样了。接下来就是如何写代码来实现训练了。