理解 SVM
目标
在本章 * 我们将对 SVM 有个直观理解
原理
线性可分离数据
下面的图像中有两类数据，红色和蓝色。在 kNN 中，对于某个测试数据，我们通常要计算它与所有训练样本的距离，并选择距离最短的训练样本作为分类依据。计算与所有样本的距离花费大量时间，而且存储所有的训练样本要花费大量的内存。只为了分类图中所示数据，我们真需要花费这么多代价吗？
换个思路。我们可以找到一条直线 f(x)=ax1 + bx2 + c 将数据分成两个区域。当我们得到一个新的测试数据 X 时，只需计算 f(X) 。如果 f(X) > 0 ，则属于蓝色组，否则属于红色组。我们可以将此直线称为决策边界。这非常简单，并且用的内存很少。像这种能够用一条直线（或更高维度的超平面）分割成两部分的数据被称为线性可分离的。
在上图中，你可以看到很多这样的直线，它们都能将两类数据分割。我们要选其中的哪一条？非常直观地说，该直线应该尽可能远离所有点。为什么呢？因为输入数据中可能存在噪声数据。这些噪声数据不应影响分类准确性。因此，选择距离样本最远的直线的抗噪声能力更强。因此，SVM 所做的是找到与训练样本具有最大距离的直线（或超平面）。请参见下图中穿过中心的粗线。
为了找到决策边界，需要训练样本。但需要投入所有训练样本进入计算吗？不。仅仅那些接近对立类别的数据就够了。在我们的图像中，它们是一个蓝色填充圆和两个红色填充正方形。我们可以称它们为支持向量，通过支持向量的线称为支持平面。使用它们足以找到决策边界。我们无需为数据的全体数量而担心。支持向量有助于减少数据的所需量。
发生了什么事呢？首先，有两个超平面被认为最能代表数据。例如，蓝色数据由 wTx + b0 > 1代表 ，而红色数据由 wTx + b0 < -1 代表，其中 w 是权重向量（ w = [w1,w2,...,wn] ）， x 是特征向量（ x = [x1,x2,...,xn] ）， b0 是偏差。权重向量决定决策边界的方向，而偏差决定其上下位置。现在，决策边界被定义为这些超平面的正中间，因此表示为 wTx + b0 = 0 。从支持向量到决策边界的最小距离由 distancesupport vectors = 1/||w|| 给出。间距是这个距离的两倍，我们需要最大化这个间距。即我们需要最小化一个新函数 L(w,b0) ，优化目标表示如下：
![图片](./img/svm_func1.png">
其中 ti 是每个类的标签， ti ∈ [-1,1] 。
非线性可分离数据
考虑到一些数据用直线并不能正确分为两类。例如，一维数据（可以理解为数轴），其中为-3 和+3为'X'类样本，-1 和+1为'O'类样本。显然，它不是线性可分离的。但是有一些方法可以解决这类问题。 如果我们可以用函数 f(x) = x2 映射这个数据集，我们得到'X'类样本为 9，'O'类样本为 1，它们是线性可分离的。
此外，我们可以将这个一维数据转换为二维数据。我们可以使用 f(x) = (x, x2) 函数来映射这些数据。然后'X'变为(-3,9)和(3,9)，而'O'变为(-1,1)和(1,1)。这也是线性可分离的。简而言之，低维空间中的非线性可分离数据在高维空间中线性可分离的可能性更大。
通常，这种方法是可行的，将 d 维空间中的点映射到某个 D 维空间 (D > d) 以尝试线性可分离能否成立。有一个想法有助于通过在低维输入（特征）空间中执行计算，从而获得高维（核）空间中的点积。我们可以通过以下示例来说明。
考虑二维空间中的两个点， p = (p1, p2) 和 q = (q1, q2) 。设 Φ 是一个映射函数，它将二维的点映射到三维空间，如下所示：
![图片](./img/svm_func2.png">
定义一个核函数 K(p,q) ，它在三维空间的两点间做一个点积，如下所示：
![图片](./img/svm_func3.png">
这意味着，在二维空间中使用点积的平方可以实现三维空间中的点积。这可以应用于更高维度的空间。因此，我们可以从较低维度本身计算更高维度的特征。一旦完成映射，就会获得一个更高维的特征空间。
在上述概念之外，还存在分类错误的情况。因此，仅仅找到具有最大间距的决策边界是不够的。我们还需要考虑分类错误的问题。有时，可能会找到间距较小的决策边界，但分类错误减少。无论如何，我们需要修改我们的模型，使其找到具有最大间距的决策边界，但分类错误较少。优化问题转化为：
![图片](./img/svm_func4.png">
下图展示了相关实现。对于训练数据的每个样本，定义新参数 ξi 。它是从相应的训练样本到正确决策区域的距离。对于那些没有被错误分类的数据，它们会落在相应的支持平面上，因此它们的距离为零。
所以新的优化问题是：
![图片](./img/svm_func5.png">
如何选择参数 C？很明显，答案取决于训练数据的分布。虽然没有一般性答案，但考虑以下准则很有用： * 较大的 C 值给出的解决方案具有较少的分类错误可能，但间距较小。当分类错误导致严重损失时，可以考虑此方案。因为优化目标是最小化参数，所以较少的分类错误也是被允许的。 * 较小的 C 值给出的解决方案具有更大的间距和更多的分类错误可能。在这种情况下，最小化并不会太关心求和项，因此它更侧重于寻找具有大间距的超平面。
