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

上篇文章中,我们介绍了SVM的基本思想,并将其推导成了一个数学问题,今天的任务,就是解决如何求解这个数学问题,同时,回答上篇文章中提出的第二个问题: 如果将正负样本分开的超平面不存在,那么如何找一个尽可能将正负样本分开的超平面?

SVM的数学问题求解

上篇文章中,我们将SVM转化成了如下的最优化问题:

svm
svm2

这里,我们再做一个小小的转化,将求最大值转化成求最小值,因为总的来说,我们对求最小值的问题更加熟悉一点,转化后是这个样子:

svm标准数学形式

这个问题的求解,数学家们已经给出了完美的办法。就是拉格朗日对偶法,但是要彻底讲清楚这个方法涉及到很多数学知识,如果粗略讲讲,忽略那些数学知识,就容易造成理解上的困惑。所以,搞机器学习,到底需要多少数学知识?

这个问题没有一定的正确答案,完全取决于你工作的需要和个人的兴趣 。如果你的工作只是理解这些模型的原理以便正确地使用它,那么,只要你觉得你的数学知识能够让你理解这个模型就可以了,如果你的工作可能会需要对模型求解的性能进行优化(这样的工作岗位我觉得是比较少的),那么肯定是理解地越透彻越好,数学知识多多益善。

最后,如果你对数学上的原理很感兴趣,那么 follow your heart即可。

本文的目的是在于说明模型的原理,所以只会在不得已时给出一些数学知识,而且也会尽可能以结论的形式给出。即数学只是我们的工具,我们的目的在于理解模型。

上面的问题, 在求解上,数学上给出了一个拉格朗日对偶求解法。该方法简单明了,我觉得对这个方法的数学证明,可以留给对数学特别有兴趣的朋友,一般情况下,我们只要知道具体的过程就可以了。这就像将大象关进冰箱,我们只需知道打开冰箱门,将大象放进去,关上冰箱门就可以了。好了,相信你已经准备好接受这个方法了,其步骤如下:

1、定义拉格朗日函数

这个函数其实就是将上面的m个大于等于0的约束条件,两边乘以-1转为小于等于0的约束条件,然后每一个约束条件左侧表达式乘以一个alpha再与目标函数相加就可以了。请注意,这里的alpha都是大于等于0的。

2、对w,b求导,令导数为0,求解

3、将第2步求得的结果代回拉格朗日函数,得到对偶问题

4、求解对偶问题,解出alpha,进而求出w,b

你可能对这样的方法为什么可行有疑问,还是那句话,这只是数学家告诉我们的一个办法,他们也证明过了,做机器学习的我们,直接拿来使用就可以了。如果你非要问清楚为什么,请参阅wiki。

你还可能觉得这个问题成对偶问题后,和原来问题相比,难度一样啊,还是一个二次规划问题,为什么非要费这么大劲呢。

答案同样是简单的,因为这个对偶的二次规划问题,已经有了高效的求解方法,就是SMO算法。我有篇文章就是专门讲解SMO算法的,请参阅(绝对原创,绝对心血结晶,强烈推荐阅读!)。第二呢 ,就是对偶问题会更便于引入核函数的概念。后续会专门讲解核函数。

当样本线性不可分时,SVM还能使用吗?

在上面的求解过程中,我们的目标是找到一个超平面,将正负样本分开。这里的一个前提假设是确实存在一个超平面,能够将正负样本分开。但理想很丰满,现实很骨感,大部分情况下,正负样本都不是能严格分开的,原因是多样的,比如数据采集有误差,或者数据本身就是不能完全分开的。

那怎么办呢?

此时,我们要回到SVM最初的思想上,SVM就是找一个将正负样本分得最开的超平面,从这个思想出发,我们一路推导,最后得出了一个数学上的最优化问题:

最小化目标函数(即二分之一的ω的二范数)就相当于最大化超平面与样本的间隔。对ω的约束就是能正确分开正负样本,并且与最近的样本点的函数间隔是1。我们称存在这样的超平面的样本集为线性可分样本集,此时的SVM也叫做线性可分SVM。

那么现在,满足约束条件的超平面已经不存在了。按理说,我们的SVM就不能用了。但是,正负样本线性不可分也是有程度之分的,一种是彻底的混乱不可分,一种是总体看来是可分,少数点使得其不可分。

对于彻底混乱不可分的情况,用核函数的办法可以使得我们继续使用SVM,简单讲就是将样本集进行映射,使得映射后的样本集正负线性可分,然后再使用SVM。如下图所示:

这个做法要在讲核函数时才能透彻说明。暂时按下不表。

对于基本线性可分,少数样本使得其不可分的情况,我们可以“放松”原来的SVM的要求,从而使其能适用这种情况。放松的思想非常简单,就是不再执着于寻找将正负样本分得最开的超平面,转而寻找将最多的样本分开且分得尽可能开,将最少的样本分不开,且分不开的程度尽可能低的超平面。这句话需要停下来反复体味一下。下面就来看看怎么来“放松”吧。

假设我们现在有一个超平面H,然后我们努力寻找它的特定表示,即ω,b,以便使得对每一个样本满足:

