[译] 支持向量机（SVM）教程

支持向量机（SVM）教程

从例子中学习 SVM

在 Statsbot 团队发布关于时间序列异常检测的帖子之后，许多读者要求我们告诉他们有关支持向量机的方法。现在是时候在不涉及复杂数学知识的情况下向您介绍 SVM，并分享有用的库和资源以帮助您入门了。

如果您已经使用机器学习来执行分类，您可能听说过支持向量机（SVM）。50 多年前被引入，它们随着时间的推移而发展，并且已经适应了各种其他问题，如回归分析、异常值分析和排名。

SVM 是许多机器学习从业者的最佳工具。在[24]7，我们也使用它们来解决各种问题。

在这篇文章中，我们将尝试深入了解 SVM 的工作原理。我会专注于建立直觉而并不追求严谨。这基本上意味着我们将尽可能多地跳过数学并建立起对工作原理的直觉理解。

分类问题

假设您的大学提供机器学习（ML）课程。课程导师观察到，如果学生擅长数学或统计学，他们将获得最大的收益。随着时间的推移，他们记录了这些科目的入学学生的分数。此外，对于其中的每一个学生，他们都有一个描述他们在 ML 课程中表现“好”或“差”的标签。

现在，他们想要确定数学和统计学分数与 ML 课程中的表现之间的关系。也许，根据他们发现的内容，他们希望指定入学课程的先决条件。

情况会怎么样呢？让我们从表示他们拥有的数据开始。我们可以绘制一个二维图，其中一个轴代表数学分数，而另一个代表统计分数。具有特定分数的学生在图表上显示为一个点。

点的颜色——绿色或红色——代表他在 ML 课程中的表现：分别为“好”或“差”。

绘出来的图有可能是这样的：

当学生要求报名时，我们的教师会要求她提供她的数学和统计学分数。根据他们已有的数据，他们会对 ML 课程中的表现做出有根据的的猜测。

我们本质上想要的是某种“算法”，你可以在其中输入表格的“得分元组”（math_score，stats_score）。它会告诉你某个学生是图形上的红点还是绿点（红色 / 绿色也可称为类或标签）。当然，该算法以某种方式体现了我们已经拥有的数据中存在的模式，也称为训练数据。

在这种情况下，找到穿过红点即和绿点集之间的直线，然后确定得分元组落在该线的哪一侧，是一个很好的算法。我们采取一方——绿色方面或红色方面——作为她在课程中最有可能表现的一个指标。

这里的直线就是我们的分割边界（separating boundary）（因为它分隔了标签）或分类器（我们用它来对点进行分类）。该图展示了在我们的问题中两种都有可能的产生的分类器。

好的 vs 坏的分类器

这是一个有趣的问题：上面的两条线都可以将红色和绿色的数据集分开。我们是否有充分的理由选择其中一个而不是另一个？

请记住，分类器的价值不在于它如何区分训练数据。我们最终希望它对尚未看到的数据点进行分类（称为测试数据）。鉴于此，我们希望选择一条线来捕获训练数据中的基本模式，因此很有可能它在测试数据上表现良好。

上面的第一条直线看起来有点“倾斜”。在它的下半部分附近，它似乎太靠近红点色数据集了，而在它的上半部分它太靠近绿色数据集了。当然，它可以完美地分离训练数据，但是如果测试点离数据集稍远一点，那么它很可能会得到一个错误的标签。

第二条直线没有这个问题。例如，看看下图中已正方形显示的测试点以及分类器指定的标签。

第二条直线尽可能远离两个数据集，同时使训练数据正确分离。它通过两个数据集的中间部分，它不那么“冒险”，可以为每个类提供一些空间来布置数据分布，从而很好的适用于测试数据。
SVM 试图找到这第二种线。我们通过视觉选择了更好的分类器，但我们需要更精确地定义基础原理以便在一般情况下应用它。这是 SVM 的简化版本：

找到能够正确分类训练数据的直线。
在所有这些直线中，选择与它最近的点距离最远的直线。

距离这条直线的最近那些点称为支持向量（support vectors）。他们围绕这条线定义的区域称为间隔（margin）。

下面显示的是第二条直线的支持向量：带有黑色边缘的点（有两个）和间隔（阴影区域）。

支持向量机为您提供了一种在许多可能的分类器之间进行选择的方法，以确保以更高的正确率标记测试数据。这种方法很简洁吧？

