支持向量机(SVM)——斯坦福CS229机器学习个人总结(三)

2023-12-28 12:58

本文主要是介绍支持向量机(SVM)——斯坦福CS229机器学习个人总结(三),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

鉴于我刚开始学习支持向量机(Support vector machines,简称SVM)时的一脸懵逼,我认为有必要先给出一些SVM的定义。

下面是一个最简单的SVM:

图一
图一

  • 分类算法:支持向量机(SVM)是一个分类算法(机器学习中经常把算法称为一个“机器”),它的目标是找到图中实线所表示的决策边界,也称为超平面(Hyperplane)
  • 支持向量(Support vectors):支持向量就是图中虚线穿过的数据点(两个×与一个O),直观上来看,它们确定了超平面的位置——超平面与过同一类的两个支持向量(两个×)的直线平行,并且两类支持向量到超平面的距离相等
  • 与logistic回归的对比:SVM与logistic回归用的是相同的模型,但是处理方式不一样——logistic回归用概率的方式求解模型(最大似然估计),SVM从几何的角度解析;另外在logistic回归中,每一个数据点都会对分类平面产生影响,在SVM中它却只关注支持向量(如果支持向量无变化,增加或者删除一些远处的数据点,产生的超平面还是一样的)——所以产生了这两个不同的算法,但是它们还是比较相似的

明明是SVM算法却在这里提到logistic回归模型是为了作为源头引出SVM的推导,至于更深的背景,比如SVM被认为几乎是最好的监督学习啦,SVM是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的啦,SVM作为统计机器学习与传统机器学习的本质区别啦……目前的我还没有形成一个整体的、完善的认识,虽然下一份总结里就要说到学习理论与结构风险最小化,但是对于海面之下的冰山,我暂时还没法看到。在这里我只是想老老实实地把SVM从推导,到转换与优化,到最后求解的过程做一个总结写下来。

还需要说明的是,图一是最简单的SVM,它是线性可分的,并且从图一上来看它是没有噪点的,第一章“SVM的推导”可以把这个漂亮的线性可分的模型推导出来。
但是实际的情况不可能这么完美。当数据线性不可分的时候,我们需要引入核函数在更高维的空间里去寻找这个超平面(数据在更高维的空间里会更加线性可分);当噪点存在的时候,我们引入软间隔分类器,这时候在支持向量附近,允许有一些噪点被分错,即允许误差的存在。而这两点都是在将目标函数转化为对偶问题之后实现的。这些都会在第二章“SVM转换与优化”中介绍。

1、SVM的推导

1.1、起源

SVM与logistic回归使用了相同的模型,现在让我们来回顾一下熟悉的logistic回归模型:

hθ(x)=g(θTx)=11+eθTx(1)

其中:
g(z)=11+ez(2)

并且其图像如下图:

这里写图片描述
图二

图像的输出是“分类结果 g(z) 是1的 概率”,它的取值范围是 (0,1) ,一般来说以0.5为界,当 g(z) 是1的概率大于0.5的时候,把 x 分类为1,当 g(z) 是1的概率小于0.5的时候,把 x 分类为0,这样,虽然它的直接输出是 (0,1) 之间的概率,却有感知器那样的分类效果。
同时可以看到当 z 在0附近时,输出概率在0.5附件徘徊,而且比较敏感,但是当 z=θTx>>0 时它的输出很接近1,当 z=θTx<<0 时它的输出很接近0。所以如果我们能够让 z>>0 或者 z<<0 ,我们就会更加确信这个样本被正确分类了。
换句话说,如果把 z=0 这条直线当做决策边界,那么数据点 z 距离这条直线越远,就越不可能被分错。
SVM就是从几何的角度,在这方面下功夫的。

下面是在logistic回归模型下,因为SVM这个算法的特点而引起的符号改变:

y=hθ(x)=g(θTx)=g(wTx+b)=hw,b(x)(3)

直观点的改变是:
θTx=θ0+θ1x1+θ2x2++θnxn=b+w1x1+w2x2++wnxn=wTx+b(4)

