AllinToyou

这个屌丝很懒，什么也没留下！

热门标签

瞎聊机器学习——全方位理解支持向量机（SVM）_支持向量机的概念图

作者：AllinToyou | 2024-03-23 06:12:00

踩

支持向量机的概念图

SVM是一种常用的二分类模型，同时我们也可以通过核技巧用它来解决一些多分类的问题，下面我们来仔细的研究一下这个神秘的模型。

一、线性可分问题

线性可分，顾名思义就是可以用一条直线能够将两个不同的种类分开的问题。我们当然可以这么去理解，但是线性不可分的问题你是否能够很快的想到一个好的例子呢？下面我们来仔细的说一下这个问题。

用上图来作为一个简单的例子，图中有三角和圆两个类别，我们想找一条线把他们分开，当然这条线有很多种画法，图中只列出简单的三种分法，此时我们可以看出用一条直线我们可以很好的将两种类别分开，此时我们就可以说这个（数据）样本是线性可分的。

非线性可分，按照上面的逻辑，就是一些在特征空间内不能被一条之前分开的样本，画图来说明一下：

在二维平面内的这样两种样本，是不是直观上不能用一条直线将他们分开呢？别急后面我们也会讲到该类问题的解决办法，我们还是先来了解一下线性可分问题。

用数学来表述一下这个问题：

假定给一个特征空间上的训练数据集： $T=\{(x_1,y_1),(x_2,y_2)......(x_n,y_n)\}$

其中： $x_i\in X=R^n$ ， $y_i \in Y=\{+1,-1\}$ ， $i=1,2,3,...,n$ （X,Y表示输出输出空间）

此时当 $y_i=+1$ 时 $x_i$ 是正例， $y_i=-1$ 时 $x_i$ 是负例，特征空间T中的 $（x_i,Y_i）$ $(x_i,y_i)$ 就是样本点。

对于线性可分的问题我们可以得到一条直线（上图三条直线中的任一条）： $w\cdot x+b=0$ ，该直线将特征空间划分为了两个部分，一部分是正类，一部分是负类，SVM中我们可以称这条直线为分离超平面。

此时设有一个通过间隔最大化得到的（下文会讲到间隔最大化）分离超平面： $w\cdot x+b=0$

我们对分离超平面添加一个决策函数： $f(x)=sign(w\cdot x+b)$ ，此时该函数我们可以称作线性可分支持向量机。

sign函数的图像如下：

二、间隔问题

首先我们看一下线性可分问题中的图像，上文提到了将三角和圆分开的直线可以有很多种，而线性可分支持向量机对应着其中间隔最大的那条直线，那么这里的间隔具体指什么呢？

（一）、函数间隔

在这里我将上文中的例图进行一定的更改，只留下红色的分离超平面，我们来讨论一下圆这个累，图中有框出的红、绿、蓝三种颜色的圆，他们都落在圆类的一侧，但是红球距离超平面的距离较远，如果我们把红圆预测为圆类，就比较确信我们的预测是正确的；同理，相对于蓝色的圆，我们就不是很确信；而对于绿色的圆，我们可以认为确信度在二者之间。

通常情况下，我们可以把一个点距离分类超平面的远近表示为预测的确信程度，在分类超平面 $w\cdot x+b=0$ 确定的情况下，我们可以用 $\left | w\cdot x+b\right |$ 来表示点 $x$ 距离超平面的远近（确信度），而上文中提到 $y_i \in Y=\{+1,-1\}$ ，此时我们可以对比 $w\cdot x+b$ 和 $y$ 的符号是否相同来表示分类是否是正确的，所以我们就可以用 $y(w\cdot x+b)$ 来表示分类的确信度和准确性，这就叫做函数间隔，我们可以用如下的方式来表示：

函数间隔：

$\widehat{\gamma }=y(w\cdot x+b)$

（二）、几何间隔

说完了函数间隔，我们再来谈谈几何间隔是什么。

对于分类超平面 $w\cdot x+b=0$ ，当我们成比例的改变它的系数w和b的时候，由于等式的性质我们发现这个分类超平面本身并没有发生变化，但是对于它的函数间隔 $\widehat{\gamma }=y(w\cdot x+b)$ 会随着改变比例的变化而变化，这样当然会对我们的计算造成很大的麻烦，也可能会对分类产生一定的影响，所以我们需要通过某些方法使得间隔是确定的值，如规范化方法：

