如果你是一名模式识别专业的研究生，又或者你是机器学习爱好者，SVM是一个你避不开的问题。如果你只是有一堆数据需要SVM帮你处理一下，那么无论是Matlab的SVM工具箱，LIBSVM还是python框架下的SciKit Learn都可以提供方便快捷的解决方案。但如果你要追求的不仅仅是会用，还希望挑战一下“理解”这个层次，那么你就需要面对一大堆你可能从来没听过的名词，比如：非线性约束条件下的最优化、KKT条件、拉格朗日对偶、最大间隔、最优下界、核函数等等。
以下我会分为四个步骤对最基础的线性SVM问题加以介绍，分别是1）问题原型，2）数学模型，3）最优化求解，4）几何解释。我尽可能用最简单的语言和最基本的数学知识对上述问题进行介绍。
一、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算法的数学建模”。
二、线性SVM算法的数学建模
一个最优化问题通常有两个最基本的因素：1）目标函数，也就是你希望什么东西的什么指标达到最好；2）优化对象，你期望通过改变哪些因素来使你的目标函数达到最优。在线性SVM算法中，目标函数显然就是那个“分类间隔”，而优化对象则是决策面。所以要对SVM问题进行数学建模，首先要对上述两个对象（“分类间隔”和“决策面”）进行数学描述。按照一般的思维习惯，我们先描述决策面。
2.1 决策面方程
2.2 分类“间隔”的计算模型
间隔的大小实际上就是支持向量对应的样本点到决策面的距离的二倍，如图2所示。
图2 分类间隔计算
所以分类间隔计算似乎相当简单，无非就是点到直线的距离公式。如果你想要回忆高中老师在黑板上推导的过程，可以随便在百度文库里搜索关键词“点到直线距离推导公式”，你会得到至少6、7种推导方法。但这里，请原谅我给出一个简单的公式如下：
三、有约束最优化问题的数学模型
就像我们在第二部分结尾时提到的，SVM问题是一个不等式约束条件下的优化问题。绝大多数模式识别教材在讨论这个问题时都会在附录中加上优化算法的简介，虽然有些写得未免太简略，但看总比不看强，所以这时候如果你手头有一本模式识别教材，不妨翻到后面找找看。结合附录看我下面写的内容，也许会有帮助。
我们先解释一下我们下面讲解的思路以及重点关注哪些问题：
1）有约束优化问题的几何意象：闭上眼睛你看到什么？
2）拉格朗日乘子法：约束条件怎么跑到目标函数里面去了？
3）KKT条件：约束条件是不等式该怎么办？
4）拉格朗日对偶：最小化问题怎么变成了最大化问题？
5）实例演示：拉格朗日对偶函数到底啥样子？
6）SVM优化算法的实现：数学讲了辣么多，到底要怎么用啊？
3.1 有约束优化问题的几何意象
图3 有约束优化问题的几何意象图
3.2 拉格朗日乘子法
.
图4：不等式约束条件下最优解位置分布的两种情况
定理二的证明详见 《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 拉格朗日对偶函数示例
尽管上述介绍在代数层面已经比较浅显了，但是没有可视化案例仍然不容易建立起直观的印象。所以我尽可能的在这里给出一个相对简单但是有代表性的可视化案例。
图5：有约束条件下的最优化问题可视化案例。
