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

01 单刀直入,先回答有必要吗?

最近和许多朋友交流,发现当前机器学习应聘时,手推SVM这道题已经越来越像快速排序一样,成为必点菜了。

那么,手推SVM是不是必要的呢?正反双方各执一词,正方说,手推SVM才能看出应聘者的理论基础,反方说,现实中,SVM限于性能,应用面很小,尤其是现在xgboost, lightGBM等高性能的boosting框架的盛行,更让SVM成为了好看不好用的东西。能说清楚基础原理就可以了,没必要手推。

我的观点是:如果你是应聘者,不要思考这个问题,赶紧多推几遍SVM,争取达到闭眼也能推出来的地步,因为你没有选择,假如你跟面试官说,这个没必要推,实际中用的不多,估计你的面试也玄了,因为面试官不知道你是说真的还是在为自己不会找理由。

如果你是面试官,我的建议是不要问了,至少不要推导SVM了,大家都是被资本剥削,你不过是找一个同事,有大把的问题可以问出应聘者能否胜任公司的岗位,只要技术水平够,性情相投就可以了。如果你也问,等你跳槽时,自己还是要付出精力去临时背背那些推导,这叫作茧自缚。

在这里插个小曲。我第一次面试时和当时公司的技术总监聊了小一个小时的曾国藩,一见如故,后来我提出薪资要求,总监说你刚从体制里面出来,不了解现在互联网薪资行情,要的太低了,我会跟HR说在你的要求上乘以1.5的。

我觉得这才是一个技术人应有的行为准则!无产阶级何必为难无产阶级,只要你觉得这个人技术水平能胜任岗位,就可以了。虽然我后来没有去那家公司,但我至今仍然从内心感谢那位总监。

不过客观讲,机器学习暴涨的需求面前,大家实战经验都有限,可用来测试面试者实际经验的问题不好找,为降低招聘风险,问一下理论推导,也是权宜之计。

02 步步为营,怎么搞定SVM的推导?

那么,怎么能够快速地,长久地记住SVM的推导呢?

看到身边不少朋友采用的办法就是一遍又一遍的抄,抄熟之后就开始自己一遍又一遍的默写。个人觉得这样做是必要的,但不是最重要的,最重要的是获得intuition,即对每一步推导背后的意图建立起自己的感觉,这样就可以逐渐从背记的状态转移到自觉推导的境界。

下面,我们就尝试尽可能简单地快速地推导一遍SVM,但是重点不是推导,而是试图根据我的理解,说明每一步推导背后的动机。理解清楚后,相信推导就是顺理成章了。

03 SCM的基本思想

SVM的基本思想非常直观。设想一个多维平面上散落着正样本和负样本,如果能找到一个超平面,恰好能将正负样本分开,那么这个超平面就可以用来对样本进行分类。如下图所示:

我们的目标是找到图中的H3。那么,很自然地,我们就会产生两个问题:

1 如果这样的超平面确实存在,那么如何找到它?

2 如果这样的超平面不存在,那么如何找一个尽可能将正负样本分开的超平面?

以上两个问题就是SVM要解决的核心问题!所有关于SVM的知识都可以归为为了解决两个问题中的一个。

有了问题,就好比有了靶子,后面的推导都是冲着靶子去的,这样就更能理解推导的原理了。围绕问题去学习,是我推崇的学习方法,它的好处有二,一是更能调动主观能动性,因为你可以就问题进行很多自己的思考,二是能让知识更加模块化,便于完善知识结构。

04 由易到难,先解决第一问题

对第一个问题的解决,实际上就会得到SVM的基本型,即线性可分的SVM。这里请注意,第一个问题的假设是这样的超平面是存在的,或者说,样本是线性可分的,这一点需要牢记在心。要解决这个问题,我们可以进一步细化出2个问题:

1、如何衡量一个超平面是否能将正负样本分开

2、如何去寻找这样的超平面

下面的推导基本上是按照以上三个问题的顺序进行的。

