支持向量机(SVM)是什么意思?

支持向量机/support vector machine (SVM)。
关注者
3297
被浏览
244917

39 个回答

@Han Oliver@Linglai Li 前辈们的解释让人受益许多。
正好最近自己学习机器学习,看到reddit上 Please explain Support Vector Machines (SVM) like I am a 5 year old 的帖子,一个字赞!于是整理一下和大家分享。(如有错欢迎指教!)

什么是SVM?

当然首先看一下wiki.
Support Vector Machines are learning models used for classification: which individuals in a population belong where? So… how do SVM and the mysterious “kernel” work?

好吧,故事是这样子的:

在很久以前的情人节,大侠要去救他的爱人,但魔鬼和他玩了一个游戏。

魔鬼在桌子上似乎有规律放了两种颜色的球,说:“你用一根棍分开它们?要求:尽量在放更多球之后,仍然适用。”


于是大侠这样放,干的不错?


然后魔鬼,又在桌上放了更多的球,似乎有一个球站错了阵营。




SVM就是试图把棍放在最佳位置,好让在棍的两边有尽可能大的间隙。


现在即使魔鬼放了更多的球,棍仍然是一个好的分界线。


然后,在SVM 工具箱中有另一个更加重要的 trick。 魔鬼看到大侠已经学会了一个trick,于是魔鬼给了大侠一个新的挑战。


现在,大侠没有棍可以很好帮他分开两种球了,现在怎么办呢?当然像所有武侠片中一样大侠桌子一拍,球飞到空中。然后,凭借大侠的轻功,大侠抓起一张纸,插到了两种球的中间。

现在,从魔鬼的角度看这些球,这些球看起来像是被一条曲线分开了。


再之后,无聊的大人们,把这些球叫做 「data」,把棍子 叫做 「classifier」, 最大间隙trick 叫做「optimization」, 拍桌子叫做「kernelling」, 那张纸叫做「hyperplane」。

图片来源:Support Vector Machines explained well








直观感受看:youtube.com/watch?





参考:
  1. Please explain Support Vector Machines (SVM) like I am a 5 year old. : MachineLearning
  2. Support Vector Machines explained well
  3. youtube.com/watch?
这篇答案贡献给想捋一捋SVM思路的看官。我的初衷是想直观地捋顺SVM的原理和求最优解,尽可能只用到必需的数学表达,但仿佛所有的数学推导都了然于胸。

先看思维导图:
  • 左边是求解基本的SVM问题
  • 右边是相关扩展


什么是SVM?
Support Vector Machine, 一个普通的SVM就是一条直线罢了,用来完美划分linearly separable的两类。但这又不是一条普通的直线,这是无数条可以分类的直线当中最完美的,因为它恰好在两个类的中间,距离两个类的点都一样远。而所谓的Support vector就是这些离分界线最近的『点』。如果去掉这些点,直线多半是要改变位置的。可以说是这些vectors(主,点点)support(谓,定义)了machine(宾,分类器)...


所以谜底就在谜面上啊朋友们,只要找到了这些最靠近的点不就找到了SVM了嘛。
如果是高维的点,SVM的分界线就是平面或者超平面。其实没有差,都是一刀切两块,我就统统叫直线了。

怎么求解SVM?
关于这条直线,我们知道(1)它在离两边一样远,(2)最近距离就是到support vector,其他距离只能更远。
于是自然而然可以得到重要表达 I. direct representation:
\arg\max_{boundary} margin(boundary),
subject to 所有正确归类的苹果和香蕉到boundary的距离都\ge margin
(可以把margin看作是boundary的函数,并且想要找到使得是使得margin最大化的boundary,而margin(*)这个函数是:输入一个boundary,计算(正确分类的)所有苹果和香蕉中,到boundary的最小距离。)
又有最大又有最小看起来好矛盾。实际上『最大』是对这个整体使用不同boundary层面的最大,『最小』是在比较『点』的层面上的最小。外层在比较boundary找最大的margin,内层在比较点点找最小的距离。
其中距离,说白了就是点到直线的距离;只要定义带正负号的距离,是{苹果+1}面为正{香蕉-1}面为负的距离,互相乘上各自的label \in \left\{ +1,-1 \right\} ,就和谐统一民主富强了。

# ========== 数学表达 begin ========== #
# 定义直线为y(x) = w^Tx+b
# 任意点x到该直线的距离为\frac{1}{||w||}(w^Tx+b)
# 对于N个训练点的信息(点的坐标,苹果还是香蕉)记为(x_i, y_i)
# 上述表达也就是[1]:
# \arg\max_{w,b}\left\{ \frac{1}{||w||}\min_{n}\left[ y_i(w^Tx_i+b) \right]  \right\}
# 不知为何这是我见过的最喜欢的写法(比心)
# 也可以写成[2]:
# \arg\max_{w,b,||w||=1} margin
subject to y_i(w^Tx_i+b)\ge margin,  \forall i
# ||w||=1就是为了表达方便[3],后面会取消这个限制
# ========== 数学表达 end ========== #

到这里为止已经说完了所有关于SVM的直观了解,如果不想看求解,可以跳过下面一大段直接到objective function。

