52ML系列(2)--SVM支持向量机

作者: beckhz | 来源:发表于2019-03-04 05:11 被阅读114次

support vector machine是一个适用于中小型数据集的强大算法，可惜深度学习崛起后淡去了昔日的光辉。。。
但是SVM依旧是一个不可忽视的机器学习算法，让我们来领略SVM的魅力吧

从最佳分割线说起

假设用一条线切开数据，将其分为两类，如图1所示，你会如何切分呢？

图1

图中第三列分法，数据点离分割线最远，直觉上来说感觉这种分法较好。为什么呢？就是直觉。。。

ok，SVM来告诉你为什么。

寻找最胖的分界线

其实很简单，从鲁棒性的角度来说，第三列的分法使得两类已有的数据离分界线最远，那么新增的数据点被误分类的概率就会第一点。

分界线越胖，鲁棒性越好，模型泛化能力也就越好，因此我们的目标是--没有蛀牙！

那么如何寻找最胖的分界线(学术术语：超平面)呢？我们用距离公式：
$distance(X,b,W) = \frac{{|W^TX+b|}}{||W||}$
其中 $W^TX+b$ 就是超平面，那么现在的目标就是求得使距离最大化的 $W$ 和 $b$ 。

等等，貌似我们还要保证所有的点被正确划分呢！试想所有被划分到正类的点应该被标注为 $y=+1$ ，而负类则被标注为 $y=-1$ ，那么被正确分类的点距超平面的距离应该与其标签同号。数学表示为：
$y\cdot (W^TX+b)>0$
ok，现在的任务变成了这样：
$max_{W,b}\ \ \ \ distance(W, b)=\frac{y\cdot (W^TX+b)}{||W||}\\ s.t.\ \ \ \ \ \ \ y_i\cdot (W^Tx_i+b)>0,\ \ \ \ i = 1,2,\cdots,N$
为了方便计算，我们令最小的函数间隔 $y\cdot (W^TX+b)=1$ 。

tips： $W^TX+b$ 表示的是函数距离，并不影响 $W,b$ 的求解。因为把函数距离扩大 $\lambda$ 倍，那 $W,b$ 也会等比例扩大 $\lambda$ 倍。

so，现在的任务又稍变了一点样子：
$max_{W,b}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \frac{1}{||W||}\\ s.t.\ \ \ \ \ \ \min_{W,b}\ \ \ y_i\cdot (W^Tx_i+b)=1,\ \ \ \ i = 1,2,\cdots,N$
接下来把最大化问题转变为最小化问题，目前任务的最终形态长这样：
$min_{W,b}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \frac{1}{2}||W||^2\\ s.t.\ \ \ \ \ \ \ \ \ y_i\cdot (W^Tx_i+b)≥1,\ \ \ \ i = 1,2,\cdots,N$
tips：最大化 $\frac{1}{||W||}$ 与最小化 $\frac{1}{2}||W||^2$ 问题是等价的， $\frac{1}{2}$ 与平方的引入只是为了方便后面计算求导。。。

任务的最终形态是一个凸二次规划问题(convex quadratic programming)，很多统计学的工具软件都带有求解二次规划问题的功能。利用工具的便利性，可以求出最好的 $W,b$ ，故而得到了最胖的分界线。

但是求解二次规划问题涉及到 $W$ 的维度，若 $d_W$ 很大，求解二次规划的计算量将变得巨大！如何解决这一问题呢？

答案就是对着SVM呕一呕🤢

拉格朗日对偶问题(Lagrange Dual Problem)

为什么要引入拉格朗日对偶问题？一方面如前文所述，对于巨大维度的数据，二次规划难以求解；另一方面在于，我们的模型是解一个带不等式条件的最优化问题，而拉格朗日对偶算法恰好就是干这个活的；最后一点在于，可以引入核函数。。。核武器。。。原子弹。。。

我们先来看看如何构建拉格朗日函数。