虽然上图显示了在二维空间中的直线和数据，但必须注意 SVM 在任意数量的维度上都可以运行; 在这些维度中，他们找到了二维直线的类比。

例如，在三维空间中，他们寻找平面（plane）（我们将很快看到这个例子），并且在更高的维度中，他们寻找超平面（hyperplane） ——二维直线和三维平面到任意数量的维度的推广。

可由直线（或通常为超平面）分隔的数据称为线性可分（linearly separaterable） 数据。超平面充当线性分类器（linear classifier）。

容错

我们在最后一节中查看了完全线性可分离数据的简单情况。然而，真实世界的数据通常是混乱的。你几乎总会遇到一些线性分类器无法正确分隔的实例。

以下是此类数据的示例：

显然，如果我们使用线性分类器，我们永远无法完全分离标签。我们也不想完全抛弃线性分类器，因为除了一些错误的点之外，它看起来似乎很适合这个问题。

SVM 如何处理这个问题？它们允许您指定您愿意接受的错误数量。

您可以为 SVM 提供一个名为“C”的参数；这允许你决定以下两者之间的权衡：

有很大的间隔。
正确分类训练数据。较高的 C 值意味着您希望训练数据上的错误较少。

值得重申的是，这是一个 权衡（tradeoff） 办法。您可以在 代价（expense） 范围内为训练数据选择更好地分类器。

下面的图显示了当我们增加 C 的值时，分类器和间隔是如何变化的（支持向量未显示）：

注意当我们增加 C 的值时，直线如何“倾斜”。在高值时，它会尝试容纳图表右下方存在的大多数红点。这可能不是我们想要的测试数据。C=0.01 的第一个图似乎更好地捕捉了总体趋势，尽管与较高 C 值的结果相比，训练数据的准确度较低。

由于这是一个权衡办法，请注意当我们增加 C 的值时，间隔的宽度会缩小。

在前面的例子中，间隔是数据点的“无人之地”。在这里，我们看到不可能有这样一种状况，既有一个良好的分割边界，又在间隔中不存在任何点。实际上一些点进入到了间隔里面。

一个重要的实际问题是为 C 确定一个好的值。由于现实世界的数据几乎从不可分离，因此这种需求经常出现。我们通常使用像 交叉验证（cross-validation） 这样的技术为 C 选择一个好的值。

非线性可分离数据

我们已经看到支持向量机如何系统地处理完美 / 几乎线性可分离的数据。它如何处理绝对不可线性分离的数据的情况呢？毕竟，很多现实世界的数据属于这一类。当然，寻找超平面已不再适用。鉴于 SVM 在这项任务上表现出色，这似乎很不幸。

以下是非线性可分数据的示例（这是着名的 XOR 数据集的变体），与线性分类器 SVM 一起显示：

你一定会认为这看起来不太好。我们在训练集上的准确率只有 75％ ——这是只用一条直线进行分隔所能达到的最优性能。更重要的是，这条直线非常靠近一些数据。最优的准确度也并不是很好，而且为了达到平衡，这条线几乎完全跨过了一些点。

我们需要做得更好

这就是我对 SVM 最喜欢的一点。这是我们到目前为止所拥有的：我们有一种非常擅长寻找超平面的技术。但是，我们也有不可线性分离的数据。那么我们该怎么办？将数据投影到一个可以线性分离的空间，并在这个空间中找到一个超平面！

我将一步一步地讲解这个想法。

我们从上图中的数据集开始，并将其投影到三维空间中，其中新坐标为：

这就是投影数据的样子。你看到我们可以在平面上滑动的平面吗？

让我们运行 SVM 吧：

好啦！我们完美地将标签分离！让我们将平面投射回原始的二维空间，看看分割边界是什么样的：

在训练数据集上有 100% 的精度并且分隔边界不会太靠近数据！好极了！

原始空间中分割边界的形状取决于投影。在投影空间中，这往往是一个超平面。

请记住，投影数据的主要目的是为了利用 SVM 发现分隔超平面的能力。

将其映射回原始空间时，分割边界不再是直线。对于间隔和支持向量也是如此。就我们的视觉直觉而言，它们在投射空间中是有意义的。
看看它们在投影空间中的样子，然后是原始空间。3D 间隔是分离超平面上方和下方的平面之间的区域（没有阴影以避免视觉混乱）。

