在Statsbot团队发布关于时间序列异常检测的帖子之后,许多读者要求我们向他们介绍支持向量机的方法。现在是向您介绍SVM(支持向量机)的时候了,而不用您辛苦的计算和使用有用的图书馆和资源来开始学习。
如果您已经使用机器学习来执行分类,您可能已经听说过支持向量机(SVM)。在50多年前引入了它们,随着时间的推移它们已经发展了,也被用于解决回归,异常值分析和排序等其他各种问题。支持向量机对许多机器学习从业者来说是最受欢迎的工具。
在这篇文章中,我们将尝试对SVM如何工作这一问题进行高层次的理解。我将专注于认识而不是精通。从本质上来说,我们将尽可能多地避免数学问题,并对工作原理有一个强烈的认识。
假设你的大学有一门机器学习(ML)课程。课程导师注意到,如果学生擅长数学或统计学,则学生可以更好的学习这门课程。随着时间的推移,他们记录了这些学科的入学学生的分数。而且,对于每一名学生,他们都有一个标签来描述他们在ML课程中的表现:“好”还是“坏”。
现在,他们想确定数学和统计分数与ML课程中的表现之间的关系。也许,根据他们的发现,他们可以指定入学的优先条件。
他们将如何去做呢?让我们从表示已经拥有的数据开始。我们可以绘制一个二维图,其中一个轴表示数学成绩,而另一个轴表示统计学成绩。我们用二维图上的点来表示有确定分数的学生。
点(绿色或红色)的颜色表示他在ML课程中的表现:分别是“好”还是“差”。
图可能是这样:
当一个学生要求报名时,我们的老师会要求她提供她的数学和统计成绩。根据他们已经掌握的数据,他们会对学生们在ML课程中的表现做一个合理的猜测。
我们本质上想要的是某种在 (math_score, stats_score)表单中的“算法”。它会告诉你学生是否是红色或绿色的点(红色/绿色也被称为类或标签)。当然,这个算法以某种方式体现了我们已有的数据中存在的模式,这也称作训练数据。
在这种情况下,找到在红色和绿色群集中间穿过的一条线,然后判断一个分数数组位于直线的哪一边,这是一个好的算法。我们预测绿色和红色中的一个作为她在课程中最可能的表现。
这里的线是我们的分离边界 (因为它将标签分开)或分类器 (我们用它来分类点)。该图显示了对于我们的问题的两种可能的分类器。
这是一个有趣的问题。上面的两条线都分开了红色和绿色的群集。我们并没有更好的理由选择其中一个。
请记住,分类器的价值并不在于如何将训练数据分开。我们最终希望它能够分类尚未给予的数据点(称为测试数据)。鉴于此,我们希望选择一条能够捕捉测试数据一般情况的线条,以便于在测试数据中处理得更好。
上面的第一条线看起来有点“歪斜”,靠近下半部分,似乎太靠近红色的集群,而在上半部分则太靠近绿色的集群。确实,它将训练数据完美地分开,但是如果测试点距离集群稍远一些,很可能会使标签分类出错。
第二条线没有这个问题。例如,看下面的图中正方形的测试点和分类器分配的标签。
第二条线保持尽可能远离两个集群,同时很好的分离了训练数据。通过正确的方法分两个数据集群,这样是低“风险“的,可以这么说,这样的数据分类器对于每个类的数据都有回旋的余地,因此可以很好地概括测试数据。
SVM尝试找到第二种类型的线。我们从视觉上选择了更好的分类器,但是我们需要更精确地定义基本理念,以便将其应用于一般情况。以下是SVM的一个简化版本:
识别这条线的最近点被称为支持向量。而他们在这条线上所定义的区域被称为边缘。
以下是支持向量所示的第二条线:带有黑色边的点(其中有两个)和边距(阴影区)。
支持向量机为您提供了一种在许多可能的分类器之间进行选择的方式,可以保证以更高正确率标记测试数据。很整洁,对吗?
虽然上面的图表只显示了二维的线条和数据,但必须注意的是,支持向量机可以在任何维度上工作。只是在上面维度中,他们找到了二维线的模拟。
例如,他们在三维空间中找到了一个平面(我们将很快看到这个例子),而在更高维度中,他们找到了一个超平面 - 将二维线和三维平面推广到任意数量的维。
可以用线(或者一般来说,超平面)分隔的数据被称为线性可分的数据。超平面充当线性分类器。
我们在上一部分中看到了完美线性分离数据的简单情况。然而,现实世界的数据通常是混乱的。几乎总会有一些线性分类器无法正确解决的情况。
这里有一个这样的数据的例子:
显然,如果我们使用线性分类器,我们永远不可能完全分离标签。我们也不想放弃使用线性分类器,因为除了很少一部分游离在一起的点之外,它看上去似乎很适合解决这个问题。
SVM如何处理这个问题?它允许您指定您愿意接受的错误数量。
您可以向SVM提供一个名为“C”的参数; 这允许你决定在下面2个方面权衡:
值得一提的是这是一个权衡。你可以以更大的代价获得更好的培训数据分类。
下面的图显示了分类器和边距随着我们增加C的值(支持向量未显示)而变化:
值得注意的是,当我们增加C的值时,这条线是如何“倾斜”的。在高值时,它会将容纳位于图的右下角的大多数红色点的标签。这可能不是我们想要的测试数据。C = 0.01的第一个曲线似乎更好地反映了整体趋势,尽管与C的较高值相比,训练数据的准确性较低。
由于这是一个折衷,请注意边缘的宽度随着我们增加C的值而缩小
在前面的例子中,边界对于样本来说是一个“无人地带”。现在,我们看到现在不可能有一个良好的分离边界和一个相关的边距。一些点处于边缘里。
决定一个很好的C的值是一个重要的实际问题。由于现实世界的数据几乎不可能完全分离,所以这种需求经常出现。我们通常使用像交叉验证这样的技术为C选择一个好的值。
我们已经看到了支持向量机如何完美的系统地处理大部分线性可分的数据。那么它如何处理绝对不可线性分离的数据的情况?毕竟,很多真实世界的数据属于这一类。当然,找到一个超平面不能再工作了。鉴于SVMs擅长这项任务,这似乎很不幸。
下面是一个非线性可分数据的例子(这是着名的XOR数据集的一个变体),用线性分类器SVM展示是这样的:
你会同意这看起来不太好。即使使用最好的一条线,我们的训练数据却依然只有75%的准确性。而且更重要的是,这条线路非常接近一些数据。准确度并不是很好,线路甚至几乎跨越了几个点在有些地方。
我们需要做得更好。
这就是我最喜欢的一个关于SVM的地方。到目前为止,我们有一个非常擅长寻找超平面的技术。但是,我们也有不能线性分离的数据。那么我们该怎么办?将数据投影线性可分的空间,并找到在这个空间中的超平面!
我将一步一步地说明这个想法。
我们从上图中的数据集开始,将其投影到一个三维空间,其中的新坐标是:
这是投影数据的样子。你有没有看到我们可以分开数据集的地方?
让我们运行我们的SVM:
完美!我们实现了完美的标签分离!让我们将平面投影回原始的二维空间,看看分离边界是什么样的:
训练数据的准确性为100%,而且分离边界不会与数据太靠近!好极了!
原始空间中分离边界的形状取决于投影。在投影空间中,这总是一个超平面。
请记住,投影数据的主要目标是使用SVM的超平面查找能力。
当您将其映射回原始空间时,分隔边界不再是一条线。对于边缘和支持向量也是如此。就我们的视觉感觉而言,它们在预计的投影空间中是有意义的。
看看它们在投影空间中的样子,然后再看看原始空间中。3D边缘是分离超平面上方和下方平面之间的区域(没有阴影以避免视觉混乱)。
投影空间中有四个支持向量,这似乎是合理的。他们处于确定边缘的2个平面上。在原来的空间里,他们仍然处于边缘,但似乎还不够。
让我们退后一步,分析发生了什么事。
这似乎是非常具体的 -因为在那里有一个2的平方根!
在这种情况下,我想说明如何对更高维度进行投影,所以我选择了一个非常具体的投影。一般来说,这是很难知道的。然而,我们所知道的是,由于Cover定理,数据在投影到更高维数时更可能变得线性可分。
在实践中,我们尝试了一些高维度的预测,看看有什么作用。事实上,我们可以将数据投影到无限维度上,而且经常运作得非常好。这应该需要一些细节,这就是下一节的内容。
不。为了让上面的例子容易理解,我使它听起来是我们需要首先投射数据。事实是,你要求SVM为你做预测。这有一些好处。首先,支持向量机使用内核来做这些预测,而且这些都很快(因为我们很快就会看到)。
另外,请记住我提到在前面提到的无限维度?如果您自己投射数据,您如何表示或存储无限维度?事实证明,SVM由于内核的存在,对此非常熟练。
现在是我们来看看内核的时候了。
最后,制作SVM的秘诀。这是我们需要看一些数学的地方。
让我们来看看迄今为止我们所看到的:
看起来SVMs普遍适用的一个重要部分就是将其投影到更高的维度上。这是内核发挥作用的地方。
首先,说几句题外话。
支持向量机的一个非常令人惊讶的方面是,在所有使用的数学机器中,精确的投影,甚至是维度的数量都没有出现。你可以用各种数据点之间的点积来表示它们(用向量表示)。对于p维向量的i和j,第一个下标表示点,第二个表示维数:
点积被定义为:
如果我们的数据集中有n个点,则SVM只需要每对点的点积就可以找到一个分类器。只是。当我们想要将数据投影到更高维度时也是如此。我们不需要为SVM提供精确的预测; 我们需要的是给它投影空间中所有点对之间的点积。
这是有必要的,因为这正是内核所做的。核函数是核函数的简称,在原始空间中的两个点作为输入,直接给出投影空间中的点积。
让我们重新回顾一下我们之前做的投影,看看我们能否想出一个相应的内核。我们还将计算我们需要为投影执行的计算次数,然后查找点积,以了解如何使用内核进行比较。
对于i点:
我们相应的投影点是:
要计算这个投影,我们需要执行以下操作:
总之,1 + 1 + 2 = 4次乘法。
新维度中的点积是:
为了计算两点i和j的点积,我们需要首先计算它们的投影。所以这是4 + 4 = 8次乘法,然后点积本身需要3次乘法和2次加法。
总之,那是:
总共有11 + 2 = 13个操作。
我声称这个内核函数给了我相同的结果:
我们先将原始空间中的矢量点积,然后平方。
让我们扩展一下,看看我的说法是否确实如此:
他是正确的。这需要多少操作?看看上面的步骤(2)。为了计算两维的点积,我需要2次乘法和1次加法。平方是另一个乘法。
所以,总之:
总共3 + 1 = 4次操作。这只是我们以前需要的操作的31%。
看起来使用内核函数计算我们需要的点积是更快的。在这里看起来并不是什么大不了的事情:对于13和4的操作数来说,但是输入点的维数要多得多,而且投影空间的维数更多,大数据集的计算所节省下来时间导致计算起来非常快。所以这是使用内核的一个巨大优势。
大多数SVM库已经预先包装了一些流行的内核,如多项式,径向基函数(RBF)和Sigmoid。当我们不使用投影时(就像本文的第一个例子),我们计算原始空间中的点积 - 我们称之为使用线性内核。
这些内核中的许多内核都会为您提供额外的工具来进一步调整数据。例如,多项式内核:
允许你选择c和d的值(多项式的次数)。对于上面的3D投影,我使用了c = 0和d = 2的多项式核函数。
但是我们还没有内核做的好!
还记得我提到过,投射到无限维度吗?如果你还没有猜到,使其工作的方式是有正确的核心功能。这样,我们实际上不必投影输入数据,也不必担心存储无限维度。
如果实际投影了数据,内核函数将计算点积。
RBF核通常用于特定的无限维投影。我们不会在这里讨论它的数学,而是看看这篇文章最后的参考文献。
我们怎样才能有无限的尺寸,但仍然可以计算点积?如果你觉得这个问题很困惑,那就考虑一下我们如何计算无穷级数的和。这是相似的。点积中有无限项,但恰好存在一个公式来计算它们的总和。
这回答了我们在前一节中提出的问题。我们总结一下:
有很多SVM库可以开始练习:
像scikit-learn这样的许多通用ML库也提供了SVM模块,这些模块通常是围绕专用的SVM库进行封装的。我的建议是从经过验证的libSVM开始。
libSVM可作为命令行工具使用,但是下载也捆绑了Python,Java和Matlab包装器。只要你有一个libSVM能理解的数据格式的文件(下载部分的README解释了这一点,以及其他可用的选项),你可以很好的去做。
事实上,如果你需要一个非常快速的感觉,看看不同的内核,C的值等等,是否会影响找到分离的边界,那么可以尝试在他们主页上的“图形界面” 。标记你的分数,选择不同的类,选择SVM参数,然后点击Run!
我无法抗拒,并迅速标出了几点:
是的,我不想让SVM变得容易。
然后我尝试了几个内核:
界面不会显示分离边界,但会显示SVM学习属于特定样本的区域。正如你所看到的,线性内核完全忽略了红点。它认为整个空间是黄绿色的。但RBF内核巧妙地为红色样本划出了一个环!
我们一直主要依靠视觉直觉。虽然这是获得初步了解的好方法,但我强烈建议您深入研究。视觉直觉可能被证明有缺陷的一个例子是理解非线性可分情况的边界宽度和支持向量。
请记住,这些数量是通过优化折衷决定的。除非你看数学,否则一些结果可能看起来是违反直觉的。
了解数学的另一个领域有助于了解内核函数。考虑一下我在这篇短文中几乎没有介绍过的RBF内核。我希望围绕它的“神秘性” - 它与无限维投影的联系,以及最后一个数据集(“圆环”)上出色的结果,让你深入研究它。
我建议的资源:
祝你学习快乐!