文档章节

机器学习 -- 支持向量机SVM

大海201506
 大海201506
发布于 2017/05/17 00:05
字数 1598
阅读 69
收藏 0

1. 背景

  1. 最早是由Corinna Cortes和Vapnik等于1995年首先提出的
  2. 深度学习(2012)出现之前,SVM被认为是机器学习中近十几年来最成功,表现最好的算法

2. 机器学习的一般框架

训练集 => 提取特征向量 => 结合一定的算法(分类器:比如决策树,KNN) => 得出结果

3. 简单介绍

3.1 例子

图中有黑色和白色两类色点,很明显H1不能分开两类点,H2勉强可以,但是H3效果是最好的。margin越大,产生误差的可能性越小。

3.2 SVM的主要内容

SVM寻找区分两类的超平面(hyper plane),使边际(margin)最大,当一个新的n维点输入时根据其在超平面的哪一侧将其归为那一类。

下面介绍边际的概念:

Q1:总共可以有多少个可能的超平面?
A1:无数条

Q2:如何选取使边际(margin)最大的超平面(Max Margin Hyperplane)?
A2:超平面到一侧最近点的距离等于到另一侧最近点的距离,两侧的两个超平面平行。

Q3:为什么要选择边际最大的超平面呢
A3:是为了新的测试点输入时可以根据在超平面的哪一侧更精确地判断测试点是属于哪一类样例。

 

3. 线性可区分(linear separable)和线性不可区分(linear inseparable)

 

前面几张图的例子都是比较完美的例子,可以用一条直线来将两类样例分开,称为线性可区分,而如图的情况下就没办法直接用一条直接将两类样例分开,称为线性不可区分。后者更复杂,所以这里我们先讨论线性可区分的情况。

4. 定义与公式建立

超平面可以定义为(中间那条线):W*X + b = 0

这里W是N维的权重,W={w1,w2,.....wn}
n是特征值得个数
X是N维的训练样例,例如一个样本点的坐标是(3,8),则xT=(3,8) ,而不是x=3(一般说向量都是说列向量,因此以行向量形式来表示时,就加上转置)。
b是偏向bias

就好比二维直线的方程式y=kx+吧,这里只是扩展到N维,点的坐标是(X1,X2,X3,...,Xn),W就好比扩展到N维的斜率k。

4.1 超平面方程

假设二维特征向量:X=(x1,x2),把b想象为额外的wight(w0),超平面方程为:

W*X + b = 0   =>  向量W*向量X +w0=0  =>  (w1,w2)*(x1,x2) + w0 = 0  =>  w1*x1 + w2*x2 + w0 = 0

所有超平面右上方的点满足:w1*x1 + w2*x2 + w0 > 0

所有超平面左上方的点满足:w1*x1 + w2*x2 + w0 < 0

将两类样例的分类标记classlabel分别用值+1和-1,字母y表示,超平面两边边际的两个平行的超平面用H1和H2表示,令两侧边际线上的点代入结果=1和-1,则H1,H2外侧:
                      H1:W1*X1 + W2*X2 + b >= 1, y=+1
                      H2:W1*X1 + W2*X2 + b <= -1, y=-1
综合以上两式,得到公式(1):
                      y*(W1*X1 + W2*X2 + b) >= 1 
也就是说所有训练集的点都满足这个公式

所有坐落在边际的两边的超平面上的被称作"支持向量(support vectors)",分界的超平面和H1,H2上任意一点的距离=1/(||W||),||W||是向量的范数, (i.e:其中||W||是向量的范数(norm))。

所以,最大边际距离为:2/(||W||)

5. 求解

5.1 SVM如何找出最大边际的超平面呢(MMH)

利用一些数学推导,以上公式(1)可变为有限制的凸优化问题(convex quadratic optimization);
利用karush-Kuhn-Tucker(KKT)条件和拉格朗日公式,可以推出MMH可以被表示为以下"决定边界":

其中,yi是支持向量点Xi(support vector)的类别标记(class label),XT是要测试的实例,阿尔法i和b0是刚才一系列计算中得到的具体值,l是支持向量点的个数。