(一)从数学上表示超平面将正负样本分开

一个超平面可以用如下的式子表示:

ω,b是超平面的参数。

一个样本点 到P(xi,yi) 超平面的几何距离(注意:这里是距离而非间隔)为:

几何距离

理解这个公式需要回忆一下线性代数知识,当然,你也可以直接承认这个公式,接受它就可以了。

若该超平面能将正负样本分开,也就是正负样本完全被超平面隔离开,该情况从数学的角度看,就等同于:

对任一个样本P(xi,yi),都有

几何间隔

这里的distance相比上面的几何距离,最大区别是它是有正负号的,称为几何间隔。几何间隔就是带符号的几何距离,就是这么简单。为什么这样就表示超平面正确区分了样本集呢?我们来具体分析下。

对于所有的正样本,yi=1,distance(xi,yi)大于0意味着

这意味着xi在超平面正的一侧,也就是在法向量ω指向的一侧

同理,对所有的负样本,yi=-1,也有

这意味着负样本都在超平面与法向量ω反向的一侧。

实际上若超平面对任一样本满足distance(xi,yi)<0,也同样可以证明超平面将正负样本分开了。不过,上面的表示并没有失去一般性,因为所谓的正负样本不过是我们的标记而已。

我们此时完全可以将正的标记为负的,将负的标记为正的,这样,能将正负样本分开的超平面,对任意一个样本,就重新满足了distance(xi,yi)>0这一条件。

问题解决。

(二)将数学表示转化为最优化问题

上面,我们已经得到结论:将正负样本分开的超平面等价于:

对任一样本(xi,yi),均有distance(xi,yi)>0

显然,这样的超平面如果存在,那一定会有无数多个,也就是说,如果一个超平面将正负样本分开了,我们只要将这个超平面进行极微小的旋转,那么,旋转得到的超平面仍然可以将正负样本分开。所以,我们不能满足于找到一个将正负样本分开的超平面,而是要寻找其中最好的那个。我们希望找到的超平面,不仅能将样本集分开,而且分得越开越好!

那么问题来了,如何度量超平面将样本集分开的程度?很简单,对于一个特定的超平面,对所有的样本,最小的distance越大,表示它将该样本集分得越开。据此,我们可以将问题转化成一个最优化的问题,即寻找能将样本集分得最开的超平面。

用数学表示就是:

(三)求解上面的最优化问题

我们解决一个问题,有一类思路就是对问题进行转换,不停地转换,直到转换成一个熟悉的,已有解决方案的问题。为了求解上面的最优化问题,我们需要对上面的问题进一步进行转换。所以,让我们继续转换上面的问题吧。

这里我们先要区分开超平面本身和超平面的表示ω,b。对一个超平面,我们肯定能找到一对ω,b来从数学上表示它,但是,当我们等倍数缩放ω,b时,缩放后的新的ωn,bn仍然表示原来的超平面。

假设对某一个特定的超平面ω,b,我们已经找到了使得里面的min取得最小值的的(xj,yj),其最小值为

按道理,我们现在应该进行外层的求最大化过程了。但是,对不同的超平面,里面的min所对应的xj, yj是各不相同的,这给我们带来麻烦。这个怎么破?方法是这样的。我们看最小值的分子部分

显然它的值是大于0的,因为我们的出发点就是从将正负样本分开的超平面中选取分得最开的那个超平面,这是我们问题的前提假设。

既然它是大于0的,那么,对这个特定的超平面,我们一定能通过等倍数缩放ω,b使得

这样一来,里面的min就变成了

这就是说,对所有的超平面ω,b,只要我们都用它们某个特定的表示,即某个特定的ω,b值,里面的min就总是

这个特定的表示就是使得对取得最小值的yj有

那么对于其他的样本点xi,yi,显然就有

因为xj,yj作为取得最小值的点,其值为1,其他的样本点自然是大于等于1了。

