【分类战车SVM】第四话：拉格朗日对偶问题（原来这么简单，你也可以轻松学会）
【分类战车SVM】第四话：拉格朗日对偶问题（原来这么简单，你也可以轻松学会）
分类战车SVM
（第四话：拉格朗日对偶问题）
查看本《分类战车SVM》系列的内容：
第一话：开题话
第二话：线性分类
第三话：最大间隔分类器
第四话：拉格朗日对偶问题（原来这么简单！）
第五话：核函数（哦，这太神奇了！）
第六话：SMO算法（像Smoke一样简单！）
附录：用Python做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)。其中为人所熟知的是波粒二重性：
波与粒子两个不相容的概念其实是同一客体在现世位面的两副面孔，两者同为场的激发形式，在同一时间同一地点，人们只能观察到两者中的一个。顺带说一句，在此图像下，任何关于波、粒联系的描述（譬如几率波论）都是多余的，甚至有些不恰当。譬如光 波就不能解释为光子的几率波，无论
还是
都不是几率的量纲。 二重性在现代物理中非常常见，不过其中很大部分并不是那么经典，因而被译作“对偶性”。譬如电磁对偶性：
这幅图作得不是很恰当，主要是下面那个圈里不知道放什么比较好= =||。电磁对偶性说的是在电、磁场对易变换：
下，真空中麦克斯维方程不变。亦即，在真空中，电、磁场是无法区分的，比如炮姐全身散发的究竟是电场还是磁场呢？正是基于这种对偶性，才会有磁单极子假说。 与“二重性”相似，“对偶性”同样讲两种不同概念实际有相同的根源。不同的是，“二重性”将两重概念容于一个客体，因而同时同地只能显现一副面孔。而“对偶性”将两重概念寄于一种客体，同时同地两副面孔都能显现。