截距b就是截距 θ0 ,向量 w 就是除了 θ0 外,剩下的向量 θ ,而且这里的向量 x 应该是差了一个 x0=1 xθ,θRn+1 xw,wRn ),但是不影响…它们表达的意思是一样的,只是换了些符号而已。
另外,这里的 g(z) 不再是式(2)中的形式,而是:
g(z)={11if(z0)if(z<0)(5)

恩…长得很像感知器。
式(3)与式(5)就是SVM模型了,参数是 θ b ,当这两个参数确定了,我们就可以做出分类超平面,对数据进行分类。

对同一个模型,logistic模型用概率的方式求解,下面就要引入函数间隔与几何间隔来从几何的角度来解析SVM了。

1.2、函数间隔(Functional margins)与几何间隔(Geometric margins)

给定一个训练样本(x(i),y(i)),我们将其 函数间隔定义为:

γ^(i)=y(i)(wTx(i)+b)(6)

函数间隔的作用有两个。
一个是 确认样本点有没有被正确分类
由式(3)与式(5)可以知道, y(i) 的取值为{ 1,1 },那么在 w,b 确定了,并且样本被正确分类的情况下, wTx+b y(i) 是同号的,即 γ^(i)=(wTx+b) ,所以当函数间隔 γ^(i)>0 ,即 γ^(i) 是正数的时候,我们就认为这个点被正确地分类了(错误分类时 γ^(i)<0 )。
另一个是 衡量该样本点被正确分类的确信度
在起源中由sigmoid函数 g(z) 我们注意到,一个点离超平面越远,其输出就越接近1,同样地, γ^(i) 越大,这个样本被分对的也确信度越大。

进一步地,相比只有一个训练样本的情况,如果给定一个训练集 S= { (x(i),y(i);i=1,2,,m) },那么整个训练集合的函数间隔为:

γ^=mini=1,2,,mγ^(i)(7)

有了函数间隔我们就可以去选择超平面了,在判断数据点有没有被正确分类这一点上,函数间隔没有问题。当所有样本点的函数间隔都是正数的时候,它们就全都被正确分类了(在这里讨论的是数据集线性可分的情况,如图一所示)。
需要注意的是,此时的超平面不一定就是最优的,所以我们还要最大化其被分类正确的确信度,这时候就需要依赖到函数间隔的第二个作用了。

但是在使得确信度最大这一点上,函数间隔却存在着缺陷。我们希望在样本点全部被正确分类的前提下,它们被分对的确信度最大,即让 γ^ 尽可能地大(这与式(7)中选取最小(即确信度最小)的 γ^(i) 来作为整个训练集的函数间隔 γ^ 并不矛盾,还有点在确立最大下界的意思)。
可是我们发现,只要成比例地改变 w b,比如把它们变成 2w 2b ,超平面并没有发生改变,但是函数间隔 γ^ 却变成了原来的两倍,这意味着,我们可以成比例地增大 w b,使得函数间隔 γ^ 变得无限大。这显然没有意义,因为超平面的位置并没有发生改变。

这时候就轮到几何间隔出场了,它是增加了约束的函数间隔,使函数间隔变得唯一,用符号 γ 表示。
直观上来看几何间隔是样本点到超平面的距离
此时改变几何间隔就能够移动超平面,同时几何间隔仍然能反映样本被正确分类的确信度,所以对几何间隔的最大化,就是对超平面的最优化。

下面我们借助图三来寻找几何间隔:

这里写图片描述
图三

设点B是向量 x ,点B在超平面上,点A为样本点向量 x(i)
因为点A与点B在法向量 w 上的距离就是几何间隔 γ(i) ,所以我们有:
x(i)γ(i)ww=x(8)

因为 γ(i) 只是一个距离常量,所以需要乘上法向量 w 的单位向量 ww w 是向量 w 的长度, w=w21+w22+w23++w2n+ ),才能在向量间直接做加减。
因为点B在超平面上,所以我们有:
wTx+b=wT(x(i)γ(i)ww)+b=0(9)

对式(9)进行求解即可得到几何间隔的形式化定义:
γ(i)=wTx(i)+bw=(ww)Tx(i)+bw(10)

这是样本点在正侧的情形,如果样本点在负的一侧,那就是:
γ(i)=((ww)Tx(i)+bw)(11)

所以为使公式一般化,几何间隔如下表示:
γ(i)=y(i)((ww)Tx(i)+bw)(12)

几何间隔与函数间隔的关系是:
γ(i)=γ^(i)w(13)

所以说几何间隔是增加了约束的函数间隔,是对函数间隔的完善,这时如果成比例地改变 w b ,几何间隔是不会改变的。

类似地,相比只有一个训练样本的情况,如果给定一个训练集 S= { (x(i),y(i);i=1,2,,m) },那么整个训练集合的几何间隔为:

γ=mini=1,2,,mγ(i)(14)

1.3、最优间隔分类器(The optimal margin classifier)

有了几何间隔,我们就可以确定最优超平面的位置,即最优间隔分类器了:

maxγ,w,bγs.t.y(i)((ww)Tx(i)+bw)γ,i=1,2,,m(15)

把图一再贴上来一次,并且默认上方的叉叉为正实例,下方的圈圈为负实例:

图一

