SVM支持向量机

1 SVM简介

SVM(support vector machine)简单的说是一个分类器，并且是二类分类器。

• Vector 通俗说就是点，或是数据。
• Machine 也就是classifier，也就是分类器。

SVM作为传统机器学习的一个非常重要的分类算法，它是一种通用的前馈网络类型，最早是由Vladimir N.Vapnik 和 Alexey Ya.Chervonenkis在1963年提出，目前的版本（soft margin）是Corinna Cortes 和 Vapnik在1993年提出，1995年发表。深度学习（2012）出现之前，SVM被认为是机器学习中近十几年最成功表现最好的算法。

2 SVM原理分析

2.1 快速理解SVM原理

很多讲解SVM的书籍都是从原理开始讲解，如果没有相关知识的铺垫，理解起来还是比较吃力的，以下的一个例子可以让我们对SVM快速建立一个认知。

给定训练样本，支持向量机建立一个超平面作为决策曲面，使得正例和反例的隔离边界最大化。

决策曲面的初步理解可以参考如下过程，

2.1.1 如下图想象红色和蓝色的球为球台上的桌球，我们首先目的是找到一条曲线将蓝色和红色的球分开，于是我们得到一条黑色的曲线。

2.1.2为了使黑色的曲线离任意的蓝球和红球距离（也就是我们后面要提到的margin）最大化，我们需要找到一条最优的曲线。如下图

2.1.3 想象一下如果这些球不是在球桌上，而是被抛向了空中，我们仍然需要将红色球和蓝色球分开，这时就需要一个曲面，而且我们需要这个曲面仍然满足跟所有任意红球和蓝球的间距的最大化。需要找到的这个曲面，就是我们后面详细了解的最优超平面

2.1.4 离这个曲面最近的红色球和蓝色球就是Support Vector

2.2 线性可分和线性不可分

线性可分-linearly separable, 在二维空间可以理解为可以用一条直线（一个函数）把两类型的样本隔开，被隔离开来的两类样本即为线性可分样本。同理在高维空间，可以理解为可以被一个曲面(高维函数)隔开的两类样本。

线性不可分，则可以理解为自变量和因变量之间的关系不是线性的。

实际上，线性可不分的情况更多，但是即使是非线性的样本通常也是通过高斯核函数将其映射到高维空间，在高维空间非线性的问题转化为线性可分的问题

2.3 函数间隔和几何间隔

• 函数间隔functional margin:给定一个训练样本有：

函数间隔代表了特征是正例或是反例的确信度。

• 几何间隔geometrical margin：
  

  向量点到超平面的距离（其中后面详细介绍）

2.4 超平面分析与几何间隔详解

前面已经对SVM的原理有了一个大概的了解，并且简单介绍了函数间隔和几何间隔的概念，为了更好的理解线性可分模式下超平面，以下将进行深入的剖析推导过程，我们假设有训练样本集，期望的响应为，这里我们用类+1和类-1来代表，以表明样本是线性可分的。

决策曲面方程如下：

其中

x：输入向量，也就是样本集合中的向量；

w：是可调权值向量，每个向量可调权值；

T：转置，向量的转置；

b：偏置，超平面相对原点的偏移。

根据逻辑回归定义展开其实就是：

其中假设约定，于是将替换成b；则有：

而（T是转置）所以有：

这里假设模式线性可分：

线性可分模式下最优超平面的示意图如下：

如上图所示：

• 为分离边缘，即超平面和最近数据点的间隔。如果一个平面能使最大，则为最优超平面。
• 灰色的方形点和原形点就是我们所说的支持向量。

假设和向量和偏置的最优解，则最优超平面的函数为：

相应的判别函数是：

以下是点x到最优超平面的二维示意图：

由上图可知r 为点x到最优超平面的距离:

那么代数距离是如何得到的呢？通过将带入

可以得到r，其中：

• 为x在最优超平面的正轴投影，
• 因为在平面上

下面给出一种更为简单且直观的理解：

首先我们必须要知道Euclidean norm范数，即欧几里德范数（以下用w表示多维的向量）：

再参考点到面的距离公式

也就是

类似的,扩展到多维的w向量也是一样，代数距离r类似于d，而

类似于 ，所以展开后也就是：

