Question

目标

在这一章当中，我们将看到对SVM的直观理解。

理论

线性可分的数据

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

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

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

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

被找到的前两个超平面最能代表数据。例如，蓝色数据由 $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 和更多的分类错误的解决方案。 在这种情况下，最小化并没有考虑和项，所以它更多地关注找到一个具有较大余量的超平面。

更多资源

NPTEL notes on Statistical Pattern Recognition, Chapters 25-29.