最近因为要在实验室大组例会上做报告的原因，需要讲一下SVM算法，花了两个星期仔细研究了SVM算法，也用libsvm包做了些实验。SVM是目前最重要的机器学习算法之一，这篇博客会着重讲数学原理，泛泛而谈的东西网上太多了，看了没啥用，当然肯定会介绍一下当前的研究热点。可能很多同学都知道这个技术，甚至多次使用过，但是我敢说一半以上的同学都不太清楚原理，甚至支持向量机分为三种：线性可分，线性不可分，非线性可分，为啥要叫支持向量机，都不清楚，我不会笑话你，因为几乎两周前我也不知道。我会尽量简单的介绍SVM中的数学原理，相信你一定能看懂，哪怕你的线性代数曾经挂过科，Let's have a try。

SVM简介

• SVM它本质上即是一个二类分类方法，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大化使它有别于感知机。对于现行可分的训练集，感知机的分离超平面是不惟一的，有无穷多个。依赖于初始值(w,b)的选择，也依赖于迭代过程中误分类点的选择顺序，如果想得到唯一的超平面，需要对分离超平面增加约束条件。而这正是支持向量机的想法。当训练集线性不可分时，感知及学习算法不收敛，迭代结果会发生震荡。这时就需要借助核方法来解决问题了。
• 支持向量机还包括核技巧，这使它成为实质上的非线性分类器。
• 支持向量机的学习策略是间隔最大化，可形式化为一个求解凸二次规划的问题。
• 给定线性可分训练数据集，通过间隔最大化学习到分离超平面：

                                w.x + b=0

以及相应的分类决策函数：

                                f(x)=sign(w.x+b)

如下图

SVM的原理

在讲SVM的模型之前，首先要明确几个概念。

函数间隔和几何间隔

对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。即，既要将正负实例点分开，又要对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。这样的超平面应该对未知的新实例有较好的分类预测能力。

如上图，红色和黑色的平面都能将 红/蓝两类分开，但红色平面更好，因为它使得离它最近的样本点的距离更大了，用它来分类有更大的确信度。

• 函数间隔

                    ŕi=yi(w.xi+b)
                    ŕ=min  ŕi               i=1,2..N

• 几何间隔

  

可以看到函数间隔是变化的，它随着w，b值不同而不同，如果w，b成比例增加，分离超平面没有变，但函数间隔却变了。而几何间隔则不同，它是固定的，是将函数间隔用||w||归一化的结果。

最大间隔法

我们的目的可以表示为下面的约束最优化问题： 约束条件表示超平面（w,b）关于每个训练样本的几何间隔至少是 r。考虑到几何间隔和函数间隔的关系，可将上式改写成： 函数间隔r'的取值并不影响最优化问题的求解。于是可取r'=1。注意到 最大化和最小化 是等价的。于是就得到下面的线性可分支持向 量机学习的最优化问题：

支持向量

训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。即满足约束条件的点： 在决定分离超平面的时候，只有支持向量起作用，如果移动支持向量将改变所求的解，但是移动间隔之外的点，不会改变解.支持向量的个数一般很少，所以支持向量机由很少的“重要的”训练样本确定。这也是为什么成为支持向量机算法的原因，这里的机可以理解成为算法的意思，比如感知机，玻尔兹曼机等等。通过下图可以清晰的看到支持向量对于决定分离超平面的决定作用。

搞清楚函数间隔，几何间隔，最大间隔法，支持向量以及我们的目标函数之后，就可以来看看SVM的基本模型吧。

SVM的三种模型

根据数据集是否线性可分，可以将SVM分成线性可分支持向量机，线性支持向量机，非线性支持向量机。

线性可分支持向量机与硬间隔最大化

通过构建拉格朗日函数将原始问题转化为对偶问题： 求解：

代入原式，得对偶目标函数为： 求解最优解a，再根据a求解 w,b.

并选择一个a的正分量ai，计算：

正分量ai对应的样本点(xi,yi)称为支持向量。 求的分类超平面： 分类决策函数：

分类决策函数只依赖于输入x和训练样本输入的内积。 这种算法称为线性可分支持向量机的对偶学习算法，是线性可分支持向量机学习的基本算法。

线性支持向量机与软间隔最大化

通常，训练数据中有一些特异点（outlier），它们的存在导致训练集是不可分的，但是将它们除去之后，训练集变得线性可分。 原来的约束条件：

考虑到outlier的存在，引入松弛变量： 引入罚项：

目标函数的两层含义： 间隔尽量大，同时使误分类点的个数尽量小，C是二者的调和系数。 如上图，被虚线圆圈起来的蓝色点就是一个outlier，我们可以引入松弛变量，将它划分位红色类，但是要加上一个惩罚项。

非线性支持向量机

并不是所有的数据集都是线性可分的，如果能用一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。 用线性分类方法求解非线性问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核计巧就是这样的方法。这要归功于核方法——除了SVM之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。

如上图，我们虽然不能一个线性超平面来将红/蓝两类分开，但是可以用一个曲面来分，这时可以将样本点映射到一个高维空间，如下：

设X为输入空间，H为特征空间，如果存在一个从X到H的映射：

                            ϕ(x)：X->H

