8.2.1 理解SVM - OpenCV 中文文档

返回介绍

8.2.1 理解SVM

发布于 2019-07-01 字数 5264 浏览 880 评论 0

目标

在这一章当中

  • 我们将看到对SVM的直观理解。

理论

线性可分的数据

考虑下面的图像,有两种类型的数据,红色和蓝色。在kNN中,对于测试数据,我们要测量它到所有训练样本的距离,并取距离最近的一个。测量所有的距离需要大量的时间,同时也需要大量的内存来存储所有的训练样本。
但考虑一下图中的数据,我们是否需要这么多资源?

image
考虑另一个想法。我们找到一条线,$ f(x)= ax_1 + bx_2 + c $,它将数据分成两个区域。当我们得到一个新的测试值$X$时,只需将其带入$f(x)$即可。如果$ f(X)> 0 $,则属于蓝色组,否则属于红色组。我们可以把这个行称为Decision Boundary 。这非常简单,也很节约内存。可以用直线(或超平面,在更高维的情况下)将这些数据分成两部分,称为线性可分离

所以在上面的图片中,你可以看到很多这样的直线都是可能的。我们将取其中哪一条?非常直观地说,我们可以说线应该尽可能地将所有的点分离开。为什么?因为传入数据中可能会有噪音。这些数据不应该影响分类的准确性。所以采取一个最远的线将提供更多抵抗噪音的免疫力。SVM所做的就是找到一个与训练样本距离最大的直线(或超平面)。看下面的图像中穿过中心的粗线。

image

所以要找到这个决定边界,你需要训练数据。你需要全部吗?没有。只需要比较靠近对面的那些数据就足够了。在我们的图像中,他们是一个蓝色的实心圆和两个红色实心的正方形。我们可以称它们为支持向量,通过它们的直线称为支持平面。用它们就足以找到我们的决策边界。我们不必担心所有的数据。它有助于减少数据。

被找到的前两个超平面最能代表数据。例如,蓝色数据由$w ^ Tx + b_0> 1$表示,而红色数据由$w^Tx + b_0 <-1$表示,其中$ w $是权向量($ x = [x_1,x_2,…,x_n] $)。 $b_0$是 bias。权重向量决定决策边界的方向,而bias点决定其位置。现在决策边界被定义在这些超平面之间的中间,所以表示为$ w ^ Tx + b0 = 0 $。从支持向量到决策边界的最小距离由下式给出:$ distance {support\ vectors} = \ frac {1} {|| w ||} $。margin值是这个距离的两倍,我们需要最大化这个margin。即我们需要最小化一个新函数$ L(w,b0)$,其中有一些约束可以表达如下:
$$
\min{w, b_0} L(w, b_0) = \frac{1}{2}||w||^2 \; \text{subject to} \; t_i(w^Tx+b_0) \geq 1 \; \forall i
$$
其中$t_i$是每个类的标签,$t_i \in [-1,1]$。

非线性可分的数据

考虑一些不能用直线分成两部分的数据。例如,考虑“X”在-3和+3之间,“O”在-1和+1之间的一维数据。显然它不是线性可分的。但是有办法解决这类问题。如果我们可以用一个函数$ f(x)= x ^ 2 $来映射这个数据集,我们得到9处的’X’和1处的线性可分的’O’。

否则,我们可以将这个一维数据转换成二维数据。我们可以使用$ f(x)=(x,x ^ 2)$函数来映射这些数据。那么’X’变成(-3,9)和(3,9),而’O’变成(-1,1)和(1,1)。
这也是线性可分的。简而言之,低维空间中的非线性可分数据更有可能在高维空间中线性可分。

通常,可以将d维空间中的点映射到某个D维空间$(D>d)$以检查线性可分性的可能性。这个想法有助于通过在低维输入(特征)空间中执行计算来计算高维(内核)空间中的点积。我们可以用下面的例子来说明。

考虑二维空间中的两点,$p =(p_1,p_2) $和$q =(q_1,q2)$。假设$\phi $是一个映射函数,它将二维点映射到三维空间,如下所示:
$$
\phi (p) = (p{1}^2,p_{2}^2,\sqrt{2} p_1 p2)
\phi (q) = (q{1}^2,q_{2}^2,\sqrt{2} q_1 q2)
$$
让我们定义一个内核函数$K(p,q)$,它在两点之间做点积,如下所示:
$$
\begin{aligned}
K(p,q) = \phi(p).\phi(q) &= \phi(p)^T \phi(q) \
&= (p{1}^2,p_{2}^2,\sqrt{2} p_1 p2).(q{1}^2,q_{2}^2,\sqrt{2} q_1 q_2) \
&= p_1 q_1 + p_2 q_2 + 2 p_1 q_1 p_2 q_2 \
&= (p_1 q_1 + p_2 q_2)^2 \
\phi(p).\phi(q) &= (p.q)^2
\end{aligned}
$$
这意味着,三维空间中的点积可以在二维空间中使用平方点积来实现。 这可以应用于更高维空间。 所以我们可以从较低维度计算更高维度的特征。 一旦我们映射它们,我们就可以得到更高的空间。

除了所有这些概念之外,还存在错误分类的问题。 所以只用最大的margin来寻找决策边界是不够的。 我们还需要考虑错误分类的问题。 有时候,可能会找到一个margin较少,但是会减少误分类的决策边界。 无论如何,我们需要修改我们的模型,使它应该找到最大的边界的决策边界,但也有更少的错误分类。 最小化标准修改为:
$$
min \; ||w||^2 + C(distance \; of \; misclassified \; samples \; to \; their \; correct \; regions)
$$
下图显示了这个概念。 对于训练数据的每个样本,定义新的参数$\xi_i$。 它是从相应的训练样本到正确的决策区域的距离。 对于那些没有被错误分类的样本来说,他们落在了相应的支持层上,所以他们的距离是零。

所以新的要优化的问题是:
$$
\min{w, b{0}} L(w,b0) = ||w||^{2} + C \sum{i} {\xi{i}} \text{ subject to } y{i}(w^{T} x{i} + b{0}) \geq 1 – \xi{i} \text{ and } \xi{i} \geq 0 \text{ } \forall i
$$
参数C应该如何选择? 很显然,这个问题的答案取决于训练数据是如何分布的。 虽然没有一般的答案,但考虑到这些规则是有用的:

  • 大的C给出的解决方案,错误分类错误较少但margin较小。 考虑到在这种情况下,分类错误是很昂贵的。 由于优化的目的是使参数最小化,所以允许很少的错误分类错误。
  • 小的C值给出更大的margin和更多的分类错误的解决方案。 在这种情况下,最小化并没有考虑和项,所以它更多地关注找到一个具有较大余量的超平面。

更多资源

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

目前还没有任何评论,快来抢沙发吧!