Support Vector Machine

作者: DejavuMoments | 来源:发表于2018-11-24 19:31 被阅读0次

[TOC]

Support Vector Machines 支持向量机

SVM 在有监督学习算法中

1.从直觉上理解什么是 SVM

要理解 SVM 就不得不提及 Margins (间隔) 这个概念，在这里会涉及对 margin 的直观理解以及对预测结果的置信程度（Confidence）度量。

让我们先回顾一下 Logistical Regression。在 LR 模型中，我们通过对条件概率 $p(y=1|x;\theta)$ 建模得到 $h_\theta(x)=g(\theta^Tx)$ . 对于每一个输入的实例 $x$ , 当且仅当 $h_\theta(x) \ge 0.5$ 或者等价于 $\theta^Tx \ge 0$ 时, 我们的模型会预测分类为 1 。

考虑训练集中的一个正类样本( $y=1$ ), 其 $\theta^Tx$ 越大, $h_\theta(x)=p(y=1|x;\theta)$ 也越大，那么对该样本其分类为 1 的 confidence degree也越大。这样的话，我们私底下就可以这么想了，如果对一个实例来说， $\theta^Tx \gg 0$ 的话，那么我们可以很自信的将这个实例归为类别 1 。同理，如果对一个实例来说 $\theta^Tx \ll 0$ 的话，那么我们可以信心十足的将这个实例归为类别 0。

所以，给定一个训练集(Training Set), 并找到一个能够拟合训练集数据的模型，这是我们的目标。

现在，让我们看一下另一种。在下图中， $\times$ 代表着类别为正的训练实例， $\bigcirc$ 代表着负训练实例，划分两类的直线便是决策边界(在 SVM 中被称为分离超平面，其方程为 $\theta_Tx=0$ ) ，以及三个被标为 A、B、C 的点。

可以看到的是，类别为 1 的点 A 距离决策边界非常远。假如要我们对点A所属类别 $y$ 做个预测的话，很显然我们会认为在这里 $y=1$ 。相反地，类别同样为 1 的点 C 距离我们的决策边界非常的近。尽管这时候它处于决策边界的上方，即类别为 1 的区域，被正确的分类了。但是只要决策边界稍微变化一点点，就很容易被预测为错误的类别 0 了，对不对？

很显然相比于点 C ，我们对点 A 的预测更有信心。而点B正处在这两者之间，这样的话，我们也可以这样认为：对距离分离超平面越远的点，我们对它所属类别预测为真的信心也愈大。对吗？离得越近的点，反而会对预测的结果没有把握。

这里的 confidence 可以认为是实例点到分类超平面的距离，距离越大，confidence 越高。

分离超平面

综上所述，SVM 算法的目标在于找到这样一个决策边界：
1.能够正确划分训练实例的类别
2.所预测实例于决策边界的距离尽量最大

决策边界

超平面

2.Notation 符号表示

为了让解释方便，在这里引入一些关于分类的数学符号的标记。让我们从最简单的二元分类开始，考虑一个线性分类器，对特征 $x$ 和类别标记 $y$ 进行分类。

在这里，我们使用 $y \in \{-1, +1\}$ 表示类别的 Label 。(想一想，为什么不使用 $y \in \{-1, +1\}$ ？) ，同时采用 $w,b$ 来表示线性分类器的参数。（为什么不使用 vector $\theta$ 表示？将 $b$ 作为 $w_0$ ) 最后，我们得到了我们的的模型：

$h_{w,b}(x) = g(w^Tx+b)$

在这里，如果 $z \ge 0$ , 则 $g(z) = 1$ ; 否则 $g(z) = -1$ 。这里的 $w,b$ 形式的表示使得我们可以将截距项 $b$ 和其他参数区别对待。因此， $b$ 扮演了原先 $\theta_0$ 的角色，而 $w$ 则代表了 $[\theta_1...\theta_n]^T$

同时也注意到，上面我们对 $g$ 的定义使得我们的分类器可以直接预测出结果 $\{0,1\}$ , 而不需要像 Logistic Regression 那样需要经过一个中间步骤（先预测 $y=1$ 的概率，然后转换为最后的 $\{0,1\}$ 类别）。

我们的目标是确定 $w,b$ 。

3.函数间隔和几何间隔 Functional and Geometric Margins

SVM 有三个关键概念： 间隔、对偶、核技巧。

SVM 可以分为三种：Hard-Margin SVM（也叫做最大间隔分类），Soft-Margin SVM 和 Kernel SVM。在这里将会讨论 SVM中的间隔（margins），并形式化定义和解释其中的函数间隔和几何间隔。

给定一个训练实例 $(x^{(i)}, y^{(i)})$ ，我们定义该实例与分离超平面 $(w,b)$ 的函数间隔为：

$\hat{\gamma}^{(i)} = y^{(i)}(w^Tx+b).$

这里我们先来理解一下这个公式，看看是否与我们之前形成的直觉理解一致：一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。

略

从一定程度上来说，使用函数间隔来表示我们对预测 confidence 的度量并不是一个好的选择。因为函数间隔有一个不太好的性质。

问题在于，上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变 w 和 b，如将他们改变为 2w 和 2b，虽然此时超平面没有改变，但函数间隔的值 f(x) 却变成了原来的2倍。其实，我们可以对法向量 w 加些Normalization 条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离--几何间隔geometrical margin的概念（很快你将看到，几何间隔就是函数间隔除以个||w||，即yf(x) / ||w||）

这里的意思就是说，函数间隔使得我们难以确定 w 和 b，因为 2w 和 2b 有着更高的 confidence。

image.png

接下来让我们讨论一下几何间隔。先来看一下下面的图：

image.png 假设我们有了B点所在的

image 分割面。任何其他一点，比如A到该面的距离以

image 表示，假设B就是A在分割面上的投影。我们知道向量BA的方向是

image （分割面的梯度），单位向量是

image 。A点是

image ，所以B点是x=

image （利用初中的几何知识），带入

image 得，

image

进一步得到

image

实际上就是点到平面距离。

4.最大间隔分类器

回想前面我们提到我们的目标是寻找一个超平面，使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面，我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。形象的说，我们将上面的图看作是一张纸，我们要找一条折线，按照这条折线折叠后，离折线最近的点的间距比其他折线都要大。形式化表示为：

优化问题。

SVM三宝： 间隔、对偶、核技巧

核技巧能够让 SVM 从普通的欧式空间（特征空间），映射到高维空间，然后可以实现一定的非线性分类。

SVM 可以分为以下三种：
Hard-Margin SVM, 也叫做最大间隔分类。
Soft-Margin SVM
Kernel SVM

首先我们来了解一下第一种，即 Hard-Margin SVM。

SVM 最初提出来是为了解决二分类问题。