使得所有x,z 属于X，都有： 则称K(x,z)为核函数， ϕ(x)为映射函数。

核函数的想法是，在学习中只定义核函数，而不显示的定义映射函数，因为直接计算核函数K(x,z)比较容易，而通过ϕ(x)，ϕ(z)计算K(x,z)并不容易，而且没有必要，它巧妙的利用了线性分类学习方法与核函数解决非线性问题的。H和ϕ(x)的取法不唯一。实际应用中往往依赖领域知识直接选择核函数，并通过实验验证选择的有效性。

常用的核函数有多项式核函数，高斯核函数等.

将输入空间映射到特征空间后的目标函数为：

用代替上式的ϕ(x). ϕ(z).

用求解方法跟线性可分SVM的解法相同，即求得最优解：
选择a的一个正分量ai，计算:

构造决策函数：

SMO算法

上面所讲的都是SVM建模方法，模型建出来之后需要有效且收敛快的算法来求解，求解SVM的算法有很多，但是最流行的是SMO算法。序列最小最优化算法（SMO）是一种启发式算法，由Microsoft Research的John C.Platt在1998年提出，并成为最快的二次规划优化算法。

其基本思想是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，一个变量是违反KKT条件最严重的那一个，另外一个由约束条件自动确定，并对子问题进行解析求解，直到所有变量满足KKT条件为止，因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数多，但是总体上很高效。

SMO算法分为两部分：求解两个变量二次规划的解析方法和选择变量的启发式算法。 这个算法的原理稍显复杂，我推荐你去看《统计学习方法》Page124页，上面有详细的描述。

SVM的多类别分类方法

支持向量机是针对二类分类问题提出的，如何扩展到多类别分类是SVM研究的重要内容。主要有3种方法： 设训练样本分属于c1,c2,...,ck个类别

• 逐一鉴别法：构造k个SVM分类器，选取判别函数值最大所对应的类别为测试数据的类别.
• 一一区分法：构造k(k-1)/2个分类器，即每两类之间构成一个SVM，累计各类别的得分, 选择得分最高者所对应的类别为测试数据的类别.
• M-ary法.

下面是我做的一个文本分类的实验，分别来叙述这几种方法。 我的问题是，我有四类文档，分别是娱乐，体育，财经，政治类，用A，B，C，D来标记。我取来自每一类的各200篇文章作为训练集，学习SVM来对新的文章进行分类。算法的代码全部来自《机器学习实战》这本书。

一一区分法：

如上图，我对每两类都构造一个SVM，得到4(4-1)/2=6个SVM，然后将输入经过每一个SVM，按照投票原则决定最后的分类。

Mary法：

为了克服一一区分法分类器较多的缺点的，有了Mary法。如上图，它只需要构造两个SVM，第一个SVM将A，B看作一类，将C，D看作一类，第二个SVM将A，C看作一类，将B，D看作一类 ，当输入分别通过两个SVM之后，可以通过如图的映射关系分出它的类别。 Mary法的缺点是，分类的结果依赖于构造SVM的方案，比如如果在上面的方案中这样构造：

• 分类器1: AD/BC
• 分类器2：AC/BD

分类的结果可能跟图中的分类结果不同。因此Mary法需要较好的SVM构造策略，好的经验是将根据先验知识将相对较相似的类分做一类，把相对差别大的类分做另一类。

调参方法

交叉验证：

在给定的样本中，拿出大部分样本进行训练，留小部分样本进行验证。常用的交叉验证方法有:Holdout验证、K折交叉验证和留一验证。

网格法寻找最优参数：

根据SVM的原理以及实际的实验结果可以分析得到，对分类准确率影响比较大的参数是惩罚参数C以及径向基核函数里的参数γ。为了对这两个参数同时进行调整以达到最好的效果，我们可以使用网格法寻优。由于C与γ之间没有依存关系，故可以使用两层循环的方式，将一定范围内的C与γ遍历，选择准确率最高的一组数据。并且根据经验可知，C与γ以指数形式变化会得到较好的效果，比如:

小结

最后我用一段我自己的话来对SVM做个总结。很浅显，但包括了SVM最关键的东西。

SVM它本质上即是一个分类方法，用w^T+b定义分类函数，于是求w、b，为寻最大间隔，引出1/2||w||^2，继而引入拉格朗日因子，化为对拉格朗日乘子a的求解（求解过程中会涉及到一系列最优化或凸二次规划等问题），如此，求w.b与求a等价，而a的求解可以用一种快速学习算法SMO，至于核函数，是为处理非线性情况，若直接映射到高维计算恐维度爆炸，故在低维计算，等效高维表现。

最后副一张SVM与逻辑斯蒂回归，决策树分类效果的图，同学们感受一下。

这篇文章仅仅知识抛砖引玉，让你对于SVM有个概念，同时又能对它的原理说的出个大概。如果你真的以为这就够了，那你真是too young了啊。 想了解更多去看看统计学习方法吧，至少我还没有说清楚什么是对偶问题，为啥要转化成对偶问题，什么是KKT条件，以及很重要的SMO算法是怎么实现的，这些内容都不容你错过。

Happy ending.