二、机器学习面试之有必要手推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科技评论

学界 | 卷积神经网络做简单任务原来有 BUG?UBER AI Lab 来支招

AI 科技评论按:UBER AI Lab 最新研究发现卷积神经网络在处理坐标变换问题上存在惊人的「无能」缺陷,并提出了一种简单的 CoordConv 策略修复了...

611
来自专栏目标检测和深度学习

推荐|改变你对世界看法的五大计算机视觉技术!

计算机视觉是当前最热门的研究之一,是一门多学科交叉的研究,涵盖计算机科学(图形学、算法、理论研究等)、数学(信息检索、机器学习)、工程(机器人、NLP等)、生物...

2628
来自专栏PPV课数据科学社区

【学习】数据挖掘中分类算法小结

数据仓库,数据库或者其它信息库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识。分类与预测是两种数据分析形式,它们可以用来抽取能够描述重要数据集...

30711
来自专栏机器学习原理

深度学习——目标检测(3)YOLO1SSD

前言:RCNN系列一般都是分为两个步骤,下面介绍one-stage方法,SSD和yolo算法 目标检测近年来已经取得了很重要的进展,主流的算法主要分为两个类型...

891
来自专栏目标检测和深度学习

综述:深度学习时代的目标检测算法

来源:https://zhuanlan.zhihu.com/p/33277354 目前目标检测领域的深度学习方法主要分为两类:two stage的目标检测算法;...

3845
来自专栏机器学习算法与Python学习

深度卷积生成对抗网络的无监督学习,补全人脸合成图像匹敌真实照

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 我们会再接再厉 成为全网优质的技术类...

3726
来自专栏专知

【CVPR2018论文笔记】非监督任意姿势人体图像合成

1432
来自专栏目标检测和深度学习

深度学习时代的目标检测综述

981
来自专栏数据派THU

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

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

592
来自专栏新智元

纳米神经网络 NanoNet:数据有限,照样玩转深度学习

【新智元导读】解决深度学习问题时,使用迁移学习能够很好地减少所需的训练数据量。但是,使用这种方法需要更多的专业知识,比如判断如何调试问题、将哪一层的输出作为输入...

34313

扫码关注云+社区