机器学习之支持向量机

2019-03-17 本文已影响2人 Vophan

支持向量机

“SVM有三宝，间隔对偶核技巧”

首先，支持向量机是一个二分类的模型。

他与感知机算法有很多相似的地方，都是使用超平面分割空间，但是与感知不同的是：

支持向量机并不是感知机的错误驱动，而是对于几何间隔的最大化。
支持向量机可以解决的问题很多样，线性可分，近似线性，非线性可分。

线性可分问题：

对于线性可分的问题：

支持向量机采用硬间隔最大的方法训练模型。

首先，我们先解释一下，什么是间隔？

间隔，就如我们所想的就是距离，而这里我们要提及的有两种间隔：

函数间隔
几何间隔

几何间隔

几何间隔，对于两个点来说，就是两个点之间的距离，至于怎么算，我想也不用说了。

但是，在分类训练问题中，往往不是两个点，而是两堆点，那么对于两堆点，什么是几何间隔呢？

就是两堆中离得最近的点到超平面的距离，而在SVM中，我们知道：

我们是通过超平面分割来实现分类的，所以这个几何距离在实际中表示的就是：

将所有点分开的确信度大小

公式就是：
$gap = \frac{y_i(\omega x_i+b)}{||\omega||}$

函数间隔

可能学习过感知机的同学，知道函数间隔，当时统计学习方法中李杭老师对函数间隔一笔带过，留到SVM这里。这里，我们就对当时的一些问题一目了然了。
$Gap = y_i(\omega x_i+b)$
在感知机中，与其说这是函数间隔，我更愿意将他理解为分类错误的判别函数，其实感知机中并没有涉及到距离，所以这也就是，支持向量机与他不同的地方。

为什么支持向量机不采用函数间隔呢？

如果我们相同比例的扩大 $\omega$ 和 $b$ ，超平面并没有变，但是函数间隔却变成了原来的n倍。所以，对于支持向量机不能使用函数间隔。

硬间隔最大化

什么是硬间隔呢？

要理解硬间隔，你需要知道什么叫软间隔，而什么是软间隔呢？这个在近似线性可分再说吧。

这里，我们只要知道，硬间隔在这里就是间隔。

所以，我们的整个训练过程，现在就变成了一个约束条件下的最优化问题：
$max \gamma\\ s.t. y_i(\frac{\omega}{||\omega||}x_i+\frac{b}{||\omega||}) \geq \gamma$
为什么要有约束条件呢？

其实很简单，首先我们要先满足线性可分，才能使用硬间隔最大化。所以，我们得保证所有的训练数据都要有一个间隔，然后在从间隔中取出最大的一个。

其实，我们可以从前面知道：

函数间隔只是用来指示分类是否正确的函数，但是对于距离并没有影响，简单的说，函数间隔只是掌握了方向，真正影响分类确信度的是 $||\omega||$ ，也就是 $\omega$ 的L2范数。

或者说这样解释：

首先因为数据是线性可分的，所以，所以一定会有两条直线穿过正例和负例的支持向量，如图：

img

上面的优化问题等价于：
$min_\mu max_{\alpha,\beta}L(\mu,\alpha,\beta)\\ s.t.\quad \alpha_i \geq0 \quad i=1,2,3,4...,m.$
证明：

现在，我们来推导一下整个过程：

首先，我们要做的是间隔最大化：
$min \frac{1}{2}||\omega||^2\\ s.t.\quad y_i(\omega x_i+b) \geq 1$
然后，我们使用拉格朗日乘子法（向量化）：
$L(\omega, b,\lambda) = \frac{1}{2}\omega^T\omega+\sum_{i=1}^N\lambda_i(1-y_i(\omega^Tx_i+b))\\ min\quad maxL(\omega, b, \lambda)\\ s.t.\quad \lambda_i\geq 0$
为了减小计算难度，我们这里使用了拉格朗日的强对偶性：
$max\quad min L(\omega, b,\lambda)\\ s.t.\quad \lambda_i \geq 0$
然后，我们开始计算：

分别对 $\omega,b$ 求偏导，等于零，再带入到拉格朗日函数中，最终我们就得到了 $min\quad L(\omega, b, \lambda)$ 的值。

最终，我们就得到了：
$max (-\frac{1}{2}\sum_{i=1}^N\sum_{j=0}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i)\\ s.t.\quad \lambda_i \geq 0 \\ \sum_{i=1}^N\lambda_iy_i=0$
这样，我们就可以看到，我们把一个不等式约束的问题通过拉格朗日转换成了等式约束问题，从而，我们可以算出这个 $\lambda$ ,然后，我们使用KKT条件算出最后的 $\omega,b$ 。

KKT条件：(强对偶性一定满足KKT)

主问题可行： $1-y_i(\omega_Tx_i+b) \leq 0;$
对偶问题可行： $\lambda_i \geq0;$
互补松弛： $\lambda_i(1-y_i(\omega_Tx_i+b)) =0;$

根据KKT条件，我们可以求出：
$\omega = \sum_{i=0}{N}\lambda_iy_ix_i\\ b = y_i - \sum_{i=1}^N\lambda_iy_ix_i^Tx_k$
最终，我们就得到了分类决策函数。

对于最后一步最大化，我们将所有数据带入，然后通过偏导等于零，求得最大值

所以，我们解决一个Hard-margin分类问题时，我们需要:

构造并解出等式约束最优化问题
计算 $\omega, b$
求出分离超平面。

线性不可分问题

显然很多时候，我们的训练数据并不是那么的完美，总是有着各种各样的噪声，所以，我们需要将我们的SVM扩展到线性不可分的情况上去。

这时候，我们就需要引入软间隔最大化

什么是软间隔呢？

我们从头说起：

往往真实情况是我们并不能完美的将所有的数据分开，总有一些特异点在硬间隔最大化的策略下无法分类。那么这时候，我们为所有数据的判断上加入了一个常数松弛变量，使特异点在松弛变量的影响下可以被分开。所以这时候，我们的约束条件就变成了：
$y_i(\omega x_i+b)\geq1-\epsilon_i$
同时，对于每个松弛变量，我们需要支付一个代价 $\epsilon_i$ ,目标函数就由原来的 $\frac{1}{2}||\omega||$ 变为了：
$\frac{1}{2}||\omega||^2+C\sum_{i=1}^N\epsilon_i$
这里的C是惩罚参数，表示了对误分类的惩罚力度。

现在，最小化目标函数就有了两层意思：

使 $\frac{1}{2}||\omega||^2$ 尽量小也就是间隔尽量大
使误分类点尽可能少

C是调和两者的参数。

现在，线性不可分的线性支持向量机的学习问题就变成了凸二次规划问题：
$min_{\omega,b,\epsilon} \frac{1}{2}||\omega||^2+C\sum_{i=1}^N\epsilon_i\\ s.t.\quad y_i(\omega x_i+b)\geq1-\epsilon_i\\ \quad \epsilon\geq0$
其他的就和上面的一样了。