5.2 对于任何测试(要归类的)实例,代入以上公式,得出的符号是正还是负决定

6. 例子

 

如图,已知训练集(2,3),(1,1),(2,0)这三个点,(2,3)是第一类,(1,1),(2,0)是第二类,怎样进行SVM计算呢。

首先可以看出支持向量是(2,3)和(1,1),向量W =(2,3)-(1,1) = (a,2a)

根据公式两侧边际线上的点W1*X1 + W2*X2 + b = 1和-1,可以列出:

2*a + 3*2a + b =1
1*a + 1*2a + b = -1
解得 a=0.4,b=-2.2


向量W = (0.4,0.8)
g(向量x) = 0.4 * X1 + 0.8 * X2 - 2.2

通过这个方程就可以对平面中的点进行判断,凡是第一类的点也就是是分界线上方的点坐标代入,结果必然大于0,第二类的点代入结果必然小于0,这样也就建立了SVM的方程。

另外我们可以看出SVM可以解决两类实例的分类问题,但一般问题中,样例的类别往往不止两类,这时候SVM是怎么处理的呢?比如有10类的样例,怎么进行分类判断?只需要建立10个SVM方程就能得到结果。比如第一个是类别1,第二个是类别2到10的集合,这样就能建立一个SVM方程;第一个是类别2,第二个是类别1和类别3到10的集合,这样就能建立第二个SVM方程,以此类推。

最后总结一下SVM的特点:

  1. 训练好的模型的算法复杂度是由支持向量的个数决定的而不是由数据的维度决定的,所以SVM不太容易产生overfitting。
  2. SVM训练出的模型完全依赖于支持向量,即使训练集里所有非支持向量全部除去,训练出的模型也完全一样。
  3. 一个SVM如果训练得出的支持向量个数较少,SVM训练出的模型比较容易被泛化。可以适用于个多的例子,而如果支持向量过多,那么可能针对这个例子区分得比较好,但是其他情况区分得并不是很好。

 

参考:http://blog.csdn.net/ewfwewef/article/details/52824711

 

 

© 著作权归作者所有

大海201506
粉丝 5
博文 96
码字总数 173986
作品 0
广州
程序员
私信 提问
机器学习-19:MachineLN之SVM(1)

你要的答案或许都在这里:小鹏的博客目录 我想说: 其实很多事情,只要你想做,是肯定有方法做的,并且可以做好; 说起SVM很多人都会感觉头疼,无非就是公式多一个,其实很多时候你真是用的话...

u014365862
2018/01/28
0
0
机器学习基础-高质量博客收藏

SVM的理解 拉格朗日对偶 - 博客频道 - CSDN.NET(完美) SVM的三层境界 支持向量机通俗导论(理解SVM的三层境界)(后面有点乱,一般般) 【整理】深入理解拉格朗日乘子法(Lagrange Multip...

陈司空
2017/04/15
0
0
以图像分割为例浅谈支持向量机(SVM)

1. 什么是支持向量机?   在机器学习中,分类问题是一种非常常见也非常重要的问题。常见的分类方法有决策树、聚类方法、贝叶斯分类等等。举一个常见的分类的例子。如下图1所示,在平面直角坐...

lyrichu
2017/07/23
0
0
用Python实现一个SVM分类器策略

支持向量机(SVM)是什么意思? 正好最近自己学习机器学习,看到reddit上 Please explain Support Vector Machines (SVM) like I am a 5 year old 的帖子,一个字赞!于是整理一下和大家分享。...

酒逢知己千杯少
2018/12/28
50
0
机器学习(15)之支持向量机原理(一)线性支持向量机

前言 支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢压制了神经网络领域好多年。如果不考虑集成...

技术小能手
2018/06/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

3_数组

3_数组

行者终成事
今天
7
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0
OpenJDK之CyclicBarrier

OpenJDK8,本人看的是openJDK。以前就看过,只是经常忘记,所以记录下 图1 CyclicBarrier是Doug Lea在JDK1.5中引入的,作用就不详细描述了,主要有如下俩个方法使用: await()方法,如果当前线...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部