零基础入门SVM支持向量机

问题导读
1.本文基础的线性SVM问题分为哪四个步骤？
2.支持向量机主要用于解决模式识别领域中什么问题？
3.SVM属于是否属于有监督学习算法？
4.什么是支持向量？
5.如何把SVM变成用数学语言描述的最优化问题模型？
6.一个最优化问题通常有两个最基本的因素？






如果你是一名模式识别专业的研究生，又或者你是机器学习爱好者，SVM是一个你避不开的问题。如果你只是有一堆数据需要SVM帮你处理一下，那么无论是Matlab的SVM工具箱，LIBSVM还是python框架下的SciKit Learn都可以提供方便快捷的解决方案。但如果你要追求的不仅仅是会用，还希望挑战一下“理解”这个层次，那么你就需要面对一大堆你可能从来没听过的名词，比如：非线性约束条件下的最优化、KKT条件、拉格朗日对偶、最大间隔、最优下界、核函数等等。这些名词往往会跟随一大堆天书一般的公式。如果你稍微有一点数学基础，那么单个公式你可能看得明白，但是怎么从一个公式跳到另一个公式就让人十分费解了，而最让人糊涂的其实并不是公式推导，而是如果把这些公式和你脑子里空间构想联系起来。

我本人就是上述问题的受害者之一。我翻阅了很多关于SVM的书籍和资料，但没有找到一份材料能够在公式推导、理论介绍，系统分析、变量说明、代数和几何意义的解释等方面完整地对SVM加以分析和说明的。换言之，对于普通的一年级非数学专业的研究生而言，要想看懂SVM需要搜集很多资料，然后对照阅读和深入思考，才可能比较透彻地理解SVM算法。由于我本人也在东北大学教授面向一年级硕士研究生的《模式识别技术与应用》课程，因此希望能总结出一份相对完整、简单和透彻的关于SVM算法的介绍文字，以便学生能够快速准确地理解SVM算法。

以下我会分为四个步骤对最基础的线性SVM问题加以介绍，分别是
1）问题原型，
2）数学模型，
3）最优化求解，
4）几何解释。

我尽可能用最简单的语言和最基本的数学知识对上述问题进行介绍，希望能对困惑于SVM算法的学生有所帮助。

由于个人时间有限，只能找空闲的时间更新，速度会比较慢，请大家谅解。



一、SVM算法要解决什么问题

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





图1 二分类问题描述


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

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

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

*关于“决策面”，为什么叫决策面，而不是决策线？好吧，在图1里，样本是二维空间中的点，也就是数据的维度是2，因此1维的直线可以分开它们。但是在更加一般的情况下，样本点的维度是n，则将它们分开的决策面的维度就是n-1维的超平面（可以想象一下3维空间中的点集被平面分开），所以叫“决策面”更加具有普适性，或者你可以认为直线是决策面的一个特例。


二、线性SVM算法的数学建模
一个最优化问题通常有两个最基本的因素：
1）目标函数，也就是你希望什么东西的什么指标达到最好；

2）优化对象，你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中，目标函数显然就是那个“分类间隔”，而优化对象则是决策面。所以要对SVM问题进行数学建模，首先要对上述两个对象（“分类间隔”和“决策面”）进行数学描述。按照一般的思维习惯，我们先描述决策面。

2.1 决策面方程

（请注意，以下的描述对于线性代数及格的同学可能显得比较啰嗦，但请你们照顾一下用高数课治疗失眠的同学们。）

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








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

我们在第一章里介绍过分类间隔的定义及其直观的几何意义。间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍，如图2所示。




图2 分类间隔计算

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





2.3 约束条件



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




2.4 线性SVM优化问题基本描述

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

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

come from future______by Chen

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

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

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

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

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

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

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

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

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

6）SVM优化算法的实现：数学讲了辣么多，到底要怎么用啊？

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




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

3.2 拉格朗日乘子法



1）最优解的特点分析




2）构造拉格朗日函数


3.3 KKT条件




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

3.4 拉格朗日对偶

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

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

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

拉格朗日对偶问题其实就是沿着这一思路往下走的过程中，为了方便求解而使用的一种技巧。于是在这里出现了三个问题：

1）有约束的原始目标函数优化问题；

2）新构造的拉格朗日目标函数优化问题；

3）拉格朗日对偶函数的优化问题。我们希望的是这三个问题具有完全相同的最优解，而在数学技巧上通常第三个问题——拉格朗日对偶优化问题——最好解决。所以拉格朗日对偶不是必须的，只是一条捷径。

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

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

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

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




3）对偶问题



4）对偶问题同解的证明

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

定理二的证明详见 《Convex Optimization》， by Boyd and Vandenberghe. Page-234, 5.3.2节。http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

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

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

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

3.5 拉格朗日对偶函数示例

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

四、线性SVM优化问题求解

4.1 基于拉格朗日乘子法的线性SVM优化问题模型

从第三章开始，我们花了相当长的时间来介绍优化技术。目的是为线性SVM问题的求解打好数学基础。接下来，让我们把目光转回公式(2.14)描述的线性SVM问题的基本模型，为了方便大家阅读，这里重新给出公式（2.14）








原文链接
作者：耳东陈

SVM支持向量机~~~