BAT面试题1:请简要介绍下SVM

文末送惊喜

接下来,每天推送1道BAT的面试题,一般问到的这些知识点都是很重要的,所以知道的呢就再复习一下,不知道的赶紧弥补。日积月累,你会在不知不觉中就已入机器学习的大门,并且越走越深。同时,此方法不光帮你学知识,还能帮你顺利拿到OFFER.

今天BAT系列第一题 说说SVM

之前,关于支持向量机的文章已经推送过4篇了。今天再在这里全面汇总下。支持向量机的简称为SVM,能在已知样本点很少情况下,获得很好的分类效果。

SVM分类两个点。已知两个样本点,如果用SVM模型,决策边界就是线g,它的斜率为已知两个样本点斜率的垂直方向,并经过两个点的中点。

这条线g就是SVM认为的分类两个样本点的最好边界线。

SVM分类多个点

添加更多的样本点,但是有意识地让它们符合上面的分布,此时的最佳决策边界发生变化了吗?没有。样本点虽然多了,但是SVM认为起到支持作用的还是那两个点,support vector就是它们,名字得来了,当然因此决策边界也未变。以上这些都是直接观察出来的,计算机是如何做这个事的?

还启发我们,SVM建立决策边界时,只关心距离决策边界最近的那两个样本点,然后取距离它们都最远的决策边g ,认为g就是最佳决策边界。

有了以上基础,SVM目标函数的结构差不多就知道了:max ( min() ),SVM添加了一个约束,得到的好处是目标函数更精简了:

arg max 1/||w||

s.t., y*f(x)>=1

注意,这个更精简的目标函数,必须满足上面的约束,它们是共生关系,缺一不可。

最大值转化为求最小值。机器学习中,遇到目标函数求最大值的,都会转化为求最小值,常规套路,SVM也不例外。

它也很简单,分母最小,原式便能最大,即:

arg min 0.5*||w||^2

s.t., y * f(x)>=1

目标函数为什么带有系数0.5,没有特殊原因,只不过求导时,0.5*2化简方便。

这是常见的二次规划问题,求解方法有很多种,拉格朗日方法、Lemke方法、内点法、有效集法、椭球算法等。

SVM的以上目标函数求解选用了拉格朗日方法,可以查阅资料,了解此求解方法,里面还用到KKT,转化为先求w,b的最小值,然后再求alfa_i的最大值问题,进而求得参数w和b,至此完毕。

SVM还考虑了软间隔,核函数问题。噪音点出现了。如下图所示,有一个带圈的噪音点出现在了右下角,决策边界在哪里?

如果决策边界这样,可以看出它不是好的决策边界,因为噪音点是错误点,不应该拿它作为支持向量。

克服噪音:松弛因子。SVM适当地放宽了约束条件,将 yi * f(xi) >=1,放宽为 yi * f(xi) >=1-ei,这个间隔ei就是软间隔。为什么要减去ei,而不是加上ei,因为前者可能使得更多的样本点成立,比如第一幅图中,作为正的支持向量点可能不满足 yi * f(xi) >=1,但是可能满足 yi * f(xi) >=1-ei,这样即便噪音点出现了,我们仍然可能得到第一幅的分类决策边界。

ei在SVM中称为松弛因子,SVM中用控制因子C来控制ei,当C很大时,ei发挥的作用很小,也就是松弛的很小;C很小时,ei发挥的作用很大,可能松弛的作用更强些。

以上介绍了SVM参数求解和软间隔部分,它们还不是SVM最巧妙的部分SVM真正精彩之处在于将低维空间线性不可分问题转化为高纬空间线性可分问题,比如一个数据集有3个特征,此时线性不可分,但是转化成9个特征后,在此空间下可能就线性可分了,如下图所示,在二维空间下线性不可分,转化到三维下,就可以得到一个线性可分面。

这是如何做到的?核函数将低维下的原始特征映射到了高维下。

数据映射到高维空间后,是否求解的复杂度陡增呢? 不会的。在低维空间下样本点求内积的结果,只需花费O(1)时间复杂度直接转化为高维下的内积结果。

至此,SVM就介绍完了,SVM的目标就是求出一个最胖的决策宽度,所有的样本点中,真正起到支持作用的点就是离着决策边界最近的点。大家可以拿两个点来求决策边界为例,想一下SVM的几何意义。

