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

个人博客

---

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

这篇文章在阐述什么

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

以下是一个简短的总结：

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

如何找到最优超平面

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

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

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

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

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

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

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

我们如何找到最大间隔

非常简单：

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

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

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

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

步骤1：你有一个数据集$\mathcal{D}$并且你想把它分类。

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

$$\mathcal{D} = \left\{ (\mathbf{x}_i, y_i)\mid\mathbf{x}_i \in \mathbb{R}^p,\, y_i \in \{-1,1\}\right\}_{i=1}^n$$

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

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

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

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

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

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

再看看超平面方程：

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

$$\mathbf{w}^T\mathbf{x} = 0$$
然而，在维基百科中关于SVM是这么说的：

任何超平面都可以写成 满足$\mathbf{w}\cdot\mathbf{x} - b=0$的点$\mathbf{x}$ 的集合

首先，我们知道了关于点积的另一种表示法，本文采用$\mathbf{w}\cdot\mathbf{x}$代替$\mathbf{w}^T\mathbf{x}$。

你可能想知道$-b$是怎么来的，是我们之前定义错了吗？

不完全，又一次是表示的问题。在我们的定义中，向量w与x有三个维度，但在维基百科中是二维的：
给出两个三维向量$\mathbf{w}(-b,-a,1)$与$\mathbf{x}(1,x,y)$

$$\mathbf{w}\cdot\mathbf{x} = -b\times (1) + (-a)\times x + 1 \times y$$
$$\begin{equation}\mathbf{w}\cdot\mathbf{x} = y - ax - b \end{equation}$$
给出两个二维向量$\mathbf{w^\prime}(-a,1)$和$\mathbf{x^\prime}(x,y)$
$$\mathbf{w^\prime}\cdot\mathbf{x^\prime} = (-a)\times x + 1 \times y$$
$$\begin{equation}\mathbf{w^\prime}\cdot\mathbf{x^\prime} = y - ax \end{equation}$$
现在如果我们在方程（2）的两边减去b得到：
$$\mathbf{w^\prime}\cdot\mathbf{x^\prime} -b = y - ax -b$$
$$\begin{equation}\mathbf{w^\prime}\cdot\mathbf{x^\prime}-b = \mathbf{w}\cdot\mathbf{x}\end{equation}$$

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

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

$$\mathbf{w}\cdot\mathbf{x} - b=0$$
我们选择其他两个划分数据集的超平面的$H_1$和$H_2$，有如下的方程：
$$\mathbf{w}\cdot\mathbf{x} - b=\delta$$ 与 $$\mathbf{w}\cdot\mathbf{x} - b=-\delta$$
以便于$H_0$与$H_1$和$H_2$等距。

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

$$\mathbf{w}\cdot\mathbf{x} - b=1$$ 与 $$\mathbf{w}\cdot\mathbf{x} - b=-1$$
现在我们想确定他们之间没有任何的数据点。
我们只选择那些符合以下两个约束的超平面：
对于每一个向量$\mathbf{x_i}$，要么 $$\begin{equation}\mathbf{w}\cdot\mathbf{x_i} - b \geq 1\;\text{for }\;\mathbf{x_i}\;\text{having the class}\;1\end{equation}$$ 要么 $$\begin{equation}\mathbf{w}\cdot\mathbf{x_i} - b \leq -1\;\text{for }\;\mathbf{x_i}\;\text{having the class}\;-1\end{equation}$$
必须满足约束。
在下面的图中，所有的红点都是$1$类，所有的蓝点都是$−1$类。

因此，让我们看看下面的图，并考虑点$A$，它是红的所以是$1$类并且我们需要验证它不违反约束$\mathbf{w}\cdot\mathbf{x_i} - b \geq1$

当$\mathbf{x_i} = A$我们看到超平面上的点满足$\mathbf{w}\cdot\mathbf{x_i} - b =1$，同样的B点也是。

当$\mathbf{x_i} = C$我们看到超平面上的点满足$\mathbf{w}\cdot\mathbf{x_i} - b >1$，同样的D、E、F、G点也是。

类似的，对于$−1$类的点也满足约束。

在下图，我们看到一对超平面满足约束：

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

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

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

结合两种约束

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

方程$(4)$和$(5)$可以合并成一个单一的约束，我们从方程$(5)$开始

$$\text{for }\;\mathbf{x_i}\;\text{having the class}\;-1$$
$$\mathbf{w}\cdot\mathbf{x_i} - b \leq -1$$
两边同乘$y_i$（在该约束中始终为-1）
$$y_i(\mathbf{w}\cdot\mathbf{x_i} - b ) \geq y_i(-1)$$
这意味着方程式$(5)$可以写做：
$$\begin{equation}y_i(\mathbf{w}\cdot\mathbf{x_i} - b ) \geq 1\end{equation}\;\text{for }\;\mathbf{x_i}\;\text{having the class}\;-1$$
在方程$(4)$中，因为y_i =1，它不改变不等号方向。
$$\begin{equation}y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \geq 1\;\text{for }\;\mathbf{x_i}\;\text{having the class}\;1\end{equation}$$
将方程式$(6)$和$(7)$写在一起 :
$$\begin{equation}y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \geq 1\;\text{for all}\;1\leq i \leq n\end{equation}$$
我们现在有一个独特的约束（方程8），而不是两个（方程4和5），但他们在数学上是等价的。所以他们的效果是一样的（保证两超平面间没有数据点）。

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

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

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

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

