机器学习（6）支持向量机

一、支持向量机

支持向量机(Support Vector Machines，SVM)，是现成最好的分类器。SVM有很多实现算法，如序列最小优化（Sequential Minimal Optimization，SMO）算法。

基于最大间隔分隔数据

将数据集分隔开来的直线称为分隔超平面(separating hyperplane)。分隔二维平面，分隔超平面是一条直线。当数据集是N维的，就是用来分隔的N-1维的对象被称为超平面。

我们把这些数据点到分隔面的距离称为间隔，也就是该点到分隔平面的法线（或垂线）长度。在训练分类器时，希望间隔尽可能的大。

支持向量，就是离分隔超平面最近的那些点，需要试着最大化支持向量到分隔面的距离。

原理推导

为了寻找最大间隔，分隔超平面可以写成w^Tx+b。

点A到分隔超平面的距离为(w^Tx+b)/||w||。

使用了类似单位阶跃函数类似的函数，返回类别标签，值为-1和+1。当数据点处于正方向时，label为+1。当数据点处于负方向是时，label为-1。保证label*(w^Tx+b)仍然是正数。

支持向量(取最近的n个点)的表示如下：

$\min_n(label \cdot (w^Tx+b) \cdot \dfrac{1}{||w||})$

需要对该间隔最大化，写作

$arg max_{(w,b)}{\{min_{(n)}(label \cdot (w^Tx+b) \cdot \dfrac{1}{||w||})\}}$

该求解相当困难，加上约束条件label * (w^Tx+b) >=1.0，并使用拉格朗日乘子法，可以将优化目标函数最后写成：(尖括号为内积)

$max_{(\alpha)}[\sum_{i=1}^m\alpha - \dfrac{1}{2}\sum_{i,j=1}^mlabel^{(i)} \cdot label^{(j)} \cdot a_i \cdot a_j \langle x^{(i)},x^{(j)} \rangle]$

再引入松弛变量C后，约束条件为:

$C \ge \alpha \ge 0,\sum_{i-1}^m \cdot label^{(i)}=0$