[关闭]
@hanxiaoyang 2017-12-14T12:47:47.000000Z 字数 6492 阅读 4765

机器学习系列(15)_SVM碎碎念part3:如何找到最优分离超平面

个人博客


这是我写的SVM之数学理解的第三部分。如果你没有读过之前的文章,在读这一篇之前建议您看一看前两篇。

这篇文章在阐述什么

这篇文章的主要目的是向你展示选择最优超平面的推理过程。

以下是一个简短的总结:

  • 我们如何找到最优超平面
  • 我们如何计算两超平面间的距离
  • SVM的最优化问题是什么

如何找到最优超平面

在第二篇文章的结尾我们计算了点到超平面间的距离,然后计算间隔为
然而,即使他不是最优超平面,他依然在数据分类这一方面有很好的效果。

cmd-markdown-logo

最优超平面是一个与数据点有最大间隔的平面。在上图中我么可以看到间隔,在两条蓝线之间,它不是完美分类数据点的最大间隔。最大间隔为,如下图所示:

cmd-markdown-logo

可以在上图中看到最优超平面,在我们找的最初的超平面的稍左位置。我是如何找到它的呢?

我简单地在M_2的中点处画了条垂线。

现在你应该感觉到超平面和间隔是密切相关的。你是对的!

如果我有一个超平面,我就能通过某一数据点计算其间隔。如果我有一间隔,就能通过他的中点找到超平面。

  • 寻找最大间隔,就是寻找最优超平面

我们如何找到最大间隔

非常简单:

  • 有一个数据集。
  • 选择两个超平面,他们可以划分数据并且两平面之间没有数据点。
  • 最大化间隔

选出的两平面之间的间隔就有可能是最大间隔。

如果它是如此的简单,为什么每个人在理解SVM时都有这么多的痛苦?这是因为它总是需要一些抽象和数学术语来理解它。

让我们一步一步的解决它:

步骤1:你有一个数据集并且你想把它分类。

大多数时候,你的数据将由n个向量组成。
每一个与一个值相关联,代表元素属于类(-1)或类(+1)。请注意,只能有两个可能的值 -1或1。
而且,大多数时候,比如当你做文本分类,向量有很多维度,我们可以说,X是一个p维向量(如果他有p维)。所以你的数据集是n对元素的集合。
在集合论中的初始数据集的更正式的定义是:

步骤2:你需要选择两个平面来划分数据,并且两平面之间没有数据点。

当你有笔和纸时,找到两个平面来划分数据很容易。但当数据为高维时,划分数据就变得困难,因为你没办法把它画出来。

此外,即使你的数据是二维的,也有可能找不到分离超平面!

只有在数据线性可分时,才能找到。

cmd-markdown-logo

因此,假设我们的数据集是线性可分的。我们想要找到中间没有数据点的两个超平面,但是我们没有办法想象他们。

了解超平面可以帮助我们做什么呢?

再看看超平面方程:

我们在之前看到过超平面的方程可以写做


然而,在维基百科中关于SVM是这么说的:

任何超平面都可以写成 满足的点 的集合

首先,我们知道了关于点积的另一种表示法,本文采用代替

你可能想知道是怎么来的,是我们之前定义错了吗?

不完全,又一次是表示的问题。在我们的定义中,向量w与x有三个维度,但在维基百科中是二维的:
给出两个三维向量



给出两个二维向量


现在如果我们在方程(2)的两边减去b得到:

对于这篇文章的剩余部分,我们将使用二维向量(如方程(2))。

给出一个超平面划分数据集并且满足:


我们选择其他两个划分数据集的超平面的,有如下的方程:

以便于等距。

然而,这里的变量是没有必要的,所以我们让来简化问题。


现在我们想确定他们之间没有任何的数据点。
我们只选择那些符合以下两个约束的超平面:
对于每一个向量,要么
要么

必须满足约束。
在下面的图中,所有的红点都是类,所有的蓝点都是类。

因此,让我们看看下面的图,并考虑点,它是红的所以是类并且我们需要验证它不违反约束

我们看到超平面上的点满足,同样的B点也是。

