支持向量机

2021-01-02

支持向量机

给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个$\{+1,-1\}$，SVM训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。除了进行线性分类之外，SVM还可以使用所谓的核技巧有效地进行非线性分类，将其输入隐式映射到高维特征空间中。

由于求解支持向量机优化问题需要用到拉格朗日乘子法，因此首先介绍拉格朗日乘子法。

1. 拉格朗日乘子法

拉格朗日乘子法是一种求解带有约束的优化问题的方法。

假设 $f(x),g_j(x),h_i(x)$ 是定义在$\mathcal{R}^n$的连续可微函数，有如下约束优化问题：

$\min_x f(x)$ $s.t.\ \ h_i(x)=0,i=1,2...,m\\ \ g_j(x)\le0,j=1,2,..,n$

假设其最优解记为 $p^\star$。

拉格朗日函数

其拉格朗日函数$L(x,\lambda,\mu)$:

$L(x,\alpha,\beta) = f(x) + \sum_i^m\lambda_ih_i(x)+\sum_j^n\mu_jg_j(x)$

其中，$\lambda,\mu$为拉格朗日乘子。

KKT条件

$g_j(x)\le0;\\\mu_j>=0;\\\mu_jg_j(x)=0$

最后一个被称为互补松弛条件。对于一般的任意问题而言，KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。

拉格朗日对偶函数

$\max_{\lambda,\mu}\Gamma(\lambda,\mu)\ \ s.t.\mu\ge0$

无论原函数凸性如何，对偶函数保证是凸函数。

如何获得对偶函数，将拉格朗日函数对$x$求偏导等于0，带回拉格朗日函数消去$x$后，就得到只包含$\lambda,\mu$的对偶函数。

对偶问题的最优解记为 $d^\star$。

弱对偶

$d^\star\le p^\star$ $\min \max L \ge \max \min L$

即极大值中的极小一定大于等于极小值中的极大。

注意：弱对偶是一个性质，是永远成立的，可能在某些问题上等号取不到。

强对偶

$d^\star = p^\star$

当弱对偶中的等号可以取到时，强对偶成立，对偶问题的最优解与原问题的最优解相同，这样通过求解对偶问题即可得到原问题的最优解。

2. 线性可分支持向量机

2.1 动机

将数据进行分类是机器学习中的一项常见任务。假设某些给定的数据点各自属于两个类之一，而目标是确定新数据点将在哪个类中。对于支持向量机来说，数据点被视为 $p$ 维向量，而我们想知道是否可以用 $p-1$ 维超平面来分开这些点。可能有许多超平面可以把数据分类。最佳超平面的一个合理选择是以最大间隔把两个类分开的超平面。因此，我们要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面，则称为最大间隔超平面（来源：中文维基百科）。

2.2 推导

2.2.1 硬间隔（hard margin）

给定训练样本集 $\mathcal{D} =\{(\pmb x_1,y_1),(\pmb x_2,y_2),…,(\pmb x_m,y_m)\},y_i\in\{+1,-1\}$。分类学习最基本的思想是基于训练集在样本空间找到一个划分超平面，将不同类别的样本区分开。其中，这个超平面可以用如下方程来描述：

$\pmb w^T\pmb x + b = 0$

其中 $\pmb w,b$ 决定了这个超平面的位置。

样本空间中某一样本 $\pmb x_i$ 到这个超平面的距离：

$r = \frac{|\pmb w^T\pmb x+b|}{||\pmb w||}$

$||\pmb w||$ 表示向量的L2范数（模长）。

假设这个超平面可以将样本完全分开，即

$\pmb w^T\pmb x_i + b > 0,y_i = 1\\ \pmb w^T\pmb x_i + b < 0,y_i = -1$

令：

$\pmb w^T\pmb x_i + b \ge 1,y_i = 1\\ \pmb w^T\pmb x_i + b \le -1,y_i = -1$

当某个样本使得上述两个等号成立时，即$\pmb w^T\pmb x_i + b = 1$ 或者 $\pmb w^T\pmb x_i + b = 1$，我们称这个样本为支持向量。

可知两个异类样本的支持向量到超平面的距离为

$\frac{2}{||\pmb w||}$

