【分类战车SVM】第四话:拉格朗日对偶问题(原来这么简单,你也可以轻松学会)

分类战车SVM

(第四话:拉格朗日对偶问题)

先看下本文的大纲:

1.回顾

2.不等式的拉格朗日乘数法

3.拉格朗日对偶问题

4.总结

附录:大自然的对偶现象

本文的内容其实很简单,就在“4.总结”的那张图中:先把上一集中的问题转变成一个拉格朗日函数的问题,然后为了方便解决,去研究这个问题的对偶问题,发现对偶问题和原问题其实是一样的。

1.回顾

前面我们把最大间隔分类器的思想用数学形式表达了出来,简单回忆一下(以下,分类器=超平面),

  • 什么是线性分类器?

可以把两种不同类别样本分开的线性模型(或者超平面)。

  • 什么是最大间隔分类器?

所有线性分类器(或者超平面)中,可以把不同类别样本分的最开的那个。

  • 最大间隔分类器,具体如何去定义?

最大间隔分类器,可以使两类样本到它的距离都最大的那个超平面——也就是这个超平面可以将两类样本分的最开。

  • 如果样本不是一个,而是一组,那么到一个超平面的距离怎么衡量?

取这组样本中距超平面最近的那个点到超平面的距离。

  • 上面说的“距离”是什么?

就是直观看到的那个“几何距离”。它的公式

  • 如此定义的最大间隔分类器,其数学表达式什么?

以上都是前面三集的内容,不明白的同学在微信公众号“数说工作室”回复“SVM1”、“SVM2”、“SVM3”查看。由于目前是实时更新,有想交流的同学也可以在公众号中给数说君留言。

2. 不等式的拉格朗日乘数法

在我们学高数的时候,都知道那个熟的不能在熟的“拉格朗日乘数法”了,但我知道,除了考研党们,大部分的人估计也忘的差不多了,现在简单回忆一下。

————复习拉格朗日乘数法————

假设我们要求f(x)的最小值,约束条件是h(x)=0,即:

Min f(x)

s.t hi(x)=0,i=1,2…n

那么可以引入拉格朗日算子a,构造拉格朗日函数:

然后对x和a求偏导,使偏导数等于0,然后解出x和a。

————以上就是拉格朗日乘数法————

但是,这里遇到的不是那么简单的一个等式约束,而是一个不等式哦。

我们仍可以通过拉格朗日函数将约束条件融合到目标函数里去,首先,仍然构造拉格朗日函数:

然后,我们令

为什么呢?我们将用下面的图予以说明:

3. 拉格朗日对偶问题

在上面,我们已经把不等式的约束问题也转变为了一个p*的问题。

但其实是仍然个很难解决的问题,因为我们要先解决不等式约束的max问题,然后再在w上求最小值。怎么办呢?如果能把顺序换一下,先解决关于w的最小值,在解决关于a的不等式约束问题就好了。即,

这个d*就是p*的对偶形式,也即原问题的对偶形式,可惜的是,对偶归对偶,却未必相等!因为,

这个不等式有一个很装逼的名字,叫弱对偶性质(Week Duality),最大值中最小的一个,也要大于等于最小值中最大的一个。这个性质从常识上想想,也是可以理解的。同时,我们可以得到一个对偶间隙,即p*-d*。

话说回来,如果我们这里恰好能够取等号,即对偶间隙消失就好了。

说到这里数说君要感慨一下这世界上的诸多“定理”、“条件”们,平时读书的时候被这些狗屁定理定律条件折磨的死去活来,真正要用的时候才觉得,发现这些定理的大神们真真儿的是救星啊~!

现在就要说一个定理,来拯救我们于水火:

在凸优化理论中,有一个Slater定理,当这个定理满足,那么对偶间隙就会消失,即:

此时称为强对偶性质(strong Duality)。幸运的是,我们这里满足Slater定理。

什么是Slater定理?感兴趣的可以了解一下,但我个人认为这对下一步的学习不重要。

————Slater定理(不重要)————

若凸优化问题存在严格可行解,即存在x,满足

则优化问题具有强对偶性(原问题中的不等式约束是f(x) ≤ 0)。

Slater定理其实就是说,存在x,使不等式 约束中的“小于等于号”要严格取到“小于号”

————Slater定理(不重要)————

好啦,现在Slater定理满足,我们有p*= d*,但是还不行,为什么?因为p* 和d*可能都有不止一个解,我们得保证p* = d*的解为最优解才行——怎能办?麻烦还没解决。别急,下面一个“KKT条件”的东东可以帮助我们。

————KKT条件————

怎样才能满足呢KKT条件呢?KKT条件又是什么呢?很简单,以我们这里的问题为例,怎样才能满足KKT条件?

——当满足Slater条件、且F(w,b,a)对w和b都可微时,KKT条件满足;

KKT条件又是什么?

——该条件如下:

也就是说,p* =d*的解即为最优解。

————KKT条件—————

咦?是不是图片显示不了呀?怎么①②后面都是空白?

实际上我故意留空的,不想把东西弄复杂。各位观众只要知道我们这里KKT条件是满足的,然后KKT条件的内容可以决定我们的问题为最优解就好了,至于KKT条件到底是什么,我留在下几集再说,因为这个条件可以帮助我们简化求解。这里写出来后会破坏文章的美感。