• $\mathcal{H}_0$是满足约束$\textbf{w}\cdot\textbf{x} - b = -1$的超平面
• $\mathcal{H}_1$是满足约束$\textbf{w}\cdot\textbf{x} - b = 1$的超平面
• $x_0$ 是 $\mathcal{H}_0$上的一点

我们称m为从$\textbf{x}_0$到超平面$\mathcal{H}_1$的垂直距离。通过定义，m就是我们所说的间隔。

因为$\textbf{x}_0$在超平面$\mathcal{H}_0$上，m是超平面$\mathcal{H}_0$与$\mathcal{H}_1$间的距离。

我们现在试着找出m的值。

你现在可能会想，如果我们在$\textbf{x}_0$上加m，我们会得到另一点，这个点说不定就在另一个超平面上！

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

我们可以找到距离$\textbf{x}_0$为m的所有的点，它可以表示成一个圆：

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

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

我们想要一个向量：

• 长度为m
• 方向垂直于平面$\mathcal{H}_1$

幸运的是，我们已经知道一个垂直$\mathcal{H}_1$的向量，是$\textbf{w}$(因为$\mathcal{H}_1 = \textbf{w}\cdot\textbf{x} - b = 1$)

我们定义$\textbf{u} = \frac{\textbf{w}}{\|\textbf{w}\|}$是$\textbf{w}$的单位向量。因为他是一个单位向量$\|\textbf{u}\| = 1$，并且他和$\textbf{w}$有相同的方向，所以它也是垂直于平面。

如果我们用$\textbf{u}$乘以$\textbf{m}$，得到向量$\textbf{k} = m\textbf{u}$，并且：

• 1.$\|\textbf{k}\| = m$
• 2.$\textbf{k}$垂直于$\mathcal{H}_1$，因为它与$\textbf{u}$具有相同方向

从这些属性中，我们可以看到，$\textbf{k}$是我们正在寻找的向量。

$$\begin{equation}\textbf{k}=m\textbf{u}=m\frac{\textbf{w}}{\|\textbf{w}\|}\end{equation}$$

我们做到啦！我们将标量m转换成一个向量$\textbf{k}$，并且我们可以将它与向量$\textbf{x}_0$相加。

如果我们在向量$\textbf{x}_0$上加$\textbf{k}$，我们在超平面$\mathcal{H}_1$上得到向$量\textbf{z}_0 = \textbf{x}_0 + \textbf{k}$，如下图所示

$\textbf{z}_0$在$\mathcal{H}_1$上意味着

$$\begin{equation}\textbf{w}\cdot\textbf{z}_0-b = 1\end{equation}$$

我们可以用$\textbf{x}_0+\textbf{k}$代替$\textbf{z}_0$

$$\begin{equation}\textbf{w}\cdot(\textbf{x}_0+\textbf{k})-b = 1\end{equation}$$
用方程式$(9)$替代$\textbf{k}$
$$\begin{equation}\textbf{w}\cdot(\textbf{x}_0+m\frac{\textbf{w}}{\|\textbf{w}\|})-b = 1\end{equation}$$
将式子打开
$$\begin{equation}\textbf{w}\cdot\textbf{x}_0 +m\frac{\textbf{w}\cdot\textbf{w}}{\|\textbf{w}\|}-b = 1\end{equation}$$
向量与自己的点积是它的模的平方，所以：
$$\begin{equation}\textbf{w}\cdot\textbf{x}_0 +m\frac{\|\textbf{w}\|^2}{\|\textbf{w}\|}-b = 1\end{equation}$$
$$\begin{equation}\textbf{w}\cdot\textbf{x}_0 +m\|\textbf{w}\|-b = 1\end{equation}$$
$$\begin{equation}\textbf{w}\cdot\textbf{x}_0 -b = 1 - m\|\textbf{w}\|\end{equation}$$

因为$\textbf{x}_0$在$\mathcal{H}_0$上，所以$\textbf{w}\cdot\textbf{x}_0 -b = -1$，带入：

$$\begin{equation} -1= 1 - m\|\textbf{w}\|\end{equation}$$
$$\begin{equation} m\|\textbf{w}\|= 2\end{equation}$$
$$\begin{equation} m = \frac{2}{\|\textbf{w}\|}\end{equation}$$
就是它！我们找到了一种计算$m$的方法

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

$$m= \frac{2}{\|\textbf{w}\|}$$
在这个公式中，我们唯一可以改变的变量是$\mathbf{w}$的模。
让我们尝试给它不同的值：
当$\|\textbf{w}\|=1$时，$m=2$；
当$\|\textbf{w}\|=2$时，$m=1$；
当$\|\textbf{w}\|=4$时，$m=\frac{1}{2}$；

我们很容易发现，$\mathbf{w}$的模越大，间隔越小。

最大化间隔也就是最小化$\mathbf{w}$的模。

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

有了以下的优化问题：

$$(\textbf{w}, b)的最小值$$ $$\|\textbf{w}\|$$ $$约束条件为 y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \geq 1$$ $$(对于i = 1, \dots, n)$$

解决这个问题就像求解方程。一旦解出来答案，我们会发现值对$(\textbf{w}, b)$满足$\|\textbf{w}\|$是最小的可能值，也满足约束条件。
这意味着我们找到了最优超平面的方程！

结论

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