Lecture8- SVM支持向量机 之核方法 + 软间隔 + SMO 算法

Lecture8

主要内容如下：

·Kernels (核方法)

·Soft Margin(软间隔) –非线性可分的情况

·SMO algorithm

1.Kernels (核方法)

这是我们探讨核方法的出发点

假设我们现在有一个输入属性（input attribute）x，有时候我们会将这个x给映射到一组新的集合上去，

比如如下例子，采用特征映射 (feature mapping) φ：

我们把得到的这组新的量称为 输入特征（input features）

这样，如果我们想通过新的这组input features求解svm，只需要把之前讲过程中的所有出现了x的地方用φ(x)代替就ok了。

假设现在有内积<x,z>,则直接将其写为<φ(x) φ(z)>，我们将这个内积定义为一个核：

一般φ(x)的维度都比较高，直接把φ(x)计算并表示出来显得很复杂，但是计算K(x,z)的复杂度一般要低一些，所以往往不必把φ(x)或者φ(z)显示地表达出来。举个例子说明：

下面看另一个核的例子，如果φ(x)和φ(z)很接近，那么它们的内积就比较大，也就是说期望核的值K(x,z)比较大；如果它们彼此远离，甚至接近正交，那么它们的内积K(x,z)就会比较小，甚至于接近0。所以我们可以认为核函数K(x,z)能够在一定程度上测定φ(x)和φ(z)的相似性，或者说x和z的相似性。比如下面这个核函数：

如果x和z接近的话，值就会接近1；反之x和z相隔很远的话，值会接近0。

那么我们能够在SVM中用到这个核吗？对于这个具体的例子来说，是可以的，这个核其实被称作Gaussian kernel,实际上对应了一个无限维度的映射函数φ。

但是问题来了，我们该如何判定一个核函数K是否合法（有效）呢？换句话说，我们能否找到一个合适的 特征映射函数φ，使得K = <φ(x) φ(z)> 对于当前问题的所有x和z都成立。如果根本都找不到一个合适的φ，说明我们无法从x，z构建出这样一个核函数！

实际上有一个结论，给出了函数K是合法的核的充分必要条件

①先来看必要条件：

假设现在已知K是一个合法的核函数，对应着一个映射函数φ。

现在，考虑包含了m个点的有限集合(不一定非得是训练集) ：

，

使得有一个m x m大小的矩阵K，的元素 Kij = K(x(i), x(j)).

这样的一个矩阵K被称为 kernel matrix（核矩阵）

根据基本的数学知识，内积是可交换的，即 <φ(x) φ(z)> = <φ(z) φ(x)>，

那么显然，对于刚刚那个核矩阵来说，Kij = Kji，也就是说，K矩阵是对称矩阵

接下来，对于任意一个向量z，φk(x)是φ(x)中的第k个值，有如下推导：

从而得知K是一个positive semi-definite matrix ---半正定矩阵。

则必要条件就为：如果K是一个合法的核函数，那么K函数对应的K矩阵就一定是一个 对称的半正定矩阵 。

实际上，这个条件也是充分条件，使得K是一个合法的核，称为Mercer kernel

Mercer定理：任何的半正定函数都可以作为核函数。

给出了判定一个核函数是否是合法的标准。

其实总结起来，核方法的作用就是将特征映射到高维空间中去，所以也不局限于SVM中应用，

2.L1 norm soft Margin

在这之前，我们探讨的都是数据线性可分的情况，但是有时候数据是线性不可分的，如下图左图；

或者即便线性可分，但是分割函数并不理想，如下图右图：

所以我们就希望算法对这些极端值不敏感，这样就相当于尽量忽略这些极端值，那么剩下的大部分样本就还是线性可分的。

这些极端值无法满足间隔大于等于1的约束条件，所以我们对每个样本点再引入一个松弛变量ξi≥0，使得间隔函数加上松弛变量大于等于1.即约束条件变为：

如果某个样本的函数间隔为 1- ξi的话，我们就应该对损失函数增加一个代价：Cξi。 所以最终的损失函数和约束条件如下：

