SVM 简介【译】

原文:An introduction to Support Vector Machines (SVM)

如果你在处理文本分类问题,为了提炼数据,可能已经尝试过朴素贝叶斯(Naive Bayes)分类算法。如果你的数据集还算正常的话,并且想要一步到位表现更好的话,可以考虑使用 SVM。SVM 是一个在有限数据集上十分快速且靠谱的分类算法。

你可能已经有一点点深入地去学习 SVM 了,是不是遇到了一些专业术语,比如:线性可分(linearly separable)核技巧(kernel trick} 以及 核函数(kernel functions)。不过不用担心,SVM 背后的思想其实很简单,并且想要实际应用到文本分类的话,并不需要多少复杂的知识。

在继续阅读之前,推荐先看一下 朴素贝叶斯分类指南(our guide to Naive Bayes classifiers),这里面有一些关于文本处理的相关知识。

开始。

SVM 是如何运行的?

通过一个简单地例子来更好地理解 SVM 以及它是如何运行的。假设有红、蓝两个标签,并且我们的数据有x、y两个特征。如果我们给出一对 (x,y),想要判断它是红还是蓝。首先画出已有数据集:

数据集

SVM 会输入这些数据点然后输出一个可以最优分割标签的超平面(在二维空间里面是一条直线)。这个超平面就是 决策边界:在我们这个例子里,落在左边的就分类为蓝,落在右边的就分类为红。如图:

在二维空间,分割超平面是一条直线

但是,哪一个才是最优超平面呢?对于 SVM 来说,最优超平面就是到所有标签的距离最大的超平面。换句话来说,就是最优超平面到最近的标签的距离是所有超平面中最大的(在这个例子中是最优分割直线到最近标签的距离为最大)。看一下这个图:

每个分割超平面到最近点的距离都不一样

可以看一下这个YouTube视频,直观感受一下最后超平面是如何找到的。

非线性数据

上面这个例子很简单,因为它是线性可分的,直接找到一条直线就可以完成分类了。然而实际应用中,大多都是线性不可分的,看看下面这个例子:

复杂数据集

很显然,上面这个数据是不可能找到一个直线来划分的。但是我们可以发现,各个标签还是相对分隔明显的,也许有其他的办法分类。

所以这里我们这样操作:新增一个第三维坐标,于是现在变成了x,y,z三个坐标。并且为了方便计算,我们定义 $z=x^2+y^2$(注意到这是一个圆的表达式)。于是在这个三维空间里,我们从垂直于y轴的方向就可以看到下面这样:

从一个不同透视角度看,现在数据集又变成线性可分了

SVM 是怎么做到这样的效果呢?我们继续看看:

.

效果看起来很棒,由于我们现在是在三维空间里,所以这个分割超平面是平行于x轴且垂直于z轴的(这里就是z=1这个平面)。

下面这张图是从z轴的方向垂直向下观察,这样又只看到x,y这两个维度了:

再回到原始的角度,发现数据很清晰地分割开来

这样我们就利用 SVM 将数据集用一个半径为1的圆周分割开来。再看下面这个:视频

这里小结一下:在这个例子中,对于线性不可分的数据,先升到三维空间,再投影到一个线性可分的二维平面进行分类,然后再回到原始的二维平面就可以将线性不可分的数据分类了。

核技巧

在上面这个线性不可分的例子中,我们找到了一种映射到高维的方法来解决了分类问题。但是,计算映射的过程很复杂,而且还要计算不止一个维度。这样处理数据集其实工作量还是比较大得,有没有更简单更高校的方法呢。有,就是我们要说的核技巧

SVM 不需要实际的向量来参与计算,真正有用的时向量之间的点积(dot products),这样我们就可以直接跳过第一步的升维映射计算过程了。

下面是我们要做的事情:

  • 引入我们需要的新空间:$z=x^2+y^2$
  • 计算出这个空间里向量之间新的点积和,例如:

$a \cdot b=x_a \cdot x_b+y_a \cdot y_b+z_a \cdot z_b$

$a \cdot b=x_a \cdot x_b+y_a \cdot y_b+(x_a^2+y_a^2) \cdot (x_b^2+y_b^2)$

  • 让 SVM 来解决分类问题,但是要使用上面这个新的点积-我们称之为核函数

这就是我们所说的核技巧,避免了许多复杂计算。通常这个是线性的,并且我们会得到一个线性分类器。但是,我们也可以使用一个非线性核(上面这个例子),从而得到一个非线性分类器,也可以避免大量计算。

值得注意的是,核技巧并不是 SVM 所特有的一部分,核技巧也可以用于其他线性分类器,例如:logistic regression。SVM 本身只关注决策边界。

SVM 如何应用于自然语言分类

根据上面的知识,我们可以在多维空间里对向量进行分类。现在要讲这个算法应用于文本分类,首先要做的就是把一条一条的文本转换为一个一个的数字向量,才能使用 SVM 来进行分类。另一方面,我们使用 SVM 进行文本分类的时候,需要关注文本的什么特征呢?

一般我们关注的就是词频,就像之前朴素贝叶斯算法中所做的一样。我们把文本看做一袋单词,出现在这里面的单词有一个特征,就是在整个文本中这个单词出现的频率,也就是词频。

词频的计算方式就是用这个词在文本中出现的次数除以整个文本的单词个数。例如这个句子”All monkeys are primates but not all primates are monkeys”,单词 “monkeys” 的词频就是 2/10=0.2,”but” 这个词的词频是 1/10=0.1。

此外,还可以使用 TF-IDF来计算词频。

经过上面的操作,我们数据集中得所有文本就变成了一系列多维向量,向量里的元素代表着每个单词的词频。这时候我们再把数据喂给 SVM 处理。我们还可以使用预处理技术例如 “stemming”,移除停顿词,以及使用 “n-grams”。

选择一个核函数

既然我们已经有了这些特征向量,剩下的事情就是为模型选择核函数了。每个问题都要具体对待,并且核函数取决于具体的数据。这个例子中我们的数据分布看起来是一个同轴的圆,所以我们选择一个适用于这些数据点的核函数。

考虑到这一点,哪个核函数才最适用于自然语言处理呢?我们需要一个非线性分类器么?或者这个数据是线性可分的么?这样一看,我们最好选择一个线性核,为什么呢?

回到上面这个例子中,我们的数据有两个特征。而 SVM 实际应用中,特征会非常多。我们的例子使用非线性核也许比较合适,可以避免过拟合。

整合

剩下的事情就是训练数据了!从数据集中拿出一部分,并为其设置标签,将其转化为词频向量,然后喂给 SVM。最终会生成一个模型。然后未标记的数据就可以用这个模型来分类了。注意也要将这些数据转化为词频向量,然后分类结果就是输出这个文本的标签。

结语

这里只是 SVM 的基础知识!

  • 总结如下:SVM 可以对线性可分的数据进行分类。
  • 如果数据线性不可分,则要使用核技巧来使得 SVM 可以生效。
  • 对于文本分类来说,尽量选用线性核。

像神经网络这样新的算法,它们有两个优势:更快速高效并且在数据量少的时候表现良好。这就使得这些新的算法更适合文本分类,只要从数据集中拿出一小部分去训练模型即可。

想要深入了解 SVM,可以学习 MIT的这个课程


THE END.

评论