直接表达虽然清楚但是求解无从下手。做一些简单地等价变换(分母倒上来)可以得到 II. canonical representation (敲黑板
\arg\min_{boundary}||w||
subject to 所有苹果和香蕉到boundary的距离\ge margin
w不过是个定义直线的参数,知道这一步是等价变换出来的表达就可以了。

# ========== 数学表达 begin ========== #
# 为了以后推导方便,一般写成:
# \arg\min_{w,b}\frac{1}{2}||w||^2

subject to y_i(w^Tx_i+b)\ge 1,  \forall i
# 这个『1』就是一个常数,这样设置是为了以后的方便
# 这个选择的自由来自于直线y(x) = w^Tx+b的参数如果rescale成kwkb不改变距离。
# ========== 数学表达 end ========== #

要得到III. dual representation之前需要大概知道一下拉格朗日乘子法 (method of lagrange multiplier),它是用在有各种约束条件(各种"subject to")下的目标函数,也就是直接可以求导可以引出dual representation(怎么还没完摔)

# ========== 数学表达 begin ========== #
# 稍微解释一下使用拉格朗日乘子法的直观理解,不作深入讨论
# L=\frac{1}{2}||w||^2-\sum_{n=1}^{N}{a_n*\left\{ y_n\left( w^Tx_n+b \right) -1 \right\} } , 其中a_n>0是橙子(划去)乘子[1]
# 可以这样想:(1) 我们的两个任务:①对参数最小化L(解SVM要求),②对乘子又要最大化(拉格朗日乘子法要求), (2) 如果上面的约束条件成立,整个求和都是非负的,很好L是可以求最小值的;(3) 约束条件不成立,又要对乘子最大化,全身非负的L直接原地爆炸
# 好棒棒,所以解题一定要遵守基本法
# ① 先搞定第一个任务对w,b最小化L
# 凸优化直接取导 => 志玲(划去)置零,得到:
# w=\sum_{n=1}^{N}{a_ny_nx_n}
0=\sum_{n=1}^{N}{a_ny_n}
# ② 第二个任务对a最大化L,就是dual representation了
# ========== 数学表达 end ========== #

稍微借用刚刚数学表达里面的内容看个有趣的东西:
还记得我们怎么预测一个新的水果是苹果还是香蕉吗?我们代入到分界的直线里,然后通过符号来判断。
刚刚w已经被表达出来了也就是说这个直线现在变成了:y(x_0) =\sum_{n=1}^{N}{a_ny_nx_n^Tx_0} +b
看似仿佛用到了所有的训练水果,但是其中a_n=0的水果都没有起到作用,剩下的就是小部分靠边边的Support vectors呀。

III. dual representation
把①的结果代回去就可以得到[1]:
\max_{all\ a_n} L(a)=\sum_{n=1}^{N}{a_n} -\frac{1}{2}\sum_{n=1}^{N}{\sum_{m=1}^{N}{a_na_my_ny_mx_n^Tx_m} }
subject to a_n \ge0,\forall n, \sum_{n=1}^{N}{a_ny_n}=0

如果香蕉和苹果不能用直线分割呢?

Kernel trick.
其实用直线分割的时候我们已经使用了kernel,那就是线性kernel, k(x_1,x_2) = x_1^Tx_2
如果要替换kernel那么把目标函数里面的内积全部替换成新的kernel function就好了,就是这么简单。
高票答案武侠大师的比喻已经说得很直观了,低维非线性的分界线其实在高维是可以线性分割的,可以理解为——『你们是虫子!』分得开个p...(大雾)

如果香蕉和苹果有交集呢?
松弛变量 (slack variable \xi\ge0)
松弛变量允许错误的分类,但是要付出代价。图中以苹果为例,错误分类的苹果\xi>1;在margin当中但是正确分类的苹果0<\xi\le 1;正确分类并且在margin外面的苹果\xi=0。可以看出每一个数据都有一一对应的惩罚。
对于这一次整体的惩罚力度,要另外使用一个超参数 (\gamma) 来衡量这一次分类的penalty程度。
从新的目标函数里可见一斑[1]:\min \frac{1}{2}||w||^2 + \frac{\gamma}{2}\sum_{n=1}^{N}{\xi_n^2}
(约束条件略)

如果还有梨呢?
可以每个类别做一次SVM:是苹果还是不是苹果?是香蕉还是不是香蕉?是梨子还是不是梨子?从中选出可能性最大的。这是one-versus-the-rest approach。
也可以两两做一次SVM:是苹果还是香蕉?是香蕉还是梨子?是梨子还是苹果?最后三个分类器投票决定。这是one-versus-one approace。
但这其实都多多少少有问题,比如苹果特别多,香蕉特别少,我就无脑判断为苹果也不会错太多;多个分类器要放到一个台面上,万一他们的scale没有在一个台面上也未可知。

这时候我们再回过头看一下思维导图划一下重点:
课后习题:
1. vector不愿意support怎么办?
2. 苹果好吃还是香蕉好吃?


最后送一张图我好爱哈哈哈 (Credit: Burr Settles)



[1] Bishop C M. Pattern recognition[J]. Machine Learning, 2006, 128.

[2] Friedman J, Hastie T, Tibshirani R. The elements of statistical learning[M]. Springer, Berlin: Springer series in statistics, 2001.

[3] James G, Witten D, Hastie T, et al. An introduction to statistical learning[M]. New York: springer, 2013.