但是费了九牛二虎之力,找到的最好的表示ω,b仍然不能使得所有样本满足上面的条件。那么,此时,我们需要一个指标来告诉我们,这个超平面在区分正负样本方面怎么样?是不是达到了我们所要求的将能分开的样本分得尽可能开,将不能分开的样本分不开的程度降得尽可能低。

我们先来看看这个超平面对能分得开的样本分开的程度吧,对这些样本而言,都是满足上面的函数间隔大于等于1的要求的,所以,超平面将这些样本分开的程度可以用

来表示,这个值越小,表示超平面将这些样本分得越开。

对那些不满足函数间隔大于等于1的样本,如何衡量超平面对它们分不开的程度呢?就是看这些样本离满足函数间隔大于等于1的要求有多远。比如对样本(xi,yi),如果对它的函数间隔加上某个数ζi,就能使得该样本对超平面的函数间隔满足大于等于1的要求,我们就称超平面对这个样本分不开的程度为ζi。将所有分不开的样本的ζi加起来就可以衡量超平面对分不开的样本的分不开的程度。显然,对于那些满足函数间隔大于等于1的样本, 它们对应的ζi为0。

至此,我们知道了如何衡量超平面对那些满足函数间隔大于等于1的样本的分得开的程度,也知道了如何衡量超平面对那些不满足函数间隔大于等于1的样本的分不开的程度。将二者结合结合起来,就是能够衡量一个超平面,对于一个线性不可分的样本的分得开的程度。这就是基本线性可分SVM,如下图所示:

对这个问题的求解仍然是使用拉格朗日对偶法,过程和上面一样,这里不再赘述。

对基本线性可分SVM的思考

回顾本文,我觉得最重要的不是SVM的对偶求解方法,也不是线性可分SVM(啥意思,通篇文章不就讲了这两个事儿吗,逗我呢?)

我这么说是认真的,因为我觉得最重要的是我们从线性可分SVM,结合现实中样本都不是完全线性可分的实际,进而调整得到基本线性可分SVM的思维过程。这样的思维方式体现了将理论与实践结合的过程,这是我觉得最可贵的思维品质。

在当前AI快速发展的形势下,新的算法每天都在涌现,很多相关工作岗位都要求能够跟踪最新技术,并结合实际运用它,为公司创造利益。“结合实际”需要的就是这种将理论结合实践的思维品质。之前,听汪榕的智能营销实践课程,我最大的收获就是学习到他那种紧紧地将理论与实际业务结合的优秀思维习惯,所以,这里也强烈推荐下他的课程,即使你不是做智能营销,也应该能从中受益。

所以,如果读完本文,让你对理论结合实际有了更深一点的体会,我觉得就值了。

软间隔是在硬间隔的基础上针对现实问题做出的调整,这是有普遍意义的,就是目标函数要能够灵活结合实际变化。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-01-15

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

卷积神经网络(CNN)新手指南

引言 卷积神经网络:听起来像是生物与数学还有少量计算机科学的奇怪结合,但是这些网络在计算机视觉领域已经造就了一些最有影响力的创新。2012年神经网络开始崭露头角...

3464
来自专栏数据派THU

卷积神经网络失陷,CoordConv来填坑(附代码&视频)

本文讲述了卷积神经网络在涉及坐标建模等方面的缺陷,但是提出了CoordConv 作为解决方案。

852
来自专栏机器之心

学界 | 正在涌现的新型神经网络模型:优于生成对抗网络

选自Medium 作者:Alfredo Canziani等人 机器之心编译 参与:黄小天、吴攀 随着深度神经网络技术的发展,新型的网络架构也在不断涌现。普渡大学...

37610
来自专栏AI研习社

机器学习算法在自动驾驶领域的应用大盘点!

AI 研习社按:本文原载于 kdnuggets,由林立宏、吴楚编译。 将汽车内外传感器的数据进行融合,借此评估驾驶员情况、进行驾驶场景分类,都要用到机器学习。本...

3717
来自专栏人工智能头条

神经网络训练中的Tricks之高效BP(反向传播算法)

1773
来自专栏云时之间

什么是卷积神经网络

哈喽,大家好,今天来让我们了解下什么是卷及神经网络,在这篇文章中,我会介绍什么是卷积神经网络,以及卷积神经网络的基本结构和某些具体的应用。话不多说,马上进入正题...

3487
来自专栏决胜机器学习

循环神经网络(四) ——words2vec、负采样、golve

2675
来自专栏新智元

【重磅】计算机视觉和 CNN 发展十一座里程碑(附论文下载)

【新智元导读】从AlexNet到ResNet,计算机视觉领域和卷积神经网络(CNN)每一次发展,都伴随着代表性架构取得历史性的成绩。作者回顾计算机视觉和CNN过...

4424
来自专栏数据分析

[机器学习]-[数据预处理]-中心化 缩放 KNN(一)

数据预处理是总称,涵盖了数据分析师使用它将数据转处理成想要的数据的一系列操作。例如,对某个网站进行分析的时候,可能会去掉 html 标签,空格,缩进以及提取相关...

3097
来自专栏专知

【专知-PyTorch手把手深度学习教程04】GAN快速理解与PyTorch实现: 图文+代码

【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工智能( 机器学习、自然语言处理、计算机视...

62311

扫码关注云+社区

领取腾讯云代金券