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

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

42 个回答

@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_0 到该直线的距离为\frac{1}{||w||}(w^Tx_0+b)

# UPDATE: 普通点到面的二位欧式距离写法应该是: d=\frac{\left( ax_1+bx_2+c \right)}{\sqrt{a^2+b^2}} (此处允许负数出现),如果升级到更高维度,是不是就和上一行一毛一样?

# 对于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.