[机器学习算法]支持向量机

原理

分类学习最基本的思想就是基于训练集在样本空间中找到一个划分超平面，将不同类别的样本区分开。但是事实上，能将训练样本划分开的超平面可能有很多，如下图所示，我们的任务就是寻找到最优的划分超平面。

划分超平面的线性方程可以表达为：

其中为法向量，决定了超平面的方向；为位移项，决定了超平面与原点之间的距离。划分超平面可由法向量和位移项确定，我们将其记为。样本空间中任意点到超平面的的距离可写为：

假设划分超平面能将样本正确分类，那么即位于超平面两侧的分别为正例和负例，即：

我们构建如下模型：

其中距离超平面最近的几个训练点正好使上式等号成立，它们被称为“支持向量”support vector，任意两个异类支持向量到超平面的距离之和为：

它也被称为“间隔”margin。支持向量与间隔的含义如下图所示：

支持向量机模型

为了找到合适的划分超平面使得产生的分类结果是最鲁棒的(即对未见示例的泛化能力最强)，我们令划分超平面的“间隔”最大化：

等价于：

参数求解

对上式使用拉格朗日乘子法可以得到:

对和求偏导为零后：

将求完偏导后的值代入原方程后可以消去和,得到对偶问题：


通过对偶问题解出后，求出和的值即可得到模型：

上述过程需要满足KKT(Karush-Kuhn-Tucker)条件，即要求：

从而对于任意的训练样本总有或者。若，则模型中不会出现该样本，也就不会对有影响；若，则必然有,所对应的样本点正好在最大间隔边界上，是一个支持向量。
这说明：训练完成后，大部分的训练样本不需要保留，最终模型只与支持向量有关。

SMO算法

上面我们得到支持向量机的对偶问题：


这本身是一个二次规划问题，可以利用通用的二次规划算法来求解。但是因为该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为此人们通过利用问题本身的特性，提出了SMO(Sequential Minimal Optimization)算法:

SMO算法：基本思路是固定之外的所有参数，然后求上的极值。由于存在约束，因此如果固定之外的其他参数，那么可直接由其他参数导出。因此SMO每次选择两个变量和并固定其他参数，在参数初始化后不断执行如下两个步骤直至收敛：

1. 选取一对需更新的和
2. 固定和以外的其他参数，求解规划问题获得更新后的和

核函数

在前面的推导过程中，我们假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类，但在现实任务中，原始样本空间可能并不存在一个能正确划分两类样本的超平面。如下图左侧的图就是非线性可分的。
假若我们能将样本从原始空间映射到一个更高纬度的特征空间，使得样本在该特征空间内线性可分，那么支持向量机就可以继续使用。比如下图右侧的图就是将原始的二维空间映射到一个合适的三维空间，从而找到了合适的划分超平面。

映射到高维度的支持向量机模型可以表示为：

其对偶问题是：


其中是样本和映射到高维空间后的内积。直接计算高维空间的内积是比较困难的，为了避开这个障碍，我们可以设想这么一个函数在原始样本空间即可计算在高维特征空间的内积。

最终的模型可以写成：

上述我们提到的就是核函数kernel function。
我们希望样本在特征空间中是线性可分的，因此合适的特征空间对支持向量机的性能至关重要，然后在不知道特征映射的形式时，我们并不知道什么样的核函数是最合适的，而核函数也仅是隐式地定义了这个特征空间。因此核函数的选择是支持向量机模型的最大影响因素。
常用的核函数包括了线性核、多项式核、高斯核、拉普拉斯核和Sigmoid核等。如下表所示：

另外，不同核函数经过组合后也可形成新的核函数，比如：

1. 若和为核函数，则对于任意正数和，其线性组合也是核函数
2. 若和为核函数，则核函数的直积也是核函数
3. 若为核函数，则对于任意函数,也是核函数

软间隔与正则化

前面我们讨论的支持向量机模型都是假设存在一个超平面能将不同类别的训练样本完全分割开的，然而现实中很难确定合适的核函数是的训练样本在特征空间中完全线性可分。即使恰好找到了某个核函数使得训练集在特征空间中线性可分，也很难断定这个结果不是由过拟合所造成的。
解决该问题的方法即允许支持向量机在一些样本上出错。为此，要引入“软间隔”soft margin的概念，如下图所示：

软间隔允许某些样本不满足约束：

在最大化间隔的时候，不满足约束的样本应该尽可能的少，于是优化目标可以改写为：

其中一个大于0的常数，是“0/1”损失函数，但是该损失函数数学性质不佳(非凸，非连续)，下面我们给出常用的三种替代损失函数：

Reference

[1] 机器学习