Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >深入理解SVM

深入理解SVM

作者头像
小小杨
发布于 2021-10-13 02:07:16
发布于 2021-10-13 02:07:16
6920
举报
文章被收录于专栏:下落木下落木

支持向量机(苏联Vapnik发明)问题

  1. 如何在线性可分样本集上画一条直线将其分开(找到最好的直线)。
  2. 如何将非线性可分样本集分开。

线性可分样本集就是一条直线能分开的集合,二者有明显界限。

  • 首先要找到一个性能指标,然后根据这个性能指标指出某一条线比其他线指标高。
  • 将一条线平行地向一侧移动,直到叉到某一个样本为止,然后平行地向另一侧移动,也是叉到某一个样本为止。这个性能指标就是两条平行线的距离。这个距离最大的一条线就是最佳的。同时两条平行线的最中间是唯一的。
  • 将平行线间的距离称为d(margin),支持向量机是最大化平行线距离d(margin)的方法。
  • 将平行线叉到的向量称为支持向量,画出这条线的方法只跟支持向量有关系,跟其他向量没关系,这也是为什么支持向量能够用在小样本集上。
  1. 定义训练数据和标签:(X1,y1)、(X2, y2)...(Xn, yn),其中X = [x1, x2 ..],是多维向量,y是+1或-1的标签。
  2. 线性模型 (W, b) WTX+ b = 0,描述超平面的线性方程。W是一个向量,如果X是n维的,那么W也是n维的。b是一个常数。WTX 一个列向量转置然后乘以一个行向量,也是一个数。
  3. 线性可分的定义。存在(W,b),使yi =+1时,WTX+ b>=0;yi =-1时,WTX+ b<0。即yi[WTXi+ b] >=0(公式一)

机器学习的过程:

  1. 确定一个方程;
  2. 确定一些要求取的参数,比如这里的W和B;
  3. 训练模型,求出参数

优化问题(凸优化问题、二次规划问题)

1.最小化minimize:||W||2, 即W模的平方。

2.限制条件Subject to:yi[WTXi+ b] >=1,其中i=1~N

如何从最大化margin转化到上面的两个问题?

事实1. WTX+ b = 0与 aWTX+ ab = 0是同一个平面,其中a是一个正实数。也就是若(W, b)满足公式一,那么(aW, ab)也满足公式一,a是负数的话符号就相反了。 事实2. 点(x0, y0)到平面(w1x + w2y +b = 0)的最短距离:d= |w1x0 + w2y0 +b| / √(w12 + w22) 那么高维上,向量X0到超平面WTX+ b = 0的距离,就是:|WTX0+ b|/ || W ||,其中分母W的模就是√(w12 + w22 + w32 ...)

我们可以用a缩放(W,b)得到(aW, ab),最终使所有支持向量X0上,有|WTX0+ b| = 1,那么非支持向量上,|WTX0+ b| >1,从而得证限制条件

此时支持向量与平面的距离d = 1/|| W ||,从而最小化|| W ||可以使d最大,得证最小化条件

注意:

  1. 限制条件最后的1可以是2、3、4...等任意整数,它们的区别只是一个常数a。
  2. 只要线性可分,一定存在W和b,反之如果线性不可分,找不到W和b满足限制条件

二次规划问题:目标函数是二次项,限制条件是一次项。要么无解,要么只有一个极值。

支持向量机效果好,是因为数学理论漂亮,漂亮在转化为了一个凸优化问题,这类问题在全局上有一个最优解。

SVM处理非线性问题

优化问题:

最小化 ||W||2/2 + C∑εi,

限制条件

1. yi[WTXi+ b] >=1 - εi,

2. εi >= 0 ,其中i=1~N

理解:有上面知道非线性情况下,找不到满足yi[WTXi+ b] >=1的(W,b),因此,放宽条件,当εi很大的时候,1-εi很小,就能满足限制条件,同时又不能让εi很大,否则问题会很发散,所以把它又放在最小化里面。εi称为松弛变量,slack variable.

所以,已知条件有Xi、Yi,即训练样本,要求的有W、b、εi

  • C∑εi被称为正则项,regulation term,C的作用是平衡每一项εi,使它们都不要太大。
  • C是事先设定的参数,起到平衡前后两项的作用。通常没有固定的值,一般根据经验在某个范围内去一个个试。

