目录
前言
第一章 了解 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