被称作样本点对超平面的函数间隔。这才是函数间隔上场的时间,特别不喜欢那些一上来就定义函数间隔和几何间隔,然后就一阵推导,总让人觉得隔靴搔痒似的。

至此,我们找到一个将里面的min消去的办法,即将所有超平面的表示加以限制,使得这个表示满足:

对所有的样本

并且这个等号是可以取到的。

此时,内层的min就是

我们的问题就转化成了这样:

s.t.

Note:

1,我们之所以选择使得对所有样本函数间隔大于等于1的超平面表示,完全是为了形式上的简洁。

也可以选大于等于0.5的超平面表示,这时里面的min就成了:

形式上显然没那么简洁了,因为分母中的2对解决问题一点用也没有。

2,表面看,我们要最大化的目标中已经没有了b。但实际上,我们知道,b已经成为了约束条件的一部分,如果b的取值破坏了约定条件,那是不可以的!

好了,到此为止,我们已经成功地从寻找最大间隔超平面这一思想出发,经过层层转化,得到了一个纯粹形式的数学问题。剩下的路程就进入了数学的领地了。

具体的推导需要很多的数学公式,但是地铁上用手机很难搞,暂时按下,回头补上。

至于对那些线性不可分的样本集,即对本文开头提出的第二个问题,后续会继续。

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ATYUN订阅号

利用深度学习改变位置感知计算

位置感知位于定位服务(LBS)的核心位置。然而,准确地估计目标的位置并不那么简单。全球定位系统(GPS),可以直接输出地理空间坐标,但它的错误可能远远超出了某些...

37711
来自专栏专知

【BicycleGAN】NIPS 2017论文图像转换多样化,大幅提升pix2pix生成图像效果

【导读】你一定记得非常热门的加州大学伯克利分校在CVPR2017上提出的图片翻译 pix2pix,它使用GAN方法可以将白马“转化”为斑马,可以把积木“转化”为...

9305
来自专栏量子位

一文带你理解Q-Learning的搜索策略,掌握强化学习最常用算法

强化学习(Reinforcement Learning, RL)属于机器学习的一个分支,利用智能体(agent)通过状态感知、选择动作和接收奖励来与环境互动。每...

1854
来自专栏大数据挖掘DT机器学习

R语言实现混合模型

普通的线性回归只包含两项影响因素,即固定效应(fixed-effect)和噪声(noise)。噪声是我们模型中没有考虑的随机因素。而固定效应是那些可预测因素,而...

5766
来自专栏机器之心

学界 | Vicarious发表Science论文:概率生成模型超越神经网络

2838
来自专栏计算机视觉战队

深度学习也可以取悦女友

深度学习目前在图像处理领域有着非常好的应用和研究,在医学领域可以用它在极早期判断癌症;在安防领域,可以用它来快速检索目标任务,进行可疑或危险人物的检测与抓捕;在...

2716
来自专栏AI科技评论

深度、卷积、和递归三种模型中,哪个将是人类行为识别方面的佼佼者?

导读:2016国际人工智能联合会议(IJCAI2016)于7月9日至7月15日举行,今年会议聚焦于人类意识的人工智能。本文是IJCAI2016接收论文之一,除了...

4379
来自专栏SIGAI学习与实践平台

怎样成为一名优秀的算法工程师

原创声明:本文为 SIGAI 原创文章,仅供个人学习使用,未经允许,不得转载,不能用于商业目的。

1744
来自专栏人工智能

宽度学习系统:一种不需要深度结构的高效增量学习系统

本文是对陈俊龙教授团队“Broad Learning System: An Effective and Efficient Incremental Learning ...

3905
来自专栏大数据挖掘DT机器学习

程序化点击率预估(CTR)

指标 广告点击率预估是程序化广告交易框架的非常重要的组件,点击率预估主要有两个层次的指标: 1. 排序指标。排序指标是最基本的指标,它决定了我们有没有能力把最合...

4038

扫码关注云+社区