SVM原理及推导

正文共2249个字,22张图,预计阅读时间15分钟。

对于二类分类问题,训练集T={(${ x }{ 1 }$,${ y }{ 1 }$),(${ x }{ 2 }$,${ y }{ 2 }$),...,(${ x }{ n }$,${ y }{ n }$)},其类别${ y }_{ n }\in ${-1,1},线性SVM通过学习得到分离超平面:

$$ w\bullet x+b=0 $$ 以及相应的分类决策函数: $$f\left( x \right) =sign(w\bullet x+b)$$

有如下图所示的分离超平面,哪一个超平面的分类效果更好呢?

Margin

直观上,超平面B1的分类效果更好一些。将距离分离超平面最近的两个不同类别的样本点称为支持向量(support vector)的,构成了两条平行于分离超平面的长带,二者之间的距离称之为margin。显然,margin更大,则分类正确的确信度更高(与超平面的距离表示分类的确信度,距离越远则分类正确的确信度越高)。

直线距离可知

所以 $$Margin=\frac { 2 }{ \parallel w\parallel } $$

目标函数

约束条件

对于所有点,还要求分类正确,即: $$w\bullet x+b\ge 1\quad \quad \quad if\quad { y }{ i }=+1$$$$ w\bullet x+b\ge -1\quad \quad \quad if\quad { y }{ i }=-1$$$${ y }_{ i }(w\bullet x+b)-1\ge 0$$

最大化Margin

$$\max { M } =\frac { 2 }{ \parallel w\parallel } \Rightarrow \min { \frac { 1 }{ 2 } { w }^{ T }w } $$

最优化问题

  • Minimize $\Phi (w)=\frac { 1 }{ 2 } { w }^{ T }w$
  • Subject to ${ y }_{ i }(w\bullet x+b)-1\ge 0$

引入拉格朗日乘子法了,优化的目标变为:

求导:

带入拉格朗日函数,对偶问题转为

等价于最优化问题:

(1)求得${ \alpha }^{ * }={ ({ \alpha }{ 1 }^{ * },{ \alpha }{ 2 }^{ * },...,{ \alpha }{ N }^{ * }) }^{ T }$

(2)计算 ${ \omega }^{ * }=\sum { i=1 }^{ N }{ { \alpha }{ i }^{ * } } { y }{ i }{ x }{ I }$ 并选择${ \alpha }{ * }$的一个正分量 ${ \alpha }_{ j }^{ * }$>0,计算

(3)求得分离超平面 ${ \omega }^{ * }\bullet x+b=0$

分类决策函数:

$$f\left( x \right) =sign({ \omega }^{ * }\bullet x+b)$$ 在线性可分SVM中,${ \omega }^{ * }$和${ b }^{ * }$只依赖于训练数据中对应于${ \alpha }{ i }^{ * }$>0的样本点$({ x }{ i },{ y }{ i })$,其他样本点对${ \omega }^{ * }$和${ b }^{ * }$没有影响。我们将训练数据中对应${ \alpha }{ i }^{ * }$>0的样本点称为支持向量。

Example

Soft Margin

求解

Non-linear SVMs

利用高维空间,数据更好的可分(优点),又避免了高维空间计算复杂(缺点)

1、Linear核:主要用于线性可分的情形。参数少,速度快,对于一般数据,分类效果已经很理想了。

2、RBF核:主要用于线性不可分的情形。参数多,分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数,不过这个过程比较耗时。个人体会是:使用libsvm,默认参数,RBF核比Linear核效果稍差。通过进行大量参数的尝试,一般能找到比linear核更好的效果。

3、多项式核函函数

4、字符串核函数

序列最小最优化算法SMO

上面这个优化式子比较复杂,里面有m个变量组成的向量α需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量,将其他的变量都视为常数。由于:

假如将

固定。那么a1,a2的之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。

为了后面表示方便,我们定义

由于

成了常量,所有的常量我们都从目标函数去除,这样我们上一节的目标优化函数变成下式:

原文链接:https://www.jianshu.com/p/e7e308584b20

本文分享自微信公众号 - 人工智能LeadAI(atleadai)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-08

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 机器学习面试之有必要手推SVM吗?

    01 单刀直入,先回答有必要吗? 最近和许多朋友交流,发现当前机器学习应聘时,手推SVM这道题已经越来越像快速排序一样,成为必点菜了。 那么,手推SVM是不是必...

    用户1332428
  • 二、机器学习面试之有必要手推SVM吗?

    上篇文章中,我们介绍了SVM的基本思想,并将其推导成了一个数学问题,今天的任务,就是解决如何求解这个数学问题,同时,回答上篇文章中提出的第二个问题: 如果将正负...

    用户1332428
  • 配置深度学习主机与环境(TensorFlow+1080Ti) | 第二章 Win10&Ubuntu双系统与显卡驱动安装

    网上安装双系统的教程不少,但多数教程所使用的硬件以现在的眼光看来显得有些过时;另外,其原有所使用的方法,对于新的硬件也不再合适。本教程写于2017年7月,希望能...

    用户1332428
  • 机器学习算法中的向量机算法(Python代码)

    掌握机器学习算法并不是一个不可能完成的事情。大多数的初学者都是从学习回归开始的。是因为回归易于学习和使用,但这能够解决我们全部的问题吗?当然不行!因为,你要学习...

    商业新知
  • 机器学习(三)—支持向量机(1)

      本文对支持向量机做了简单介绍,并对线性可分支持向量分类机、线性支持向量分类机以及核函数做了详细介绍。

    oYabea
  • Peter教你谈情说AI | 10支持向量机(1)—SVM原型

    “谈情说AI” 有段日子没有更新了,今天我们挽起袖子继续新的一节。从今天起我们的学习之旅进入了新的阶段,之所以说是新的阶段,是因为之前讲的几个模型:线性回归、朴...

    刘盼
  • 支持向量机原理讲解(一)

    磐创AI
  • 机器学习,你不得不掌握的十大算法(中)

    这是小詹关于机器学习的第③篇文章 导读:通过本篇文章可以对ML的常用算法有个常识性的认识,没有代码,没有复杂的理论推导,就是图解一下,知道这些算法是什么,它们是...

    小小詹同学
  • 趣文 | 程序员们,都进来看看编程语言之父都有谁

    1、PHP PHP之父,Rasmus Lerdorf,1994年,为了要维护个人网页而制作的一个简单的用Perl语言编写的程序。这些工具程序用来显示 Rasmu...

    小莹莹
  • Activation

    刘笑江

扫码关注云+社区

领取腾讯云代金券