by pluskid, on 2010-09-08, in 
本文是“支持向量机系列”的第一篇，参见本系列的其他文章。
支持向量机即 Support Vector Machine，简称 SVM 。我最开始听说这头机器的名号的时候，一种神秘感就油然而生，似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起，然后再做成一个 Machine ，一听就很玄了！
不过后来我才知道，原来 SVM 它并不是一头机器，而是一种算法，或者，确切地说，是一类算法，当然，这样抠字眼的话就没完没了了，比如，我说 SVM 实际上是一个分类器 (Classifier) ，但是其实也是有用 SVM 来做回归 (Regression) 的。所以，这种字眼就先不管了，还是从分类器说起吧。
SVM 一直被认为是效果最好的现成可用的分类算法之一（其实有很多人都相信，“之一”是可以去掉的）。这里“现成可用”其实是很重要的，因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间，都有一种“鸿沟”，有些很 fancy 或者很复杂的算法，在抽象出来的模型里很完美，然而在实际问题上却显得很脆弱，效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。
好了，由于 SVM 的故事本身就很长，所以废话就先只说这么多了，直接入题吧。当然，说是入贴，但是也不能一上来就是 SVM ，而是必须要从线性分类器开始讲。这里我们考虑的是一个两类的分类问题，数据点用 $x$ 来表示，这是一个 $n$ 维向量，而类别用 $y$ 来表示，可以取 1 或者 -1 ，分别代表两个不同的类（有些地方会选 0 和 1 ，当然其实分类问题选什么都无所谓，只要是两个不同的数字即可，不过这里选择 +1 和 -1 是为了方便 SVM 的推导，后面就会明了了）。一个线性分类器就是要在 $n$ 维的数据空间中找到一个超平面，其方程可以表示为
\[
w^Tx + b = 0
\]
一个超平面，在二维空间中的例子就是一条直线。我们希望的是，通过这个超平面可以把两类数据分隔开来，比如，在超平面一边的数据点所对应的 $y$ 全是 -1 ，而在另一边全是 1 。具体来说，我们令 $f(x)=w^Tx + b$ ，显然，如果 $f(x)=0$ ，那么 $x$ 是位于超平面上的点。我们不妨要求对于所有满足 $f(x)<0$ 的点，其对应的 $y$ 等于 -1 ，而 $f(x)>0$ 则对应 $y=1$ 的数据点。当然，有些时候（或者说大部分时候）数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在，不过关于如何处理这样的问题我们后面会讲，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。
如图所示，两种颜色的点分别代表两个类别，红颜色的线表示一个可行的超平面。在进行分类的时候，我们将数据点 $x$ 代入 $f(x)$ 中，如果得到的结果小于 0 ，则赋予其类别 -1 ，如果大于 0 则赋予类别 1 。如果 $f(x)=0$，则很难办了，分到哪一类都不是。事实上，对于 $f(x)$ 的绝对值很小的情况，我们都很难处理，因为细微的变动（比如超平面稍微转一个小角度）就有可能导致结果类别的改变。理想情况下，我们希望 $f(x)$ 的值都是很大的正数或者很小的负数，这样我们就能更加确信它是属于其中某一类别的。
从几何直观上来说，由于超平面是用于分隔两类数据的，越接近超平面的点越“难”分隔，因为如果超平面稍微转动一下，它们就有可能跑到另一边去。反之，如果是距离超平面很远的点，例如图中的右上角或者左下角的点，则很容易分辩出其类别。
实际上这两个 Criteria 是互通的，我们定义 functional margin 为 $\hat{\gamma}=y(w^Tx+b)=yf(x)$，注意前面乘上类别 $y$ 之后可以保证这个 margin 的非负性（因为 $f(x)<0$ 对应于 $y=-1$ 的那些点），而点到超平面的距离定义为 geometrical margin 。不妨来看看二者之间的关系。如图所示，对于一个点 $x$ ，令其垂直投影到超平面上的对应的为 $x_0$ ，由于 $w$ 是垂直于超平面的一个向量（请自行验证），我们有
\[
x=x_0+\gamma\frac{w}{\|w\|}
\]
又由于 $x_0$ 是超平面上的点，满足 $f(x_0)=0$ ，代入超平面的方程即可算出
\[
\gamma = \frac{w^Tx+b}{\|w\|}=\frac{f(x)}{\|w\|}
\]
不过，这里的 $\gamma$ 是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 $y$ 即可，因此实际上我们定义 geometrical margin 为：
\[
\tilde{\gamma} = y\gamma = \frac{\hat{\gamma}}{\|w\|}
\]
显然，functional margin 和 geometrical margin 相差一个 $\|w\|$ 的缩放因子。按照我们前面的分析，对一个数据点进行分类，当它的 margin 越大的时候，分类的 confidence 越大。对于一个包含 $n$ 个点的数据集，我们可以很自然地定义它的 margin 为所有这 $n$ 个点的 margin 值中最小的那个。于是，为了使得分类的 confidence 高，我们希望所选择的 hyper plane 能够最大化这个 margin 值。
不过这里我们有两个 margin 可以选，不过 functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩放 $w$ 的长度和 $b$ 的值，这样可以使得 $f(x)=w^Tx+b$ 的值任意大，亦即 functional margin $\hat{\gamma}$ 可以在 hyper plane 保持不变的情况下被取得任意大，而 geometrical margin 则没有这个问题，因为除上了 $\|w\|$ 这个分母，所以缩放 $w$ 和 $b$ 的时候 $\tilde{\gamma}$ 的值是不会改变的，它只随着 hyper plane 的变动而变动，因此，这是更加合适的一个 margin 。这样一来，我们的 maximum margin classifier 的目标函数即定义为
\[
\max \tilde{\gamma}
\]
当然，还需要满足一些条件，根据 margin 的定义，我们有
\[
y_i(w^Tx_i+b) = \hat{\gamma}_i \geq \hat{\gamma}, \quad i=1,\ldots,n
\]
其中 $\hat{\gamma}=\tilde{\gamma}\|w\|$ ，根据我们刚才的讨论，即使在超平面固定的情况下，$\hat{\gamma}$ 的值也可以随着 $\|w\|$ 的变化而变化。由于我们的目标就是要确定超平面，因此可以把这个无关的变量固定下来，固定的方式有两种：一是固定 $\|w\|$ ，当我们找到最优的 $\tilde{\gamma}$ 时 $\hat{\gamma}$ 也就可以随之而固定；二是反过来固定 $\hat{\gamma}$ ，此时 $\|w\|$ 也可以根据最优的 $\tilde{\gamma}$ 得到。处于方便推导和优化的目的，我们选择第二种，令 $\hat{\gamma}=1$ ，则我们的目标函数化为：
\[
\max \frac{1}{\|w\|}, \quad s.t., y_i(w^Tx_i+b)\geq 1, i=1,\ldots,n
\]
通过求解这个问题，我们就可以找到一个 margin 最大的 classifier ，如下图所示，中间的红色线条是 Optimal Hyper Plane ，另外两条线到红线的距离都是等于 $\tilde{\gamma}$ 的：
到此为止，算是完成了 Maximum Margin Classifier 的介绍，通过最大化 margin ，我们使得该分类器对数据进行分类时具有了最大的 confidence （实际上，根据我们说给的一个数据集的 margin 的定义，准确的说，应该是“对最不 confidence 的数据具有了最大的 confidence”——虽然有点拗口）。不过，到现在似乎还没有一点点 Support Vector Machine 的影子。很遗憾的是，这个要等到下一次再说了，不过可以先小小地剧透一下，如上图所示，我们可以看到 hyper plane 两边的那个 gap 分别对应的两条平行的线（在高维空间中也应该是两个 hyper plane）上有一些点，显然两个 hyper plane 上都会有点存在，否则我们就可以进一步扩大 gap ，也就是增大 $\tilde{\gamma}$ 的值了。这些点呢，就叫做 support vector ，嗯，先说这么多了。
ps: 本文开头那张照片来源于这里。Allaboutinquiry 同学留言揭露典故真相啦： 😀
关于这个同学举牌子的典故我知道，我也是CMU的。这是在2009年在Pittsburgh举行的G20峰会现场外面。很多反对G20的，支持G20的都来凑热闹。我们这位同学也来了，鱼目混珠的高举Support Vector Machine的牌子。很多老美就晕了，你说你支持加强控制二氧化碳排放我懂，你支持的的这个Vector Machine是个什么东西啊？然后这个同学搞笑的目的就达到了。
喜欢你的博客，因为每篇文章都有科学小品文的感觉。
SVM的目标肯定是“对最不 confidence 的数据具有了最大的 confidence”。但是直接用距离对应每个数据点的confidence，我还有些疑问，虽然很多情况下这么用都有不错的效果。
在使用了kernel的非线性情况中，距离是kernel映射的高维空间中的值。但不同的kernel，甚至不同参数的同类型kernel，会映射到不同的高维空间（即使这个空间无法显式构造）。这造成了两个确定的数据点在不同kernel下的confidence的大小不确定。这样的confidence可靠吗？
具体的情况是，引入新的训练数据后，发现需要修改训练参数来达到最好的效果，这时高维空间已经改变。
当然实际应用中应该构造尽可能吻合数据内在特性的特征空间，避免这种情况。
确实在不同的 Kernel 下 margin 的大小会不一样，但是 SVM 要追求的并不是不同 Kernel 下 margin 数值大小里求一个最大的，而是在固定了 Kernel 之后去确定 margin 最大的那个超平面。也就是说 SVM 的目标函数本身是并不能用来选择具体是哪个 Kernel 的，这是一个 model selection 的问题，和 SVM 要优化的问题不是在一个层次上的。
关于 data adaptive Kernel ，可以参考 ICML 2005 年的一篇 Beyond the point cloud: from transductive to semi-supervised learning 。
我有疑问的并不是SVM的优化的目标，而是基于SVM的优化结果对具体数据点设置confidence是否合理。
使用到超平面的距离作为confidence后，SVM不仅给出了定性的分类结果，而且是定量的。也就是离分割平面越远的点越属于某类别。这样的理解下，所有支持向量则是最不可靠的点。极端的用法就是用距离这个置信度作为新的维度来衡量所有数据点，并重新设定分类阈值。这相当于平行地移动了超平面。
而按我的理解，SVM是针对整体统计的优化，目标是使两个类别之间的距离最大化。而这个距离并不能用于个别数据点之间的比较。
使用距离 separating plane 的距离作为 confidence 的度量是合理的，不止是 SVM ，任何一个用超平面进行分类的算法都是这样。而“所有支持向量则是最不可靠的点”也是对的，当然要看你如何去理解“可靠”一词。你可以参考用 SVM 做 Active Learning 的文章，就是优先选择超平面附近的点，因为它们的不确定性最大。
我想文中的confidence应该只是定性的说明，而不是数学意义上的置信度。
另外，“所有支持向量则是最不可靠的点”，可靠与否应该是针对分类测试时所用的描述语吧。在training的时候，所有数据点都是同样的百分百可靠，因为都是有label的数据。
数学符号和公式在Chrome浏览器里显示效果不佳
位置有些错乱
在IE里有些偏淡偏细
在FIREFOX里会有不均匀的情况
看来这个东西还是IE里显示效果比较正常
装了STIX字体后好了一点
但还是不能算好看…
不知道你是什么系统？我试过 Linux 下的 Firefox 和 Windows 下的 Chrome 都是很不错的，事实上我觉得目前 Chrome 下显示是最漂亮的。不过确实有碰到错位的情况，但是只是偶尔，似乎是 bug ，需要重新打开 Chrome 。
可以在公式上右键，会有菜单弹出来，可以定制公式的显示，比如全体 scale 为 130% 的话，会看起来清晰不少。
[…] This post was mentioned on Twitter by yongsun, wuyuntao. wuyuntao said: [GR] 支持向量机: Maximum Margin Classifier: 支持向量机即 Support Vector Machine，简称 SVM 。我最开始听说这头机器的名号的时候，一种神秘感就油然而生，似乎把 Suppo… http://bit.ly/clls3K […]
喜欢这样的文章。
[…] 支持向量机: Maximum Margin Classifier —— 支持向量机简介。 […]
我们将数据点 x 带入 f(x) 中
此处是 “代入” 吧
嗯，没错，多谢指正！已经改过来了。
“我们可以很自然地定义一个包含 n 个点的数据集的 margin 为所有 n 个点中最小的那个 margin 的值。” 哥哥你这句话真是让人费劲啊！ -_-‘
好吧，我改过了……
kid大人 我还是不那么明白 为什么r（hat）可以设置成1呢？
有更加formal的说明吗？
因为对于一个确定的解（超平面），可以有无穷多个 w （长度不同），每个 w 对应一个 $\hat{\gamma}$ ，所以说这个玩意变动是对解没有影响的，你可以把它看成一个等价关系，构成一个等价类，我们就取这个等价类里 $\hat{\gamma}=1$ 的那个代表元。
喔喔 有多明白一些 THANKS！
那我换个角度问，这里最终是要导出最大的margin只和超平面的法向量有关，但距离公式里是有偏移量b的，这个b怎么去掉的？Burges的文章里也是这个也是一带而过。有formal的说法吗？
关于 b 的计算，可以看 Ng 的讲义里有。
[…] 支持向量机: Maximum Margin Classifier /?p=632 […]
你好，我也是搞ML的，感觉看了你的博客有新的体会，也有新的困惑啊~
呵呵，两个问题：
1.推导约束条件时，为什么直接“根据 margin 的定义”就直接得到，\\gamma_i >= \\gamma啊？这个约束意思就是所有点的functional margin都必须大于等于\\gamma，具体怎么直观理解？
2.其实那个geometrical margin就是点到直线的距离公式嘛，可以直接得到，你那样一推导反而有些不好理解了，呵呵，个人意见
你好，因为 margin 的定义就是 $\gamma=\min_i\gamma_i$ ，所以自然 $\gamma\leq\gamma_i$ 啦。
点到直线的距离的公式我自己是不知道的，就这样推导啦，不过反正公式也可以这样推出来，记不住那么许多公式也没有关系了，嘿嘿。
明白了，呵呵
[…] 支持向量机: Maximum Margin Classifier /?p=632 […]
请问，本文第一张图片，就是有个帅哥举牌子的那张图，有什么说道啊？
想知道举牌子的那张图片什么典故？
我也不知道，猜测也许是某游行活动之类的，别人都支持某个人，然后他写了个“支持” vector machine ……
那帅哥好像今年phd毕业了 搞好多active learning
啊，你不说我还真没有注意到，原来《Active Learning Literature Survey》就是他写的啊！
呵呵 那是他博士论文一章添了点改的
你是今天申请美国的phd吗 话说我算是machine learning／vision方向
这样啊！
我不是今年申请，你是今年？现在拿到 offer 了吗？
关于这个同学举牌子的典故我知道，我也是CMU的。这是在2009年在Pittsburgh举行的G20峰会现场外面。很多反对G20的，支持G20的都来凑热闹。我们这位同学也来了，鱼目混珠的高举Support Vector Machine的牌子。很多老美就晕了，你说你支持加强控制二氧化碳排放我懂，你支持的的这个Vector Machine是个什么东西啊？然后这个同学搞笑的目的就达到了。
哈哈！谢谢！大赞典故！我编辑到正文里去啦~ 😀
我去年申的 现在已经在米国了。。。不过刚搞这方面 一点都不熟
原来如此，不过慢慢就会熟悉啦～
这是我看你博客的第一篇文章，感觉真好，激发了我的兴趣。。。。。把一个我从来没有接触过的东西讲的通俗易懂啊！！大牛一个。。。。。我会继续关注您的博客，向您学习！！！
[…] 支持向量机: Maximum Margin Classifier —— 支持向量机简介。 […]
请问你的坐标图都是用什么软件做的，还有我的毕业论文想参考你这个系列的文章，觉得你应该给这个系列写一个bib的引用供大家参考
坐标图，不记得了……也许是 Illustrator 或者 powerpoint 之类的吧，不过这种简单的图应该随便找个工具都能画啦。 bibtex 还是不要啦，这个只是非正式的 tutorial ，不能算正式出版物的 :p
有一点不太明白望指教。那个geometrical margin相当于x点到超平面的距离，那么想请问一下那个functional margin的意义是什么呢？
呃，可以看成一个正比于 geometrical margin 的量……
写得很好！浅显易懂！！
\tilde{\gamma} = y\gamma = \frac{\hat{\gamma}}{\|w\|}
这个公式好像不对吧？
这里是定义啊，哪里不对？
不好意思。字太小，以至于把Y的两个上标看成相同了。
geometrical margin的计算错了吧，对x=x0+γ*ω/||ω||两边作用f,应该得到γ=ωTx+b=f(x)才对啊！也就是没有下面的||ω||。
你好，w^T w = ||w||^2 ，有个平方的，只能消掉一个。
关于这个怎么求出来 我还是有点不解。
那么x=xo+rw/||w|| -> f(x) = f(xo+rw/||w||) ->f(x)=f(xo) + f(rw/||w||) =o+f(rw/||w||)
由于f(x)= w^Tx + b，所以f(rw/||w||)= r||w||^2/||w|| +b = r||w||+b,
因为f(x) = f(xo)+f(rw/||w||) ,可是推导不出来最后的那个公式，请问我的带进去哪里出错了。
我刚才从一份Lecture notes上得到了如何推导，我这里写出来吧，x=xo+rw/||w||，首先两边诚意W^T,
=>w^Tx = w^Txo + r w^T w /||w|| ,
w^Tx 就是之前那个functional margin – b, 因为functional margin是 w^Tx +b=>f(x)-b =w^Tx
把左边的b移到右边 ，w^Txo + b =0,因为xo那个点是在Hyper plane, hyper plane上的方程是f(x)=0
这样,f(x)= r w^T w /||w||，由于楼主说过 w^T w = ||w||的平方，所以最后就可以得出，r=f(x)/||w||
奥，对。丢人了。：-p 基本概念都忘完了，泛函分析白学了。
不过，这里的 γ 是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别 y 即可。
你好 楼主 我是名新手。请问 这里乘上对应的类别y即可，类别y是指取值，+1, -1吗，
你好，对的，+1 、-1 两类。
不过这里我们有两个 margin 可以选，不过 functional margin 明显是不太适合用来最大化的一个量，因为在 hyper plane 固定以后，我们可以等比例地缩放 w 的长度和 b 的值，这样可以使得 f(x)=wTx+b 的值任意大
这段开始到后面 有点不明白，
不变的情况下被取得任意大，而 geometrical margin 则没有这个问题，因为除上了 ∥w∥ 这个分母，所以缩放 w 和 b 的时候 γ˜ 的值是不会改变的，它只随着 hyper plane 的变动而变动
w值变化和|w|值变化率不一样，所以r””的值是会改变的？ 新手不明白啊，求解
w 的方向不变，长度变化的情况下，再怎么变 geometrical margin 都不会变化，因为分母上已经除以那个长度值了，所以相当于缩放之后又缩放回来了。
下面这句话
二是反过来固定 γˆ ，此时 ∥w∥ 也可以根据最优的 γ˜ 得到。处于方便推导和优化的目的，我们选择第二种，令 γˆ=1 ，则我们的目标函数化为：
你这句话意思是不是说，不论两边的正负数据的支持向量如何分布，比如说有可能H1,H2线是直的，有可能H1,H2线是45独斜的，但不管线条如何怎样，H1,H2 始终是yi(wxi+b) =1, 只不过每种情况下b,w参数不一样。斑竹 我这句理解正确吗
恩，对的，只要是 support vector 就满足那样的性质。
你好，请问一个问题，对于二维空间所对应的超平面就是一条直线，那么如果W改变的话，对应的直线是否就应该改变呢？那么如何调整W和d是的f(x)达到很大呢，刚刚开始了解这个方面，请多多指点。
你好，w 的方向改变的话直线也会改变，如何调整的话这是一个数值优化问题。
谢谢，我还得多多学习了。☺
博主写得太好了，学习学习
为什么我的浏览器显示不了数学公式呢？
什么浏览器？
你好，是360的浏览器。
这个不会是基于 IE6 之类的内核吧？主流的浏览器 Firefox Chrome 还有比较新的 IE 应该都能正常显示的。
你好!刚开始学ML，请教一个问题，结构风险最小化原则体现在支持向量机的哪个点上？
margin 最大化。
楼主好！我现在在做一种病——ADHD的分类，现在觉得特征选择是很重要的，是不是只要特征选择选好了输入到SVM里不怎么调整参数什么的就可以大概分类成功率很好？？？
拜读了lz的N篇文章后，对这个领域有更浓厚的兴趣。请问楼主所在的lab 有没有phd position，申请条件如何
非常感谢
你好，PhD position 正常情况下每年都有的，申请总体来说比较困难吧。
你好，感谢LZ的回复。请问LZ 有何联系方式（个人主页啥的），想咨询点phd position。
非常感谢
可以发我邮箱。
刚开始了解关于SVM的内容，就看到了楼主的一篇好博。
觉得文章写的真好，还是大三写的。就觉得楼主前途无量，果然发现楼主已经在MIT Phd.
我在纽约 fordham 读cs master, 以后多关牛博，也希望和楼主多交流。
kid大神，“另外两条线到红线的距离都是等于 γ˜ 的”，这是为什么呢？
能不能借用的你的几个SVM的图，打算用在ppt里面，解释一下什么是SVM
没问题的
由于 w 是垂直于超平面的一个向量.这句话怎么理解。。。。看直线是表示斜率吧。。。
求大神给稍微解释下。。。
多谢楼主的文章。 对svm很感兴趣。
Logan同学的问题我来证明一下吧.
证明:超平面wx+b=0垂直于向量w
对于超平面内任一向量AB
点A和点B因为是超平面上的点
满足f(A)=0;f(B)=0,
即wA+b=0,wB+b=0
同时向量AB可以表示为A-B (点A,点B都是空间内的向量).
那么w(A-B)=wa-wb=(-b)-(-b)=0
所以w与超平面内任一向量垂直,所以w与超平面垂直.
证毕
p.s.另外”对最不 confidence 的数据具有了最大的 confidence”实际上就是求一个超平面,这个平面使得两个不同类的点到平面的距离的下界最大,这样解释可能没这么拗口.
大神，您好。看你的blog已经成为习惯了。2013的总结也看了。今天又返回到svm看看。我现在想出国留学做文本挖掘方向，请问有推荐入门级的项目吗？方便发封邮件到我邮箱(jetfish1900@163.com)吗？谢谢！
你好，虽然属于 retrieval 而不是 mining，不过 TREC 每年都有比赛的（ http://trec.nist.gov/pubs/call2014.html ），另外 Kaggle 上可以找找有没有相关的比赛或者项目。
总觉得这里好像推导有问题：
又由于 x0 是超平面上的点，满足 f(x0)=0 ，代入超平面的方程即可算出
γ=f(x)/∥w∥
我代入计算得到的是γ=f(x)*∥w∥
求解释
因为你算错了吧？你自己解释一遍你怎么得到那个结果的也许就知道哪里出错了
大神你好！想请问一下怎么定义“hyper plane 保持不变”呢，为什么“等比例地缩放 w 的长度和 b 的值”以后，hyper plan会保持不变呢？
就是 hyperplane 的位置不变啊。就是 hyperplane 的方程不变。 Ax + b = 0 这个方程，两边同时乘以一个 scale 不会改变这个方程。
同请教，Ax+b=0两边同时乘以一个 s, hyperplane 的方程不变, 但是hyperplane会变吧，例如图二中的红色直线，A变成As，红色直线的斜率变了，b变成bs，截距也变了？我是在哪里理解错了
A是向量形式的权重，不是斜率。
同一个文同时出现了 “hyper plane” 和「超平面」两个词，最好一致性地只用其中一个词。
真是太棒啦，我看了好多资料都没能理解。现在总算有点初步的理解啦。
你好~ 看了你的blog真的很有收获。我有个小小的问题，这里 n 的意义是不是混用了呢，在第四段里 n 指的是空间的维数， 但是在后面优化问题的推到里面，n 的意义似乎变成了训练样本的数目。