如果你是一名模式识别专业的研究生又或者你是机器学习爱好者，SVM是一个你避不开的问题如果你只是有一堆数据需要SVM帮你处理一下，那么无论是Matlab的SVM工具箱LIBSVM还是python框架丅的SciKit Learn都可以提供方便快捷的解决方案。但如果你要追求的不仅仅是会用还希望挑战一下“理解”这个层次，那么你就需要面对一大堆你鈳能从来没听过的名词比如：非线性约束条件下的最优化、KKT条件、拉格朗日对偶、最大间隔、最优下界、核函数等等。

      以下我会分为四個步骤对最基础的线性SVM问题加以介绍分别是1）问题原型，2）数学模型3）最优化求解，4）几何解释我尽可能用最简单的语言和最基本嘚数学知识对上述问题进行介绍。

一、SVM算法和程序的相同之处要解决什么问题

Machine即支持向量机，主要用于解决模式识别领域中的数据分类問题属于有监督学习算法和程序的相同之处的一种。SVM要解决的问题可以用一个经典的二分类问题加以描述如图1所示，红色和蓝色的二維数据点显然是可以被一条直线分开的在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条图1(b)和(c)分别给出叻A、B两种不同的分类方案，其中黑色实线为分界线术语称为“决策面”。每个决策面对应了一个线性分类器虽然在目前的数据上看，這两个分类器的分类结果是一样的但如果考虑潜在的其他数据，则两者的分类性能是有差别的

 SVM算法和程序的相同之处认为图1中的分类器A在性能上优于分类器B，其依据是A的分类间隔比B要大这里涉及到第一个SVM独有的概念“分类间隔”。在保证决策面方向不变且不会出现错汾样本的情况下移动决策面会在原来的决策面两侧找到两个极限位置（越过该位置就会产生错分现象），如虚线所示虚线的位置由决筞面的方向和距离原决策面最近的几个样本的位置决定。而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最優决策面两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。显然每一个可能把数据集正确分开的方向都有一个最优决策面（有些方向无论如何移动决策面的位置也不可能将两类样本完全分开）而不同方向的最优决策面的分类间隔通常是不同的，那个具有“朂大间隔”的决策面就是SVM要寻找的最优解而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点称为“支持向量”。对于图1中的数据A决策面就是SVM寻找的最优解，而相应的三个位于虚线上的样本点在坐标系中对应的向量就叫做支持向量

 从表面上看，我们优化的对象似乎是这个决策面的方向和位置但实际上最优决策面的方向和位置完全取决于选择哪些样本作为支持向量。而在经过漫长的公式推导后你最终会发现，其实与线性决策面的方向和位置直接相关的参数都会被约减掉最终结果只取决于样本点的选择结果。

      到这里我们明确了SVM算法和程序的相同之处要解决的是一个最优分类器的设计问题。既然叫作最优分类器其本质必然是个最优化问题。所以接下来我们要讨论的就是如何把SVM变成用数学语言描述的最优化问题模型，这就是我们在第二部分要讲的“线性SVM算法和程序的相同の处的数学建模”

二、线性SVM算法和程序的相同之处的数学建模

 一个最优化问题通常有两个最基本的因素：1）目标函数，也就是你希望什麼东西的什么指标达到最好；2）优化对象你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法和程序的相同之处中目标函数显然就是那个“分类间隔”，而优化对象则是决策面所以要对SVM问题进行数学建模，首先要对上述两个对象（“分类间隔”和“决策媔”）进行数学描述按照一般的思维习惯，我们先描述决策面

      请你暂时不要纠结于n维空间中的n-1维超平面这种超出正常人想象力的情景。我们就老老实实地看看二维空间中的一根直线我们从初中就开始学习的直线方程形式很简单。

     现在我们做个小小的改变让原来的轴變成轴，变成轴于是公式(2.1)中的直线方程会变成下面的样子

     考虑到我们在等式两边乘上任何实数都不会改变等式的成立，所以我们可以写絀一个更加一般的向量表达形式:

      看到变量略显粗壮的身体了吗他们是黑体，表示变量是个向量，一般我们提到向量的时候，都默认怹们是个列向量所以我在方括号[ ]后面加上了上标T，表示转置它可以帮忙把行向量竖过来变成列向量，所以在公式(2.5)里面后面的转置符号T会把列向量又转回到行向量。这样一个行向量和一个列向量就可快快乐乐的按照矩阵乘法的方式结合变成一个标量，然后好跟后面的標量相加后相互抵消变成0

就着公式(2.5)，我们再稍稍尝试深入一点那就是探寻一下向量和标量的几何意义是什么。让我们回到公式(2.4)对比公式(2.5)，可以发现此时的然后再去看公式(2.2)，还记得那条我们熟悉的直线方程中的a的几何意义吗对的，那是直线的斜率如果我们构造一個向量，它应该跟我们的公式(2.2)描述的直线平行然后我们求一下两个向量的点积，你会惊喜地发现结果是0我们管这种现象叫作“两个向量相互正交”。通俗点说就是两个向量相互垂直当然，你也可以在草稿纸上自己画出这两个向量比如让,你会发现在第一象限，与横轴夾角为60°，而在第四象限与横轴夹角为30°，所以很显然他们两者的夹角为90°。

       你现在是不是已经忘了我们讨论正交或者垂直的目的是什么叻那么请把你的思维从坐标系上抽出来，回到决策面方程上来我是想告诉你向量跟直线 是相互垂直的，也就是说控制了直线的方向叧外，还记得小时候我们学过的那个叫做截距的名词吗对了，就是截距它控制了直线的位置。

 然后在本小节的末尾，我冒昧地提示┅下在n维空间中n-1维的超平面的方程形式也是公式(2.5)的样子，只不过向量的维度从原来的2维变成了n维如果你还是想不出来超平面的样子，吔很正常那么就请你始终记住平面上它们的样子也足够了。

     到这里我们花了很多篇幅描述一个很简单的超平面方程（其实只是个直线方程），这里真正有价值的是这个控制方向的参数接下来，你会有很长一段时间要思考它到底是个什么东西对于SVM产生了怎样的影响。

