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

相关文章

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

“小数据”的统计学

一、小数据来自哪里? 科技公司的数据科学、关联性分析以及机器学习等方面的活动大多围绕着”大数据”,这些大型数据集包含文档、 用户、 文件、 查询、 歌曲、 图片...

3356
来自专栏BestSDK

深度学习 VS 深度克隆,谁才是解决聊天机器人的最佳方法?

对话式 AI (聊天机器人)涉及到三个维度的问题:(1)语言技能(2)知识获取(3)对话行为。 这三者虽然强相关,但人类大脑通过单独的实验,在不同的时间段内,可...

2935
来自专栏机器学习算法与理论

《白话深度学习与Tensorflow》学习笔记(1)

刚入手一本《白话深度学习与Tensorflow》,哈哈,一直看深度学习很火,其实自己一知半解,都没有对这个领域进行一点系统的学习,现在准备看看这本书,开始入门。...

3578
来自专栏iOSDevLog

100天写机器学习代码100天写机器学习代码

今天进入#100DaysOfMLCode我深入研究了实际Logistic回归的深度,以及它背后的数学运算是什么。了解如何计算成本函数,以及如何将梯度下降算法应用...

361
来自专栏深度学习那些事儿

一篇文章解决机器学习,深度学习入门疑惑

研究生有不少日子,和之前的几个学长以及几个学弟偶尔也聊聊天。大部分聊的话题无关乎这几年大火的机器学习深度学习神经网络,而这篇文章的目的,则是从学生的角度(不管是...

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

期待已久的—YOLO V3

好久不见各位研友(研究好友,不是考研的小伙伴,嘿嘿)!最近,因为题主学校事情比较繁忙,没有花更多的时间在我们的平台,希望关注支持我们的您,原谅我们更新的速度,希...

43316
来自专栏专知

春节充电系列:李宏毅2017机器学习课程学习笔记29之循环神经网络 Recurrent Neural Network Part3

【导读】我们在上一节的内容中已经为大家介绍了台大李宏毅老师的机器学习课程的Recurrent Neural Network进阶知识。这一节将主要针对讨论Recu...

3409
来自专栏小詹同学

人脸识别(一)——从零说起

这是关于人脸的第①篇原创!(源码在第三篇) 人脸识别的英文名称是 Face Recognition,前段时间查找资料学的时候发现,不少人将人脸识别和人脸检测(...

41010
来自专栏新智元

世界首个无监督幽默生成系统诞生,深度学习下一个大战场:讲段子!

【新智元导读】作者研发了第一个完全无人监督的笑话生成系统,使用的只是大量未标注的数据。这表明生成笑话并不像一般认为的那样,总是需要深度的语义理解。 摘要 幽默的...

35113
来自专栏AI科技大本营的专栏

最讨厌说大话,只想聊经验!我从创建Hello world神经网络到底学会了什么?

我开始跟神经网络打交道是在几年之前,在看了一篇关于神经网络用途的文章后,我特别渴望能够深入研究一下这个在过去几年间吸引了众多关注的问题解决方案。 2015年,斯...

3625

扫描关注云+社区