vlambda博客
学习文章列表

0x00 前言

支撑向量机，SVM(Support Vector Machine)，其实就是一个线性分类器。在最初接到这个算法时，我们可能会一头雾水：这个名词好奇怪[问号脸]，怎么“支持”？什么“向量”，哪来的“机”？

本篇文章从“不适定问题”开始介绍SVM的思想，通过支撑向量与最大间隔引申到如何将其转换为最优化问题，并数学推导求解有条件限制的最优化问题。相信学完本篇之后，大家一定会对SVM算法有一个大体上的认识。

0x01 由决策边界开始

1.1 分类中的“不适定问题”

首先，我们看一个简单的二分类问题。在二维的特征平面中，所有的数据点分为了两类：蓝色圆形和黄色三角。我们的目标是找到了一条决策边界，将数据分类。但实际上我们可以找到多条决策边界。

这就所谓的“不适定问题”。“不适定问题”会影响模型的泛化性。比如在下面的模型中，被黄色箭头标出的点被决策边界划为蓝色圆点，但实际上它和黄色三角更近一些。也就说决策边界的选择，不仅要考虑已经存在的数据上的是否分类正确，还要考虑是否能够更好地划分未出现的测试数据：

逻辑回归算法如何解决“不适定问题”问题呢？首先定义一个概率函数sigmoid函数：

然后根据概率函数进行建模：

建立损失函数:

最小化损失函数，从而求出一条决策边界（线性）：

（以上内容回顾文章《Kaggle出场率No.1的逻辑回归算法到底是如何推导出来的》、《逻辑回归的本质及损失函数的推导、求解》、《逻辑回归的决策边界及多项式》）

也就说，逻辑回归的损失函数完全是由训练数据集确定的。

1.2 SVM中的决策边界

支撑向量机如何解决“不适定问题呢”？SVM要找到一条泛化性比较好的决策边界，就是这条直线要离两个分类都尽可能的远，我们认为这样的决策边界就是好的：

如上图所示：在上面的两个类别中，离决策边界最近的点到决策边界的距离尽可能地远。

那也就是说，我们可以忽略其他大部分的数据点，只关注这几个特殊的点即可。

0x02 Support Vector & Margin

2.1 定义及思想

将最优决策边界向上&下平移，在遇到第一个点时停下来，这个点被称为支撑向量Support Vector；支撑向量到决策边界的距离是d；这两条平移后的直线的间隔（2d）被称为最大间隔Margin。

支撑向量就是支撑着两条平移边界的点，我们只需要重点研究这几个支撑向量即可，这也是SVM名称的由来；Margin就是分界面可以移动的范围，范围越大表示容错能力越强。

所以我们可以看到，所谓的支撑向量机，最初就是一个线性分类器，只不过这个线性分类器不仅能把样本分对，可以最大化Margin。

到目前为止，我们就将SVM转换为了一个最优化问题，下面的工作就是求出Margin的数学表达式，即将支撑向量机思想转化为数学问题。

2.2 转化为最优化问题（核心）

回忆解析几何的知识，点 到直线 的距离：

扩展到n维空间：点 到 (其中 是n维向量， 是截距)的距离为：

然后我们去找决策边界的表达式：

求出在满足下面的条件下， 的值是多少。

我们将上面的两个式子进行合并，即可以将 提到前面去。这样，支撑向量机的所有数据点都要满足下面的式子：

对于任意支撑向量点 到决策边界的距离为 ，我们要最大化Margin，将前面的式子带入后得到 ，也就是 。

即相当于最小化 。

OK，现在我们已经得到了SVM的最优化问题:

即最优化的目标函数为 ，还要有限定条件（ ）：所有数据满足

我们发现，SVM的最优化问题是有限制条件的，与之前接触的没有限制条件的全局最优化问题的计算方法很不同。

0x03 求解有条件限制的最优化问题

3.1 数学推导

通过六步数学推导，求解有条件限制的最优化问题。如果觉得吃力，大家可以仅仅了解推导过程，记住结果即可。

第一步：给出表达式

对于有约束条件的最优化问题，用拉格朗日乘数法来解决，得到（ 是拉格朗日系数）：

此时，我们要求 基于 的极小值。

第二步：求导

我们对 进行求导，可以得到两个式子：

从上两式子可以看出，我们已经求得了 和 的关系，只要后面接着能够求出优化函数极大化对应的 ，就可以求出 了，至于 ，由于上两式已经没有 ，所以最后的 可以有多个。

第三步：转换对偶问题

将 的求导结果带回到原式 中，得到新的目标函数 ：

其实 和 是对偶问题。我们可以通过拉格朗日对偶将优化问题转化为等价的对偶问题来求解，原问题和对偶问题在一般情况下是不等价的，但是在SVM中是等价的。

第四步：求

把 方程解出来，会得到很多 ，大部分都为0，少部分非0，就是支撑向量。

第五步：求

我们将所有非零的支撑向量相乘并累加起来，最终得到 。

这里要注意，两个向量做内积，是SVM运算的精华所在。

第六步：求

已知 ，将 的结果带入，并且在两侧同时乘以 后得到：，则得到 :

3.2 SVM如何求解示例

通过一个简单的例子，展示SVM如何求解。有两个样本：

通过约束条件: ，可以得到：

我们要优化的表达式为： 。需要先求出 .

将 带入到矩阵 中，已知： ；则有：

带入到表达式中，得到：

则表达式 的最大值为： 。

带回到 中则可以得到： ；计算 ： 。

最终得到判决平面为： ；Margin为

0xFF 总结

其实我们可以看到，SVM算法也没有多么神秘。其最核心的思想就是从Input Space向更高维的Feature Space的映射，进行有Margin的线性分类。

在这一篇文章中，我们要做的就是学习支持向量机算法的相关概念、算法思想、推导过程。一边体会算法的奥义，一边为后续的进一步学习做准备。

在线性可分问题中，对于样本点来说，存在一根直线可以将样本点划分，我们称之为Hard Margin SVM；但是事实上，并不是所有情况都是完美的，这就引出了下一篇文章就讲解Soft Margin SVM以及相关知识。大家加油！