在投影空间中有 4 个支持向量，这似乎是合理的。它们位于定义间隔的两个平面上。在原始空间中，它们仍然处在间隔上，但到这一步似乎还不够。

让我们退一步分析发生的事情：

1. 我怎么知道将数据投射到哪个空间？

看起来我完全明确该怎么做——在那里放置一个 2 的平方根！

在这个例子中，我想展示的是向高维的投影是如何工作的，所以我选择了一个非常具体的投影。一般来说，这一点是很难知道的。然而，我们所知道的是，由于 Cover 定理，当投影到更高维度时，数据更可能是线性可分的。

在实践中，我们尝试一些高维投影，看看哪些有效。实际上，我们可以将数据投影到无限维度，并且通常效果还不错。这值得详细讨论，也就是下一节的内容。

2. 我应该首先投影数据，然后运行 SVM 吗？

不。为了使上面的例子易于掌握，我的做法看起来好像我们需要首先投影数据。事实上，你要求 SVM 为你进行投影。这有一些好处。首先，SVM 使用一些名为 ** 核函数（kernel）** 的东西进行这些投影，这些投影非常快（我们很快就会看到）。

另外，还记得我在前一节提到的投射到无限维度吗？如果你自己投影数据，你如何表示或存储无限维度？事实证明，SVM 对此非常聪明，同样得益于核函数。

现在是时候来看看核函数了。

核函数

最后，让 SVM 有效工作是有秘诀的。这也是我们需要学习数学知识的地方。

让我们来看看到目前为止我们所看到的情况：

对于线性可分的数据，SVM 表现得非常好。
对于几乎可线性分离的数据，通过使用正确的 C 值，SVM 仍然可以很好地运行。
对于不能线性分离的数据，我们可以将数据投影到完全 / 几乎可线性分离的空间，从而将问题降至第 1 步或第 2 步，我们又重新开始处理数据。

看起来，将 SVM 普遍适用于各种情况的一件重要操作是是将它投射到更高的维度。这就是核函数的用处。

首先，说点题外话。

SVM 的一个非常令人惊讶的地方是，在它使用的所有数学运算中，精确投影，甚至维数的数量都没有显现。你可以根据各种数据点（表示为向量）之间的点积（dot products） 来表达所有内容。对于 p 维向量的 i 和 j，其中第一个下标表示某一个点，第二个下标表示维度编号：

点积是这样定义的：

如果我们的数据集中有 n 个点，则 SVM 仅仅需要通过每对点的点积来构建分类器。仅此而已。当我们想要将数据投影到更高维度时，也是如此。我们不需要为 SVM 提供精确的投影；我们需要在投影空间中的所有点的组合之间计算点积。

这是有重大意义的，因为这正是核函数所做的。核函数（kernel function的缩写）在原始空间中将两个点作为输入，并直接在投影空间中给出点积。

让我们重新审视之前做过的投影，看看我们是否可以提出相应的核函数。我们还将留意为投影执行的计算次数，然后计算点积——看看如何使用核函数进行比较。

对于点 i：

我们相应的投影点是：

要计算此投影，我们需要执行以下操作：

获得新的第一维数据：1 次乘积
第二维数据：1 次乘积
第三维数据：2 次乘积

总共，1+1+2 = 4 次乘积。

新维度中的点积是：

要计算两个点 i 和 j 的点积，我们需要先计算它们的投影。因此，4 + 4 = 8 次乘积，然后点积本身需要 3 次乘法和 2 次加法。

总之，就是：

乘积：8（投影）+ 3（点积）= 11 次乘积
加法：2（点积）

总共是 11 + 2 = 13 次运算。

我声明这个核函数的结果是一样的：

我们首先在原始空间中取矢量的点积，然后对结果进行平方运算。

让我们展开它并检查我的说法是否正确：

确实如此。这需要多少次运算？看看上面的第（2）步。要计算二维的点积，我需要 2 次乘法和 1 次加法。平方是另一种乘法。

所以，总共是：

乘法：2（原始空间中的点积）+ 1（对于平方结果）= 3 次乘法
加法：1（原始空间中的点积）

共计 3 + 1 = 4 次运算。这只是我们之前需要的进行的 31％的运算量。