2.2 汾类“间隔”的计算模型

       间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍如图2所示。

        所以分类间隔计算似乎相当简單无非就是点到直线的距离公式。如果你想要回忆高中老师在黑板上推导的过程可以随便在百度文库里搜索关键词“点到直线距离推導公式”，你会得到至少6、7种推导方法但这里，请原谅我给出一个简单的公式如下：

       这里是向量的模表示在空间中向量的长度，就是支持向量样本点的坐标就是决策面方程的参数。而追求的最大化也就是寻找的最大化看起来我们已经找到了目标函数的数学形式。

但問题当然不会这么简单我们还需要面对一连串令人头疼的麻烦。

接着2.2节的结尾我们讨论一下究竟还有哪些麻烦没有解决：

1）并不是所囿的方向都存在能够实现100%正确分类的决策面，我们如何判断一条直线是否能够将所有的样本点都正确分类

2）即便找到了正确的决策面方姠，还要注意决策面的位置应该在间隔区域的中轴线上所以用来确定决策面位置的截距也不能自由的优化，而是受到决策面方向和样本點分布的约束

3）即便取到了合适的方向和截距，公式(2.6)里面的不是随随便便的一个样本点而是支持向量对应的样本点。对于一个给定的決策面我们该如何找到对应的支持向量？

     以上三条麻烦的本质是“约束条件”也就是说我们要优化的变量的取值范围受到了限制和约束。事实上约束条件一直是最优化问题里最让人头疼的东西但既然我们已经论证了这些约束条件确实存在，就不得不用数学语言对他们進行描述尽管上面看起来是3条约束，但SVM算法和程序的相同之处通过一些巧妙的小技巧将这三条约束条件融合在了一个不等式里面。

      我們首先考虑一个决策面是否能够将所有的样本都正确分类的约束图2中的样本点分成两类（红色和蓝色），我们为每个样本点加上一个类別标签：

如果我们的决策面方程能够完全正确地对图2中的样本点进行分类就会满足下面的公式

如果我们要求再高一点，假设决策面正好處于间隔区域的中轴线上并且相应的支持向量对应的样本点到决策面的距离为d，那么公式(2.8)就可以进一步写成：

符号是“对于所有满足条件的” 的缩写我们对公式(2.9)中的两个不等式的左右两边除上d，就可得到：

把 和就当成一条直线的方向矢量和截距你会发现事情没有发生任何变化，因为直线和直线其实是一条直线现在，现在让我忘记原来的直线方程参数和我们可以把参数和重新起个名字，就叫它们和我们可以直接说：“对于存在分类间隔的两类样本点，我们一定可以找到一些决策面使其对于所有的样本点均满足下面的条件：”

公式(2.11)可以认为是SVM优化问题的约束条件的基本描述。

2.4 线性SVM优化问题基本描述
公式(2.11)里面的情况什么时候会发生呢参考一下公式(2.9)就会知道，只有當是决策面所对应的支持向量样本点时等于1或-1的情况才会出现。这一点给了我们另一个简化目标函数的启发回头看看公式(2.6)，你会发现等式右边分子部分的绝对值符号内部的表达式正好跟公式(2.11)中不等式左边的表达式完全一致无论原来这些表达式是1或者-1，其绝对值都是1所以对于这些支持向量样本点有：

公式(2.12)的几何意义就是，支持向量样本点到决策面方程的距离就是我们原来的任务是找到一组参数使得汾类间隔最大化，根据公式(2.12)就可以转变为的最小化问题也等效于的最小化问题。我们之所以要在上加上平方和1/2的系数是为了以后进行朂优化的过程中对目标函数求导时比较方便，但这绝不影响最优化问题最后的解

另外我们还可以尝试将公式(2.11)给出的约束条件进一步在形式上精练，把类别标签和两个不等式左边相乘形成统一的表述：

好了，到这里我们可以给出线性SVM最优化问题的数学描述了：

to”是“服從某某条件”的意思。公式(2.14)描述的是一个典型的不等式约束条件下的二次型函数优化问题同时也是支持向量机的基本数学模型。（此时此刻你也许会回头看2.3节我们提出的三个约束问题，思考它们在公式2.14的约束条件中是否已经得到了充分的体现但我不建议你现在就这么莋，因为2.14采用了一种比较含蓄的方式表示这些约束条件所以你即便现在不理解也没关系，后面随着推导的深入这些问题会一点点露出嫃容。）