为什么说满足了式(15)的超平面就是最优间隔分类器,即图中的实线?
首先,在 正确分类的情况下,我们要承认 几何间隔 γ 是正数(如果 γ 是负数,证明分类都不正确,那就没有讨论下去的必要了,更不用提什么最优),所以如果每个样本点都服从了式(15)中 y(i)((ww)Tx(i)+bw)γ 这个式子,那么我们就可以认为“所有样本点的几何间隔都大于一个正数”,即这些样本点都被正确分类了。这正是函数间隔的第一个作用。于是在这个前提下,我们发现超平面只能画在图一的两条虚线即支持向量之间,而且要跟虚线平行。

其次,我们来考虑最优的问题。虽说确定了超平面一定在两条虚线之间,但是那里面仍然有无数个超平面,如何确定最优?
综合几何间隔与函数间隔的第二个作用,我们有这样的结论:“几何间隔越大,样本被正确分类的确信度越大”,当式(15)中 maxγ,w,bγ 这个式子满足的时候,我们发现超平面正好处于两条虚线的中线位置,它也是我们直观上能想象到的最好的位置了。为什么这么巧?
直观上来说,支持向量是最靠近超平面的存在,所以由式(14)可以知道,支持向量的几何间隔,就是整个样本集的几何间隔,因为其它的点离超平面更远,不在考虑范围之内了。
我们可以想象一下这条实线(超平面)沿着平行的方向上下移动,举个极端的例子,超平面移动到支持向量上,与某一条虚线重合了,这时候所有样本点也是分类正确的,但是此时的几何间隔 γ=0 ,它是不满足“几何间隔最大”这个要求的,然后我们慢慢将超平面从虚线向另一侧的虚线移动,每移动一分几何间隔 γ 就增大一分,直到达到中线的位置,支持向量到超平面的距离相等, γ 才达到最大,超平面达到最优(如果超平面继续向另一侧虚线移动, γ 又会变小)。

解释了这么多是为了说明,满足了式(15)的参数 w,b 可以确定最优超平面,所以它就是我们的目标函数了。那是不是就可以开始对式(15)进行求解了,求解得到了 w,b ,SVM的工作就完成了。

嗯,是的,求解得到 w,b ,SVM的工作就完成了。但是,工作还没有开始。因为这个样子的目标函数没法求解,或者直接求解难度太大,因为它不是一个凸函数,没法用常规的梯度下降或者牛顿法求解。目前的我也不知道如果不用讲义上给的方法,还有没有别的方法可以手动求解。所以,按着给出的方法接着往下走吧。

由函数间隔与几何间隔的关系 γ(i)=γ^(i)w ,我们可以对 式(15)进行如下的改写:

maxγ^,w,bγ^ws.t.y(i)(wTx(i)+b)γ^,i=1,2,,m(16)

因为函数间隔的改变不影响超平面的位置,所以为了进一步化简目标函数,我们给函数间隔一个约束 γ^=1 使其变得唯一,此时 γ^w=1w ,又因为最大化 1w 与最小化 12w2 是一样的,所以有:
minγ,w,b12w2subject toy(i)(wTx(i)+b)1,i=1,2,,m(17)

这样,目标函数就变成式(17)的样子了,接下来就可以对这个函数进行求解了。

2、SVM的转换与优化

2.1、SVM转换——引入拉格朗日对偶与KKT条件

2.1.1、目标函数转化为原始问题(Primal problem)

现在,我们将目标函数式(17)改写一下 :

f(w)g(wi)=12w2=y(i)(wTx(i)+b)+10(18)

然后引入 拉格朗日乘子(Lagrange multipliers) α

这篇关于支持向量机(SVM)——斯坦福CS229机器学习个人总结(三)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/546020

相关文章

SpringKafka消息发布之KafkaTemplate与事务支持功能

《SpringKafka消息发布之KafkaTemplate与事务支持功能》通过本文介绍的基本用法、序列化选项、事务支持、错误处理和性能优化技术,开发者可以构建高效可靠的Kafka消息发布系统,事务支... 目录引言一、KafkaTemplate基础二、消息序列化三、事务支持机制四、错误处理与重试五、性能优

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

使用DeepSeek搭建个人知识库(在笔记本电脑上)

《使用DeepSeek搭建个人知识库(在笔记本电脑上)》本文介绍了如何在笔记本电脑上使用DeepSeek和开源工具搭建个人知识库,通过安装DeepSeek和RAGFlow,并使用CherryStudi... 目录部署环境软件清单安装DeepSeek安装Cherry Studio安装RAGFlow设置知识库总

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

定价129元!支持双频 Wi-Fi 5的华为AX1路由器发布

《定价129元!支持双频Wi-Fi5的华为AX1路由器发布》华为上周推出了其最新的入门级Wi-Fi5路由器——华为路由AX1,建议零售价129元,这款路由器配置如何?详细请看下文介... 华为 Wi-Fi 5 路由 AX1 已正式开售,新品支持双频 1200 兆、配有四个千兆网口、提供可视化智能诊断功能,建

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操