为什么要加正则项?

  1. 以前没有解,要使其有解,就需要加正则项。
  2. 目标函数有解,但其解并不想要的,比如目标函数凹凸不平,也需要加正则项。

低维到高维映射φ(x)

问题:之前的解都是求解直线,但如果最优解其实是圆形怎么办?比如一堆1包围了0。

vapnik一个创意的想法是,不在低维的空间找圆形、椭圆等其他形状,而是在高维的空间还是找直线。x => φ(x)

举例:x1(0, 0)和x2(1,1)属于第一类,x3(1, 0)和x4(0, 1)属于第二类。一个映射方案是[a,b] =>[a2, b2, a, b, ab]

那么x1: [0, 0] => [0, 0, 0, 0, 0], x2: [1, 1] => [1, 1, 1, 1, 1],x3: [1, 0] => [1, 0, 1, 0, 0] , x4: [0, 1]=>[0, 1, 0, 1, 0]。(转置)

如何求解W和b?一个解是:W = [-1,-1,-1,-1, 6],b=1

维度越高,被线性分开的可能性越高,如果是无限维,被线性分开的概率为1。

SVM精髓:

我们可以不知道无限维映射φ(x)的显式表达,我们只要知道一个核函数kernal function,K(x1, x2) = φ(x1)Tφ(x2),那么 ||W||2/2 + C∑εi这个优化式仍然可解。

φ(x1)Tφ(x2)是两个无限维向量的内积,就是一个数,也就是不需要φ(x)的具体表达式,只要知道核函数就行了。

常见的核函数:

1. 高斯核 K(x1, x2) = e^-(||x1-x2||2/2σ2)

2. 多项式核函数 K(x1, x2) = (x1Tx2 + 1)d,其中d是多项式的阶数,由于d有限,所以φ(x)是有限维

