0x00 支持向量机

在机器学习中，支持向量机（support vector machine，常简称为SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法建立一个将新的实例分配给两个类别之一的模型，使其成为非概率二元（binary classifier）线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。

0x01 间隔与支持向量

首先看一张图：

如果要用一条直线将两种类型的图形分开，那这样的直线我们可以找到很多条。那么哪条才是最好的分割线？

我们可以设想一下，目前的样本并不代表所有可能发生的情况，如果进入新样本，很有可能会存在向直线贴近的样本，那么如果选择的直线到两边最近的点间隔越长，输入新样本时越过这条线的机会就越小，泛化能力就越强。

图中距离这条分割线最近的这几个点，就被称为支持向量。

两个异类支持向量到这条直线的距离之和，就被称为间隔。

假设我们分割线的方程如下：

其中w是法向量。

我们的可以通过它将训练样本正确分类，即

留出间隔，令：

则间隔的数学表示为：

我们为了找到最大间隔，也就是使γ最大，也就是使||w||²最小，就可以转换成找

的最小值。这被称为支持向量机的基本型。

0x02 对偶问题

上面的问题最终转换成求支持向量机基本型的最小值问题，这是一个凸二次规划问题，可以直接求解，但是我们有更优的计算方法。那就是通过拉格朗日乘子法得到其”对偶问题“。

具体做法是对每条约束都增加拉格朗日乘子αi，则该问题可以写成：

这个时候要求其最小值，从之前转换成最小值的模型前加了1/2这点就可以想到，我们接下来肯定要通过求导，求导数零点，找极值点来完成。

所以分别对w和b求导可以得出：

将其结论代回L中可得对偶问题：

这个结果，我们就可以直接交给机器去处理数据求这个式子的最大值了。

0x03 核函数

线性可分的训练样本我们可以通过直线将其正确分类，但是如果遇到线性不可分的训练样本，或许就不能通过一条直线来进行分割。

这种情况下，我们可以将样本从原本的空间映射到一个更高维度的空间，使样本在这个空间内线性可分。

比如二维平面中的样本投影到三维空间中，就可以通过一个超平面线性分割两类样本了：

具体做法是用Φ(x)代表x映射之后的特征向量，对偶问题就变为：

在计算Φ(xi)的转置与Φ(xj)的矩阵乘积时，在高维会变的十分困难，所以就引入了：

Φ(xi)与Φ(xj)内积等于它们在原始样本空间通过k函数计算的结果，这样就不用去高维计算内积。这个k函数就被称为核函数。

常用的核函数如下：

并不是所有的情况通过核函数映射之后都是线性可分的，我们会根据实际的情况去选取合适的核函数，使其映射到高维之后可以分割，然后高维分割的超平面在原始平面上的投影就是在原始平面上的分割曲线。

0x04 硬间隔和软间隔

即使使用了核函数，实际中，我们仍然存在一种不可分的情况，即两类样本互相有一部分出现在对方的区域，如图：

那么这种情况，我们的处理方式就是允许支持向量机在一些样本上出错，也就是“软间隔”。

对应的所有样本都被正确分类就被称为“硬间隔”。

在之前机器学习的经验中我们都明白，出错就会有损失，那么我们需要一个损失函数来计算惩罚，最终的优化目标是在最大化间隔的同时使不满足约束的样本尽可能少，可写为：

这里面使用的损失函数是0/1损失函数：

我们也有其他几种替代损失函数可供选择：

在软间隔情况中，只使满足最终优化目标的值优化到最小即可。

0x05 支持向量机的优缺点

支持向量机的优势在于:

• 在高维空间中非常高效

• 即使在数据维度比样本数量大的情况下仍然有效

• 在决策函数（称为支持向量）中使用训练集的子集,因此它也是高效利用内存的

• 通用性: 不同的核函数 核函数与特定的决策函数一一对应，常见的kernel已
  经提供,也可以指定定制的内核

支持向量机的缺点包括:

• 如果特征数量比样本数量大得多,在选择核函数 核函数 时要避免过拟合,
  而且正则化项是非常重要的

• 支持向量机不直接提供概率估计