机器学习基石--学习笔记01--linear hard SVM

  1. 云栖社区>
  2. 博客>
  3. 正文

机器学习基石--学习笔记01--linear hard SVM

吞吞吐吐的 2017-09-12 14:33:00 浏览607
展开阅读全文

背景

支持向量机(SVM)背后的数学知识比较复杂,之前尝试过在网上搜索一些资料自学,但是效果不佳。所以,在我的数据挖掘工具箱中,一直不会使用SVM这个利器。最近,台大林轩田老师在Coursera上的机器学习技法课程上有很详细的讲授SVM的原理,所以机会难得,一定要好好把握这次机会,将SVM背后的原理梳理清楚并记录下来。这篇文章总结第一讲linear hard SVM的相关内容。

   

最好的分割线

之前有讲过PLA,即在线性可分的数据中,找到一条线,能够区分开正负样本,如下所示:

上面三条线,都是PLA的解,但是哪条才是最好的呢?凭直觉而言,最右边是最好的,因为右边第三条对噪声的容忍度最高。

上图中灰色区域是噪声,区域越大,噪声越大。可以发现,最右边可以容忍的噪声是最大。现在是以点的视角来观察,下面以线的视角观察,

同样的,最右边的线扩展后得到的"垫子"最厚。"垫子"的厚度通常叫做margin(边缘)。垫子扩展到最近的正负样本就停止扩展,这些在垫子边缘上的正负样本叫做支持向量(每个样本就是一个向量)。

   

问题来了

知道了支持向量机的定义和优点后,那么问题来了,我们要解一个什么问题?

形式化的问题定义如下

如果符合上面条件的w(平面法向量)和b(平面截距)存在,由于平面公式可以伸缩(即wTx+b=0与3wTx+3b=0表示同一个平面),所以总可以找到一组w*和b*,使得min y(w*x+b*) = 1,那么有

经过上面的平面缩放变化,问题可以简化为如下形式

是不是看起来简单多了。

   

二次规划

为了进一步简化计算,将目标函数经过一番变化,可以得到如下利于优化的形式

这个问题形式和二次规划(线性规划的亲戚,)一致,所以可以使用二次规划的方法求解。二次规划的一般形式如下:

将linear hard SVM的求解公司套用QP一般形式,接下来就可以通过任何实现QP解法的工具计算求解,这里略去具体的变量映射关系,有兴趣的读者可以尝试。对于非线性问题,可以通过对x做二次转化或其他转化,然后求解。

   

VC维度

相比较PLA的平面,linear hard SVM得到的平面结果更苛刻,

由于有"厚垫子",linear hard SVM不能shatter任意3个inputs,这说明有更少的dichotomies,更小的VC维度,也就有更好的泛化效果。同时,如果使用特征转换,可以使linear hard SVM进行一些更精细的分类。

   

总结

Linear hard SVM的解法中需要训练数据线性可分,然后通过缩放平面和等价转换,将原始问题转成QP问题求解。数据线性可分在实际情况中很难出现,所以linear hard SVM的应用价值比较有限。同时,在特征转换时,将原始数据映射到其他空间的计算无法省略(好像是废话)。接下来课程中,会使用一些更有趣的方法解决这两个问题,敬请期待。

声明:如有转载本博文章,请注明出处。您的支持是我的动力!文章部分内容来自互联网,本人不负任何法律责任。

本文转自bourneli博客园博客,原文链接:http://www.cnblogs.com/bourneli/p/4198839.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
吞吞吐吐的
+ 关注