里面的理论涉及到,点到直线的距离,目标函数通过添加一个约束条件变得更加精简,此时变为了已知约束条件和目标函数的二次规划问题,采取了拉格朗日法求最佳决策边界,也就是w和b。

为了解决噪音点,约束条件做了一定的松弛。

核函数是添加的一个映射,将低维空间下的数据映射到高维下,并且计算的时间复杂度几乎未改变,这是核函数顺利实施的前提。

BAT系列第一题

说说SVM 目标函数和约束怎么得来的?

更容易理解SVM的目标函数和约束怎么得来的思路,因此,记录下来,与大家一起分享。设 g(x) = wx+b,则样本点到g(x)的距离为:

|g(x)| / ||w||

SVM 建立决策边界时,只关心距离决策边界最近的那两个样本点,然后取距离它们都最远的决策边,转化为数学公式为:

max(min(|g(x)| / ||w||))

将它化简为:

max( 1/||w||)

s.t. yi*g(xi) >=1

怎么想出来的?

如果设 |g(x)| >= 1 ,则 min( |g(x)| / ||w|| ) = 1 / ||w|| , 进一步地,max(min(|g(x)| / ||w||)) ,可以化简为:

max ( 1 / ||w|| )

那么, |g(x)| >= 1 ,如何化简为 yi * g(xi) >= 1 呢? 注意到 yi 是 第 i 个样本的标签值,要么为 1, 要么为 -1. 当 g(x) >= 0,代表为正例,即 yi = 1,当 g(x) < 0,代表负例,即 yi = -1,因此,|g(x)| = yi * g(x) >= 1.

OK. 接下来便是求解如下最优化目标和约束的优化问题:

max( 1/||w||)

s.t. yi*g(xi) >=1

关于支持向量机更加全面的公式推导,请参考之前花几天时间写的文章:

这样一步一步推导支持向量机,谁还看不懂?

原文发布于微信公众号 - Python与机器学习算法频道(alg-channel)

原文发表时间:2018-10-07

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

长文干货!走近人脸检测:从VJ到深度学习(下)

深度学习给目标检测带来的变革 人脸检测作为一种特定类型目标的检测任务,一方面具有其自己鲜明的特点,需要考虑人脸这一目标的特殊性,另一方面其也和其它类型...

3968
来自专栏算法channel

斯坦福大学NLP-cs224课程笔记2:词向量

详细请参考:斯坦福大学NLP-cs224课程笔记1:应用深度学习到自然语言处理简介

1252
来自专栏机器之心

学界 | 稳!DeepMind提出多任务强化学习新方法Distral

选自arXiv 机器之心编译 参与:蒋思源、黄小天 深度强化学习因为复杂的环境而很难进行有效的训练,通常我们会简化环境或使用共享神经网络参数的方法进行多任务学习...

3095
来自专栏AI研习社

深度学习目标检测概览

本文是翻译自Object detection: an overview in the age of Deep Learning - Tryolabs Blog ...

4876
来自专栏机器之心

ICLR 2018 | 斯坦福大学论文通过对抗训练实现可保证的分布式鲁棒性

31112
来自专栏人工智能头条

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

1773
来自专栏人工智能LeadAI

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

上篇文章中,我们介绍了SVM的基本思想,并将其推导成了一个数学问题,今天的任务,就是解决如何求解这个数学问题,同时,回答上篇文章中提出的第二个问题: 如果将正负...

4066
来自专栏新智元

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

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

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

【干货】机器算法学习感悟(下)

今天的内容是续接昨天的,请喜欢的亲们一如既往的支持! (…………续) 第二个是KNN。KNN将测试集的数据特征与训练集的数据进行特征比较,然后算法提取样本集中特...

3276
来自专栏思影科技

《大话脑成像》系列之十一:浅谈广义线性模型(--设计矩阵和对比矩阵)

咳咳,这篇短文继续讲统计。(老实说,下面的内容比较严肃与难懂,如果你觉得实在太晦涩,建议放弃吧,我们之间是不可能的) 学过统计的都知道,统计方法...

1.2K9

扫码关注云+社区

领取腾讯云代金券