我们对超平面中的法向量w进行一定的约束得到：

$\gamma _i=\frac{w\cdot x_i+b}{\left \| w \right \|}$

不难发现当 $\left \| w \right \|=1$ 时， $\gamma _i=w\cdot x_i+b$ 也就是等于我们之前提到的函数间隔（只不过此时还没有分正负类），所以对于 $\gamma _i$ 放大任意倍的 $\left \| w \right \|$ ，间隔 $\gamma _i$ 不在发生变化，此时我们便可以称这个不会变化的间隔为几何间隔。

对于几何间隔上面是用函数间隔来推出的过程，如果不是很理解，可以把它认定是点到直线的距离（二维空间内）或者点到平面的距离（三维空间内）。

再对几何间隔添加上我们之前提到的表示分类正确性的y一项得到几何间隔的具体表达式：

$\gamma _i=y_i(\frac{w\cdot x_i+b}{\left \| w \right \|})$

其中 $\left \| w \right \|$ 称为w的L2范数（在后续其他文章中会讲到这个名词）。

综上我们可以得到函数间隔和几何间隔之间的关系 $\gamma =\frac{\widehat{\gamma }}{\left \| w \right \|}$ 。

三、间隔最大化

在一种我们提到过间隔最大化得到的分类超平面经过sign函数后可以得到线性可分支持向量机，下面我们来说一下间隔最大化具体是怎么回事。

第二节中我们提到了确信度的问题，为了保证更高的确信度我们是不是应该尽量让每一个点到分类超平面的几何间隔都达到最大化，这样做的目的是对于新的数据点，我们不仅能将它分到正负类别中，同时离分类超平面很近的点我们也可以将它很好的分类，并且能够保证有很大的确信度，我们就可以说这个超平面对新数据有很好的预测能力。

我们将间隔最大化的问题转换为约束最优化问题：我们希望最大化几何间隔 $\gamma$ 的同时又希望每个测试样本点的几何间隔至少是 $\gamma$ 。

$\underset{w,b}{max}:\gamma$

$s.t.:y_i(\frac{w\cdot x_i+b}{\left \| w \right \|})\geqslant \gamma$ ， $i=1,2,...,N$ (s.t.表示约束条件)

根据上节中提到的几何间隔和函数间隔之间的关系我们可以把上述问题进一步转化：

$\underset{w,b}{max}:\frac{\widehat{\gamma}}{\left \| w \right \|}$

$s.t.:y_i(w\cdot x_i+b)\geqslant \widehat{\gamma}$ ， $i=1,2,...,N$

我们要求的解释w,b的值，所以可以认为式中的 $\widehat{\gamma }$ 的值对不等式的值以及最优化问题并没有影响，所以为了便于求解我们令 $\widehat{\gamma }=1$ ，并且最大化 $\frac{1}{\left \| w \right \|}$ 的问题同样可以等价于 $\frac{1}{2}\left \| w \right \|^2$ ，则上述问题继续转化：

$\underset{w,b}{min}:\frac{1}{2}\left \| w \right \|^2$

$s.t.:y_i(w\cdot x_i+b)-1\geqslant 0$ ， $i=1,2,...,N$

此时我们便转化成了一个凸二次规划问题：

凸优化我们可以看做是一个凸函数去找最低点的问题（例如梯度下降法的过程）。

而二次规划是指目标函数为变量的二次函数和约束条件为变量的线性函数。

为了便于求解此类问题我们可以通过求解对偶问题得到原始问题的最优解，这样既可以简单的求解又可以引入后续对非线性分类问题的讨论。

四、支持向量

上文中我们根据间隔最大化原则求得了分离超平面和分类决策函数，下面我先用一个图来表示一下我们所求得的最大间隔边界以及支持向量。

在线性可分的情况下，训练数据集的样本点中与分离超平面最近的样本点的实例称作为支持向量。

如上图所示，我用两条黑色的直线来表示最大间隔边界，而图虫有红色的圆和红色的三角位于最大间隔边界上，这样的一些样本点我们就可以称他为支持向量。

所以我们可以说支持向量是使得第三节中的约束条件 $s.t.:y_i(w\cdot x_i+b)-1\geqslant 0$ 等号成立的点。

即：

$y_i(w\cdot x_i+b)-1=0$

对于正例点 $y_i=+1$ ：

$w\cdot x+b=1$

对于负例点 $y_i=-1$ ：

