李航统计学习－支持向量机（SVM）之我的理解

支持向量机 是一种 二分类模型

SVM 不同于 感知机   是因为 SVM学习策略是间隔最大化，可以将该问题理解为凸二次规划问题，也可以将该问题理解为正则化的合叶损失函数最小化问题

支持向量机学习方法 可以从简单到繁杂分成三种：

 线性可分支持向量机（可以使用硬间隔最大化学习线性分类器），

 线性支持向量机（使用软间隔最大化学习），

 非线性支持向量机（使用核技巧以及软间隔最大化）

现在给支持向量机解决问题做一个通用的描述：

 问题的输入是：一组训练数据集T={(x1, y1),(x2, y2), ... ,(xn, yn)}, xi 是n维向量，yi是一个二元数据{+1,-1}

  输出是：找到一个分离超平面（对应的方程是 w*x + b = 0），将结果为 +1的数据和结果为 -1的数据分开

我们将yi＝＋1称之为正例，－1称之为负例

为了解决这类问题，我们将一类一类讲述分体的解决方法

当训练样本是属于线性可分时，存在无穷个分离超平面可以将两类数据正确分开，此时为了最优分类线性可分的数据集，

我们将线性可分数据利用间隔最大化求出分离超平面。

啥叫做间隔最大化呢，这个就要开始讲述函数距离以及几何距离。

一般来说，一个点距离一个评判标准的预测方向越远，说明确信度越高。比如：我们预测 4小时以上没吃饭的人可能肚子饿，如果某个人 5小时没吃饭，我们可以判断这个人有可能肚子饿，如果某个人8小时没吃饭，我们更加能够判断这个人肚子饿。为什么呢，因为时间距离 (8 - 4)> (5 - 4)，所以我们更加有把握觉得这个人肚子饿。将问题推广到n维空间上，我们自己定义一个公式|w*x+b|，表示点x距离超平面的远近。标记y与w*x+b的符号是否一致能够表示分类是否正确，当w*x+b>0时，y=1,当w*x+b<0时，y=-1。因此y与w*x+b永远同号，所以y(w*x+b)在预测分离超平面上恒大于0。所以y(w*x+b)能够度量分类的正确性以及可信度，如果w*x+b>0，但是y<0，那么y(w*x+b)<0，就是一个失败的预测。

如下图：

根据以上知识，我们可以开始介绍函数间隔以及几何间隔了

函数间隔概念：

这里注意超平面不是w,而是(w,b)，n+1维。函数间隔有个特点，就是能够等比例的缩放，而超平面并没有改变。想想，4x1 + 6x2 + 8 = 0和2x1 + 3x2 + 4 ＝ 0描述的其实是同一个平面，但是函数距离却被缩成了原来的1/2。这可以让我们想到可以对超平面的法向量做一个规范化，||w|| = 1，使得函数间隔无论怎么缩小放大，间隔都是确定的，这个时候函数间隔就变成了几何间隔。

因此，几何间隔的概念就能够引出来了：

讲完函数间隔和几何间隔后，我们可以开始将啥是间隔最大化了。

首先，我们知道，支持向量机学习的基本想法有两个：

1. 求解能够正确划分训练数据集

2. 几何间隔最大，就是离超平面最近的两个点（min）距离要最大（max）［我们也称之为硬间隔最大化］

其实也能够比较容易解释为啥要这样做，因为这样能够最大化的原理超平面，这样的话可信度就更高（敲黑板！一个点距离一个评判标准的预测方向越远，说明确信度越高。）

下面我们就开始谈谈求解最大间隔分离超平面吧，下面是关于集合间隔最大分离超平面问题的数学描述：

求几何距离的最大值，其实也就是求函数r关于w,b的极大值（公式7.9），但是这个极大值又不能够毫无约束，因为所有数据距离超平面的长度都要大于等于r值（公式7.10）。根据几何间隔和函数间隔的关系，可以转化成公式7.11，7.12。

