机器学习——支持向量机（SVM)

支持向量机（Support Vector Machine，SVM）是一种用于分类问题的监督算法。支持向量机试图在数据点之间绘制两条线，它们之间的边距最大。为此，我们将数据项绘制为 n 维空间中的点，其中，n 是输入特征的数量。在此基础上，支持向量机找到一个最优边界，称为超平面（Hyperplane），它通过类标签将可能的输出进行最佳分离。

---

首先来了解一下什么是支持向量,下面举一个简单的例子。

如上图，对于一个二分类场景，可以有无数线将其分开。被虚线截到的一个或者多个样本就叫做支持向量。

---

1.1 线性可分的SVM

如果有一个线性函数能够将样本分开，就称这些数据样本是线性可分的。线性函数，简单说来，在二维空间中就是一条直线，三维空间中就是一个平面。高于三维，我们统称为 超平面。

关于上面图中存在的一个问题：就是可以有无数条直线将样本分开，所以需要找出一条可以正确分开样本并且结果是最优的。

最优化的原则就是所有的样本能正确分类并且不同样本之间的间隔要最大。转化为所有的支持向量到线性函数（超平面）的距离最大，这样就能保证最优结果，并且此结果下只可能有一条最优线将样本分开。

![在这里插入图片描述](https://img-blog.csdnimg.cn/c66bf52ef35c496eb85de79f7c9725dd.png#pic_center

接下来应该要怎样计算间隔呢？

用如下线性方程来描述超平面 W^T x+b=0; 其中W为法向量，决定了超平面的方向，b为位移量，决定了超平面与原点的距离。假设对于样本（x_i,y_i),用y_i =+1来表示正样本，y_i =-1来表示负样本。（当然可以的+1，-1不是肯定的，你也可以取2，3，4… -2,-3,-4…).说明一下：y_i 是标签值。可以得到如下图结果：

通过放缩，可以使在支持向量x₀上有|w^Tx₀+b| = 1,而在非支持向量上有|w^Tx₀+b| >1.

所有有一个支持向量点x₀到超平面的距离：
$$d=\frac{|wTx0+b|}{||w||}=\frac{1}{||w||}$$

$$所以r=2d=\frac{2}{||w||}这里的||w||是2范数，关于范数，不懂的地方可以搜索一下。$$

最终最大化支持向量到超平面的距离就等价于最小化||w||，为了放方便求导等原因，最小化||w||转化为最小化1/2||w||² 。此时可以写出支持向量机的限制条件 :

arg_min 1/2||w||² st. yi(w^Tx_i+b)>=1

1.2 线性不可分的SVM

线性不可分意味着某些样本点（x_i,y_i)不能满足间隔大于等于1的条件。如下图：

一种思路是对每个样本点引入一个松弛变量δ_i>0，使得间隔加上松弛变量大于等于1，最优化问题变为求解1/2||w||² +C*Σδ_i，其中C>0为惩罚一个参数；约束条件就变为 yi(w^Tx_i+b) > 1 - δ_i 。这样将非线性问题转而和线性可分问题的一样求解过程。

---

处理非线性问题的另外一种思路就是利用核函数，通过将数据映射到高维空间来解决原视空间线性不可分的情况。在线性不可分的情况下，SVM首先在低纬空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最后在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。

如上，对于异或问题线性不可分，通过选择合适的核函数将二维映射到三维，找到一个超平面是其线性可分。

最优化问题和受限条件转化为如上式子

下面是一些常见的核函数