• SVM涉及的相关概念
• SVM算法
• 凸优化基础
• 线性可分支持向量机
• 线性不可分支持向量机
• 非线性支持向量机
• 最小二乘支持向量机
• 参考

支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的 ，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够 推广应用到函数拟合等其他机器学习问题中。

1963年，Vapnik在解决模式识别问题时提出了支持向量方法，这种方法从训练集中选择一 组特征子集，使得对特征子集的划分等价于对整个数据集的划分，这组特征子集就被称为 支持向量(Support Vector，SV)；

1971年，Kimeldorf提出使用线性不等约束重新构 造SV的核空间,解决了一部分线性不可分问题；1990年，Grace、Boser和Vapnik等人开始对SVM进行研究； 1995年，Vapnik正式提出统计学习理论。

SVM涉及的相关概念

支持向量机和线性分类器(如逻辑回归)都是线性模型。虽然SVM是线性模型，但是它的求解过程要比线性模型困难不少。

1. 它是一种最大间隔的线性分类器，它只会考虑在decision bound比较近的这些点，而在逻辑回归问题中，即使离决策边界很远，它还是会产生一个loss function。
2. 通过核函数可以做非线性的问题。

对于分类问题，分开两类数据其实有很多种解法，那哪一种解法是最好的呢？也就是说SVM是从线性可分情况下的最优分类面发展而来，最优分类面就是要求分类线不但能将 两类正确分开，且使分类间隔最大(分类间隔最大能够使得算法在测试数据集上取得较好效果，或者说数据本身存在噪声，较大的分类间隔能够取得较好效果)。

SVM考虑寻找一个满足分类要求的超平面,并 且使训练集中的点距离分类面尽可能的远,也 就是寻找一个分类面使它两侧的空白区域 (margin)最大。这与逻辑回归算法不一样，在逻辑回归算法中所有的点都会影响分类边界，而在SVM 算法中不会，它更多考虑的是支持向量。

过两类样本中离分类面最近的点且平行于最 优分类面的超平面上

分类任务