因此就转化成了关于函数距离的公式求解，由于公式 7.11 中的r = min(yi(wi*x + b)), 公式中的w,b同时放大缩小倍数都不会影响公式7.11，7.12。所以可以令r = 1。此外，求1/||w||的最大值等价于求解 ||w||的最小值，也可以等价于1/2*||w||^2的最小值，所以公式可以转化成如下形式：

该问题其实就可以转化成一个凸二次规划问题。

要成为凸二次规划问题，需要满足的条件如下：

1. 目标函数（7.13）是二次函数

2. 目标函数和约束函数都是在R^n上可微的

3. 约束函数是仿射函数（这个条件我也不知道，知道的朋友们可以在评论区解释下谢谢）

求解目标函数相当于求解出最优 w*,b*，这样就能够求解出最大分离平面w*• x + b* = 0，最后就能够求出来分类决策函数f(x) = sign(w* • x + b* = 0)了。

到此，可以讲一下线性可分支持向量机学习算法了。

最大间隔分离超平面是存在且唯一的，证明从略，可以看看书上咋讲的。

分离超平面是怎么形成的呢，这个就要讲讲概念支持向量了了。

支持向量就是 训练数据集的样本点中与分离超平面距离最近的样本点的实例，这个概念书中也讲的挺清楚的，我就不详细叙述了。

求解线性可分支持向量机

作为带约束问题的最优化求解，我们可以使用Lagrange对偶性求解该对偶问题。

首先根据每一个不等式约束，引进Lagrange乘子αi >= 0，定义拉格朗日函数：

根据对偶性，原始问题的对偶问题就是极大极小问题：

 max(α)min(w,b) L(w,b,α)

其中 max(α) 是因为(1 - yi(w*xi + b)) <= 0, max(1 - yi(w*xi + b))其实就能够把约束项给去掉。

中间计算过程：

最后不等式可以等价于如下：

从以上目标函数可以看到，此时目标函数只剩下a1...an是未知变量，其余数据都已知，我们对这些变量依次求偏导数，这样子就能够求出ai。

知道了ai后，根据等式 w - ∑aiyixi = 0可以求出来向量w。

再根据等式w.x + b = 0,求出 b。

这样就能够得到分类决策函数 f(x) = sign(∑ai*yi(x.xi) +b*) 了

完美！这样就能够解决线性可分支持向量机了。

现在我们讲讲如何解决线性支持向量机问题，这个问题不能使用线性可分支持向量机的解决方法来解决，

because 这些约束都不成立。

因此就要修改硬间隔最大化，将其修改成软间隔最大化来解决。

so，what is 软间隔最大化呢？

讲这个问题之前，我们先来描述下线性支持向量机问题的基本描述：

线性不可分意味着有某些样本点无法满足间隔大于等于1的约束条件，解决这个问题的方法是，引入一个松弛变量ξ >= 0,这样子就能够将函数间隔加上松弛变量，使其大于等于1，这样约束条件就变为

       yi(w*xi+b)>=1 - ξi

同时，对每个松弛变量都要支付一个代价ξi * C，因此，目标函数就变成了1/2 * ||w|| + C∑ξi。C是惩罚参数，大于0，具体的值需要根据问题决定。这个就是软间隔最大化。

因此我们可以将该线性不可分的问题转换成如下的形式：

我们先称它为原问题，这个是一个凸二次规划问题，因而关于(w,b,ξ)的解是存在的。

其中，最优解 w 是唯一存在的，b 存在于一个区间。这样我们就能够得到一个分类决策函数了

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

因此，原始问题的对偶问题就变成了：

  

过程的推导可以看下图：

函数8的推导可以看看下图：

于是就可以求出w，b来了，w，b和a的关系如下

证明从略，比较简单，直接看书就好了。

因此，综上我们可以得到以下算法：

现在我们来讲讲软间隔的支持向量：