下面我们就彻底抛开p*,只研究d*就可以了。

首先我们固定a,让F关于w和b最小化,老办法,对w和b求导:

然后带入到F(w,b,a)中去,

接着,我们可以求对a的极大了,也就是说,我们剩下的问题仅仅剩下:

下一步,我们就要求这个问题,得到a的值,进而就可以知道w和b的值了。

那么这个a怎么解?这是我们后面要讲的了——SMO高效优化算法

4. 总结

我们完善一下前面的那张流程图,得到本文的一个大纲:

附录:大自然的对偶现象

最后我们来看一下大自然的对偶现象,关注数说君微博的朋友一定发现,前两天我转发过一篇关于对偶想象的一篇脑洞打开的文章,是知乎网友“灌汤包烧麦”写的(http://www.zhihu.com/question/22708816/answer/34828092),文中列举了一些对偶的现象,现截取部分内容如下:

这是尼西亚会议敲定的三位一体论,主要讨论的是耶稣与耶老爷子究竟是不是同一人的问题。一个人既是自己的老子,又是自己的儿子,这在常识上错得也太离谱了。但一神教下不允许两神并立,所以父子又必属同一客体。最终的论断是:在现世父、子不是同一人,但在更高位面上同属一物。两者同是神在现世的投影,在同一时刻、同一地点,人们只能观测到父、子中的一个。

三位一体(trinity)的核心在于:常识上相斥甚至相悖的概念可能容于同一客体。其简化版为二重性(duality)。其中为人所熟知的是波粒二重性:

波与粒子两个不相容的概念其实是同一客体在现世位面的两副面孔,两者同为场的激发形式,在同一时间同一地点,人们只能观察到两者中的一个。顺带说一句,在此图像下,任何关于波、粒联系的描述(譬如几率波论)都是多余的,甚至有些不恰当。譬如光 波就不能解释为光子的几率波,无论

还是

都不是几率的量纲。 二重性在现代物理中非常常见,不过其中很大部分并不是那么经典,因而被译作“对偶性”。譬如电磁对偶性:

这幅图作得不是很恰当,主要是下面那个圈里不知道放什么比较好= =||。电磁对偶性说的是在电、磁场对易变换:

下,真空中麦克斯维方程不变。亦即,在真空中,电、磁场是无法区分的,比如炮姐全身散发的究竟是电场还是磁场呢?正是基于这种对偶性,才会有磁单极子假说。 与“二重性”相似,“对偶性”同样讲两种不同概念实际有相同的根源。不同的是,“二重性”将两重概念容于一个客体,因而同时同地只能显现一副面孔。而“对偶性”将两重概念寄于一种客体,同时同地两副面孔都能显现。

原文发布于微信公众号 - 数说工作室(shushuojun)

原文发表时间:2014-12-24

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IT派

推荐|14种模型设计帮你改进你的卷积神经网络(CNN)!

如果你觉得好的话,不妨分享到朋友圈。 摘要: 这14 种原创设计模式可以帮助没有经验的研究者去尝试将深度学习与新应用结合,对于那些没有机器学习博士学位的人来说...

36760
来自专栏机器之心

AAAI 2018 | 浙江大学提出设计网络嵌入算法的度惩罚原则,可有效保留无标度特性

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

简单易懂的讲解深度学习(入门系列之七)

1986年,辛顿教授和他的团队重新设计了BP算法,以“人工神经网络”模仿大脑工作机理,又一次将人工智能掀起了一个浪潮。但是,当风光不再时,辛顿和他的研究方向,逐...

9930
来自专栏个人分享

数据挖掘10大算法详细介绍

在一份调查问卷中,三个独立专家小组投票选出的十大最有影响力的数据挖掘算法,今天我打算用简单的语言来解释一下。

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

如何识别图像边缘

图像识别?的搜寻结果 百度百科 [最佳回答]图像识别,是指利用计算机对图像进行处理、分析和理解,以识别各种不同模式的目标和对像的技术。一般工业使用中,采用工业相...

49960
来自专栏新智元

6段Python代码刻画深度学习历史:从最小二乘法到深度神经网络

【新智元导读】深度学习为什么会成为今天的样子?让我们用六段代码来刻画深度学习简史,用Python展现深度学习历史上关键的节点和核心要素,包括最小二乘法、梯度下降...

47490
来自专栏人工智能

你应该知道的建模的几种方法

近期,66号学苑携手ZRobot CEO乔杨为大家带来“企业级信用评分模型”系列课的第二课,本期课程乔杨老师主要介绍了建模的主要方法及在应用中需要注意的情况。以...

25590
来自专栏Petrichor的专栏

深度学习: CV顶会 & CV顶刊

[1] 计算机视觉顶尖期刊和会议有哪些 [2] cvpr中poster,oral,spotlight的区别是什么 [3] AI学术会议Deadline清...

45030
来自专栏人工智能头条

拓扑数据分析在机器学习中的应用

408120
来自专栏专知

【MLA首日报告摘要】周志华、马毅等教授分享机器学习最新进展

【导读】第15届中国机器学习及其应用研讨会今天11月4日在北京交通大学举行,海内外从事机器学习及相关领域研究的10余位专家与会进行学术交流,包括特邀报告、顶会论...

38550

扫码关注云+社区

领取腾讯云代金券