目录
前言
第一章 了解 SVM 1
1.1 什么是 SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 线性分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 分类标准 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.2 1 或 –1 分类标准的起源：Logistic 回归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.3 形式化表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 线性分类的一个例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 函数间隔与几何间隔 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.1 函数间隔 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 点到超平面的距离定义：几何间隔 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 最大间隔分类器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 支持向量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
第二章 深入 SVM 8
2.1 从线性可分到线性不可分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 从原始问题到对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2 序列最小最优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.3 线性不可分的情况 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 核函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 特征空间的隐式映射：核函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 如何处理非线性数据 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 几个核函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 核函数的本质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3 使用松弛变量处理离群点的方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
第三章 证明 SVM 20
3.1 线性学习器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 感知机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 非线性学习器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1 Mercer 定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 损失函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 最小二乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4.1 什么是最小二乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.4.2 最小二乘法的解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
目录
3.5 SMO 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5.1 SMO 算法的解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5.2 SMO 算法的步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.3 SMO 算法的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.6 支持向量机的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6.1 文本分类 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
参考资料 30
前言
动笔写这个支持向量机（support vector machine）是费了不少劲和困难的，原因很简单，一者这个东西本
身就并不好懂，要深入学习和研究下去需花费不少时间和精力，二者这个东西也不好讲清楚，尽管网上已经有朋
友写得不错了（见文末参考链接），但在描述数学公式的时候还是显得不够。得益于同学白石的数学证明，我还
是想尝试写一下，希望本文在兼顾通俗易懂的基础上，真真正正能足以成为一篇完整概括和介绍支持向量机的导
论性的文章。
本文在写的过程中，参考了不少资料，包括《支持向量机导论》、《统计学习方法》及网友 pluskid 的支持向
量机系列
1
等等，于此，还是一篇学习笔记，只是加入了自己的理解和总结，有任何不妥之处，还望海涵。全文
宏观上整体认识支持向量机的概念和用处，微观上深究部分定理的来龙去脉，证明及原理细节，力保逻辑清晰
& 通俗易懂。
同时，阅读本文时建议大家尽量使用 chrome 等浏览器，如此公式才能更好的显示，再者，阅读时可拿张纸
和笔出来，把本文所有定理.公式都亲自推导一遍或者直接打印下来（可直接打印网页版或本文文末附的 PDF，
享受随时随地思考、演算的极致快感），在文稿上演算。
Ok，还是那句原话，有任何问题，欢迎任何人随时不吝指正 & 赐教，感谢。
1
http://blog.pluskid.org/?page_id=683
第 1 层 了解 SVM
1.1 什么是 SVM
要明白什么是支持向量机 Support Vector Machines, SVM ，便得从分类说起。
分类作为数据挖掘领域中一项非常重要的任务，它的目的是学会一个分类函数或分类模型（或者叫做分类
器），该模型能吧数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别。
本文将要介绍的支持向量机算法便是一种分类方法。
..
支持向量机
所谓支持向量机，顾名思义，分为两个部分了解：一，什么是支持向量（简单来说，就
是支持或支撑平面上把两类类别划分开来的超平面的向量点，下文将具体解释）；二，这里的
“机（machine，机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如
分类机（当然，也叫做分类器），而支持向量机本身便是一种监督式学习的方法（至于具体什
么是监督学习与非监督学习，请参见此系列Machine Learning & Data Mining 第一篇），它
广泛的应用于统计分类以及回归分析中。
而支持向量机是 90 年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小
来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良
好统计规律的目的。
对于不想深究支持向量机原理的同学（比如就只想看看支持向量机是干嘛的），那么，了解到这里便足够了，
不需上层。而对于那些喜欢深入研究一个东西的同学，甚至究其本质的，咱们则还有很长的一段路要走，万里长
征，咱们开始迈第一步吧（相信你能走完）。
1.2 线性分类
OK，在讲 SVM 之前，咱们必须先弄清楚一个概念：线性分类器（也可以叫做感知机，这里的机表示的还
是一种算法，本文第三部分“证明 SVM”中会详细阐述）。
1.2.1 分类标准
这里我们考虑的是一个两类的分类问题，数据点用 x 来表示，这是一个 n 维向量，w
T
上标中的“T”代表
转置，而类别用 y 来表示，可以取 1 或者 –1 ，分别代表两个不同的类。一个线性分类器就是要在 n 维的数据
空间中找到一个超平面，其方程可以表示为：
w
T
x + b = 0 (1.2.1)
上面给出了线性分类的定义描述，但或许读者没有想过：为何用 y 取 1 或者 –1 来表示两个不同的类别呢？其实，
这个 1 或 –1 的分类标准起源于 Logistic 回归，为了完整和过渡的自然性，咱们就再来看看这个 Logistic 回归。
1
评论0