支持向量机

Udacity Machine Learning Support Vector Machine


在做分类问题时,想要找到最好的那条线:

会选择中间的那条线,为什么没有选择平行的另外两条线,因为它们属于 Overfitting ,过度相信了 training data,

那要怎么样找到这条线呢:

注意此时的 y 是分类用的 label,要么是 +1,要么是 -1 。

需要思考一个问题是,在沿着这条线上的点,它们的 Label 是什么呢?是0。

所以这个 Boundary Line 会有3个可能值,同时想要两条灰色线之间的距离最大。

那么怎么计算这条线的距离呢

可以在两条灰色线各取一个点,然后计算它们之间的距离,也就是在 +1 和 -1 的两条线上取点。

x1-x2 和这条线的方向是一样的,我们想要这条线达到最大,那就需要 norm(W) 越小,等式左边的部分叫做 Margin。

所以我们的目标就是,找到一个 Decision Boundary 来最大化 Margin。

这样就可以很好地分类。而这个问题就转化到了等式右边,也就是要最大化 2/norm(W),并且可以正确地分类 。 把这个问题转化为数学问题是:

而最大化 2/norm(W) 这个问题,可以进一步转化为更简单的问题,这是个 Quadratic Programming Problem:

进一步还等价于下面这个问题:

关于上面这个问题,有一些特质: 1.如果知道了 alpha,就可以得到 w,知道了 w,就可以知道 b

2.通常情况下,大多数 alpha=0,意味着这些点对w没有影响 也就是说,为了找到这个解,有些 vector 是没有贡献的,你只需要从少数的 vector 就可以获得找到最优 W 的 support。

即,构建一个 machine,只包含这些 support vector,即这些非零的 alpha 相应的点。

直观上看,0-alpha 就是离 Decision Boundary 比较远的那些点,它们很难对这条线做贡献。

有点像 KNN,因为只有 local points 起作用,但是前提是你已经知道哪些 points matter。 求解这个问题,其实是在找到底哪些点可以 throw away。

Xi transpose Xj,意义是,一个向量在另一个向量的投影,如果垂直则为0,如果方向相同,则为正,如果相反,则为负,所以这是一个 similarity 的表示。

有时并不能完全地分出两类,但是可以让误差最小。


对于下面这个数据,我们想得到一个 circle

一类在圈内,一类在圈外,用 phi 这个三维的函数就可以分开,而不需要事先知道谁是正是负。但是却不需要用 phi,因为它可以用 (X‘T)^2 来表示。

公式里的 Xi'Xj 可以用 kernel 来表示,来衡量 Similarity

意义就是 向更高维度的空间投影,在高维空间里就可以被 linearly seperated。

下面这几种形式都可以作为 kernel。 第三个是多项式。 第四个是 radial basis kernel,如果 x和y 很近,那么 k 就趋近于 1,如果 x和y 很远,那么 k 就趋近于 0,而且加上平方之后,这个还是对称的。 第五个更像是 sigmoid。 kernel function 可以有很多,而且它的应用也很广,可以用于 string 和 figure。 这些都属于 Mercer Condition,是一种用距离去衡量的方法,而不是随意地构造。


总结:

1.Margin 很重要,它关系着 Generalization 还是 Overfitting 2.目标是 Margin 的最大化 3.Margin 最大化的方法:Quadratic Problem 4.在QP中知道了什么是 Support Vector,只需要一个子集就可以建立 Classifier 5.Kernel Trick:通过向高维空间投影,把低维的非线性 Boundary 转化为高维空间的线性 classifier。

另外关于SVM,July有一篇非常详细的博文: http://blog.csdn.net/v_july_v/article/details/7624837

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

良心GitHub项目:各种机器学习任务的顶级结果(论文)汇总

417110
来自专栏AI科技评论

开发 | 为什么ResNet和DenseNet可以这么深?一文详解残差块为何有助于解决梯度弥散问题。

AI科技评论按:本文作者Professor ho,原文载于其知乎主页,雷锋网获其授权发布。 传统的“提拉米苏”式卷积神经网络模型,都以层叠卷积层的方式提高网络深...

46450
来自专栏杨熹的专栏

用 TensorFlow 让你的机器人唱首原创给你听

Siraj 的视频 源码 今天想来看看 AI 是怎样作曲的。 本文会用 TensorFlow 来写一个音乐生成器。 当你对一个机器人说:我想要一种能够表达出希...

35560
来自专栏新智元

计算机视觉中,目前有哪些经典的目标跟踪算法?

【新智元导读】这篇文章将非常详细地介绍计算机视觉领域中的目标跟踪,尤其是相关滤波类方法,分享一些作者认为比较好的算法。 相信很多来这里的人和我第一次到这里一样,...

920100
来自专栏数据派THU

各类机器学习问题的最优结果合集!附论文及实现地址索引

来源:中国大数据 本文为你介绍RedditSota 统计的各种机器学习任务的最顶级研究成果(论文)。 该 GitHub 库提供了所有机器学习问题的当前最优结果,...

40360
来自专栏目标检测和深度学习

深度学习之基础网络演进、分类与定位的权衡|牛喀技研

深度学习,目标检测,图像,智能驾驶 编译:牛喀网-钱伟 前言 本篇关注基础网络架构的演进和处理分类、定位这一矛盾问题上的进展。 基础网络结构的演进 基础网络(...

89570
来自专栏目标检测和深度学习

目标检测入门(四):特征复用、实时性

文章结构 本文的第一部分关注检测模型的头部部分。对与每张图片,深度网络其实是通过级联的映射获得了在某一流形上的一个表征,这个表征相比原图片更有计算机视角下的语义...

42470
来自专栏IT派

干货|如何做准确率达98%的交通标志识别系统?

摘要: 我们可以创建一个能够对交通标志进行分类的模型,并且让模型自己学习识别这些交通标志中最关键的特征。在这篇文章中,我将演示如何创建一个深度学习架构,这个架构...

39760
来自专栏人工智能头条

计算机视觉中,目前有哪些经典的目标跟踪算法?

86760
来自专栏人工智能LeadAI

为什么ResNet和DenseNet可以这么深? | 一文详解残差块为何能解决梯度弥散问题

传统的“提拉米苏”式卷积神经网络模型,都以层叠卷积层的方式提高网络深度,从而提高识别精度。但层叠过多的卷积层会出现一个问题,就是梯度弥散(Vanishing),...

37370

扫码关注云+社区

领取腾讯云代金券