SVM(支持向量机)（一）

（整理自AndrewNG的课件，转载请注明。整理者：华科小涛@http://www.cnblogs.com/hust-ghtao/）

SVM（Support Vector Machines）系列会循序渐进地给大家讲解支持向量机，内容有点多，打算分四篇博文介绍。SVM是最好的有监督学习算法之一，它有很多忠实的fans，执着地认为它就是最好的。为了讲述SVM，我们从线性可分数据开始（后来会去掉线性可分的约束），引出Margin（间隔）的概念；接下来会讨论optimal margin classifier（最忧间隔分类器），过渡到拉格朗日的对偶问题；我们还会介绍kernels（核函数），通过它SVM可以解决高维问题（甚至是无限维）；最后我们会介绍SMO算法，这是实现SVM的有效算法。

1 函数间隔(function margin)和几何间隔(geometric margin)

1.1直观理解

为了引出间隔的概念，我们先来回顾一下logistic 回归，Logistic回归目的是从特征学习出一个0/1分类模型，而这个模型是将特性的线性组合作为自变量，由于自变量的取值范围是负无穷到正无穷。因此，使用logistic函数（或称作sigmoid函数）将自变量映射到(0,1)上，映射后的值被认为是属于y=1的概率。

假设函数：

，其中是的特征向量，是logistic函数。 的函数图像如下：

，可以看到将从负无穷到正无穷映射到。

我们令：表示输入变量被映射为y=1的概率。

对于输入变量，如果，也就是，我们则判断y=1。否则，判断y=0。

考虑一个y=1对应的样本，越大，则越大，越接近1，那么我就对我们的判断更加自信，换言之，y=1的置信度越大。直觉上理解，要想让我们的Logistic回归置信度很高，应该满足以下下条件：

和。

这里是通过训练集学习出来的边界条件，也就是对于任意的输入变量，的值离边界都很远，我们认为这是一个很好的分类器，我们就将这个差值定义为函数间隔。

为了更好的理解，请看下图：

，图中的直线是通过算法学习出的判决边界，新输入三点A、B、C，要求我们对其进行分类，显然都可以进行分类。但是若要问你那个点被正确分类的置信度最大，是A，因为它离边界的距离最远，B次之，我们对C的分类的置信度是最低的。这里的点到判决直线的距离就是几何间隔。

1.2 符号定义

上面只是直观地介绍了函数间隔和几何间隔，为了更加正式地定义间隔的概念，我们需要重新定义一下有关的Notation：

在明确一下需要解决的问题：对于二值分类问题，输入变量，目标变量是类的标号，确定线性分类器。与Logistic回归不同，我们用表示类别的标号，用表示分类器：，其中，其中

，对于给定的通过这样的假设函数，输出变量就是1或-1，而省略了Logistic回归计算概率的中间过程。

1.3 正式定义

对于一个给定的训练样本，我们定义的函数间隔：。

当时，为了使函数间隔尽量大，要为正且尽量大；当时，为了使函数间隔尽量大，要为负且尽量小。

另外，对于一个输入样本，若，我们认为分类正确。

我们刚才定义的函数价格是针对单个样本的，现在定义对于整个训练集的函数间隔：

，就是距离判决边界最近的点对应的函数间隔。

那我们用函数间隔来衡量线性分类器的性能怎么样？假如我们的分类面为，那么把缩放任意倍数，分类面不会发生变化，但函数间隔却发生了变化。例如：，分类面仍为为，但函数间隔却变为，扩大了2倍，所以用函数间隔来衡量分类器并不合理。为此引入几何间隔的概念。

先看下图：

，样本点的几何间隔就是样本点到分类面（分类线）的几何距离，如图中线段AB。

求解AB乃简单的几何问题：已知，用表示几何间隔，w是分类面的法向量，则以求得B点，又因为B点在分类面上，满足方程：，所以有：

，

解方程得到：

。

这是对于的情况，对于我们得到

，写到一起：

。

注意两点：（1）当时，几何间隔和函数间隔相等；

（2）等比缩放，几何间隔不变。

同样定义对与整个训练集的集合间隔：

，就是距离判决边界最近的点对应的几何间隔。

2 最优间隔分类器（The optimal margin classifier）

对于给定的样本集，我们假设其是线性可分的，就是可以找到合适的超平面（hyperplane），将正类和负类正确的分开。我们如何找到这个超平面，从而使对于整个训练集的几何间隔最大，则优化问题可描述如下：

，目标函数是使几何间隔最大化，约束为全局的几何间隔应该是所有样本几何间隔中最小的，使

的值为几何间隔。到此分类器的模型已经确定，就差求参数了。

但是有点问题，是个非凸的约束，不利于用现有的工具求解，需要将此约束转化一下，于是有了如下形式：

，就是将目标函数和约束都转换成了关于函数间隔的，但注意这只是形式上的转换，我们的目的还是最大几何间隔。

约束是凸约束啦，糟糕，目标函数又非凸啦，那就再转换一下。假如我们求得了，和对应的几何间隔，我们缩放不会改变分类面和几何间隔，就是说对分类性能没有影响。那我们就可以调整，令函数间隔，不会影响计算结果，目标函数

，使目标函数最大化等价于使最小化，所以将问题转化为：

。这就是最优间隔分类器的最终形式。目标函数和约束都是凸函数啦，可以利用QP软件来求解啦。

总结一下：这部分的思路还是比较清楚，为了引出间隔的概念，先回顾了Logistic回归，并给了函数间隔和几何间隔的概念。以几何间隔为目标函数学习分类面，给出最优分类器的基本形式，但不利于求解，所以经过两部形式转换，将目标和约束都转换成凸函数，可用QP求解。注意，这不是我们的终极目的，接下来我们还会介绍更优的算法来求解最优间隔分类器的问题。