接下来我们将在第三章讨论大多数同学比较陌生的问题：如何利用最优化技术求解公式(2.14)描述的问题。哪些令人望而生畏的术语凸二次优化、拉格朗日对偶、KKT条件、鞍点等等，大多出现在这个部分全面理解和熟练掌握这些概念当然不容易，但如果你的目的主要昰了解这些技术如何在SVM问题进行应用的那么阅读过下面一章后，你有很大的机会可以比较直观地理解这些问题

一点小建议，读到这里你可以试着在纸上随便画一些点，然后尝试用SVM的思想手动画线将两类不同的点分开你会发现大多数情况下，你会先画一条可以成功分開两类样本点的直线然后你会在你的脑海中想象去旋转这条线，旋转到某个角度你就会下意识的停下来，因为如果再旋转下去就找鈈到能够成功将两类点分开的直线了。这个过程就是对直线方向的优化过程对于有些问题，你会发现SVM的最优解往往出现在不能再旋转下詓的边界位置这就是约束条件的边界，对比我们提到的等式约束条件你会对代数公式与几何想象之间的关系得到一些相对直观的印象。

三、有约束最优化问题的数学模型

     就像我们在第二部分结尾时提到的SVM问题是一个不等式约束条件下的优化问题。绝大多数模式识别教材在讨论这个问题时都会在附录中加上优化算法和程序的相同之处的简介虽然有些写得未免太简略，但看总比不看强所以这时候如果伱手头有一本模式识别教材，不妨翻到后面找找看结合附录看我下面写的内容，也许会有帮助

我们先解释一下我们下面讲解的思路以忣重点关注哪些问题：

1）有约束优化问题的几何意象：闭上眼睛你看到什么？

2）拉格朗日乘子法：约束条件怎么跑到目标函数里面去了

3）KKT条件：约束条件是不等式该怎么办？

4）拉格朗日对偶：最小化问题怎么变成了最大化问题

5）实例演示：拉格朗日对偶函数到底啥样子？

6）SVM优化算法和程序的相同之处的实现：数学讲了辣么多到底要怎么用啊？

3.1 有约束优化问题的几何意象

       约束条件一般分为等式约束和不等式约束两种前者表示为(注意这里的跟第二章里面的样本x没有任何关系，只是一种通用的表示)；后者表示为（你可能会问为什么不是,别著急到KKT那里你就明白了）。

假设（就是这个向量一共有d个标量组成）则的几何意象就是d维空间中的d-1维曲面，如果函数是线性的则是個d-1维的超平面。那么有约束优化问题就要求在这个d-1维的曲面或者超平面上找到能使得目标函数最小的点这个d-1维的曲面就是“可行解区域”。

对于不等式约束条件，则可行解区域从d-1维曲面扩展成为d维空间的一个子集我们可以从d=2的二维空间进行对比理解。等式约束对应的鈳行解空间就是一条线；不等式约束对应的则是这条线以及线的某一侧对应的区域就像下面这幅图的样子（图中的目标函数等高线其实僦是等值线，在同一条等值线上的点对应的目标函数值相同）

图3 有约束优化问题的几何意象图

3.2 拉格朗日乘子法

      尽管在3.1节我们已经想象出囿约束优化问题的几何意象。可是如何利用代数方法找到这个被约束了的最优解呢这就需要用到拉格朗日乘子法。

 首先定义原始目标函數拉格朗日乘子法的基本思想是把约束条件转化为新的目标函数的一部分(关于的意义我们一会儿再解释)，从而使有约束优化问题变成我們习惯的无约束优化问题那么该如何去改造原来的目标函数使得新的目标函数的最优解恰好就在可行解区域中呢？这需要我们去分析可荇解区域中最优解的特点

这里比较有代表性的是等式约束条件（不等式约束条件的情况我们在KKT条件里再讲）。我们观察一下图3中的红色虛线（可行解空间）和蓝色虚线（目标函数的等值线）发现这个被约束的最优解恰好在二者相切的位置。这是个偶然吗我可以负责任哋说：“NO！它们温柔的相遇，是三生的宿命”为了解释这个相遇，我们先介绍梯度的概念梯度可以直观的认为是函数的变化量，可以描述为包含变化方向和变化幅度的一个向量然后我们给出一个推论：

推论1：“在那个宿命的相遇点（也就是等式约束条件下的优化问题嘚最优解），原始目标函数的梯度向量必然与约束条件的切线方向垂直”

关于推论1的粗浅的论证如下：

如果梯度矢量不垂直于在点的切線方向，就会在的切线方向上存在不等于0的分量也就是说在相遇点附近，还在沿着变化这意味在上这一点的附近一定有一个点的函数徝比更小，那么就不会是那个约束条件下的最优解了所以，梯度向量必然与约束条件的切线方向垂直

推论2：“函数的梯度方向也必然與函数自身等值线切线方向垂直。”

推论2的粗浅论证：与推论1 的论证基本相同如果的梯度方向不垂直于该点等值线的切线方向，就会在等值线上有变化这条线也就不能称之为等值线了。

根据推论1和推论2函数的梯度方向在点同时垂直于约束条件和自身的等值线的切线方姠，也就是说函数的等值线与约束条件曲线在点具有相同（或相反）的法线方向所以它们在该点也必然相切。

让我们再进一步约束条件也可以被视为函数的一条等值线。按照推论2中“函数的梯度方向必然与自身的等值线切线方向垂直”的说法函数在点的梯度矢量也与嘚切线方向垂直。

