支持向量机(SVM)硬核入门-基础篇

• 2019 年 10 月 31 日
• 筆記

1 引子

关于SVM，流传着一个关于天使与魔鬼的故事。

传说魔鬼和天使玩了一个游戏，魔鬼在桌上放了两种颜色的球（图1.1）。魔鬼让天使用一根木棍将它们分开。这对天使来说，似乎太容易了。天使不假思索地一摆，便完成了任务（图1.2）。

图1.1 分球问题1

图1.2 分球问题1的解

魔鬼又加入了更多的球。随着球的增多，似乎有的球不能再被原来的木棍正确分开（图1.3）。

图1.3 分球问题2及其解

魔鬼最后给了天使一个新的挑战（图1.4）。按照这种球的摆法，世界上貌似没有一根木棒可以将它们完美分开。但天使一拍桌子，便让这些球飞到了空中，然后抓起一张纸片，插在了两类球的中间（图1.5）。从魔鬼的角度看这些球，则像是被一条曲线完美的切开了（图1.6）。

图1.4 分球问题3

1.5 高维空间中分球问题3的解

图1.6　魔鬼视角下分球问题3的解

本小节引用自《百面机器学习》诸葛越）

2 概述

和第1节中的分球游戏类似，支持向量机SVM就是一个二分类模型，它通过引入一个超平面，将样本点分隔成两簇，以达到预测样本类别的目的。SVM算法的主要过程就是求出这个分隔超平面。其中：

分球问题1对应：线性可分支持向量机。这是最简单的支持向量机，所有样本都能够完美地被线性分隔。

分球问题2对应：基于软间隔的线性支持向量机。这种支持向量机能够容忍一定的误差和异常点。

分球问题3对应：基于核函数的非线性支持向量机。SVM将低维的样本特征空间映射到高维，再利用高维的超平面进行分隔。

在基础篇中，我将只介绍线性可分支持向量机，因为基础篇的目的是删烦就简，让读者了解到一个尽可能简单的支持向量机SVM。

剩下的两种支持向量机及一些高级的知识点，将会在进阶篇中进行描述。

3 基本概念

在定义了样本点到超平面的间隔后，我们继续定义样本训练集到超平面的间隔：训练集中所有样本到超平面的间隔的最小值

其中N为样本点数量。

图3.4 间隔和支持向量

如图3.4所示，正例样本中距离超平面最近的点是点A和点B，它们距离超平面的距离为γ，负例样本中距离超平面最近的点是点C，它们距离超平面的距离也为γ。

支持向量机SVM算法的最终目的，就是求出一个超平面，使得训练集间隔γ最大，以达到最好的分类效果，即求得：

这也是后续最优化问题的目标函数。

3.4 支持向量

最后解释支持向量机SVM算法名称的由来。

如图3.4，超平面仅由样本点A、B、C决定，和其它样本点无关。这些决定超平面位置的样本点，就被称为支持向量。

在线性可分支持向量机中，正例和负例至少各有1个支持向量，至多有无穷多个。

最为简单的情况是：正例1个支持向量，负例1个支持向量，超平面即为这两个支持向量的垂直平分线。如图3.5所示。

图3.5 由两个支持向量生成的间隔最大的超平面

6 附录：拉格朗日对偶性

这节介绍如何利用拉格朗日函数及对偶问题，求解带约束条件的最优化问题。此外，对偶问题还能为后续引入核函数提供便利。

对于如下最优化问题的泛用性表示：

我们将其称为原始问题。

在求解f(x)的最小值的时候，还要考虑约束条件，很麻烦。有没有一个函数既能够表示f(x)，又能够把约束条件包含进去呢？

为解决这个问题，拉格朗日函数被提出了：

可以证明（我这里就不证明了）：

在满足约束条件时，

在不满足约束条件时

所以：

再交换下极大极小顺序（这里就不证明交换顺序不会改变函数结果了）：

这样，我们就找到了原始问题（带约束条件的最优化问题）的替代形式，并命名为对偶问题：

对偶问题相对于原始问题，就好求解多了。

最后，补充下最优值点需要满足的条件（KKT条件）：

（1）原始问题可行：

（2）对偶问题可行：

（3）对偶互补松弛：

参考文献

[1]李航 统计学习方法 清华大学出版社

[2]张皓 从零构建支持向量机（SVM）

[3]诸葛越 百面机器学习 人民邮电出版社

[4]彭一洋 如何通俗地讲解对偶问题 https://www.zhihu.com/question/58584814

[5]周志华 机器学习 清华大学出版社

本文转载自公众号：数论遗珠，作者：阮智昊