我们看到超平面上的点满足,同样的D、E、F、G点也是。

类似的,对于类的点也满足约束。
cmd-markdown-logo

在下图,我们看到一对超平面满足约束:
cmd-markdown-logo

我们测试一下不符合约束的情况:

cmd-markdown-logo

cmd-markdown-logo

cmd-markdown-logo

当不满足约束时,它意味着什么。这就意味着我们不能选择这两个超平面。因为此时超平面之间出现了数据点。

通过这些定义,我们找到了一种方法可以达到我们的初始目标--选择两个中间没有数据点的超平面。它不仅仅适用于这个例子,也适应更高维的例子。

结合两种约束

在数学中,人们喜欢简洁地表达事物。

方程可以合并成一个单一的约束,我们从方程开始



两边同乘(在该约束中始终为-1)

这意味着方程式可以写做:

在方程中,因为y_i =1,它不改变不等号方向。

将方程式写在一起 :

我们现在有一个独特的约束(方程8),而不是两个(方程4和5),但他们在数学上是等价的。所以他们的效果是一样的(保证两超平面间没有数据点)。

步骤3:两个超平面之间的距离最大化

这可能是最难的部分。但不要担心,我会慢慢的解释一切。

a)我们的两个超平面之间的距离是什么

在试图最大化两个超平面之间的距离之前,我们首先要问自己:我们如何计算呢?
让我们:

  • 是满足约束的超平面
  • 是满足约束的超平面
  • 上的一点

我们称m为从到超平面的垂直距离。通过定义,m就是我们所说的间隔。

因为在超平面上,m是超平面间的距离。

我们现在试着找出m的值。
cmd-markdown-logo

你现在可能会想,如果我们在上加m,我们会得到另一点,这个点说不定就在另一个超平面上!

但这并不起作用,因为m是一个标量,是一个向量,在一个向量上加一个标量是不可能的。然而,我们知道,将两个向量相加是可能的,所以如果我们将m变换成一个向量,我们将能够做一个加法。

我们可以找到距离为m的所有的点,它可以表示成一个圆:

cmd-markdown-logo

看着这张图,向量的必要性是清楚的。我们只有长度m而缺少一个关键的信息:方向。

我们不能将一个标量添加到一个向量上,但我们知道,如果我们用一个向量乘一个标量,我们将得到另一个向量。

我们想要一个向量:

  • 长度为m
  • 方向垂直于平面

幸运的是,我们已经知道一个垂直的向量,是(因为)

cmd-markdown-logo

我们定义的单位向量。因为他是一个单位向量,并且他和有相同的方向,所以它也是垂直于平面。

cmd-markdown-logo

如果我们用乘以,得到向量,并且:

  • 1.
  • 2.垂直于,因为它与具有相同方向

从这些属性中,我们可以看到,是我们正在寻找的向量。

cmd-markdown-logo

我们做到啦!我们将标量m转换成一个向量,并且我们可以将它与向量相加。

如果我们在向量上加,我们在超平面上得到向,如下图所示

cmd-markdown-logo

上意味着

我们可以用代替


用方程式替代

将式子打开

向量与自己的点积是它的模的平方,所以:


因为上,所以,带入:




就是它!我们找到了一种计算的方法

b) 如何最大化两个超平面之间的距离
我们现在有一个公式来计算间隔:


在这个公式中,我们唯一可以改变的变量是的模。
让我们尝试给它不同的值:
时,
时,
时,

我们很容易发现,的模越大,间隔越小。

最大化间隔也就是最小化的模。

我们的目标是最大化间隔。在所有满足约束条件超平面中,我们选择有最小的超平面,因为它同时有着最大间隔。

有了以下的优化问题

解决这个问题就像求解方程。一旦解出来答案,我们会发现值对满足是最小的可能值,也满足约束条件。
这意味着我们找到了最优超平面的方程!

结论

我们发现,为了找到最优超平面,我们需要解决一个优化问题。优化问题有点棘手,而且你需要更多的信息来解决他们。这就是为什么解决这个优化问题将在本教程系列的第4部分讲述!谢谢阅读。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注