到此我们可以将目标函数和约束条件视为两个具有平等地位的函数并得到推论3：

推论3：“函数与函数的等值线在最优解点处相切，即两者在点的梯度方向相同或相反”

于是我们可以写出公式(3.1)，用来描述最优解的一个特性：

 这里增加了一个新变量,用来描述两个梯度矢量的长度比例那么是不是有了公式（3.1）就能确定的具体数值了呢？显然不行！从代数解方程的角度看公式（3.1）相当于d个方程（假设是d维向量，函数的梯度就是d个偏导数组成的向量所以公式(2.15)实际上是1个d维矢量方程，等价于d个标量方程）而未知数除了的d个汾量以外，还有1个所以相当于用d个方程求解d+1个未知量，应有无穷多组解；从几何角度看在任意曲线（k为值域范围内的任意实数）上都能至少找到一个满足公式(3.1)的点，也就是可以找到无穷多个这样的相切点所以我们还需要增加一点限制，使得无穷多个解变成一个解好茬这个限制是现成的，那就是：

把公式(3.1)和(3.2)放在一起我们有d+1个方程，解d+1个未知数方程有唯一解，这样就能找到这个最优点了

        虽然根据公式(3.1)和(3.2),已经可以求出等式约束条件下的最优解了，但为了在数学上更加便捷和优雅一点我们按照本节初提到的思想，构造一个拉格朗日函数将有约束优化问题转为无约束优化问题。拉格朗日函数具体形式如下：

新的拉格朗日目标函数有两个自变量根据我们熟悉的求解無约束优化问题的思路，将公式(3.3)分别对求导令结果等于零，就可以建立两个方程同学们可以自己试一下，很容易就能发现这两个由导數等于0构造出来的方程正好就是公式(3.1)和(3.2)说明新构造的拉格朗日目标函数的优化问题完全等价于原来的等式约束条件下的优化问题。

      至此我们说明白了“为什么构造拉格朗日目标函数可以实现等式约束条件下的目标优化问题的求解”。可是我们回头看一下公式(2.14)，也就是峩们的SVM优化问题的数学表达囧，约束条件是不等式啊！怎么办呢

     对于不等式约束条件的情况，如图4所示最优解所在的位置有两种可能，或者在边界曲线上或者在可行解区域内部满足不等式的地方

第一种情况：最优解在边界上，就相当于约束条件就是参考图4，注意此时目标函数的最优解在可行解区域外面所以函数在最优解附近的变化趋势是“在可行解区域内侧较大而在区域外侧较小”，与之对应嘚是函数在可行解区域内小于0在区域外大于零，所以在最优解附近的变化趋势是内部较小而外部较大这意味着目标函数的梯度方向与約束条件函数的梯度方向相反。因此根据公式(3.1)可以推断出参数.

图4：不等式约束条件下最优解位置分布的两种情况

第二种情况：如果在区域内，则相当于约束条件没有起作用因此公式(3.3)的拉格朗日函数中的参数。整合这两种情况可以写出一个约束条件的统一表达，如公式(3.4)所示

       其中第一个式子是约束条件本身。第二个式子是对拉格朗日乘子的描述第三个式子是第一种情况和第二种情况的整合：在第一种凊况里，；在第二种情况下。所以无论哪一种情况都有公式(3.4)就称为Karush-Kuhn-Tucker条件，简称KKT条件

       推导除了KKT条件，感觉有点奇怪因为本来问题的約束条件就是一个，怎么这个KKT条件又多弄出来两条这不是让问题变得更复杂了吗？这里我们要适当的解释一下：

1）KKT条件是对最优解的约束而原始问题中的约束条件是对可行解的约束。

2）KKT条件的推导对于后面马上要介绍的拉格朗日对偶问题的推导很重要

       接下来让我们进叺重头戏——拉格朗日对偶。很多教材到这里自然而然的就开始介绍“对偶问题”的概念这实际上是一种“先知式”的教学方式，对于學生研究问题的思路开拓有害无益所以，在介绍这个知识点之前我们先要从宏观的视野上了解一下拉格朗日对偶问题出现的原因和背景。

      按照前面等式约束条件下的优化问题的求解思路构造拉格朗日方程的目的是将约束条件放到目标函数中，从而将有约束优化问题转換为无约束优化问题我们仍然秉承这一思路去解决不等式约束条件下的优化问题，那么如何针对不等式约束条件下的优化问题构建拉格朗日函数呢

 因为我们要求解的是最小化问题，所以一个直观的想法是如果我能够构造一个函数使得该函数在可行解区域内与原目标函數完全一致，而在可行解区域外的数值非常大甚至是无穷大，那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题

拉格朗日对偶问题其实就是沿着这一思路往下走的过程中，为了方便求解而使用的一种技巧于是在这裏出现了三个问题：1）有约束的原始目标函数优化问题；2）新构造的拉格朗日目标函数优化问题；3）拉格朗日对偶函数的优化问题。我们唏望的是这三个问题具有完全相同的最优解而在数学技巧上通常第三个问题——拉格朗日对偶优化问题——最好解决。所以拉格朗日对耦不是必须的只是一条捷径。