其实很简单，还记得我们的目标函数跟条件函数吗？把目标函数跟条件函数写成一个式子，当然条件函数需要乘以一个拉格朗日乘子 $\alpha_n≥0,\ n=1,2,\cdots ,N$ (Lagrange multiplier)，写法如下：
$L(W,b,\alpha)=\underbrace{\frac{1}{2}||W||^2}_{object}+\sum_{n=1}^N\alpha_n(\underbrace{1-y_n\cdot (W^Tz_n+b)}_{constraint})$
我们要让 $object$ 最小，同时又要保证 $constraint$ 成立，于是问题转化成这样：
$SVM \equiv min_{W,b}(max_{all\ \alpha_n≥0}L(W,b,\alpha))$
怎么一下最大一下最小，真是莫名其妙。。。

我们这样来看这个式子：
$min_{W,b}(\infty\ if\ violate;\ \frac{1}{2}||W||^2\ if\ feasible)$
条件函数也可以认为是对SVM模型能够正确分类数据的一种约束对不对？ $\alpha_n$ 则是这个约束的权重，这样就存在一种约束的临界点：

如果某个分类点 $x_i$ 没有被正确分类，那么这个模型违背了正确分类所有点的初衷 $y_n\cdot (W^Tz_n+b)≥0$
注意 $constraint$ ，错误分类时会大于零。考虑到 $object$ 是恒正的，而 $\alpha_i$ 也是非负的，这时 $\alpha_i$ 会机智的将整个式子变成正无穷，你还想求最小值？我强制让你无解！╭(╯^╰)╮
如果是正确分类的点呢？ $\alpha_i$ 说，好吧，你乖我就不欺负你。于是 $\alpha_i$ 又机智的让 $constraint$ 等于0，这样整个式子就是 $\frac{1}{2}||W||^2$ 。

ok，这就是拉格朗日算法的精髓，如果你都弄清楚了说明你已经掌握SVM了！吗？

好吧，还没有。。。实际上我们还没有说对偶呢。上面的式子是个最大值问题，并不好求解，于是对偶问题粉墨登场。
$min_{W,b}(max_{all\ \alpha_n≥0}L(W,b,\alpha)) ≥\underbrace{max_{W,b}(min_{all\ \alpha_n≥0}L(W,b,\alpha))}_{Lagrange\ dual\ problem}$
这就是对偶问题，神奇的把求最大最小值的操作互换了位置。更神奇的是，由于SVM模型恰好符合某些条件，对偶问题与原始问题之间竟然可以取等号了。感兴趣的同学可以自行脑补其中的奥妙。😳

有了对偶问题，任务转化为了求最小值：
$max_{all\ \alpha_n≥0}[min_{W,b}\underbrace{\frac{1}{2}||W||^2+\sum_{n=1}^N\alpha_n(1-y_n\cdot (W^Tz_n+b))}_{L(W,b,\alpha)}]$
于是我们就可以开心的求偏导了。

求解 $minL(W,b,\alpha)$

对b求偏导并令其为零
$▽_b\ L(W,b,\alpha)=-\sum_{n=1}^N\alpha_ny_n=0$
对W求偏导并令其为零
$▽_W\ L(W,b,\alpha) = W-\sum_{n=1}^N\alpha_ny_nz_n=0$
得到：
$W=\sum_{n=1}^N\alpha_ny_nz_n$
$\sum_{n=1}^N\alpha_ny_n=0$
带入到 $L(W,b,\alpha)$ 中，得到 $minL(W,b,\alpha)$ 最终形态：
$minL(W,b,\alpha) =-\frac{1}{2}||\sum_{n=1}^{N}\alpha_ny_nz_n||^2+\sum_{n=1}^{N}\alpha_n$
求 $minL(W,b,\alpha)$ 对 $\alpha$ 的最大值
$max_{all\ \alpha \geq 0\ ;W=\sum_{n=1}^N\alpha_ny_nz_n;\ \sum_{n=1}^N\alpha_ny_n=0}-\frac{1}{2}||\sum_{n=1}^{N}\alpha_ny_nz_n||^2+\sum_{n=1}^{N}\alpha_n$
上式可以利用SMO算法，启发式的求解 $\alpha_n$ 。
此时，如果满足KKT条件成立，那么上式的解也就是原始问题的解。

