分类算法之支持向量机:SVM(理论篇)

算法,机器学习 2017-12-10

起步

支持向量机这部分比较难,本身也涉及很多数学理论,并不好懂,需要花费不少的时间和精力去理解。

背景

最早在1963年,由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 提出。而目前的版本(soft margin)是由Corinna Cortes 和 Vapnik在1993年提出,并在1995年发表。

在深度学习出现之前(2012),支持向量机被认为机器学习中近十几年最成功,表现最好的算法。

了解SVM

支持向量机( support vector machine ),简称SVM,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

看个例子:

20171210171805.png

在这个二维的平面中,用一条直线将上面的点分成两类,显然 H1 无法将点区分开,而H2 和 H3 都可以,但这两条哪个更好呢?作为分界线,H3 是更合适的,因为分界线其两边有尽可能大的间隙,这样的好处之一就是能在使用中有利于预测。

这是在二维上的,我们找的是线,如果是三维,我们找的是面。总的来说我们是寻找区分两类的超平面( hyper plane ),使边界( margin )最大。在一个 n 维空间中,超平面的方程定义为:

a_1x_1 + a_2x_2 + ... + a_nx_n = b

Image.png

总共可以有多少个可能的超平面?无数条。

我们要寻找的超平面是到边界一测最近点的距离等于到另一侧最近点的距离,在这个边界中,边界两侧的超平面平行。

点到超平面的距离

在二维平面中,计算点 (x0, y0) 到线 ax + by + c = 0 的距离是:

d = |\frac{ax_0 + by_0 + c}{\sqrt{a^2 + b^2}}|

在 n 维空间中,点到超平面的距离:

d = |\frac{a_1x_1 + a_2x_2 + ... + a_nx_n + c}{\sqrt{a_1^2 + a_2^2 +...+ a_n^2}}|

将点的坐标和系数都向量化表示,距离公式可以视为:

\frac1{||w||}|wx+b|

其中 w = {w0, w1, w2,...,wn}

我们寻找的超平面,是先寻找各分类到超平面的距离最小,在寻找距离之和最大的超平面,在 N 个训练点,点的坐标记为 xi,结果分类为yi,构成 (xi, yi)