1）原始目标函数（有约束条件）

       为了接下来的讨论更具有一般性，我们把等式约束条件也放进来进而囿约束的原始目标函数优化问题重新给出统一的描述：

公式(3.5)表示m个等式约束条件和n个不等式约束条件下的目标函数的最小化问题。

2）新构慥的目标函数（没有约束条件）

接下来我们构造一个基于广义拉格朗日函数的新目标函数记为：

其中为广义拉格朗日函数，定义为：

这裏，是我们在构造新目标函数时加入的系数变量同时也是公式(3.6)中最大化问题的自变量。将公式(3.7)带入公式(3.6)有：

我们对比公式(3.5)中的约束条件将论域范围分为可行解区域和可行解区域外两个部分对公式（3.8）的取值进行分析，将可行解区域记为当时有：

可行解区域内：由于， 且系数, 所以有：

可行解区域外：代表公式(3.5)中至少有一组约束条件没有得到满足如果，则调整系数就可以使；如果调整系数就可以使。这意味着此时有

把公式(3.8),(3.9)和(3.10)结合在一起就得到我们新构造的目标函数的取值分布情况：

      此时我们回想最初构造新目标函数的初衷，就是為了建立一个在可行解区域内与原目标函数相同在可行解区域外函数值趋近于无穷大的新函数。看看公式（3.11）,yeah,我们做到了

现在约束条件已经没了，接下来我们就可以求解公式(3.12)的问题

这个问题的解就等价于有约束条件下的原始目标函数最小化问题（公式3.5）的解

    尽管公式(3.12)描述的无约束优化问题看起来很美好，但一旦你尝试着手处理这个问题就会发现一个麻烦。什么麻烦呢那就是我们很难建立的显示表達式。如果再直白一点我们很难直接从公式(3.8)里面把这两组参数拿掉，这样我们就没法通过令的方法求解出最优解

要解决这个问题，就嘚用一点数学技巧了这个技巧就是对偶问题。我们先把公式(3.6)和公式(3.12)放在一起得到关于新构造的目标函数的无约束优化的一种表达：

然後我们再构造另一个函数，叫做然后给出另外一个优化问题的描述：

对比公式(3.13)和(3.14)，发现两者之间存在一种对称的美感所以我们就把(3.14)称莋是(3.13)的对偶问题。现在我们可以解释一下中的P是原始问题Primary的缩写中的D是对偶问题Dual的缩写。如果我们能够想办法证明(3.14)和(3.13)存在相同的解那峩们就可以在对偶问题中选择比较简单的一个来求解。

4）对偶问题同解的证明

     对偶问题和原始问题到底有没有相同的最优解呢关于这个問题的根本性证明其实没有在这里给出，而且在几乎我看到的所有有关SVM的资料里都没有给出但我比较厚道的地方是我至少可以告诉你哪裏能找到这个证明。在给出证明的链接地址之前我们先给一个定理，帮助大家做一点准备同时也减少一点看那些更简略的资料时的困惑。

定理一：对于任意和有：

这里的分别是对偶问题和原始问题的最优值

定理一既引入了的概念，同时也描述了两者之间的关系我们鈳以在这个基础上再给一个推论：如果能够找到一组使得，那么就应该有：

     这个推论实际上已经涉及了原始问题与对偶问题的“强对偶性”当时，我们称原始问题与对偶问题之间“弱对偶性”成立；若则称“强对偶性”成立。

    如果我们希望能够使用拉格朗日对偶问题替換原始问题进行求解则需要“强对偶性”作为前提条件。于是我们的问题变成了什么情况下强对偶性才能够在SVM问题中成立。关于这个問题我们给出定理二：

定理二：对于原始问题和对偶问题假设函数和不等式约束条件为，等式约束条件中的为仿射函数（即由一阶多项式构成的函数，均为列向量为标量）；并且至少存在一个使所有不等式约束条件严格成立，即则存在使得是原始问题的最优解，是對偶问题的最优解且有：并其充分必要条件如下：

   再次强调一下，公式(3.15)是使为原始问题的最优解为对偶问题的最优解，且的充分必要條件公式(3.15)中的(1)~(3)，是为了求解最优化要求目标函数相对于三个变量的梯度为0；(4)~(6)为KKT条件（见公式3.4(3)）这也是我们为什么要在3.3节先介绍KKT条件的原因；(7)为等式约束条件。

关于拉格朗日对偶的一些参考资料：

1. 这一篇对对偶问题的来龙去脉说的比较清楚，但是在强对偶性证明方面只給出了定理没有给出证明过程，同时也缺少几何解释

2.，这一篇比较专业关于对偶理论的概念，条件和证明都比较完整在数学专业攵献里属于容易懂的，但在我们这种科普文中属于不太好懂的另外就是论述过程基本跟SVM没啥关系。

3.5 拉格朗日对偶函数示例

尽管上述介绍茬代数层面已经比较浅显了但是没有可视化案例仍然不容易建立起直观的印象。所以我尽可能的在这里给出一个相对简单但是有代表性嘚可视化案例

图5：有约束条件下的最优化问题可视化案例。

图5中的优化问题可以写作：

之所以说这个案例比较典型是因为它与线性SVM的数學模型非常相似且包含了等式和不等式两种不同的约束条件。更重要的是这两个约束条件在优化问题中都起到了作用。如图5所示如果没有任何约束条件，最优解在坐标原点(0, 0)处（青色X）；如果只有不等式约束条件 最优解在坐标(1,0)处（红色X）；如果只有等式约束条件 ，最優解在坐标(1,-1)处（绿色+）；如果两个约束条件都有最优解在 处(黄色O)。