$w\cdot x+b=-1$

五、对偶问题

首先需要明确一下对偶问题的由来，对偶问题是一种应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。

原始问题：

$\underset{w,b}{min}:\frac{1}{2}\left \| w \right \|^2$

$s.t.:y_i(w\cdot x_i+b)-1\geqslant 0$ ， $i=1,2,...,N$

首先构建拉格朗日函数：

$L(w,b,\alpha )=\frac{1}{2}\left \| w \right \|^2-\sum_{i=1}^{N}\alpha _iy_i(w\cdot x+b)+\sum_{i=1}^{N}\alpha _i$ ，

$\alpha_i\geqslant 0$ ，

$i=1,2,...,N$

$\alpha=(\alpha_1,\alpha_2,...,\alpha_N)^T$ ，该项表示拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$\underset{\alpha}{max}\underset{w,b}{min}L(w,b,\alpha)$

为了求解我们先求 $L(w,b,\alpha )$ 中w，b的极小再求 $\alpha$ 的极大。

（一）、求极小：

我们对w,b求偏导并置零，再带入 $L(w,b,\alpha )$ 即可求得 $\underset{w,b}{min}L(w,b,\alpha )$ ，具体过程不做演示，这里给出结果：

对w求偏导可得到： $w=\sum_{i=1}^{N}\alpha_iy_ix_i$

对b求偏可得到： $\sum_{i=1}^{N}\alpha_iy_i=0$

带入我们构建的拉格朗日函数得到：

$\underset{w,b}{min}L(w,b,\alpha )=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i$

（二）、求极大：

已知极小值的情况下，其导数即为极大值，此时可以认为

$\underset{\alpha}{max}=-\underset{\alpha}{min}$

由此便得到了原始问题的对偶问题

$\underset{\alpha}{min}=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i$

$s.t.:\sum_{i=1}^{N}\alpha_iy_i=0$ ， $\alpha_i\geqslant 0$ ， $i=1,2,...,N$

到这里我们就得到了原始最优化问题和对偶最优化问题（上文中红标处）

根据slater条件，因为原始问题的目标函数和约束条件都是凸函数，并且该约束条件是严格可行的，所以我们认为存在 $\widehat{w},\widehat{b},\widehat{\alpha}$ ，使得 $\widehat{w},\widehat{b}$ 是原始问题的解， $\widehat{\alpha}$ 是对偶问题的解。

现在我们来求一下 $\widehat{\alpha}$ 的最优解：

设有 $\widehat{\alpha}=(\widehat{\alpha_1},\widehat{\alpha_2},...,\widehat{\alpha_N})^T$ 是对偶最优化问题的解，则至少存在一个 $\widehat{\alpha_j}$ 使得 $\widehat{\alpha_j}> 0$ （若不存在会造成 $\widehat{\alpha}=0,\widehat{w}=0$ ）

则有 $\widehat{w}$ 的最优解 $\widehat{w}=\sum_{i=1}^{N}\widehat{\alpha_i}y_ix_i$

再根据KKT条件（拉格朗日对偶性的一个定理）：

乘子非负： $\alpha_i\geqslant 0$ ， $i=1,2,...,N$

约束条件： $y_i(w\cdot x_i+b)-1\geqslant 0$ ， $i=1,2,...,N$

互补条件： $\alpha_i(y_i(w\cdot x_i+b)-1)=0$ ， $i=1,2,...,N$

根据互补条件，并且上文中推得 $\widehat{\alpha_j}> 0$ ，那么至少存在一个j使得 $y_j(\widehat{w}\cdot x_j+b)-1=0$ ，根据此式以及我们上面求得的 $\widehat{w}$ ，我们即可求得最优的 $\widehat{b}$ ：

$\widehat{b}=y_j-\sum_{i=1}^{N}\widehat{\alpha_i}y_i(x_i\cdot x_j)$

到此我们就求得了整个问题的最优解，求得的分离超平面即为：

$\sum_{i=1}^{N}\widehat{\alpha_i}y_i(x\cdot x_i)+\widehat{b}=0$

分类决策函数为：

$f(x)=sign(\sum_{i=1}^{N}\widehat{\alpha_i}y_i(x\cdot x_i)+\widehat{b})$

也就是说，分类决策函数只依赖于输入x和训练样本输入的内积，上式就是线性可分支持向量机的对偶形式。