看起来使用核函数来计算我们需要的点积更快。这可能看起来不是什么大问题：我们正在对比 4 次运算和 13 次运算，但是随着输入点的维度越来越多，并且投影空间的维度越来越高，大型数据集的计算节省的时间就越来越多。这就是使用核函数的一个巨大优势。

大多数 SVM 库已经预先打包了一些流行的核函数，如 多项式、径向基函数（RBF）和Sigmoid 函数。当我们不使用投影时（如本文的第一个例子），我们在原始空间中计算点积——我们把这个称之为线性核函数。

其中许多核函数为您提供了额外的手段，可以根据您的数据进一步调整它。例如，多项式核函数：

允许您选择 c 和 d 的值（多项式的次数）。对于上面的 3D 投影，我使用了 c = 0 和 d = 2 的多项式核函数。

但是我们还没有完成核函数的强大功能！

还记得我之前提到过的投射到无限维度吗？如果您还没有猜到，其实让它工作的方法就是拥有合适的核函数。这样，我们就不必对输入数据进行投影，也不用担心存储无限维数据的问题。

如果你有准确的投影数据，核函数将会计算点积。

RBF 核函数通常用于特定的无限维投影。我们将不在这里进行数学计算，请查看本文末尾的参考资料。

我们怎样才能在无限维度的情况下仍然可以计算点积？如果您发现这个问题令人困惑，请考虑我们如何计算无穷级数的和。类似的，点积中有无限项，但恰好存在计算其总和的公式。

这回答了我们在上一节中提出的问题。总结一下：

我们通常不会为我们的数据定义具体的投影。相反，我们从可用核函数中挑选，在某些情况下调整它们，以找到最适合数据的核函数。
当然，没有什么能阻止我们定义自己的核函数，或者自己执行投影，但在很多情况下我们并不需要这么做。或者我们至少从我们能做的事情开始。
如果有可用于我们想要的投影的核函数，我们一般选择使用核函数，因为它通常计算更快
RBF 核函数可以将点投影到无限维度。

开始使用 SVM 库

有很多 SVM 库供你开始练习：

libSVM
SVM-Light
SVMTorch

像 scikit-learn 这样的许多通用 ML 库也提供 SVM 模块，这些模块通常是专用 SVM 库的包装器。我的建议是从经过试验测试的 libSVM 开始。

libSVM 可用作命令行工具，但下载文件也捆绑了 Python、Java 和 Matlab 包装器。只要你有一个包含 libSVM 能够理解的格式的数据文件（下载的 README 文件解释了这个，以及其他可用的选项）你就能够使用它。

事实上，如果你需要非常快速地了解不同的核函数和不同的 C 值等等是如何影响寻找分割边界的，请在其主页上尝试使用“图形界面”。标记属于不同类的数据点，选择 SVM 参数，然后点击 Run！

我迫不及待地迅速标出几个点：

是的，我不是让 SVM 变得容易。

然后我尝试了几个核函数：

界面不显示分割边界，但显示 SVM 学习属于特定标签的区域。如你所见，线性核函数完全忽略了红点。它认为整个空间为黄色（一说绿色）。但是 RBF 核函数巧妙地使用了戒指形状的区域覆盖了红色标记！

有用的资源

我们一直主要依靠视觉上的直观理解。虽然这是获得初步理解的好方法，但我强烈建议您深入挖掘。视觉上的直观理解的例子可能不足以理解间隔宽度以及用于非线性可分离情况的支持向量。

请记住，这些数量是通过优化权衡来决定的。除非你去看数学原理，否则一些结果可能看似违反直觉。

数学有用的另一个方面是理解核函数。我在这篇短文中几乎没有介绍过 RBF 核函数。我希望它的“神秘”感——它与无限维投影的关系再加上最后一个数据集（“环”）上的奇妙结果——已经说服你去仔细研究它。

我推荐的资源：

视频讲座：从数据中学习。作者是 Yaser Abu-Mostafa。讲座从 14 到 16 部分讨论了 SVM 和核函数。如果你正在寻找 ML 的简介，我也强烈推荐整个系列，它在数学和直觉之间保持着良好的平衡。
书：统计学习的要素。作者是 Trevor Hastie、Robert Tibshirani 和 Jerome Friedman。第 4 章介绍了 SVM 背后的基本思想，第 12 章则全面论述了它。

好好学习，天天向上！