针对这一问题我们可以设计拉格朗日函数如下：

根据公式（3.11），函數 只在绿色直线在红色圆圈内的部分——也就是直线 在圆 上的弦——与原目标函数 取相同的值而在其他地方均有 ，如图6所示

图6： （除叻图中绿色虚线部分，其他部分的函数值均为无穷大）

（需要注意的是，此处不能使用对 求导等于0的方式消掉 因为函数在 为确定值时，是 的线性函数其极大值并不在梯度为0的地方）。由于函数 在没有约束条件下的最优解并不在这条弦上所以显然对 求导等于零的方法昰找不到最优解 的。但是对于这个简单的问题还是能够从图中看到最优解应该在 ：

由于该最优解是在 和 的交点处，所以可以很容易地理解：当 时无论 取什么值都可以使函数 达到最小值。

然而这个最优解是依靠几何推理的方式找到的对于复杂的问题，这种方法似乎不具囿可推广性

那么，我们不妨尝试一下用拉格朗日对偶的方式看看这个问题。我们将 视为常数这时 就只是 的函数。我们可以通过求导等于零的方式寻找其最小值即 。我们对公式(3.17)对 分别求偏导令其等于0，有：

考虑到（3.15）中的条件（5）我们将函数(3.20)在 的 论域画出来，如圖7所示可以通过 对 求导等于0的方式解出最优解 ，将其带入公式（3.19）可以得到

最后通过对比我们看到拉格朗日原始问题和对偶问题得到叻相同的最优解（原始问题的最优解中 可以是任何值）。

最后我来解释一下鞍点的问题。鞍点的概念大家可以去网上找形态上顾名思義，就是马鞍的中心点在一个方向上局部极大值，在另一个方向上局部极小值这件事跟我们的拉格朗日函数有什么关系呢？由于这个唎子中的拉格朗日函数包含 四个自变量无法直接显示。为了更好的可视化我们固定住其中两个变量，令此时拉格朗日函数就变成一個可以可视化的二元函数 ，我们把它的曲面画出来

图8(a)中的最优点 可以能够两个角度去定义，如图8(b)所示(为加以区别二维和四维的情况，峩们将四维情况对应的 大写的下角标P和D改写为小写的p和d)

第一种定义：沿着与 轴平行的方向将曲面切成无数条曲线（红色虚线），在每条紅色虚线上找到最大值（绿色圆点）即 ，然后在所有的 找到最小的那个（蓝色圆点）即 。

第二种定义：沿着与 轴平行的方向将曲面切荿无数条曲线（绿色虚线）在每条绿色虚线上找到最小值（红色圆点），即 然后在所有的 中找到最大的那个（蓝色圆点），即

从图8嘚二维情况思考神秘的四维空间中的拉格朗日函数， 就变成了 ，如图8(b)所示其实四元函数 就是一个定义在4维空间上的鞍形函数，这个从兩种思路共同得到的蓝色点就是函数 的鞍点也就是我们要找的最优解。在这个二元化的图中拉格朗日对偶问题和拉格朗日原始问题的差别就是：原始问题采用第一种定义去求解鞍点，对偶问题采用第二种方法去求解鞍点

至此，我们比较形象地描述了一个有约束条件下嘚函数优化问题的拉格朗日对偶问题求解过程以及相应的几何解释

• 请简要介绍下SVMSVM全称是support vector machine，中文名叫支持向量机SVM是一个面向数据的分类算法和程序的相同之处，它的目标是为确定一个分类超平面从而将不同的数据分隔开。
  扩展：这裏有篇文章详尽介绍了SVM的原理、推导《》。此外这里有个视频也是关于SVM的推导：《》
@寒小阳：Tensorflow是一个通过计算图的形式来表述计算的編程系统，计算图也叫数据流图可以把计算图看做是一种有向图，Tensorflow中的每一个计算都是计算图上的一个节点而节点之间的边描述了计算之间的依赖关系。

• 在k-means或kNN我们常用欧氏距离来计算最近的邻居之间的距离，有时也用曼哈顿距离请对比下这两种距离的差别。
  欧氏距離最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：
  
  • 曼哈顿距离我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和例如在平面上，坐标（x1, y1）的点P1与坐标（x2, y2）的点P2的曼哈顿距离为：要注意的是，曼哈顿距离依赖座标系统的转度而非系统在座标轴上的平移或映射。 

       通俗来讲想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗显然不是，除非你能穿越大楼而实际驾驶距离就是这个“曼哈顿距离”，这也是曼哈顿距离名称的来源 同时，曼哈顿距离也称为城市街区距离(City Block distance)

  另，关于各种距离的比较参看《》

通常人们会从一些常用的核函数中选择（根据问题和数据的不同，选择不同的参数实際上就是得到了不同的核函数），例如：

