理解支持向量机(SVM)算法

理解SVM

目标

在这一章中，将学习

• 直观理解SVM

理论

线性可分数据

给定下面的图像，它具有两种数据类型——红色和蓝色。在kNN算法中，对于测试数据，用来测量其与所有训练样本的距离，并以最小的距离作为样本。测量所有距离都需要花费大量时间，并且需要大量内存来存储所有训练样本。但是考虑到图像中给出的数据，是否需要比较那么多多次距离？

考虑另一个想法。找到一条线$f(x)=a{x}_1+b{x}_2+c$，它将两条数据都分为两个区域。当得到一个新的test_data X时，只需将其替换为f(x)即可。如果f(X)>0，则属于蓝色组，否则属于红色。可以将该线称为**“决策边界（Decision Boundary）”，该方法非常简单且有效利用内存。可以将这些数据用直线（或高维超平面）一分为二的数据称为线性可分离**数据。

因此，在上图中，可以看到很多条线都是可能的。我们会选哪一个？非常直观地，直线应该离所有点尽可能远地经过。这是因为传入的数据中可能会有噪音，噪声数据不应该影响分类的准确性。因此，离得越远的分割线将具有更大的抗干扰能力。因此，SVM要做的是找到一条线，该条线离训练样本的距离最大的直线（或超平面），比如下面图像中穿过中心的粗线。

因此，为了找到决策边界就需要使用训练数据，但是否需要全部的训练数据吗？结果并不需要所有的数据，只是互相靠近对方类别的那些点就足够了。在上图中，只需要一个蓝色填充的圆圈点和两个红色填充的正方形这三个数据即，这些点也被称为支撑向量（Support Vectors），通过它们的线（虚线）被称为支撑平面（Support Planes），这足以找到所需要的决策边界。不用考虑所有的数据，这有助于减少数据量。

接下来，找到了最能代表数据的前两个超平面。例如，蓝色数据由$w^{T}x+b_0>-1$表示，红色数据

由$w^{T}x+b_0<-1$表示，其中w是权重向量(weight vector)($w=[w_1,w_2,\dots ,w_n]$)，x是特征向量($x=[x_1,x_2,\dots ,x_n]$)。b_0是偏置(bias)。权重矢量决定决策边界的方向，而偏置确定其位置。现在

将决策边界定义为这些超平面之间的中间，因此表示为$w^{T}x+b_0=0$。从支持向量到决策边界的

最小距离由$distanc{e}_{supportvectors}=\frac{1}{||w||}$给出。间隔是此距离的两倍，因此需要最大化此间隔。也就是说，需要使用一些约束来最小化新的函数$L(w,b_0)$，这些约束可以表示如下：

${\min }_{w,b_0}L(w,b_0)=\frac{1}{2}||w|{|}^2\text{subject to}{t}_i(w^{T}x+b_0)\ge 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,q_2)$。令ϕ为映射函数，它将二维点映射到三维空间，如下所示：

$\varphi (p)=(p_1^2,p_2^2,\sqrt{2}{p}_1{p}_2)\varphi (q)=(q_1^2,q_2^2,\sqrt{2}{q}_1{q}_2)$

定义一个核函数K(p,q)，该函数在两点之间做一个点积，如下所示：
$\begin{array}{rl}K(p,q)=\varphi (p).\varphi (q)& =\varphi (p{)}^T\varphi (q)\\ & =(p_1^2,p_2^2,\sqrt{2}{p}_1{p}_2).(q_1^2,q_2^2,\sqrt{2}{q}_1{q}_2)\\ & =p_1^2{q}_1^2+p_2^2{q}_2^2+2p_1{q}_1{p}_2{q}_2\\ & =(p_1{q}_1+p_2{q}_2{)}^2\\ \varphi (p).\varphi (q)& =(p.q{)}^2\end{array}$

这意味着，可以使用二维空间中的平方点积来实现三维空间中的点积，这可以应用于更高维度的空间。因此，可以从较低维度特征本身计算较高维度的特征。一旦将它们映射，将获得更高维度的空间。

除了所有这些概念之外，还存在分类错误的问题。因此，仅找到具有最大间隔的决策边界是不够的，还需要考虑分类错误的问题。有时，可能会找到间隔较小但分类错误减少的决策边界。无论如何，需要修改模型以便它可以找到具有最大间隔且分类错误较少的决策边界。最小化标准修改为：

$min||w|{|}^2+C(distanceofmisclassifiedsamplestotheircorrectregions)$

下图显示了此概念，对于训练数据的每个样本，定义一个新的参数${\xi }_i$，它是从其相应的训练样本到其正确决策区域的距离。对于那些未分类错误的样本，它们落在相应的支撑平面上，因此它们的距离为零。

因此，新的优化函数为：

${\min }_{w,b_0}L(w,b_0)=||w|{|}^2+C{\sum }_i{\xi }_i\text{ subject to }{y}_i(w^T{x}_i+b_0)\ge 1-{\xi }_i\text{ and }{\xi }_i\ge 0\forall i$

如何选择参数C？显然，这个问题的答案取决于训练数据的分布方式。尽管没有一般性的答案，但以下规则是很有用的：

• C的值越大，解决方案的分类错误越少，但给予的边界宽度余量也越小。考虑到在这种情况下，进行错误分类错误是昂贵的。由于优化的目的是最小化参数，因此几乎没有误分类的错误
• C的值越小，解决方案给予的边界宽度余量就越大，分类误差也越大。在这种情况下，最小化损失对分类错误总和项的考虑不多，因此它更多地集中在寻找具有大间隔的超平面上

附加资源

• docs.opencv.org/4.5.4/d4/db…

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