注：对于对偶问题同样的，我们将 $\alpha_i> 0$ 时的实例点称作为支持向量。

六、引入松弛变量的线性支持向量机

上文中我们讲述的内容全都是在线性可分的情况下，而实际问题中这种状况经常是不存在的，那么当线性不可分的时候又应该怎么办呢？

如图：有少数的样本点使得我们不能够用一条直线将两个类别分开，也就意味着我们上文最大间隔中讲到的约束条件 $s.t.:y_i(w\cdot x_i+b)-1\geqslant 0$ 是不满足的，此时我们可以引进一个松弛变量 $\xi \geqslant 0$ ，使得我们的函数价格加上松弛变量后可以大于等于1，也就是：

$y_i(w\cdot x_i+b)+\xi \geqslant 1$

此时的间隔最大化我们称之为软间隔最大化

此时对于每一个松弛变量，我们目标函数同时也要添加一个 $\xi _i$ ，则目标函数变为：

$\frac{1}{2}\left \| w \right \|^2+C\sum _{i=1}^{N}\xi_i$

这里的C我们称之为乘法系数（C>0），C越小时对误分类的惩罚越小，越大时惩罚也就越大，当C取到无穷时，可以认为给了误分类项足够大的惩罚（导致 $\xi _i$ 变得极小），此时的最大间隔也自然又回到了硬间隔最大化上。

此时我们可以根据上两式得到原始问题，求解依然可以使用上午中的对偶问题，结果不发生变化，这里不再赘述。

七：损失函数

SVM中常用的损失函数是(hinge)合页损失函数。

$L_{hinge}(z)=max(0,1-z)$

而完整的SVM的损失函数其实就是在合页函数的后面多加了一个L2正则项：

$L_{svm}=\sum_{i=1}^{N}(1-y_i(w\cdot x_i+b))+\lambda \left \| w \right \|^2$

加入L2正则项的目的：使求解稳定快速，防止过拟合。

八、非线性支持向量机

上文中我们首先提到了线性可分支持向量机，后来又引入了松弛变量说了一下线性支持向量机，下面我们再来说一下非线性支持向量机。

（一）、核技巧

对于非线性支持向量机，我们需要用核技巧将线性支持向量机推广到非线性支持向量机，不仅是SVM其他的一些类似问题也可以用该方式来解答。

所谓核技巧其实就是使得在原空间内不可分的数据映射到更高维度的空间上，然后再使用线性的方法将他们分开的一种思想，用下图来表示一下：

可以看到图左的数据在二维空间内不能用一条直线将他们分开，我们将它映射到一个三维的空间内，此时就会存在一个平面（黄色的部分）将两类分离开来，对于这种思想我们就可以称之为核技巧。

（二）、核函数

说了核技巧我们就不得不说它的重要部分——核函数。

核函数的定义：

我们设X是输入空间，H是特征空间，如果存在一个X到H映射关系： $\phi (x):X\rightarrow H$ ，使得对所有的 $x,z\in X$ ，函数 $K(x,z)$ 满足条件 $K(x,z)=\phi(x)\cdot \phi(z)$ ，则成 $K(x,z)$ 为核函数， $\phi(x)$ 为映射函数，其中 $\phi(x)\cdot \phi(z)$ 称为 $\phi(x)$ 和 $\phi(z)$ 的内积。（内积我们在上文中见过）

通常，直接计算 $K(x,z)$ 比较容易而通过 $\phi(x)$ 和 $\phi(z)$ 计算 $K(x,z)$ 并不容易。但是在我们第五节中推得的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及到输入示例与实例之间的内积，所以对于对偶问题目标函数的内积我们可以用核函数来代替，此时的目标函数就变成了：

$W(\alpha )=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha _i\alpha_jy_iy_jK(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i$

分类决策函数就变成了：

$f(x)=sign(\sum_{i=1}^{N}\widehat{\alpha_i}y_iK(x_i\cdot x_j)+\widehat{b})$

对于什么样的函数 $K(x,z)$ 可以称之为核函数，具体参考《统计学习方法》中的过程，由于过于复杂这里不做推导。

（三）、常用的核函数

多项式核函数：

$K(x,z)=(x\cdot z+1)^p$

高斯核函数：

$K(x,z)=exp\left(-\frac{\left \| x-z \right \|^2}{2\sigma ^2}\right)$

九、SVM的优缺点

优点:

SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维度灾难”。

缺点:

二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/293559