arg\,\max_{w,b}\big\{\frac1{||w||}\min_n[y_i(w^Tx_i + b)]

因为 SVM 是仅支持二分类的模型,因此 yi 仅有两种取值,我们就定义为 1 和 -1,为什么是这两个值,因为这两个值会简化求解过程。

再从超平面推导

(xi, yi) 中,我们用 Xi 表示了点的坐标,yi 表示了分类结果,这样多引入了一个维度。该怎么算呢,别急,回头看看我们的超平面:

w^Tx + b = 0

在超平面的上方的点满足:

w^Tx_i + b \textgreater 0

在超平面下面的点则满足:

w^Tx_i + b \textless  0

因为 yi 只有两种取值 1 和 -1。因此就满足:

\left\{
\begin{array}{lr}
w^Tx + b \ge 1 , when\,y = 1 \\
w^Tx + b \le -1 , when\,y = -1
\end{array}
\right.

整合这两个等式(左右都乘以 yi,当yi是负值时,不等号要改方向)得:

y_i(w^Tx + b) \ge 1 , \forall{i}

支持向量

那么什么是支持向量呢? 所有坐落在边界的边缘上的点被称作是 “支持向量”。分界边缘上的任意一点到超平面的距离为:

\frac1{||w||}

其中,||w|| 是向量的范数( norm ),或者说是向量的模。它的计算方式为:

\begin{align*}
||w|| &= \sqrt{w * w} \\
&= \sqrt{w_1^2 + w_2^2 + ... + w_n^2}
\end{align*}

所以,最大边界距离为:

\frac2{||w||}

找出最大边界的超平面

那么,SVM 如何找出最大边界的超平面( MMH )呢?由于这部分的推导比较难,有空时我再整理这部分的过程,在这边呢,就简单说下步骤,然后给出结果。

  1. 利用一些数学推导,把 yi(w^T*x + b) >= 1 变为有限制的凸优化问题( convex quadratic optimization );
  2. 利用 Karush-Kuhn-Tucker ( KKT ) 条件和拉格朗日公式,可以推出 MMH 可以被表示为以下的“决定边界( decision boundary )”
d(X^T) = \sum_{i=1}^l{y_ia_iX_iX^T + b_0}

公式中各符号的含义为:

  • l :表示 支持向量点 的个数;
  • yi : 第i个支持向量点;
  • Xi :支持向量的类别标记( class label );
  • aib0:都是单一数值型参数。

对于测试实例,代入以上公式,按得出结果的正负号来进行分类。

SVM 算法有这几个特性:

  • 训练好的模型的算法复杂度是由支持向量的个数决定的,而不是由数据的维度决定的。所以 SVM 不太容易产生过拟合( overfitting )的情况;
  • SVM 训练出来的模型完全依赖于支持向量,即使训练集里所有非支持向量的点都被去除,重新训练,结果仍然会得到完全一样的模型;
  • 一个 SVM 如果训练得出的支持向量个数比较小,那训练出的模型比较容易被泛化。

线性不可区分的情况

有些情况下,是无法用一条直线来进行划分的:

Image.png

多数情况下,数据集在空间中对应的向量不可被一个超平面区分开。这种情况要怎么使用 SVM 呢? 这种情况用两个步骤来解决:

  1. 利用一个非线性的映射把原数据集中的向量点转化到一个更高维度的空间中;
  2. 在这个高维度的空间中找一个线性的超平面来进行可区分处理。

20171211000938.png

如上图表示的,将其从一维转为二维空间,然后在二维空间进行求解。youtube上有个可视化的演示: https://www.youtube.com/watch?v=3liCbRZPrZA

main-qimg-de8f2ca9c807ee184e2509639fce066d.jpg

动图展示的demo:

1364952814_3505.gif

本章讨论的是映射到高维空间的方式。

原始数据转化到高维

举个例子,在三维空间中的向量 X = (x1, x2, x3) 转化到六维空间 Z 中去,令:

\begin{align*}
\Phi_1(X) &= x_1 \\
\Phi_2(X) &= x_2 \\
\Phi_3(X) &= x_3 \\
\Phi_4(X) &= x_1^2 \\
\Phi_5(X) &= x_1x_2 \\
\Phi_6(X) &= x_1x_3
\end{align*}

新的决策超平面为:

d(Z) = WZ + b_0

其中,W 和 Z 都是向量,这个超平面是线性的,解出 W 和 b 后,待会原方程:

\begin{align*}
d(Z) &= w_1x_1+w_2x_2+w_3x_3+w_4(x_4)^2+w_5x_1x_2+w_6x_1x_3+b_0 \\
&= w_1z_1+w_2z_2+w_3z_3+w_4z_4+w_5z_5+w_6z_6+b_0
\end{align*}

这类转换的求解过程中,是需要计算内积,而内积的复杂度非常高,改怎么解决? 这就需要使用 核方法

核方法

在处理非线性的情况中,SVM 选择一个核函数 ( kernel trick ),通过函数 k(.,.) 将数据映射到高维空间。支持向量机首先在低维空间中完成计算,然后通过核函数将输入空间映射到高维特征空间,最终在高维空间中构造出最优分离超平面。

核函数例子: 假设两个向量:x = (a1, a2, a3) y = (b1, b2, b3) ,定义方程:

f(x) = (x1x1, x1x2, x1x3, x2x1, x2x2, x2x3, x3x1, x3x2, x3x3)

假设核函数为: K(x, y) = (<x, y>)^2 , 且设 x = (1, 2, 3) y=(4, 5, 6) 则有:

f(x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)
f(y) = (16, 20, 24, 20, 25, 36, 24, 30, 36)
<f(x), f(y)> = 16 + 40 + 72 + 40 + 100 + 180 + 72 + 180 + 324 = 1024

而核函数计算为: K(x, y) = (4 + 10 + 18 ) ^2 = 32^2 = 1024 ,相同的结果,使用核函数是不是容易计算很多。

核函数能很好的避开直接在高维空间中进行计算,而结果却是等价的。常见的几个核函数 ( kernel functions )有:

h度多项式核函数(polynomial kernel of degree h)

K(X_i,X_j) = (X_iY_j+1)^n

高斯径向基核函数(Gaussian radial basis function kernel)

K(X_i,X_j) = e^{-\frac{{||X_i-Y_j||}^2}{2\sigma^2}}

S型核函数(Sigmoid function kernel)

K(X_i,X_j) = tanh(\kappa X_iY_i-\delta)

如何选择使用哪个核函数? 根据先验知识,比如图像分类,使用RBF,尝试不同的核函数,根据结果准确度而定。

多分类的情况

SVM 是二分类模型,如果空间中有多个分类,比方有苹果,梨,香蕉。那么SVM就需要对每个类别做一次模型,是苹果还是不是苹果?是香蕉还是不是香蕉?是梨子还是不是梨子?从中选出可能性最大的。也可以两两做一次SVM:是苹果还是香蕉?是香蕉还是梨子?是梨子还是苹果?最后三个分类器投票决定。因此,多分类情况有两种做法:

  • 对于每个类,有一个当前类和其他类的二类分类器( one-versus-the-rest approach)
  • 两两做一次二类分类器( one-versus-one approace )

本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

赏个馒头吧