K(x1, x2) 能写成 φ(x1)Tφ(x2)的充要条件是(Mercer's Theorem):

1. 满足交换律 K(x1, x2) = K(x2, x1)

2. 半正定性,对于所有的Ci和Xi, 有∑i∑jCiCjK(Xi, Yi) >= 0。其中Ci是常数,Xi是向量。

原问题与对偶问题

原问题Prime Problem:

1. 最小化f(ω)

2. 限制条件

① gi(ω) <=0,其中i =1~K;

②hi(ω) = 0,其中1 = 1~M

原问题非常普适,最小化可以转为最大化问题,限制条件大于等于可以转为小于等于,后面的h(ω) = 0可以转为h(ω) -C= 0

对偶问题Dual Problem:

先定义函数:

L(ω, α, β) = f(ω) + ∑iαigi(ω) + ∑iβihi(ω) = f(ω) + αTg(ω) + βTh(ω)。其中后面的形式是向量的形式

对偶问题定义:

1. 最大化 θ(α, β) = inf所有ω( L(ω, α, β) ),

2. αi >=0,其中i=1~K

inf指求括号内的最小值,即在限定了α,和β,去遍历所有的ω,求L的最小值。所以每确定一个α,和β,都能算出一个最小值,θ(α, β)只和α, β有关。然后再针对所有的α, β,再求θ的最大值。里面求最小,外面求最大。

定义:G = f(ω*) - θ(α*, β*) >=0,G叫做原问题与对偶问题的间距(Duality Gap)。对于某些特定的优化问题,可以证明G等于0。

强对偶定理:若f(ω)为凸函数, g(ω) = aω+b,h(ω)=cω+d,则此优化问题的原问题与对偶问题间距为0。即f(ω*) = θ(α*, β*) => 对于所有的i=1-K,α*i = 0 或者gi(ω*) = 0

凸函数

凸函数:如果在函数图像上任取两点,函数图像在这两点之间的部分都在两点线段的下边,那么就成为凸函数,否则称为凹函数。凸函数只有一个极小值,比如x2,而sinx有多个极值。

对于任意(0,1)中有理数λ,有

如果f连续,那么λ可以改变成区间(0,1)中的任意实数。

几何意义只是一维的,而代数的定义可以是向量,即任意维。

将支持向量机的原问题转为对偶问题

注意转化后的对偶问题中的βi和αi对应着原来对偶问题的一个αi,因为gi(ω) <=0,而支持向量机的不等式的限制条件有两个,所以都写上了。

对向量求偏导,就是对其每个分量求偏导。

WTW,蹦出来个αj,只是个符号,因为写αi不合适了

对于上面的推倒后的式子,已知的是所有的y,和kernal函数,未知的是所有的α。怎么把求α转化为求W和b?根据上面W的公式就可以。

KKT条件对应到SVM上:

SVM算法流程分为训练流程和测试流程,训练时,先求出所有的α,再算b

可见所有的φ(x)都转成了kernel函数

核函数

线性核等于没用,解原问题和解对偶问题的复杂度一样。多项式核函数d是几维,就对应到几维。高斯核是低维映射到高维。

每个核函数都要调参数,多项式核函数要调的参数是d,高斯核要调的是方差。

SVM训练时的一个经验是,必须归一化,一般用高斯归一化,即减掉均值,然后除以平均值,而不是最小最大归一化。

SVM用高斯核的话,只有两个参数要调,一个是C平衡前面的W和后面的εi,另一个是高斯核中的方差。

C范围:2-5~215,方差范围:2-15~23,组合有21*19种

交叉验证的好处:

  • 不使用训练样本进行测试,因为无法验出真实水平。
  • 尽可能地充分利用训练样本,比如只有5000个样本,分成abcde五组,每次取出4份进行训练,另一份进行测试,保证每一次训练时,样本足够的多。

折数越多,训练模型越多,10折就是10个模型,5折就是训练5次。5000个样本,最多5000折,每次取4999个进行训练,1个进行测试。这种称为leave-one-out cross validation

支持向量20%左右正常,如果特别多,说明没有训练好,或者数据本身就没有规律。

ROC曲线

为什么同一个系统中TP增加,FP也增加?小平同志说,改革开放了,好的东西进来了,蚊子苍蝇也进来了。因为自身性能不变,把更多的正例识别称正例,那么一定也会将更多的反例识别为正例。同理FN增加=>TN增加。

ROC (Receiver Operating Character)曲线, 是一条横坐标FP,纵坐标TP的曲线。

给定一个模型,怎么画出ROC曲线?从小到大变换下面的阈值,每次变换一个阈值,测出TP和FP。FP等于0时,表示把所有的样本判为负例,此时TP也为0,FP等于1表示把所有的样本判为正例。

等错误率 (Equal Error Rate, EER)是两类错误FP和FN相等时候的错误率,可以直观的表示系统性能。

对于不同的应用,判别模型好坏的标准不同。对于人脸开锁的应用而言,容忍错误低,即要FP最小,或者是0情况下,FP的最大值。

ROC下的面积称为AUC,面积越大,一般性能越好。

可以用ROC曲线、EER、AUC,但不要单纯用识别率来判断,识别率高不代表性能就好(这是机器学习领域懂和不懂的人的一个区别)。

SVM处理多类问题

  1. 改造优化的目标函数和限制条件,使之能处理多类。论文 SVM-Multiclass Multi-class Support Vector Machine
  2. 一类 VS 其他类
  3. 一类 VS 另一类

一类 VS 其他类:

如果一个样本被判为C1或C2,那就看哪一个负的多,因为y=-1,说明...是负的,看更偏向于谁。

一类 VS 另一类:

根据经验,改造公式的方法并不好用,因为SVM适合在两类中寻找最大间隔。

如果有N类,一类VS其他类的方法要做N个SVM模型,一类VS另一类要做(N*(N-1))/2个SVM模型。根据经验,后者更佳。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 下落木 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
机器学习之深入理解SVM
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/54984251
大黄大黄大黄
2018/09/14
6710
机器学习之深入理解SVM
【ML】支持向量机(SVM)从入门到放弃再到掌握
朋友,你通过各种不同的途经初次接触支持向量机(SVM)的时候,是不是会觉得这个东西耳熟能详,感觉大家都会,却唯独自己很难理解? 每一次你的老板或者同仁让你讲解SVM的时候,你觉得你看过这么多资料,使用过这么多次,讲解应该没有问题,但偏偏在分享的时候结结巴巴,漏洞百出? 每一次机器学习相关的面试在问到支持向量机(SVM)的时候,尽管你觉得你都准备好了,可是一次又一次败下阵来,以至于觉得问那些问题的人(是不是脑子有…)是那么的厉害,每一次都能精准发觉到你的不足和漏洞,让你怀疑你掌握的是假的SVM,然后让你怀疑人生? 那还等什么,快来看看这篇文章吧,原价998,现在只要。。。(不好意思,扯偏了。)
全栈程序员站长
2022/09/06
5700
【ML】支持向量机(SVM)从入门到放弃再到掌握
我是这样理解--SVM,不需要繁杂公式的那种!(附代码)
支持向量机(Support Vector Machine,SVM)是众多监督学习方法中十分出色的一种,几乎所有讲述经典机器学习方法的教材都会介绍。关于SVM,流传着一个关于天使与魔鬼的故事。
mantch
2019/07/30
1.1K0
我是这样理解--SVM,不需要繁杂公式的那种!(附代码)
【原创】支持向量机原理(一) 线性支持向量机
支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法,不考虑特定的训练数据集,在分类算法中的表现SVM说是排第一估计是没有什么异议的。
lujohn3li
2020/03/05
1K0
【原创】支持向量机原理(一) 线性支持向量机
SVM 概述
支持向量机的线性分类:是给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于他们落在间隔的哪一侧来预测所属类别。
为为为什么
2022/10/28
1.3K0
SVM 概述
【原创】支持向量机原理(二) 线性支持向量机的软间隔最大化模型-3.5
很多人第一次听说 SVM 时都觉得它是个非常厉害的东西,但其实 SVM 本身“只是”一个线性模型。
lujohn3li
2020/03/06
9400
【原创】支持向量机原理(二) 线性支持向量机的软间隔最大化模型-3.5
支持向量机(SVM) (2)
在上一次的介绍中,我们稍微了解到了关于support vector machine 的一些入门知识。今天,我们将真正进入支持向量机的算法之中,大体的框架如下: 1、最大间隔分类器 2、线性可分的情况(详细) 3、原始问题到对偶问题的转化 4、序列最小最优化算法 1、最大间隔分类器 函数间隔和几何间隔相差一个∥w∥ 的缩放因子(感觉忘记的可以看一下上一篇文章)。按照前面的分析,对一个数据点进行分类,当它的间隔越大的候,分类正确的把握越大。对于一个包含n 个点的数据集,我们可以很自然地定义它的间
昱良
2018/04/04
8690
支持向量机(SVM) (2)
手把手教你实现SVM算法
什么是机器学习 (Machine Learning) 机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域。 机器学习的大致分类: 1)分类(模式识别):要求系统依据已知的分类知识对输入的未知模式(该模式的描述)作分析,以确定输入模式的类属,例如手写识别(识别是不是这个数)。 2)问题求解:要求对于给定的目标状态,寻找一个将当前状态转换为目标状态的动作序列。 S
机器学习AI算法工程
2018/03/12
1.8K0
手把手教你实现SVM算法
支持向量机(SVM)的分析及python实现「建议收藏」
(本文所有代码都是基于python3.6的,数据及源码下载:传送门 ##引言 今天我们算是要来分享一个“高级”的机器学习算法了——SVM。大家自学机器学习一般都会看斯坦福的CS229讲义,初学者们大都从回归开始步入机器学习的大门。诚然回归学习起来与使用起来都很简单,但是这能达到我们的目的么?肯定不够的,要知道,我们可以做的不仅仅是回归。如果我们把机器学习算法看作是一种带斧子,剑,刀,弓,匕首等的武器,你有各种各样的工具,但你应该学会在正确的时间使用它们。打个比方,我们通常认为“回归”是一种能够有效地切割和切割数据的剑,但它不能处理高度复杂的数据。相反,“支持向量机”就像一把锋利的刀——它适用于更小的数据集(因为在大数据集上,由于SVM的优化算法问题,它的训练复杂度会很高),但它在构建模型时更加强大和有效。 ##什么是支持向量机 “支持向量机”(SVM)是一种监督机器学习算法,可用于分类或回归挑战。然而,它主要用于分类问题。在这个算法中,我们将每一个数据项作为一个点在n维空间中(其中n是你拥有的特征数)作为一个点,每一个特征值都是一个特定坐标的值。然后,我们通过查找区分这两个类的超平面来进行分类。如下图所示:
全栈程序员站长
2022/09/06
1.4K0
支持向量机(SVM)的分析及python实现「建议收藏」
支持向量机原理篇之手撕线性SVM
Python版本: Python3.x 运行平台: Windows IDE: Sublime text3 一、前言 说来惭愧,断更快半个月了,本打算是一周一篇的。感觉SVM瞬间难了不少,推导耗费了很多时间,同时身边的事情也不少,忙了许久。本篇文章参考了诸多大牛的文章写成的,对于什么是SVM做出了生动的阐述,同时也进行了线性SVM的理论推导,以及最后的编程实践,公式较多,还需静下心来一点一点推导。 本文出现的所有代码,均可在我的github上下载,欢迎Follow、Star:https://githu
机器学习算法工程师
2018/03/06
2K0
支持向量机原理篇之手撕线性SVM
理解SVM的三层境界(二)
第二层、深入SVM 2.1、从线性可分到线性不可分 2.1.1、从原始问题到对偶问题的求解 接着考虑之前得到的目标函数: 由于求 的最大值相当于求 的最小值,所以上述目标函数等价于(w由分母变
IT派
2018/03/29
1.9K0
理解SVM的三层境界(二)
机器学习(15)之支持向量机原理(一)线性支持向量机
关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法,不考虑特定的训练数据集,在分类算法中的表现SVM说是排第一估计是没有什么异议的。 SVM是一个二元分类算法,线性分类和非线性分类都支持。经过演进,现在也可以支持多元分类,
昱良
2018/04/04
1.2K0
机器学习(15)之支持向量机原理(一)线性支持向量机
机器学习算法(一)SVM
机器学习的一般框架: 训练集 => 提取特征向量 => 结合一定的算法(分类器:比如决策树、KNN)=>得到结果
全栈程序员站长
2022/11/08
2.4K0
机器学习算法(一)SVM
Python3《机器学习实战》学习笔记(八):支持向量机原理篇之手撕线性SVM
版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 https://blog.csdn.net/c406495762/article/details/78072313
Jack_Cui
2019/05/25
6840
Python3《机器学习实战》学习笔记(八):支持向量机原理篇之手撕线性SVM
SVM原理详解
SVM入门(一)至(三)Refresh 按:之前的文章重新汇编一下,修改了一些错误和不当的说法,一起复习,然后继续SVM之旅. (一)SVM的简介 支持向量机(Support Vector  Machine)是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中[10]。  支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样
triplebee
2018/01/12
1.4K0
SVM原理详解
用一张图理解SVM的脉络
SVM在之前的很长一段时间内是性能最好的分类器,它有严密而优美的数学基础作为支撑。在各种机器学习算法中,它是最不易理解的算法之一,要真正掌握它的原理有一定的难度。在本文中,SIGAI将带领大家通过一张图来理清SVM推导过程的核心过程。
SIGAI学习与实践平台
2018/08/07
3K0
用一张图理解SVM的脉络
支持向量机通俗导论(理解SVM的三层境界)【转载】
原文链接:https://blog.csdn.net/v_JULY_v/article/details/7624837
用户6021899
2019/08/21
9310
支持向量机通俗导论(理解SVM的三层境界)【转载】
支持向量机1--线性SVM用于分类原理
在机器学习中,支持向量机(SVM,也叫支持向量网络),是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。是由Vapnik与同事(Boser等,1992;Guyon等,1993;Vapnik等,1997)在AT&T贝尔实验室开发。支持向量机是基于统计学习框架与由Chervonenkis(1974)和Vapnik(1982,1995)提出Vapnik–Chervonenkis理论上的最强大的预测方法之一。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。
数据STUDIO
2021/06/24
1.8K0
支持向量机与支持向量回归(support vector machine and support vector regression)
支持向量机和支持向量回归是目前机器学习领域用得较多的方法,不管是人脸识别,字符识别,行为识别,姿态识别等,都可以看到它们的影子。在我的工作中,经常用到支持向量机和支持向量回归,然而,作为基本的理论,却没有认真地去梳理和总结,导致有些知识点没有彻底的弄明白。这篇博客主要就是想梳理一遍支持向量机和支持向量回归的基础理论知识,一个是笔记,另一个是交流学习,便于大家共勉。
全栈程序员站长
2022/09/02
7200
机器学习-支持向量机SVM算法
支持向量机(Support Vector Machine, SVM)对监督学习下二分类问题提供了一个绝妙的解决方案。通过对偶函数和核函数求解,将适用范围从二维线性推广到多维非线性模型,使用相关方法变形,也可用于多分类问题和回归问题。
唔仄lo咚锵
2023/05/23
5750
机器学习-支持向量机SVM算法
相关推荐
机器学习之深入理解SVM
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档