在线性不可分的情况下，将对偶问题（7.37 -- 7.39）的解a*中对应a*>0的样本点（xi，yi）的实例称之为支持向量（软间隔的支持向量）

为啥这么说呢，是因为当ai = 0时，该项中的 xi，yi 对 w, b的生成不会造成影响（w = ∑aiyixi, b = yj - ∑yiai*(xixj)）（纯属个人理解）

当 ai > 0时，结果就能够影响到 w，b值了

所谓叫做支持向量，就是能够影响分离超平面的生成的才叫做支持向量。

现在讲讲软间隔支持向量的分布位置：

当拉格朗日乘子函数达到最优解时，

 ∑ai(yi(w.xi+b) - 1 + ξi) = 0 （1）

 ∑uiξi = 0 （2）

这样拉格朗日乘子函数L 才等于 目标函数

所以，当a < C时，ξ = 0，支持向量恰好落在间隔边界上，原因如下：

如果 ai < C 那么 ui = C - ai > 0，因为 （2），我们可以知ξi = 0，那么

 yi(w.xi+b)-1= 0 => yi(w.xi+b) = 1，所以向量恰好落在间隔边界上

如果 ai = C 那么 ui = C - ai = 0,因为（2），ξi 可以取任何 > 0 的值，那么

 当 0 < ξ < 1时，根据（1）可以知道 0 < yi(w.xi + b) = 1 - ξ < 1， 所以向量落在分离超平面和间隔边界之间的区域内

 当ξ = 1时，同上，yi(w.xi +b) = 0，所以该向量落在分离超平面上

 当ξ > 1时，同上，yi(w.xi +b) < 0，可以推理出该点在分离超平面错误分类的一侧

合页损失函数

对于线形支持向量机还有另外一种解释，就是最小化以下目标函数

    ∑[1 - yi(w.xi + b)]+ + λ||w||^2

第一项比较好理解，令1 - yi(w.xi + b) = z，就有

    [z]+= z if z > 0 else 0

关于第一项的函数，我们称之为合叶损失函数

函数图像如下（红色线部分）：

证明从略，直接看书就好了，很简单的。

现在讲讲非线性支持向量机：当我们要处理的分类是非线性可分时候，我们就要使用非线性支持向量机来解决问题。

首先来给大家看非线性可分的问题是什么样的吧。

如下图左，X代表负例，*代表正例，需要用椭圆将其划分开，如果使用线性的方法的话，将起不到好效果。所以，我们需要想一个办法，将左边的非线性可分的数据使用一个超平面将他们分开。

假设椭圆分割面的函数长这样：

   w1*(x1)^2 + w2*(x2)^2 + b = 0

令z = x^2，那么，分离超平面就变成了这个函数，

   w1*z1 + w2*z2 + b = 0

这样就能够使用解决线性可分问题的方法解决非线性可分问题了！

从上面我们可以看出，解决非线性可分问题时候，先做个变换，将原空间数据映射到目标空间，然后在新空间中运用线性可分的分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。那么，什么是核技巧呢？

首先定义核函数：

核技巧的想法是，在学习于预测中只定义核函数K(x, z)，而不显式定义映射函数Φ。这样就能够提供映射函数不好求的的解决办法了。通常特征空间是不唯一的，可以使用多种特征空间，即便是同样的特征空间也可以有不同的映射。

核技巧在SVM中的应用

由于在线性支持向量机的对偶问题中，无论是目标函数，还是决策函数（分离超平面）都只涉及到实例与实例之间的内积。所以我们可以用核函数K(xi,xj) = Φ(xi) *Φ(xj) 来代替。此时的目标函数就变成了：

  W(a) = 1/2∑∑ai.aj.yi.yj.K(xi,xj) - ∑ai

分类决策函数也可以变成这样：

  f(x) = sign(ai*yi Φ(xi)Φ(x) + b*) = sign(ai*yi.K(xi,x) + b*)

常用的核函数