support vector machine 是一个适用于中小型数据集的强大算法, 可惜深度学习崛起后淡去了昔日的光辉...
但是 SVM 依旧是一个不可忽视的机器学习算法, 让我们来领略 SVM 的魅力吧
从最佳分割线说起
假设用一条线切开数据, 将其分为两类, 如图 1 所示, 你会如何切分呢?
图 1
图中第三列分法, 数据点离分割线最远, 直觉上来说感觉这种分法较好. 为什么呢? 就是直觉...
ok,SVM 来告诉你为什么.
寻找最胖的分界线
其实很简单, 从鲁棒性的角度来说, 第三列的分法使得两类已有的数据离分界线最远, 那么新增的数据点被误分类的概率就会第一点.
分界线越胖, 鲁棒性越好, 模型泛化能力也就越好, 因此我们的目标是 -- 没有蛀牙!
那么如何寻找最胖的分界线 (学术术语: 超平面) 呢? 我们用距离公式:
其中 就是超平面, 那么现在的目标就是求得使距离最大化的 和.
等等, 貌似还有个条件没考虑到, 我们还要保证所有的点被正确划分呢! 如何满足这个条件呢? 试想所有被划分到正类的点应该被标注为, 而负类则被标注为, 那么被正确分类的点距超平面的距离应该与其标签同号. 数学表示为:
ok, 现在的任务变成了这样:
为了方便计算, 我们令最小的函数间隔.
tips:表示的是函数距离, 并不影响 的求解. 因为把函数距离扩大 倍, 那 也会等比例扩大 倍.
so, 现在的任务又稍变了一点样子:
接下来把最大化问题转变为最小化问题, 目前任务的最终形态长这样:
tips: 最大化 与最小化 问题是等价的,与平方的引入只是为了方便后面计算求导...
任务的最终形态是一个凸二次规划问题(convex quadratic programming), 很多统计学的工具软件都带有求解二次规划问题的功能. 利用工具的便利性, 可以求出最好的, 故而得到了最胖的分界线.
但是求解二次规划问题涉及到 的维度, 若 很大, 求解二次规划的计算量将变得巨大! 如何解决这一问题呢?
答案就是对着 SVM 呕一呕
拉格朗日对偶问题(Lagrange Dual Problem)
为什么要引入拉格朗日对偶问题? 一方面如前文所述, 对于巨大维度的数据, 二次规划难以求解; 另一方面在于, 我们的模型是解一个带不等式条件的最优化问题, 而拉格朗日对偶算法恰好就是干这个活的; 最后一点在于, 可以引入核函数... 核武器... 原子弹...
我们先来看看如何构建拉格朗日函数.
其实很简单, 还记得我们的目标函数跟条件函数吗? 把目标函数跟条件函数写成一个式子, 当然条件函数需要乘以一个拉格朗日乘子
(Lagrange multiplier), 写法如下:
我们要让 最小, 同时又要保证 成立, 于是问题转化成这样:
怎么一下最大一下最小, 真是莫名其妙...
我们这样来看这个式子:
条件函数也可以认为是对 SVM 模型能够正确分类数据的一种约束对不对?则是这个约束的权重, 这样就存在一种约束的临界点:
如果某个分类点 没有被正确分类, 那么这个模型违背了正确分类所有点的初衷
注意 , 错误分类时会大于零. 考虑到 是恒正的, 而 也是非负的, 这时 会机智的将整个式子变成正无穷, 你还想求最小值? 我强制让你无解!╭(╯^╰)╮
如果是正确分类的点呢?说, 好吧, 你乖我就不欺负你. 于是 又机智的让 等于 0, 这样整个式子就是.
ok, 这就是拉格朗日算法的精髓, 如果你都弄清楚了说明你已经掌握 SVM 了! 吗?
好吧, 还没有... 实际上我们还没有说对偶呢. 上面的式子是个最大值问题, 并不好求解, 于是对偶问题粉墨登场.
这就是对偶问题, 神奇的把求最大最小值的操作互换了位置. 更神奇的是, 由于 SVM 模型恰好符合某些条件, 对偶问题与原始问题之间竟然可以取等号了. 感兴趣的同学可以自行脑补其中的奥妙.
有了对偶问题, 任务转化为了求最小值:
于是我们就可以开心的求偏导了.
求解
对 b 求偏导并令其为零
对 W 求偏导并令其为零
得到:
带入到 中, 得到 最终形态:
求 对的最大值
利用 SMO 算法, 启发式的求解.
此时, 如果满足 KKT 条件成立, 那么上式的解也就是原始问题的解.
所谓 KKT 条件有如下几条:
支持向量
这里注意看下最后一个条件
如果 这个等式成立, 说明
至此, 硬间隔 SVM 解完.
我屮... 什么是硬间隔? 就是模型强制认定数据集是线性可分的, 如果线性不可分的话... 就嗝屁了.
WTF! 费这么大劲, 你跟我说然并卵? 别急... 还有软间隔呢...
软间隔 SVM
未完待续...
参考引用:
台湾大学林轩田《机器学习基石》课程
《统计学习方法》-- 李航
来源: http://www.jianshu.com/p/de1ac0ccaec2