所谓KKT条件有如下几条：

$y_n\cdot (W^Tz_n+b) \geq 1$
$\alpha_n \geq 0$
$▽_b\ L(W,b,\alpha) = 0$
$▽_W\ L(W,b,\alpha) = 0$
$\alpha_n(y_n\cdot (W^Tz_n+b) -1) = 0$

支持向量

这里注意看下最后一个条件
$\alpha_n(y_n\cdot (W^Tz_n+b) -1) = 0$
如果 $\alpha_n>0$ 时，使得 $y_n\cdot (W^Tz_n+b) =1$ 这个等式恒成立，说明 $\alpha_n>0$ 的点，一定都落在最大间隔边界上面！而这些点，且只有这些点决定了SVM的最大间隔，这些点就是支持向量！吃到这些点的小鸡就是支持向量鸡！👿

至此，硬间隔SVM解完。

什么是硬间隔？就是模型强制认定数据集是线性可分的，如果线性不可分的话，模型是失效的。

WTF！费这么大劲，你跟我说然并卵？别急。。。还有软间隔呢。。。🤮

软间隔SVM

目前为止，我们处理的SVM模型有个硬性的条件是数据集为线性可分，对于非线性可分的数据集硬间隔SVM无法求解。那么有没有聪明一点的SVM模型呢？所谓软硬兼施方能治标治本，硬的不行来软的嘛。

在硬间隔模型中，将所有数据点正确分类这个条件太苛刻了，偶尔允许几个点被误分类直觉上能够提高泛化能力。

允许有误分类点就意味着，有些数据点是不满足约束条件的。我们引入一个松弛变量 $\zeta_n\geq 0$ 将约束条件修改成下面的样子，来描述这种含有误分类点的情况：
$y_n\cdot (W^Tz_n+b) \geq 1 - \zeta_n$

这个式子表示，有些数据点可以不在分界线正确的那一边，允许你有 $\zeta$ 这么多的误差。分界线也会受到 $\zeta$ 的影响，变成了这样：
$min\frac{1}{2}||W||^2+C\sum_{n=1}^N\zeta_n$
我们的首要任务是最大化间隔，但是由于存在误分类点，间隔不得不小一点，小到SVM实在看不下去了，那好吧，就让你被误分类吧。参数 $C>0$ 在其中就是平衡最大间隔跟最小误差点个数的。

现在的问题是这个样子：
$min\frac{1}{2}||W||^2+C\sum_{n=1}^N\zeta_n$
$s.t. \ \ \ \ y_n\cdot (W^Tz_n+b) \geq 1 - \zeta_n$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \zeta_n \geq 0,\ \ \ \ n = 1,2,3,\cdots ,N$
后面的工作照搬硬间隔SVM的方法，首先引入拉格朗日函数：
$L(W,b,\zeta,\alpha,\beta)\equiv \frac{1}{2}||W||^2+C\sum_{n=1}^N\zeta_n+\sum_{n=1}^N\alpha_n(1-\zeta_n-y_n(W^Tz_n+b))+\sum_{n=1}^N\beta_n(-\zeta_n)$
接下来转化为对偶问题：
$min_{W,b,\zeta}[max_{\alpha,\beta}L(W,b,\zeta,\alpha,\beta)]$

未完待续。。。

参考引用：

台湾大学林轩田《机器学习技法》课程
《统计学习方法》——李航
七月在线课程

52ML系列(2)--SVM支持向量机

从最佳分割线说起

寻找最胖的分界线

拉格朗日对偶问题(Lagrange Dual Problem)

支持向量

软间隔SVM

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

自然科普

程序员