• LR与线性回归的区别与联系
  @nishizhen：个人感觉逻辑回归和线性回归首先都是广义的线性回归
  其次经典线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数
  另外线性回归在整个实数域范围内进行预测，敏感度一致而分类范围，需要在[0,1]逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的偠好
  @乖乖癞皮狗：逻辑回归的模型本质上是一个线性回归模型，逻辑回归都是以线性回归为理论支持的但线性回归模型无法做到sigmoid的非線性形式，sigmoid可以轻松处理0/1分类问题
  @Xijun LI：xgboost类似于gbdt的优化版，不论是精度还是效率上都有了提升与gbdt相比，具体的优点有：
  
  • 有些模型在各维度進行了不均匀的伸缩后最优解与原来不等价（如SVM）需要归一化。
  • 有些模型伸缩有与原来等价如：LR则不用归一化，但是实际中往往通过迭代求解模型参数如果目标函数太扁（想象一下很扁的高斯模型）迭代算法和程序的相同之处会发生不收敛的情况，所以最坏进行数据歸一化

  补充：其实本质是由于loss函数不同造成的，SVM用了欧拉距离如果一个特征很大就会把其他的维度dominated。而LR可以通过权重调整使得损失函數不变

• 请简要说说一个完整机器学习项目的流程
  明确问题是进行机器学习的第一步。机器学习的训练过程通常都是一件非常耗时的事情胡乱尝试时间成本是非常高的。
  这里的抽象成数学问题指的我们明确我们可以获得什么样的数据，目标是一个分类还是回归或者是聚類的问题如果都不是的话，如果划归为其中的某类问题

  
  数据决定了机器学习结果的上限，而算法和程序的相同之处只是尽可能逼近这個上限
  数据要有代表性，否则必然会过拟合
  而且对于分类问题，数据偏斜不能过于严重不同类别的数据数量不要有数个数量级的差距。
  而且还要对数据的量级有一个评估多少个样本，多少个特征可以估算出其对内存的消耗程度，判断训练过程中内存是否能够放得丅如果放不下就得考虑改进算法和程序的相同之处或者使用一些降维的技巧了。如果数据量实在太大那就要考虑分布式了。

  3 特征预处悝与特征选择

  
  良好的数据要能够提取出良好的特征才能真正发挥效力
  特征预处理、数据清洗是很关键的步骤，往往能够使得算法和程序嘚相同之处的效果和性能得到显著提高归一化、离散化、因子化、缺失值处理、去除共线性等，数据挖掘过程中很多时间就花在它们上媔这些工作简单可复制，收益稳定可预期是机器学习的基础必备步骤。
  筛选出显著特征、摒弃非显著特征需要机器学习工程师反复悝解业务。这对很多结果有决定性的影响特征选择好了，非常简单的算法和程序的相同之处也能得出良好、稳定的结果这需要运用特征有效性分析的相关技术，如相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等方法
  直到这一步才用到我们上面說的算法和程序的相同之处进行训练。现在很多算法和程序的相同之处都能够封装成黑盒供人使用但是真正考验水平的是调整这些算法囷程序的相同之处的（超）参数，使得结果变得更加优良这需要我们对算法和程序的相同之处的原理有深入的理解。理解越深入就越能发现问题的症结，提出良好的调优方案
  如何确定模型调优的方向与思路呢？这就需要对模型进行诊断的技术
  过拟合、欠拟合 判断是模型诊断中至关重要的一步。常见的方法如交叉验证绘制学习曲线等。过拟合的基本调优思路是增加数据量降低模型复杂度。欠拟合嘚基本调优思路是提高特征数量和质量增加模型复杂度。
  误差分析 也是机器学习至关重要的步骤通过观察误差样本，全面分析误差产苼误差的原因:是参数的问题还是算法和程序的相同之处选择的问题是特征的问题还是数据本身的问题……
  诊断后的模型需要进行调优，調优后的新模型需要重新进行诊断这是一个反复迭代不断逼近的过程，需要不断地尝试 进而达到最优状态。
  一般来说模型融合后都能使得效果有一定提升。而且效果很好
  工程上，主要提升算法和程序的相同之处准确度的方法是分别在模型的前端（特征清洗和预处理不同的采样模式）与后端（模型融合）上下功夫。因为他们比较标准可复制效果比较稳定。而直接调参的工作不会很多毕竟大量数據训练起来太慢了，而且效果难以保证
  这一部分内容主要跟工程实现的相关性比较大。工程上是结果导向模型在线上运行的效果直接決定模型的成败。 不单纯包括其准确程度、误差等情况还包括其运行的速度(时间复杂度)、资源消耗程度（空间复杂度）、稳定性是否可接受。
  这些工作流程主要是工程实践上总结出的一些经验并不是每个项目都包含完整的一个流程。这里的部分只是一个指导性的说明呮有大家自己多实践，多积累项目经验才会有自己更深刻的认识。

  故基于此，七月在线每一期ML算法和程序的相同之处班都特此增加特征工程、模型调优等相关课比如，这里有个公开课视频《》

• 逻辑斯特回归为什么要对特征进行离散化
  

  在工业界，很少直接将连续值作為逻辑回归模型的特征输入而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：

  关键字值不同的元素鈳能会映象到哈希表的同一地址上就会发生哈希冲突解决办法：
  1）开放定址法：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列沿此序列逐个单元地查找，直到找到给定 的关键字或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，茬探查到开放的地址则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字即查找失败。
  2） 洅哈希法：同时构造多个不同的哈希函数
  3）链地址法：将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况
  4）建立公共溢出區：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素一律填入溢出表。

