|
|||||
|
本文是“支持向量机系列”的第五篇，参见本系列的其他文章。 作为支持向量机系列的基本篇的最后一篇文章，我在这里打算简单地介绍一下用于优化 dual 问题的 Sequential Minimal Optimization (SMO) 方法。确确实实只是简单介绍一下，原因主要有两个：第一这类优化算法，特别是牵涉到实现细节的时候，干巴巴地讲算法不太好玩，有时候讲出来每个人实现得结果还不一样，提一下方法，再结合实际的实现代码的话，应该会更加明了，而且也能看出理论和实践之间的差别；另外（其实这个是主要原因）我自己对这一块也确实不太懂。 在电脑上输入公式一直不是一件很愉快的事情，经历过 Word 的公式编辑器时代，还有 MathType ，只能说输入不方便而且结果非常难看。LaTeX 虽然号称是“所想即所得”，书写数学公式也相对流畅，然而有时候稍微复杂的公式写出来变成一堆结构不明显的代码，实在是比较难以继续——又不是所见即所得的，LaTeX 的错误信息又是那么让人摸不着头脑，遇到复杂的公式总是忍不住写一部分又编译一下看看是不是有问题，结果弄得很麻烦。但总归 LaTeX 渲染出来的公式目前来说还是最好看的，而且所见即所得的公司编辑确实也比较难做。Office 2007 开始有了新的公式编辑器，可以使用类似 LaTeX 的语法，渲染结果也比以前的那种要漂亮许多，不过那个所见即所得的编辑实在是非常难以驾驭，经常出现的结果是写了一大坨公式想要删掉其中的一个符号却删不掉，Office 只准你把这一整坨一起删掉，实在是很恶心，而且有时候还会有一些诡异的 bug 。就目前我尝试过的解决方案来说，我个人觉得 Emacs + CDLaTeX.el 是输入起来最迅速的，各种常用的符号、加粗斜体等操作都可以迅速完成；而最好用的是 LyX ，所见即所得的 LaTeX 公式编辑，总的编辑体验比 TeXmacs 要好。 本文是“支持向量机系列”的第四篇，参见本系列的其他文章。 在最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据，使用 Kernel 方法对原来的线性 SVM 进行了推广，使得非线性的的情况也能处理。虽然通过映射 $\phi(\cdot)$ 将原始数据映射到高维空间之后，能够线性分隔的概率大大增加，但是对于某些情况还是很难处理。例如可能并不是因为数据本身是非线性结构的，而只是因为数据有噪音。对于这种偏离正常位置很远的数据点，我们称之为 outlier ，在我们原来的 SVM 模型里，outlier 的存在有可能造成很大的影响，因为超平面本身就是只有少数几个 support vector 组成的，如果这些 support vector 里又存在 outlier 的话，其影响就很大了。例如下图： 用黑圈圈起来的那个蓝点是一个 outlier ，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个 outlier 的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时 margin 也相应变小了。当然，更严重的情况是，如果这个 outlier 再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。 本文是“支持向量机系列”的第三篇，参见本系列的其他文章。 前面我们介绍了线性情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过，由于是线性方法，所以对非线性的数据就没有办法处理了。例如图中的两类数据，分别分布为两个圆圈的形状，不论是任何高级的分类器，只要它是线性的，就没法处理，SVM 也不行。因为这样的数据本身就是线性不可分的。 对于这个数据集，我可以悄悄透露一下：我生成它的时候就是用两个半径不同的圆圈加上了少量的噪音得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用 $X_1$ 和 $X_2$ 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式： \[ 注意上面的形式，如果我们构造另外一个五维的空间，其中五个坐标的值分别为 $Z_1 = X_1$, $Z_2=X_1^2$, $Z_3=X_2$, $Z_4=X_2^2$, $Z_5=X_1X_2$，那么显然，上面的方程在新的坐标系下可以写作： 本文是“支持向量机系列”的第二篇，参见本系列的其他文章。 上一次介绍支持向量机，结果说到 Maximum Margin Classifier ，到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图： 可以看到两个支撑着中间的 gap 的超平面，它们到中间的 separating hyper plane 的距离相等（想想看：为什么一定是相等的？），即我们所能得到的最大的 geometrical margin $\tilde{\gamma}$ 。而“支撑”这两个超平面的必定会有一些点，试想，如果某超平面没有碰到任意一个点的话，那么我就可以进一步地扩充中间的 gap ，于是这个就不是最大的 margin 了。由于在 $n$ 维向量空间里一个点实际上是和以原点为起点，该点为终点的一个向量是等价的，所以这些“支撑”的点便叫做支持向量。 之前一直用一个 LaTeX 的 WordPress 插件来显示公式，插件的工作原理很简单，把公式用 LaTeX 编译为 dvi ，然后用 dvi2png 之类的工具转换为图片，最后根据公式的文本内容算出一个 Hash 值，作为图片的文件名，缓存起来，下次遇到需要显示同样的公式的时候，如果文件已经存在的话，就不重新生成一遍了。 本文是“支持向量机系列”的第一篇，参见本系列的其他文章。 支持向量机即 Support Vector Machine，简称 SVM 。我最开始听说这头机器的名号的时候，一种神秘感就油然而生，似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起，然后再做成一个 Machine ，一听就很玄了！ 不过后来我才知道，原来 SVM 它并不是一头机器，而是一种算法，或者，确切地说，是一类算法，当然，这样抠字眼的话就没完没了了，比如，我说 SVM 实际上是一个分类器 (Classifier) ，但是其实也是有用 SVM 来做回归 (Regression) 的。所以，这种字眼就先不管了，还是从分类器说起吧。 SVM 一直被认为是效果最好的现成可用的分类算法之一（其实有很多人都相信，“之一”是可以去掉的）。这里“现成可用”其实是很重要的，因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间，都有一种“鸿沟”，有些很 fancy 或者很复杂的算法，在抽象出来的模型里很完美，然而在实际问题上却显得很脆弱，效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。 |
 |
||||
|
Copyright © 2021 Free Mind - All Rights Reserved |
|||||
by pluskid, on 2010-09-15, in 
Comments