对比点平面的公式，以上的r也就多维度空间向量的到最优超平面的距离。

再看上图，如果x = 0 即原点则有

那么是如何得到的呢？很简单，如上面分析的

因为x = 0，它在原点，它与任意可调权值向量w相乘都等于0，于是有：

注意b为偏置，只是决定了决策曲面相对原点的偏离，结合上图我们可知道：

• b > 0 则原点在最优超平面的正面；
• b < 0 则原点在最优超平面的负面；
• b = 0 则原点就在最优超平面上。

找到的这个最优超平面的参数和, 于是在样本向量集中, 有一对一定满足（因为是常数，它只是决定了决策曲面相对原点的偏离）：

满足上式的点就是则为支持向量，这些点距离决策曲面也就时超平面最近时最难区分的点。于是根据点到超平面的距离公式:

在超平面的正面和负面我们有任一支持向量满足代数距离：

如果让表示两个分离边缘的最优值，则根据上式有：

所以我们可以看出，如果要使得最大，则就必须使得最小，也就可以总结为：

最大化两个类之间的分离边缘等价于最小化权值向量w的欧几里得范数。

2.5 二次最优化

回头看我们前面提到的，给定一个训练集，我们的需求就是尝试找到一个决策边界使得几何间隔最大，回归到问题的本质那就是我们如何找到这个最大的几何间隔？ 要想要最大化间隔（margin），正如上面提到的：

最大化两个类之间的分离边缘等价于最小化权值向量w的欧几里得范数。

即：

其中：也就是前面提到的函数间隔：，回顾几何间隔：，约束条件就是让函数间隔等于几何间隔。

或是将优化的问题转化为以下式子：

其中，就是将函数间隔和几何间隔联系起来。

我们发现以上两个式子都可以表示最大化间隔的优化问题，但是我们同时也发现无论上面哪个式子都是非凸的，并没有现成的可用的软件来解决这两种形式的优化问题。

于是一个行之有效的优化问题的形式被提出来，注意它是一个凸函数形式，如下：

以上的优化问题包含了一个凸二次优化对象并且线性可分，概括来说就是需找最优超平面的二次最优化，这个优化的问题可以用商业的凸二次规划代码来解。

凸函数：

在凸集中任取两个点连成一条直线，这条直线上的点仍然在这个集合内部，左边

凸函数局部最优就是全局最优，而右边的非凸函数的局部最优就不是全局最优了

2.6 拉格朗日对偶性（Largrange duality）深入分析

下面要具体介绍的拉格朗日对偶性，它可以引导我们到优化问题的对偶形式，因为对偶形式在高维空间有效的运用核（函数）来得到最优间隔分类器的方法中扮演了非常重要的角色。对偶形式让我们得到一个有效的算法来解决上述的优化问题并且相较通用的二次规划商业软件更好。

优化问题的对偶形式的方法简单来说就是通过Lagrange Duality变换到对偶变量 (dual variable)的优化问题之后，应用拉格朗日对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：

• 一是原问题的对偶问题往往更容易求解
• 二者可以自然的引入核函数，进而推广到非线性分类问题

通过应用拉格朗日对偶性我们可以寻找到最优超平面的二次最优化，

所以以下可以将寻找最优超平面二次最优化（原问题），总结为以下几个步骤：

1. 在原始权重空间的带约束的优化问题。（注意带约束）
2. 对优化问题建立拉格朗日函数
3. 推导出机器的最优化条件
4. 最后就是在对偶空间解决带拉格朗日乘子的优化问题。 注：以上这个四个步骤是对优化问题的的概括，后面会注意讲解这几个步骤。

于是首先想到的几个随之而来的几个问题：

• 第一个问题是拉格朗日对偶性是什么？
• 第二问题是为什么拉格朗日对偶性可以帮助我们找到最优超平面的二次最优化？

• 第三个问题是如何运用拉格朗日对偶性找到最优超平面的二次最优化？
  下面的内容将对以上三个问题进行深入的分析。

  首先对于第一个问题，我们首先必须清楚两个概念即原问题和对偶问题,以及他们之间的关系.

原问题

假设是定义在上的连续可微函数，考虑约束最优化问题:

称为约束最优化问题的原问题。注意必须是连续可微的。类似的对比我们之前分析的最优超平面的二次最优化问题: