机器学习十大算法之四：SVM（支持向量机）

SVM(支持向量机)

支持向量机(Support Vector Machine)是一种十分常见的分类器，曾经火爆十余年，分类能力强于NN，整体实力比肩LR与RF。核心思路是通过构造分割面将数据进行分离，寻找到一个超平面使样本分成两类，并且间隔最大。而我们求得的w就代表着我们需要寻找的超平面的系数，如下图：
机器学习十大算法之四：SVM（支持向量机）

一、超平面

1.超平面方程

一条直线方程，其中m是斜率， c是直线在y轴的截距，它的直线方程可以表示： $y = m x + c$
二维空间里面，一条直线的方程可以表示为： $A x + B y + C = 0$
三维空间里面，平面的方程可以表示为： $A x + B y + C z + D = 0$
依次推广， n维空间的超平面方程可以表示为： $A x_{1} + B x_{2} + C x_{3} + D x_{4} + E x_{5} + F x_{6} + \dots . + K = 0$
一般的对于n维空间的超平面的一般方程使用矩阵形式表示如下：

w^{T} x = 0

其中

w

和

x

是向量，

w^{T} x

是两个向量的点积。向量

w

通常被称为权重。

w, x

皆为向量，

w^{T} x + b = 0

就是

a_{1} * x_{1} + a_{2} * x_{2} + \dots a_{n} * x_{n} + b = 0

对b做统一为

x = 1

处理
因为n维空间对应的是n维坐标系，仅仅用

x 、 y 、 z

几个字母较难表示，所以此处用

x_{1} 、 x_{2} 、 x_{3} 、 \dots 、 x_{n}

来表示n维坐标系，各个维度的系数此处也可以用

w_{1} 、 w_{2} 、 w_{3} 、 \dots 、 w_{n}

来表示;

2.求数据点到超平面方程距离

由超平面方程： $w^{T} x + b = 0$
那么对于这个平面上任意两个点 $x^{i} ， x^{j}$ ，可以得到:

w^{T} x^{i} + b = 0 w^{T} x^{j} + b = 0

把上面两个点做差，可以得到

w^{T} \cdot (x^{j} - x^{j}) = 0

而

x^{j} - x^{j}

这两个点的差还是在这个平面上，所以可以得到

w^{T}

是这个超平面的一个法向量，垂直于这个超平面。
对于空间中任意一个不属于这个超平面的点

x^{1}

，它到这个超平面的距离要怎么得到呢？
参考下面点到平面的距离，只要找到法向量并投影就可以得到；
机器学习十大算法之四：SVM（支持向量机）

所以：我们可以连接点

x^{1}

和点

x^{i}

,得到

x^{1} - x^{i}

,把它与超平面的法向量

\vec{w}

做向量乘法，然后再除以法向量的长度，可以得到:

d = \frac{w^{T} (x^{1} - x^{i})}{| | w | |} - - - - - - - - - - - 又 因 为 w^{T} x^{i} + b = 0 - - - - - - - - - 可 以 得 到 如 下 距 离 算 法 - - - - - - - - - - - - - d = \frac{w^{T} x^{1} + b}{| | w | |}

这里我们没有考虑到式子的正负，因为距离都是正的，所以结合向量机本身的假设把

y_{1}

乘上去，是的上面式子永远非负，我们就得到超平面关于特征空间中某点

x^{1}

的几何间隔:

d = y^{1} \frac{w^{T} x^{1} + b}{| | w | |}

因此，在支持向量机中，对线性方程 $w^{T} x = 0$ ，样本点D到超平面的距离就有：

r = \frac{| w^{T} x + b |}{| | w | |}

所以：
（1）定义超平面(w,b)关于样本点

(x_{i}, y_{i})

的几何间隔为：

γ_{i} = y_{i} (\frac{w}{| | w | |} \cdot x_{i} + \frac{b}{| | w | |})

（2）定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点

(x_{i}, y_{i})

的几何间隔之最小值，即：

γ = min_{i = 1, 2, . . ., N} γ_{i}

二、离超平面最近的点距离超平面尽可能的远

支持向量机的最核心思想就是最大化分隔两个类的间隔，但这句话并不是很好理解。
这句话有点绕，分开三步看：
1.找到一个超平面，求出样本点到超平面的距离（上面的距离公式）
2.找到这些距离中最小的，这个最小的就是离超平面最近的点（这个只要把所有的点到平面的距离求出来就可以了）
3.使得超平面尽可能的距离这个最近的点尽量远

这个是主要疑问点，距离确定了怎么能又要求尽可能的远呢？这时候的距离不是一个定值么？其实这个可以看出一个动态的规划问题，我们假设超平面或者说支持平面是一个有n种可能函数，这n种可能都有对应的样本集D中点到n个超平面的距离的集合,我们就是从这n个超平面中选取一个能保证距离最近的点离超平面有最大值；

这样里面有涉及到一个约束问题：
1.取样本点对每一个超平面 $(w_{i}, b_{i})$ 的距离这个超平面来说最近的样本点距离 $γ_{i}$ ,找出对每一个 $(w_{i}, b_{i})$ 来说最近的 $γ_{i, m i n}$ ；
2.保证 $γ$ 是所有超平面中最小的最大值；就是找到 $γ_{i, m i n}$ 中 $i = 1, 2, 3... n$ 中的最大值；

从这两点出发就可以找到最符合要求的支持平面了；以上两点可以抽象成一个约束问题：

\begin{aligned} (1) & m a x (\frac{\hat{γ}}{| | w | |}) \\ (2) & s . t . y_{i} \cdot (\frac{w^{T} x_{i} + b}{| | w | |}) \geq \frac{\hat{γ}}{| | w | |} \end{aligned}

为了便于优化推导，我们可以令

γ = 1

\begin{aligned} (3) & m a x_{w, b} (\frac{1}{| | w | |}) \\ (4) & s . t . y_{i} \cdot (w^{T} x_{i} + b) \geq 1 \end{aligned}

对于式子（3）而言最大化

\frac{1}{| | w | |}

和最小化

\frac{1}{2} | | w | |^{2}

是等价的（为了可导便于优化）可以变成如下：

\begin{aligned} (5) & m i n_{w, b} (\frac{1}{2} | | w | |^{2}) \\ (6) & s . t . y_{i} \cdot (w^{T} x_{i} + b) \geq 1 \end{aligned}

这个约束问题可以根据拉个朗日方法求得约束条件下的极值问题(拉个朗日乘子法会单独说明)：

三、构建拉格朗日函数

通过拉格朗日乘子法，由5,6两式可以得到：

L (w, b, a) = \frac{1}{2} | | w | |^{2} - \sum_{i = 1}^{n} a_{i} (y_{i} . (w^{T} . Φ (x_{i}) + b) - 1)

化简，将1提取出来得到：

\begin{matrix} (7) & L (x, α, β) = \frac{1}{2} | | w | |^{2} - \sum_{i = 1}^{N} α_{i} y_{i} (w^{T} x_{i} + b) + \sum_{j = 1}^{N} α_{i} \end{matrix}

对式子7求极值可以通过求导法，在导函数为零时求得极值；
所以对式子求偏导可得：

\begin{aligned} \frac{δ L}{δ w} & = 0 => w = \sum_{i = 1}^{n} a_{i} y_{i} x_{i} \\ \frac{δ L}{δ b} & = 0 => 0 = \sum_{i = 1}^{n} a_{i} y_{i} \end{aligned}

将上面两个值带入到式（7）可以化简得到：

\begin{aligned} L (w, b, a)_{m i n (w, b)} & = \frac{1}{2} w^{T} w - w^{T} \sum_{i = 1}^{n} a_{i} y_{i} x_{i} - b \sum_{i = 1}^{n} a_{i} y_{i} + \sum_{i = 1}^{n} a_{i} \\ = \sum_{i = 1}^{n} a_{i} - \frac{1}{2} (\sum_{i = 1}^{n} a_{i} y_{i} x_{i})^{T} \sum_{i = 1}^{n} a_{i} y_{i} x_{i} \\ = \sum_{i = 1}^{n} a_{i} - \frac{1}{2} \sum_{i = 1, j = 1}^{n} a_{i} a_{j} y_{i} y_{j} x_{i} x_{j} \end{aligned}

上面式子就是一个只关于

α

的函数方程；这个时候就是要求点到超平面要足够远的问题了（求确定w,b情况下最大间隔）；
所以上面式子的求极值也可以转换成拉格朗日乘子法问题：就是求

m i n_{w, b} L (w, b, α)

中(w,b)确定情况下对

α

变量求极大值；根据这个可以得到如下约束与函数关系：

\begin{aligned} m a x_{a} \sum_{i = 1}^{n} a_{i} - \frac{1}{2} \sum_{i = 1, j = 1}^{n} a_{i} a_{j} y_{i} y_{j} x_{i} x_{j} \\ s . t . \sum_{i = 1}^{n} a_{i} y_{i} = 0 \\ a_{i} \geq 0, i = 1, 2, . . ., N \end{aligned}

上面的式子求极大值可以转换为下面的式子求极小值：

\begin{aligned} m i n_{a} \frac{1}{2} \sum_{i = 1, j = 1}^{n} a_{i} a_{j} y_{i} y_{j} x_{i} x_{j} - \sum_{i = 1}^{n} a_{i} \\ s . t . \sum_{i = 1}^{n} a_{i} y_{i} = 0 \\ a_{i} \geq 0, i = 1, 2, . . ., N \end{aligned}

上面的对偶的式子所获得的解，能不能代表是原来式子的所需极值问题的解呢？这个可以根据广义拉格朗日的对偶问题证明：此时约束条件下求得的极值就是原来约束条件的极值。