分类任务就是确定对象属于哪个预定义的目标类。分类任务的输入数据是记录的集合，每条记录也称为实例或样例，用元组(

考虑二分类任务，其目标属性为

Sigmoid函数转换为 0或 1。 Sigmoid函数定义如下：

Logistic回归：目的是从特征中学习出一个0/1分类模型，这个模型是将特征的线性组合作为自变量，由于自变量的取值范围是(

Sigmoid函数将自变量映射到(0,1)上，映射后的值被认为是属于

根据Sigmoid函数的特性，假设：

上式表示，已知样本

分类任务进一步理解

从上面可以看出，

因此Logistic回归就是要学习得到参数

。

将目标属性

线性分类函数跟Logistic回归的形式化表示 。将假设函数

• 线性可分数据集

需要注意的是：对于上述问题我们需要数据集是线性可分的，不然不管如何分类都找不到这样一个平面。

线性可分数据集：存在某个超平面

上图中的这些数据就是线性可分的，所以可以用一条直线将这两类数据分开，二维中是一条直线，多维中就是一个超平面。

这个超平面可以用分类函数

SVM算法

SVM所要解决的问题

假定给定数据图，圆的为正类，方的为负类，要想通过一个划分超平面（这里是二维，所以是条直线）将不同类别的样本分开。从图中可以看出，能将训练样本分开的划分超平面可能有很多，但是我们应该去选择哪一个呢？

直观上，我们应该选择中间红色的那个，因为它对于 训练样本局部扰动的“容忍”性最好；

比如，训练集外的样本可能比图中的样本更接近两类 的划分超平面，这将使许多划分超平面出现错误，而 红色的超平面受到的影响是最小的，也就是说，这个 划分超平面的分类结果是最鲁棒的，对未知样本的泛 化能力最强。

在所有的划分超平面中，有一个平面是最好的，它可以尽可能地让所有的样本点都离该划分 超平面最远，这就是SVM要做的。

函数间隔

有三个实例

一般来说，一个点距离超平面的远近可以相对地表示分类预测的确信程度。

可以看出：当一个点

对于给定的训练数据集

定义超平面(

函数间隔为

定义超平面(

几何间隔

• 为平面
  的法向量

取超平面任意点

平面的法向量。

• 点
  到超平面
  ：
  =0的距离
  (d为正值)。即
  。

设

另外，直接计算其内积，可以得到：

由于有

因此，可以等到：

• 对于给定的训练数据集
  和超平面(
  )：

定义超平面(

几何间隔公式如下，它一般是样本点到超平面的带符号的距离，当样本点被超平面正确分类时，就是 样本点到超平面的距离(将每个样本点

定义超平面(

几何间隔为超平面( SVM所要做的事情。

几何间隔与函数间隔的关系为：

如果超平面的参数

支持向量的函数间隔为1，SVM的优化目标为：

约束条件表示的是最大化的一定是支持向量。要求解上述问题我们需要一定的凸优化基础，接下来简要介绍一下所需数学知识部分。

凸优化基础

拉格朗日对偶性 – 原问题

假设

对于上述约束化问题首先引入拉格朗日函数 ( 将等式和不等式约束融入到一个目标函数中去，从而只用一个函数表达我们的问题。)：

其中，

• 构建关于
  的函数：
  。
• 假设给定某个违反原始问题约束条件的
  ，即存在某个
  使得
  或
  。

若

假设给定某个符合原始问题约束条件的

由以上两个式子可以得到：

则极小化问题

与原问题等价，即有相同的解。（因为当趋向无穷时，问题无解，因此必须 满足约束条件）。

• 广义拉格朗日函数的极小极大问题：
  。

拉格朗日对偶性 – 对偶问题

• 构建关于
  和
  的函数：

• 则其极大化问题称为广义拉格朗日函数的极大极小问题

• 将其表示为约束最优化问题，称为原始问题的对偶问题

原问题与对偶问题之间的关系

• 弱对偶性：若原始问题与对偶问题都有最优解，则对偶问题最优解与原问题最优解具备以下关系：

• 强对偶性：满足
• 强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到 原始问题的解，在 SVM 中就是这样做的。
• 当然并不是所有的对偶问题都满足强对偶性 ，在 SVM 中是直接假定了强对偶性的成立， 其实只要满足一些条件，强对偶性是成立的，比如说 KKT条件。

KKT条件：对于原始问题及其对偶问题，假设函数

Karush-Kuhn-Tucker (KKT)条件：

线性可分支持向量机

线性可分SVM

设有如下两类样本的训练集：

线性可分情况意味着存在超平面，使训练点中的正类和负类样本分别位于该超平面的两侧。

如果能确定这样的参数对(

硬间隔最大化

存在的问题：这样的参数对(

解决办法是采用最大间隔原则：即选择使得训练集

目标函数：

约束条件：

基于对偶的线性可分SVM学习算法

构建拉格朗日对偶函数：

根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：

(1) 固定

可以得到：

(2) 将结果代入拉格朗日函数中，整理后可得：

根据拉格朗日对偶性，原问题的对偶问题是极大极小问题：

即需要先求

(3) 求

对偶问题：

(4) 求解上述问题可得到最优的

分类超平面：

分类决策函数：

以上是推导过程，实际使用过程是这样的：

1. 构造并求解最优化问题

求得最优解：

1. 计算
   ：

选择

1. 求得分离超平面：

1. 获得分类决策函数：

• 我们得到的原问题的对偶问题的目标函数为：

第一项为正则化项，第二项为模型精度。

• 如果
  是支持向量的话，上式中
  (因为此向量到分类超平面的函数间隔为1)；
• 对于非支持向量来说，函数间隔会大于1，因此会有
  ，由于有约束条件
  ，因此为了满足最大化，在最优解
  中，必须有
  。
• 结构风险最小化：目标函数第二项为模型精度，第一项为正则化项，有效保证稀疏性，以降低置信风险，因而SVM是基于结构风险最小化的学习方法。

线性不可分支持向量机

线性不可分

• 设有如下两类样本的训练集：

线性不可分情况意味着不存在这样的超平面，使训练点中的正类和负类样本能 够完全分别位于该超平面的两侧，即无法将它们完全分开。如果要用超平面来 划分的话，必然有错分的点。

现实情况：我们只会线性可分的方法；

处理思路：允许分类误差，并且在目标函数 中引入对分类误差的惩罚。

软间隔最大化

• 允许支持向量机在一些样本上出错，需要我们将硬间隔最大化改为软间隔最大化，当然，在最大化软间隔的同时，不满足约束的样本应尽可能的少。
  软间隔要求是
  。
• 为了解决某些样本不满足约束的情况，对每个样本点(
  )引入一个松弛变量
  ，使函数间隔加上松弛变量大于等于1，这样约束条件就变为：

• 为了避免
  取太大的值，需要在目标函数中对他们进行惩罚，其中
  称为惩罚系数，
  值大时，对误分类的惩罚增加，
  值小时对误分类的惩罚减小。

有了上面的思路，可以和线性可分支持向量机一样来考虑线性支持向量机的学习问题，线性不可分的线性支持向量机的学习问题就变为如下凸二次规划问题：

• 通过求解以上凸二次规划问题，即软间隔最大化问题，得到分离超平面为：

相应的分类决策函数为：

基于对偶的学习算法

构建拉格朗日对偶函数：

(1) 分别对

可以推出：

(2) 将结果代入拉格朗日函数中，整理后可得：

(3) 求

对偶问题，凸二次规划问题，有唯一的最优解：

(4) 求解上述问题可得到最优的

得到分类超平面：

得到分类决策函数：

以上是推导过程，实际使用过程是这样的：

1. 构造并求解最优化问题

求得最优解：

1. 计算
   ：

选择

1. 求得分离超平面：

1. 获得分类决策函数：

软间隔支持向量

软间隔支持向量具有以下性质：

• 软间隔的支持向量
  或在间隔边界上，或在间隔边界与分离超平面之间，，或在分离超平面 误分一侧；
  。
• 若
  ，则
  (前面偏导条件)，支持向量
  恰好落在间隔边界上；
• 若
  ，
  ，则
  ，则正确分类，支持向量
  在间隔边界与分离超平面之间；
• 若
  ，
  ，则支持向量
  在分离超平面上；
• 若
  ，
  ，则分类错误，支持向量
  在分离超平面的误分一侧。

非线性支持向量机

非线性数据

在现实任务中，我们得到的数据一般都不是线性可分的，这时线性可分支持向 量机就不适用了。非线性数据意味着不存在这样的超平面，使训练点中的正类 和负类样本能够完全分别位于该超平面的两侧。

Kernel核函数方法

核方法的主要思想： 基于这样一个假设：“在低维空间中不能线性分割的点集，通过转化为高维空间中的点集 时，很有可能变为线性可分的”。

具体来说，在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核 函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优的分离超平面， 从而把平面上本身不好分的非线性数据分开。

SVM处理非线性数据的一般方法：

选择一个非线性特征集，并将数据改写成新的表达方式，这等价于应用一个固定的非线性 映射，将数据映射到高维特征空间，在高维特征空间中使用线性分类器。

其中，

映射。

这意味着线性分类方法求解非线性分类问题一般分为两步：

• 使用一个变换将原空间的数据映射到新空间。
• 在新空间里使用线性分类学习方法从训练数据中学习分类模型。

映射函数相当于把原来的分类函数进行了映射：

映射之后为：

而其中的

• 使用映射函数方法的再思考：

设两个向量

另外，我们注意到：

可以发现，上面的两个式子有很多相同的地方，实际上，我们只需要把某几个维度线性缩放 一下，然后加上一个常数维度，具体来说，上面这个式子的计算实际上和映射效果相同：

• 两种方法的区别：

一个是映射到高维空间中，然后再根据内积的公式计算：

而另一个则直接在原始空间中计算，而不需要显式地写出映射后的结果：

现在我们回忆下前面提到的维度爆炸，在前一种方法已经无法计算的情况下，后一种方法却 依旧能处理，甚至无穷维度也没有问题。

我们把这里的计算两个向量在隐式映射过后在空间中的内积的函数叫做核函数，例如，前面 的例子中，核函数为，例如，前面的例子中，核函数为：

核函数能够简化映射空间中的内积运算。

• 核函数的定义：

设

• 核技巧：

在核函数

使用核技巧，解决了计算的复杂性问题，避开了直接在高维空间中进行计算，，而结果却是等价的。

• 针对任意一个映射，手工设计出相应的核函数是很困难的，所以我们通常是在 常用的核函数中，按照问题和数据特点，进行选择：

多项式核函数:

高斯核函数：

• 高斯核函数中参数
  对模型性能的影响。

如果

性质1. 当

如果

性质 2. 若RBF核中尺度参数

总的来说，通过调控参数

线性核函数：

核函数的本质

通常我们遇到的数据都是线性不可分的，我们需要将其映射到高维空间，但是这 可能带来维度灾难；这时候，核函数便是一种很好的解决方法，核函数的价值就 在于它虽然也是将特征进行从低维到高维的映射，但是核函数的巧妙之处在于它 事先在低维上进行计算，而将实质上的分类效果表现在高维上，这样做也就避免 了在高维空间中的复杂运算。

基于Kernel的SVM：假设现在你是一个农场主，圈养了一批羊，但为了预防狼群 袭击羊群，你需要搭建一个篱笆来把羊和狼分开，但是篱笆应该建在哪儿呢？

基于核函数的非线性支持向量机

给定训练数据集

(1) 选取适当的核函数

(2) 选择

(3)构造分类决策函数：

最小二乘支持向量机

LSSVM概述

LSSVM提出的背景

• 支持向量机是针对小样本问题，基于结构风险最小化，较好地解决了以往机器学习模型中的 过学习、非线性、维数灾难以及局部极小值等问题，具有较好的泛化能力；
• 然而，该方法在大规模训练样本时，存在训练速度慢、稳定性差等缺陷，从而制约了其使用 范围（学习过程中需要求解二次规划问题）；
• 因此，1999年，Suykens和Vandewalle等人在SVM的基础上提出LSSVM（Least Square Support Vector Machine, LSSVM），该算法的计算复杂度大为减少，使得训练速度得到提高。
• 最小二乘支持向量机（LSSVM）是标准支持向量机的一种扩展，该算法将支持 向量机的求解从二次规划问题转化为线性方程组。
• 它与支持向量机的不同之处在于它把不等式约束改成等式约束，并把经验风险 由偏差的一次方改为二次方。

分类问题回顾：

给定训练数据集

分类支持向量机的目标是构造如下形式的分类器，使得

LSSVM分类算法：

(1) 构建LSSVM的分类优化问题的目标函数：

(2) 相比于SVM，其约束条件有所不同，它将SVM的不等式约束改为等式约束：

(3) 构造拉格朗日函数：

(4) 根据KKT条件，取最优值时应该满足对各变量的偏导数为0的约束条件：

消去

(5) 在上式的线性方程组系统中：

(6) 令

得到：

回归问题回顾

给定训练数据集

回归(Regression)支持向量机的目标是构造如下形式的预测函数，使得

最小二乘支持向量回归算法LSSVR

(1) 构建LSSVR的优化问题的目标函数：

(2) 相比于SVM，其约束条件有所不同，它将SVM的不等式约束改为等式约束：

(3) 构造拉格朗日函数：

(4)根据KKT条件，取最优值时应该满足对各变量的偏导数为0的约束条件：

消去

(5) 在上式的线性方程组系统中：

(6) 令

得到：

参考

【1】本文主要参考东北大学大数据科学课程SVM小节。