支持向量机的目标就是最大化上述距离，使得超平面尽可能的分开所有样本点。

就有如下优化问题：

$\begin{array}{cl} \max_{\pmb w,b} & {\frac{2}{||\pmb w||}} \\ {\text { subject to }} & {y_i(\pmb w^T\pmb x+b )\ge1}&{i=1,2,...,m}\\\end{array}$

等价于：

$\begin{array}{cl} \min_{\pmb w,b} & {\frac{1}{2}||\pmb w||^2} \\ {\text { subject to }} & {y_i(\pmb w^T\pmb x+b )\ge1}&{i=1,2,...,m}\\\end{array}$

这就是支持向量机的目标函数。

现在的问题就是如何求解上述带有约束的优化问题。

引入拉格朗日乘子 $\alpha_i \ge0$，该约束问题对应的拉格朗日函数如下：

$L(\pmb w,b,\pmb \alpha) = \frac{1}{2}||\pmb w||^2 +\sum_{i=1}^m\alpha_i(1-y_i(\pmb w^T\pmb x_i+b))$

其中，$\pmb \alpha = (\alpha_1,\alpha_2,…,\alpha_m)$。

分别对$\pmb w,b$求导并令其等于0可得：

$\frac{\partial L}{\partial \pmb w} = \pmb w - \sum_{i=1}^m\alpha_iy_i\pmb x_i = 0$ $\frac{\partial L}{\partial b} = \sum_{i=1}^m\alpha_iy_i = 0$

注意： $\sum_{i=1}^m\alpha_iy_i = 0$ 指的是最终求和为0，其中的每一项 $\alpha_iy_i$ 可能不为0。

带回拉格朗日函数中，消去$\pmb w,b$有：

$\frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\pmb x^T_i\pmb x_j +\sum_{i=1}^m\alpha_i - \sum_{i=1}^m\alpha_iy_i(\sum_{j=1}^m\alpha_jy_j\pmb x_j^T\pmb x_i + b)$

即：

$\max_{\pmb \alpha}-\frac{1}{2} \sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\pmb x^T_i\pmb x_j +\sum_{i=1}^m\alpha_i\\\sum_{i=1}^m\alpha_iy_i = 0\\ \alpha_i\ge0$

这就是拉格朗日函数的对偶问题。

求解出最优的 $\pmb \alpha^\star$ 后，最优超平面为：

$\pmb w^T\pmb x + b = \sum_{i=1}^m\alpha_iy_i\pmb x_i^T\pmb x+b$

2.2.2 软间隔（soft margin）

3. 线性支持向量机

4. 核函数

$\mathcal{K}(\pmb x,\pmb y) = \phi(\pmb x)\phi(\pmb y)\tag{1}$

常见的核函数：

齐次多项式（$·$）表示向量内积：

$\mathcal{K}(\pmb x,\pmb z) = (\pmb x·\pmb z)^d = (\pmb x^T\pmb z)^d$

非齐次多项式：

$\mathcal{K}(\pmb x,\pmb z) = (\pmb x·\pmb z + 1)^d$

径向基函数（也叫高斯核函数）：

$\mathcal{K}(\pmb x,\pmb z) = e^{-\frac{||\pmb x - \pmb z||^2}{2\sigma^2}}$

支持向量机和感知机的区别？

作者：DeAlVe
链接：https://www.zhihu.com/question/51500780/answer/482442236
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这是一个很有意思的问题，明白了这个问题就可以从直觉上理解SVM为什么会产生大间隔。

普通的感知器不能产生大间隔(margin)，而SVM可以，所以这两个肯定不是一个东西。
带margin的感知器可以通过两种手段产生大间隔：一种是早停，另一种是加正则化项。
加入了L2正则化项的带 margin的感知器就是SVM。

大家都知道，感知器是不能产生大间隔的，因为它只以分对为目的，不关心分界面离数据点有多远，从它的目标函数很容易看出来（这里直接搬了 @猪猪专业户的公式），它公平对待每一个数据：

$\min_{w,b}\frac{1}{n}\sum_{i=1}^n max(0, -y_i(w^Tx_i+b))\\$ (1)

