二、机器学习面试之有必要手推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 条评论
登录 后参与评论

相关文章

来自专栏新智元

【TensorFlow超级指南】你能想到的TF教程和资源都在这里了

【新智元导读】众所周知,TensorFlow已然成为机器学习的热门工具。不论是学习还是从事与机器学习相关的工作,能够灵活使用TensorFlow可以大幅提高作业...

672
来自专栏大数据文摘

选择困难症?一文通解如何选择最合适的机器学习算法

1704
来自专栏人工智能

从AlexNet到残差网络,理解卷积神经网络的不同架构

导读: 卷积神经网络对视觉识别任务很有帮助。优秀的卷积神经网络具有数百万个参数和大量隐藏层。事实上,一个错误的经验法则是:「隐藏层的数量越多,卷积神经网络越好」...

1837
来自专栏IT派

入门 | 一文了解什么是语义分割及常用的语义分割方法有哪些

人类是如何描述场景的?我们可能会说「窗户下有一张桌子」,或者「沙发右边有一盏灯」。图像理解的关键在于将一个整体场景分解成几个单独的实体,这也有助于我们推理目标的...

642
来自专栏机器之心

深度 | 从AlexNet到残差网络,理解卷积神经网络的不同架构

3007
来自专栏灯塔大数据

荐读|初学者如何选择合适的机器学习算法

文主要的目标读者是机器学习爱好者或数据科学的初学者,以及对学习和应用机器学习算法解决实际问题抱有浓厚兴趣的读者。 面对大量的机器学习算法,初学者通常会问自己一...

4117
来自专栏CreateAMind

DeepMind时间序列生成模型

使用vae推理;lstm 时间相关建模;external memory加强记忆;和神经图灵机 可微分计算机等进行比较。

972
来自专栏机器学习算法全栈工程师

ResNet, AlexNet, VGG, Inception: 理解各种各样的CNN架构

作者:叶 虎 编辑:王抒伟 本文翻译自ResNet, AlexNet, VGG, Inception: Understanding various ar...

6475
来自专栏新智元

【干货】TensorFlow 实用技巧:模型盘点,使用情况及代码样例

本文将介绍当前 TensorFlow 上的所有抽象模型,描述每个模型的使用情况以及简单的代码样例。详细的示例请访问这里:https://github.com/c...

3277
来自专栏null的专栏

机器学习中的特征空间

声明:这篇博文主要是对参考文献中的那个PPT的学习之后记下的一些笔记,整理出来与大家一起分享,若笔记中有任何错误还请不吝指出,文中可能会使用到原作者的一些图,若...

3236

扫描关注云+社区