损失函数中多出来的那部分代价想表达的意思是，最小化这部分代价意味着更少的样本点，会需要加上这个ξ才能满足函数间隔大于1；试想，如果ξ是一个极大的数的话，那么光凭借ξ的值就能满足约束条件了，那么我们的函数间隔那部分就没有意义了，所以希望ξ这部分代价能取的尽量的小。C是一个常数，用来控制这部分的权重而已。

如果说我们之前讲的线性可分的数据的SVM可以被称为 线性可分支持向量机，那么这里对于线性不可分的数据，但是却近似线性可分（比如只有极个别的极端值，）的数据，是能够通过软间隔来学习出线性SVM的，可称为 线性支持向量机。

同样可以写出它的拉格朗日乘式，

具体的详细的推导过程我们就不细讲了，参考Lecture7中的详细推导步骤，这里直接给出对偶结果：

我们会发现这个对偶问题与Lecture7中解决线性可分SVM中的对偶问题相比，只是对于αi的约束多了一个：αi≤C，

但要主要的是对于b的计算公式需要进行修改。同时KKT dual-complementarity（对偶互补条件）为：

要想解决这个对偶问题，就会讲到下面的SMO算法

3.SMO algorithm (sequential minimal optimization)顺序最小优化算法

坐标上升法：

先来看一个无约束优化问题：

W是参数α的函数，现在我们先不考虑有关SVM的任何东西，这就是个单纯的优化问题。我们在前面已经就讲过两种优化方法，梯度上升和牛顿方法，可以用来解决这个问题，但是这次提出一个新的方法：坐标上升法：

可以看到在算法的最内层循环中，我们固定除了αi的其余所有参数，然后对于参数αi最大化整个函数，最内层按照α1、α2、α3…的循环（也可以选择其他更复杂的顺序）。

这里朋友们要注意的是 在算argmax，而不是max，

就是说我们这里求的不是函数的最大值，而是使函数能取得最大值的参数αi的最大值

坐标上升算法是一个相当高效的算法，执行过程见下图：

图中的椭圆是我们想要优化的一个二次函数的轮廓。坐标上升算法的初始点为（2，-2），图中描点的路径是到达全局最大的路径。在每一步，坐标上升算法平行地沿着一个轴运动，一次仅有一个变量被优化。简单的说，就是固定x求能使得函数值最大的y，再固定y求能使函数值最大的x，如此循环……

了解了坐标上升算法之后，我们再来看之前提到的对偶问题：

对于这个对偶问题，我们确实需要求解一系列的αi，那么我们能直接使用坐标上升算法吗？

答案是不行！

因为约束条件中的第二个条件所限制，以α1为例：如果想固定除了α1以外的所有其它α是不能做到的，因为：

即因为它们的和是一个固定值，如果固定了其余m-1个参数，那么这一个参数也就被固定了。所以不能直接使用坐标上升算法。

但是，如果我们同时更新两个参数，固定其余m-2个参数可否呢？这样其实就可以了，因为这两个参数自己有自己调整的内部空间。

这就是SMO算法，过程如下：

SMO是一个高效的算法的关键原因是，更新αi，αj可以被高效地计算。

可以简单的推导一下：

现在固定除了α1，α2 之外的其余m-2个α，那么就会得到一个新的约束：

因为右侧被固定，就是一个常数而已，改写为：

画出函数图：

因为约束条件中0≤αi≤C，所以α1和α2必须存在于[0,C]×[0,C]的方形区域内，直线为：α1y(1)+α2y(2) = ζ,

与框形区域有两个交点。

可知，固定α1时， α2需要落在[L,H]范围内，否则无法满足条件，此图中L=0.

我们完全可以将α1写作α2的函数：α1 = (ζ − α2y(2)) y(1).

那么优化问题可以被写为：

Y因为其他参数都被固定，所以这可以视为仅仅是一个关于α2的二次函数，如果我们先暂时不考虑α2的限制范围，直接通过梯度方法求得最小值，那么设这个值为：α2-new-unclipped

然后再对其进行截断操作：

之后再把这个值代入优化函数中去求α1即可