带margin的感知器是这样的，只改动了一个地方：

$\min_{w,b}\frac{1}{n}\sum_{i=1}^n max(0, 1-y_i(w^Tx_i+b)) \\$ (2)

有没有发现，损失函数就是hinge loss，这个改进使得感知器具备了产生大间隔的潜质，因为hinge loss有一段平坦区，允许平坦区内的点被分错，这样就可以撑起来一个管道（类似于SVM）。

虽然带margin的感知器有了hinge loss，但是它依然不能产生大间隔，看下面这个目标函数：

$\min_{w,b}\frac{1}{n}\sum_{i=1}^n max(0, \gamma-y_i(w^Tx_i+b)) \\$ (3)

目标函数(2)和(3)是等价的，因为把(2)的一个解 $(w, b)$ 放大 $\gamma$ 倍就得到了(3)的一个解 $(\gamma w, \gamma b)$ 。如果令 $\gamma \rightarrow +\infty$ ，我们就得到了任意大的函数间隔；如果令 $\gamma \rightarrow 0$ ，(3)就变成(1)了，函数间隔消失了。然而函数间隔不是我们想要的，几何间隔才是（几何间隔 = 函数间隔 / 模长）。

带margin的感知器可以通过增大权向量的模长而增大函数间隔，但是几何间隔却是不变的，这显然不是我们想要的。如果我们能限制模长的增长，就有可能获得大的几何间隔。而限制模长的方法有两个：早停和正则化。

先来看早停是如何产生大间隔的，如下图（来自[1]）：

(a)是普通感知器得到的分界面，过拟合且没有产生大间隔；(b)(c)(d)分别是带margin的感知器迭代1, 10, 100个epoch之后得到的分类面，可以看出随着迭代次数的增多，间隔渐渐消失，具体的讲解可以看参考文献[1]。一种直觉而不太严谨的理解是：趁着权向量还没有来得及快速增大就停止学习。

除了早停，还有一种方法可以产生大间隔，那就是加入对权向量的L2正则化，限制模长的增长：

$\min_{w,b}\frac{1}{n}\sum_{i=1}^n max(0, 1-y_i(w^Tx_i+b)) + \alpha ||w||_2^2 \\$ (4)

与(2)相比，(4)加入了对权向量模长的惩罚项，从而避免了产生像(2)一样的无意义的大函数间隔。

而(4)就是SVM。

所以，SVM可以视为对感知器的二阶改进：第一阶改进是加入了 $\gamma$ 获得hinge loss，从而具备了产生大间隔的潜质；第二阶改进是加入了权向量的L2正则化项，从而避免产生无意义的大函数间隔，而是产生大的几何间隔。

参考文献：

[1] Collobert R, Bengio S. Links between perceptrons, MLPs and SVMs[C]//Proceedings of the twenty-first international conference on Machine learning. ACM, 2004: 23.

另附：

感知机的目标就是找到一个分割平面，使得尽量得区分正确。SVM的目标是找到一个分割平面，不仅区分正确，而且要让正负样本尽量远离这个分割平面。下图里面，$H_2$ 就是感知机的（不一定唯一），$H_3$ 就是SVM的。

5. 非线性支持向量机

当样本集不是线性可分的时候，就需要引入核函数对样本的特征进行升维处理。

6. 多分类支持向量机

参考：https://www.cnblogs.com/zhizhan/p/4448668.html

a.一对多法（one-versus-rest,简称1-v-r SVMs）。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样 $k$ 个类别的样本就构造出了 $k$ 个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

b.一对一法（one-versus-one,简称1-v-1 SVMs）。其做法是在任意两类样本之间设计一个SVM，因此 $k$ 个类别的样本就需要设计 $k(k-1)/2$ 个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。

7. OneClass支持向量机

OneClass 支持向量机也是支持向量机类算法中的一种，不同的是这个是无监督算法，也就说不需要类别标签。他的基本思想就是在样本空间找到一个半径最小的超球面（超球面是指三维以上的空间中的球面，对应的二维空间中就是曲线，三维空间中就是球面）尽可能将样本围在这个超球中。当不属于超球中的样本输入模型，模型就会输出no，从而完成分类。