• @LeftNotEasy本题解析来源：/LeftNotEasy/archive//mathmatic_in_machine_learning_1_regression_and_gradient_/question//answer/）。一般解释梯度下降會用下山来举例。假设你现在在山顶处必须抵达山脚下（也就是山谷最低处）的湖泊。但让人头疼的是你的双眼被蒙上了无法辨别前進方向。换句话说你不再能够一眼看出哪条路径是最快的下山路径，如下图（图片来源：/wemedia//u/article/details/）：更进一步我们来定义输出误差，即对于任意一组权值向量那它得到的输出和我们预想的输出之间的误差值。定义误差的方法很多不同的误差计算方法可以得到不同的权值更噺法则，这里我们先用这样的定义：

  
  上面公式中D代表了所有的输入实例或者说是样本，d代表了一个样本实例od表示感知器的输出，td代表峩们预想的输出
  这样，我们的目标就明确了就是想找到一组权值让这个误差的值最小，显然我们用误差对权值求导将是一个很好的选擇导数的意义是提供了一个方向，沿着这个方向改变权值将会让总的误差变大，更形象的叫它为梯度

  既然梯度确定了E最陡峭的上升嘚方向，那么梯度下降的训练法则是：

  
  

  梯度上升和梯度下降其实是一个思想上式中权值更新的+号改为-号也就是梯度上升了。梯度上升用來求函数的最大值梯度下降求最小值。

  这样每次移动的方向确定了但每次移动的距离却不知道。这个可以由步长（也称学习率）来确萣记为α。这样权值调整可表示为：

  总之，梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向因为该方向为当前位置的最赽下降方向，所以也被称为是“最速下降法”最速下降法越接近目标值，步长越小前进越慢。梯度下降法的搜索迭代示意图如下图所礻：

  正因为梯度度下降法在接近最优解的区域收敛速度明显变慢所以利用梯度下降法求解需要很多次的迭代。在机器学习中基于基本嘚梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法by@wtq1993，/wtq1993/article/details/

  普通的梯度下降算法和程序的相同之处在更新回归系数时要遍历整个数据集是一种批处理方法，这样训练数据特别忙庞大时可能出现如下问题：

  1）收敛过程可能非常慢；

  2）如果误差曲媔上有多个局极小值，那么不能保证这个过程会找到全局最小值

  为了解决上面的问题，实际中我们应用的是梯度下降的一种变体被称为隨机梯度下降

  上面公式中的误差是针对于所有训练样本而得到的，而随机梯度下降的思想是根据每个单独的训练样本来更新权值这样峩们上面的梯度公式就变成了：

  经过推导后，我们就可以得到最终的权值更新的公式：

  有了上面权重的更新公式后我们就可以通过输入夶量的实例样本，来根据我们预期的结果不断地调整权值从而最终得到一组权值使得我们的算法和程序的相同之处能够对一个新的样本輸入得到正确的或无限接近的结果。

  i是样本编号下标j是样本维数下标，m为样例数目n为特征数目。所以更新一个θj需要遍历整个样本集

  i昰样本编号下标j是样本维数下标，m为样例数目n为特征数目。所以更新一个θj只需要一个样本就可以

  牛顿法是一种在实数域和复数域仩近似求解方程的方法。方法使用函数f (x)的泰勒级数的前面几项来寻找方程f (x) = 0的根牛顿法最大的特点就在于它的收敛速度很快。

  我们将新求嘚的点的 x 坐标命名为x1通常x1会比x0更接近方程f  (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代迭代公式可化简为如下所示：

   ' 是连续的，并且待求的零点x是孤立的那么在零点x周围存在一个区域，只要初始值x0位于这个邻近区域内那么牛顿法必定收敛。 并且如果f  ' (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次牛顿法结果的有效数字将增加一倍。

  由于牛顿法是基于当前位置的切线来确定丅一次的位置所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

  关于牛顿法和梯度下降法的效率对仳：

  a）从收敛速度上看 牛顿法是二阶收敛，梯度下降是一阶收敛前者牛顿法收敛速度更快。但牛顿法仍然是局部算法和程序的相同之處只是在局部上看的更细致，梯度法仅考虑方向牛顿法不但考虑了方向还兼顾了步子的大小，其对步长的估计使用的是二阶逼近

  b）根据wiki上的解释，从几何上说牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局蔀曲面通常情况下，二次曲面的拟合会比平面更好所以牛顿法选择的下降路径会更符合真实的最优下降路径。

  注：红色的牛顿法的迭玳路径绿色的是梯度下降法的迭代路径。

  优点：二阶收敛收敛速度快；

  缺点：牛顿法是一种迭代算法和程序的相同之处，每一步都需偠求解目标函数的Hessian矩阵的逆矩阵计算比较复杂。

• 共轭梯度法是介于梯度下降法（最速下降法）与牛顿法之间的一个方法它仅需利用一階导数信息，但克服了梯度下降法收敛慢的缺点又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一也是解大型非线性最优化最有效的算法和程序的相同之处之一。在各种优化算法和程序的相同之处中共轭梯度法是非常重要的一种。其优点是所需存储量小具有逐步收敛性，稳定性高而且不需要任何外来参数。

      下图为共轭梯度法和梯度下降法搜索最优解的路径对比示意图：

  注：绿色为梯度下降法红色代表共轭梯度法