最后：对于给定的样本点就可以通过上面的约束条件求得 $α$ ，而通过 $α$ 就可以根据（7）式子中求偏导得到的w,b和 $α$ 关系求得对应的超平面。由这个可以得到，超平面是唯一的。

\begin{aligned} w^{*} = \sum_{i = 1}^{n} a_{i}^{*} y_{i} x_{i} \\ b^{*} = y_{i} - \sum_{i = 1}^{n} a_{i}^{*} y_{i} (x_{i} y_{i}) \end{aligned}

上面推导成立的两个隐藏条件是拉格朗日的对偶问题和KKT条件，那么这两个又是什么呢？
这个可以参考：真正理解拉格朗日乘子法和 KKT 条件

四、对线性不可分数据优化

对线性不可分数据需要修改上述的硬间隔最大化，使其软间隔最大化;
线性不可分意味着某些样本点 $(x_{i}, y_{i})$ 不能满足函数间隔大于等于1的约束条件，我们可以对每个样本点 $(x_{i}, y_{i})$ 引入一个松弛变量 $ξ_{i} \geq 0$ ，使得函数间隔加上松弛变量大于等于1，这样约束条件变成：

y_{i} \cdot (w^{T} x_{i} + b) \geq 1 - ξ_{i}

同时，为每个松弛变量

ξ_{i}

，补充一个代价

ξ_{i}

，目标函数由原来的

\frac{1}{2} | | w | |^{2}

变成

\frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{N} ξ_{i}

所以原来的求解问题可以变换为如下：

\begin{aligned} (91) & m i n_{w, b} (\frac{1}{2} | | w | |^{2} + C \sum_{i = 1}^{N} ξ_{i}) \\ (92) & s . t . y_{i} \cdot (w^{T} x_{i} + b) \geq 1 - ξ_{i} \\ (93) & ξ_{i} \geq 0, i = 1, 2, . . ., N \end{aligned}

为了解决个别正例和负例样本点很接近时，引入松弛因子
当C趋近于无穷大时，容忍度越低，分类越严格
当C趋近于很小时，意味着容忍度很高
对于引入松弛变量后的求解可以参见SVM的一般求解方法。

五、核函数的引入

在SVM中，其中最重要的也是最核心的就是核函数的选取和参数选择，当然这个需要大量的经验来支撑。SVM相对感知机而言，它可以解决线性不可分的问题，那么它是怎么解决的呢？它的解决思想很简单，就是对原始数据的维度变换，一般是扩维变换，使得原样本空间中的样本点线性不可分，但是在变维之后的空间中样本点是线性可分的，然后再变换后的高维空间中进行分类。
这个时候的对偶凸优化就表示为了：

\begin{aligned} m a x_{a} \sum_{i = 1}^{n} a_{i} - \frac{1}{2} \sum_{i = 1, j = 1}^{n} a_{i} a_{j} y_{i} y_{j} Φ (x_{i}) Φ (x_{j}) \\ s . t . \sum_{i = 1}^{n} a_{i} y_{i} = 0 \\ a_{i} \geq 0, i = 1, 2, . . ., N \end{aligned}

其中

Φ (x_{i})

表示原来的样本扩维后的坐标。
在求解对偶问题的过程中都会用到各样本点的内积的结果，那么这时候问题来了，在很多情况下，扩维可能会把原数据扩到很高维(甚至无穷维)，这时候直接求内积是非常困难的，我们为了避免做这样的事就提出了核函数的概念。
核函数：任意两个样本点在扩维后的空间的内积，如果等于这两个样本点在原来空间经过一个函数后的输出，那么这个函数就叫核函数。

举个例子，假设所有样本点都是二维点，其值分别为(x,y)， $k (x_{i}, x_{j}) =< x_{i}, x_{j} >^{2}$ 他对应的映射方式 $Φ ((x, y)) = (x^{2}, \sqrt{2} x y, y^{2})$ 以验证任意两个扩维后的样本点在3维空间的内积等于原样本点在2维空间的函数输出：

\begin{aligned} < Φ (x_{1}), Φ (x_{2}) > & = < (x_{1}^{2}, \sqrt{2} x_{1} y_{1}, y_{1}^{2}), (x_{2}^{2}, \sqrt{2} x_{2} y_{2}, y_{2}^{2}) > \\ = x_{1}^{2} x_{2}^{2} + 2 x_{1} x_{2} y_{1} y_{2} + y_{1}^{2} y_{2}^{2} \\ = (x_{1} x_{2} + y_{1} y_{2})^{2} \\ = < v_{1}, v_{2} >^{2} \\ = K (v_{1}, v_{2}) \end{aligned}

有了这个核函数，以后的高维内积都可以转化为低维的函数运算了，这里也就是只需要计算低维的内积，然后再平方。明显问题得到解决且复杂度降低极大。总而言之，核函数它本质上隐含了从低维到高维的映射，从而避免直接计算高维的内积。