支持向量机入门简介
在Statsbot团队发布关于时间序列异常检测的帖子之后，许多读者请求我们向他们介绍支持向量机的相关方法。现在是时候抓紧时间来向你简单介绍下SVM，我们会通过分享有用的图书馆和资源而不是用复杂的数学知识来带你入门SVM。
如果你已经使用过机器学习的方法来执行分类操作，那可能已经听说过支持向量机（SVM）。支持向量机的概念在50多年前被引入，随着时间的推移它们不断发展，并且也被用于回归，异常值分析和排序等其他各种问题。支持向量机在许多机器学习从业者的“武器库”中是最受欢迎的工具。
在这篇文章中，我们将尝试在更深的层次上来理解SVM如何工作。我将专注于启发直觉认识而不是一板一眼的说教。从根本上来说，这意味着我们将尽可能多地忽略相关的数学知识，以对SVM的工作原理有一个强烈的直观认识。
分类问题
假设你的大学有一门机器学习（ML）课程。课程导师注意到，擅长数学或统计学的学生往往在这门课上表现出色。随着时间的推移，他们记录了这些学科的入学登记学生的分数。而且，对于每一名学生，他们都有一个标签来描述其在ML课程中的表现：“好”或者“坏”。
现在，导师们想确定学生们的数学课和统计学分数与ML课程中的表现之间的关系。也许，根据他们的发现，他们想要指定注册ML课程的先决条件。
导师们该怎么做呢？让我们从表示他们拥有的数据开始。我们可以绘制一个二维图，其中一个轴表示数学成绩，而另一个轴表示统计学成绩。具有某个分数的学生被显示为图上的一个点。
点的颜色（绿色或红色）表示他在ML课程中的表现：分别表示是“好”还是“差”。
这样的一个图看起来可能就是这样的：
当一个学生要求报名登记时，导师会要求他提供自己的数学和统计学成绩。根据导师们已经掌握的数据，他们会对报名的学生在ML课程中的表现做一个明智的猜测。
从根本上来说，我们想要的是某种“算法”，算法的输入是表单（math_score，stats_score）的“分数元组”。它会告诉你学生在二维图上是红色的点还是绿色的点（红色/绿色也被称为类或标签）。当然，这个算法以某种方式体现了我们已有的数据（也称为训练数据）中存在的模式。
在这种情况下，找到在红色和绿色群集之间穿过的一条线，然后确定该线的哪一边是得分元组，这是一个很好的算法。我们采取一边 - 绿色的一面或红色的一面 - 作为报名ML课程学生在该课程最有可能的表现，这是个很好的指标。
这条线是我们的分离边界 （因为它将标签分开）或分类器（我们用它来对点分类）。上图显示了适用于分类问题的两个可能的分类器。
好分类器与坏分类器
这里有个有趣的问题。上面的两条线都将红色和绿色的群集分开。是否存在一个很好的理由选择其中一条线而不是另一条？
请记住，分类器的价值并不在于如何很好地将训练数据分开。我们最终希望它能够分类尚未看到的数据点（称为测试数据）。鉴于此，我们希望选择一条能够捕捉训练数据中的一般模式的线条，这样这条线有可能在测试数据中表现依然良好。
第一条线看起来有点“歪斜”，靠近下半部分，似乎跑得太靠近红色的集群，而在上半部分则跑得太靠近绿色的集群。当然，它将训练数据完美地分开，但是如果它看到的测试点距离集群稍远一些，很可能得到错误的标签。
第二条线没有这个问题。例如，看下面的图中显示为正方形的测试点和分类器分配的标签。
第二条线尽可能地保持远离两个集群，同时恰当地将训练数据分离。因为恰好在这两个集群中间，它的“风险”更少，这样每个类的数据分布就有了一定的回旋余地，因此可以很好地概括测试数据。
SVM尝试找到第二种类型的线条。我们从视觉上选择了更好的分类器，但是我们需要更精确地定义更底层的哲学原理，以便将其应用于一般情况。以下是SVM的一个简化版本：
- 找到正确分类训练数据的线条。
- 在所有这些线中，挑选线的最近点到其距离最大的一条线。
识别这条线的最近点被称为支持向量。而他们在这条线上所定义的区域被称为边缘。
以下所示为带有支持向量的第二条线：带有黑边的点（其中有两个）和边缘（阴影区）。
支持向量机为你提供了一种在许多可行的分类器之间进行选择的方式，可以保证更高的正确标记测试数据的概率。这相当整洁，不是吗？
虽然上面的图表展示的是二维的线条和数据，但必须注意的是，支持向量机可以在任何维度上工作。在这些维度中，他们找到了二维线的模拟。
例如，他们在三维空间中找到了一个平面（我们将很快看到这个例子），而在更高维度中，他们找到了一个超平面 - 将二维线和三维平面推广到任意数量的维。
可以用线（或者一般来说，超平面）分隔的数据被称为线性可分的数据。超平面充当线性分类器。
容错性
在上一节中，我们看到了完美线性分离数据的简单情况。然而，真实世界的数据通常是混乱的。几乎总会有一些线性分类器无法正确使用的情况。
这里有一个这样的数据的例子：
显然，如果我们使用线性分类器，我们永远不可能完全分离标签。我们也不想放弃线性分类器，因为除了一些错误的点之外，它看上去似乎很适合这个问题。
SVM如何处理这个问题？它可以让你指定愿意接受的错误数量。
你可以向SVM提供一个名为“C”的参数; 这允许你决定以下两点的权衡关系：
- 是否有很大的边缘。
- 是否正确分类训练数据。参数C的值越大意味着对训练数据分类的错误越少。
需要强调的是这只是一种折衷方式。你可以以更大的边缘为代价来获得更好的训练数据分类结果。
下面的图显示了分类器和边距随着我们增加C的值而变化的情况（没有显示支持向量）：
请注意当我们增加C的值时这条线的倾斜程度。在高值时，它会试图容纳位于图的右下角的大多数红色点的标签。对于测试数据来说这可能不是我们想要的结果。C = 0.01的第一个曲线似乎更好地反映了整体趋势，尽管与C的较高值相比，由训练数据得出的准确性较低。
由于这是一种折衷方案，注意边缘的宽度随着我们增加C的值而缩小
在前面的例子中，边缘是一个“无人地带”。而现在，我们看到不可能同时有一个良好的分离边界和一个与之相关联的没有点的边缘。总会有一些点蔓延到边缘之内。
决定参数C的值是一个关键的实践问题。由于现实世界的数据几乎不可能完全分离，所以这种需求经常出现。我们通常使用像交叉验证这样的技术为C选择一个好的值。
非线性可分的数据
我们已经看到了支持向量机如何系统地处理完美或者几乎线性可分的数据。那它如何应对数据绝对不可线性分离的情况？毕竟，很多真实世界的数据都属于这一类数据。当然，找到一个超平面不再起作用了。这似乎是不幸的，因为支持向量机在这个任务上表现得很出色。
下面是一个非线性可分数据的例子（这是著名的XOR数据集的一个变体），用线性分类器SVM发现：
你可能认为结果看起来不太好。我们对训练数据只有75％的准确性 - 这是最好的一条线的结果。而且更重要的是，这条线路非常接近一些数据。最好的准确度还不是很好，甚至为了达到这个结果，分隔线几乎跨越了几个点。
我们需要做得更好。
这就是我最喜欢的关于SVM的一个地方。到目前为止，我们有一个非常擅长寻找超平面的技术。但是，我们也有不能线性分离的数据。那么我们该怎么办？我们可以将数据映射到一个它是线性可分的空间中，并在这个空间中找到一个超平面！
我将一步一步地说明这个想法。
我们从上图中的数据集开始，将其投影到一个三维空间，其中的新坐标是：
这是投影数据到空间后的样子。有没有看到一个我们可以插入超平面的地方？
现在让我们在这个空间数据上运行SVM：
Bingo！我们得到了一个完美的标签分离！让我们将平面投影回原始的二维空间，看看分离边界是什么样的：
分析边界对训练数据的准确性为100％，并且分离边界不会与数据太靠近！好极了！
原始空间中分离边界的形状取决于投影。在投影空间中，这总是一个超平面。
记住，投影数据的主要目标是让SVM查找超平面的强大能力能得以利用。
当你将其映射回原始空间时，分隔边界不再是一条线。对于边缘和支持向量亦是如此。就我们的视觉直觉而言，它们在投影空间中是有意义的。
看看它们在投影空间中的样子，然后在看看原始空间中的样子。3D的边缘是超平面上方和下方平面之间的区域（为了避免视觉混乱不加阴影处理）。
投影空间中有四个支持向量，这似乎是合理的。他们位于确定边缘的两个平面上。在原来的空间里，他们仍然处于边缘，但这似乎还不够。
让我们回退一步，分析一下发生了什么事。
1.我怎么知道将数据投影到什么空间？
我表现得相当明确了- 在变换公式那里有一个2的平方根！
在这种情况下，我想说明如何对更高维度进行投影，所以我选择了一个非常具体的投影。一般来说，这是很难理解的。然而，我们所知道的是，由于Cover定理，数据在投影到更高维数时更有可能是线性可分的。
在实践中，我们尝试了一些高维度的预测，看看有什么作用。事实上，我们可以将数据投影到无限维度上，而且效果经常非常好。这点值得更加详细地说明，这也是下一节的内容。
2.所以我先映射数据然后再运行SVM？
答案是否定的。为了让前面的例子容易理解，我做得看起来首先需要投影数据。实际上，是你让SVM为你进行数据映射。这有一些好处。比如，支持向量机使用内核来做这些投影，而且这都会很快（我们很快就会看到其中原因）。
另外，还请记得我在前面提到的无限维度的方法吗？如果你自己投影数据，你怎么表示或存储无限维度？事实证明，SVM对此十分灵活，这又是内核的功劳。
现在我们是时候关注下内核了。
内核
最后，来看看使得SVM运转的秘诀。这方面我们需要知道一些数学知识。
让我们来看看迄今为止我们所了解的：
- 对于线性可分数据，SVM工作得非常好。
- 对于几乎线性分离的数据，通过使用C的正确值，SVM仍然可以很好地工作。
- 对于不能线性分离的数据，我们可以将数据投影到一个完全/几乎线性可分的空间，这样可以将问题简化到1或2，我们又回到了原来的工作。
看起来使得SVMs普遍适用的一个重要部分就是将其投影到更高的维度上。这就是内核大显身手的地方。
首先，谈谈有点偏题的。
支持向量机的一个非常令人惊讶的方面是，在它所使用的所有数学工具中，精确的投影，甚至是维度的数量都没有出现。你可以用各种数据点（用向量表示）之间的点积来表示它们。对于p维向量i和j来说，第一个下标表示数据点，而第二个下标表示维度。
点积被定义为：
如果我们的数据集中有n个点，则SVM 只需要每对点的点积就可以找到一个分类器。仅是如此。当我们想要将数据投影到更高维度时也是如此。我们不需要为SVM提供精确的投影; 我们需要给它投影空间中所有点对之间的点积。
这具有重要作用，因为这正是内核所做的。内核是内核函数的简称，它在原始空间中接收两个点作为输入，然后直接给出投影空间中的点积。
让我们重新回顾一下我们之前做的投影，看看我们能否想出一个相应的内核函数。我们还将记录我们需要为投影执行的计算次数，然后查找点积，以了解使用内核是如何显出优势的。
对于点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库可以作为练习起步：
像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章则对其进行全面的讲解。
祝你快乐地（机器）学习！
