有监督分类：支持向量机分类

1.前言

上一篇主要研究了《最小二乘用于分类》也实现了模式识别。然而，虽然与错误分类率对应的0/1损失的间隔函数是单调非增的，但是L2损失并不是单调非增的，所以使用最小二乘学习法进行模式识别还是有些不自然。这里，再次综述一下支持向量机分类器，关于SVM的话题已经写了近10篇文章了。本文更偏重于介绍支持向量机分类器中所使用的损失概念，并且讨论支持向量机分类器向鲁棒学习进行拓展的方法。

2.间隔最大化分类

这里将对基于间隔最大化原理的支持向量机分类器算法做详细分析。

首先从线性的2分类问题进行说明。

w为把正样本与负样本隔离开的超平面的法线，γ为截距，如下图所示：

w是分类超平面的法线，γ是截距

只要能够对各个训练样本的间隔：

为正时的w和γ进行学习，就可以利用这个模型对所有的训练样本进行正确地分类了：

像上式那样没有等号的开集约束条件，在数学上坑你比较难以处理，所以这里利用参数w和γ的值可以任意决定的性质，将其变换为如下别这样包含等号的闭集约束条件：

当存在满足这样条件的w和γ时，我们称这样的训练样本为线性可分样本。

2.1 硬间隔支持向量机分类器

对于线性可分的训练样本，可以把所有的训练样本都正确分类的解有无数个。这里一般选取能够最充裕地把正样本和负样本进行分离的超平面做为最优解、这个最充裕的概念，是与正则化后的间隔的最小值相对应的：

从几何上讲，间隔为两端的两个超平面wTx+γ=+1 和 wTx+γ=-1的间距的一半。使这个间隔最大（间隔的倒数平方最小）的超平面对应的分类器，称为硬间隔支持向量机分类器。如下图所示：

硬间隔支持向量机分类器的分类超平面，从正样本和负样本的中间通过。

对于任何正样本x+，都有wTx+γ=+1，对于任意的负样本x-，都有wTx+γ=-1

硬间隔支持向量机分类器假定训练样本是线性可分的。但是在实际应用中，这种情形并不多见，大部分情况训练样本都线性不可分的。因此，下面还将介绍与这个假定相对应的软间隔支持向量机分类器。

2.2 软间隔支持向量机分类器

软间隔支持向量机分类器的基本思路是：允许在间隔的计算中出现少许的误差（松弛变量） e=(e1,e2,...,en):

C>0是调整误差允许范围内的参数（惩罚系数）。C越大，e=(e1,e2,...,en)越趋近于零，软间隔支持向量机分类器越接近硬间隔支持向量机分类器。如图所示：

软间隔支持向量机分类器允许间隔的计算出现少量误差

3.支持向量机分类器的求解方法

支持向量机分类器的最优化问题：

是目标函数为二次函数，约束条件为线性的典型的二次规划问题。目前已经开发出很多求解二次规划问题的的优秀算法，因此可以使用这些算法对支持向量机分类器进行求解。

3.1 二次规划问题综述

二次规划问题时域矩阵F/G以及向量f/g相对应的，由下式定义的最优化问题：

这里把向量不等式GΘ≤g分解，表示各个元素的不等式：

假定矩阵F是正定的（也就是说所有的固有值都是正的），当天件不充分、数值不稳定的时候，为F的对角元素加上一个特别小的正值，从未使其稳定性得以提高。

3.2 求解思路

最原始的d维线性分类器中，只包含d+1个w和γ变量，而最优化问题中除了w和γ以外，还必须对松弛变量e=(e1,e2,...,en)求解。因此，需要最优化的变量就增加为d+1+n个。计算时间也会相应的增加。

拉格朗日继续登上舞台：

并考虑其最优化问题的等价表现形式，也就是拉格朗日对偶问题：

根据上述优化进行偏导求解：

带入原式，拉格朗日对偶问题就可以用下式表示：

这个最优化问题，利用只有n个最优变量的二次规划问题，实现比原始最优化问题更搞笑的求解过程。其解为：

    

这一块主要目的是介绍基于二次规划的拉格朗日对偶问题的指向hi想来那估计分类器求解方法。其实，这一段时间，关于如何高效地求解支持向量机分类器的研究非常热门。

对于无法使用最小二乘学习很好进行分类的数据，采用SVM可以获得非常完美的结果：

线性支持向量机分类实例（200个对偶参数，197个变为0，只有3个参数样本非零）

这里我们会发现，支持向量机的对偶参数解非常的系数，下面进行详细探讨。

4.稀疏性

之前谈过，采用L1范数约束求得的节为稀疏性，但是根据上节，我们也会发现，用支持向量机分类器对对偶解进行求解时，即是没有使用L1约束，也得到了倾向于稀疏的解。

为了对此进行说明，首先研究一下a’的最优条件，也就是KKT条件。对偶变量和约束条件应该满足如下的互补条件：

在上式中，mi=(wTxi+γ)yi表示的是间隔；根据上面求偏导的结论：

将上式加以组合，对偶变量ai和间隔mi之间可以得到如下关系式：

也就是说：ai等于0的时候，训练样本xi位于间隔边界上或间隔边界内侧，可以充裕地进行分类。当0<ai<C时，xi恰好位于分割边界上，可正确分类。当ai=C时，xi位于间隔边界上或者边界外侧，如果间隔误差（松弛变量大于1），则间隔为负，训练样本xi就不恒正确分类。

实际中，与ai>0相对应的训练样本xi称为支持向量。

5.使用核映射的非线性模型

前面介绍的是对与线性可分模型的支持向量机分类器的学习方法。本节主要探讨SVM如何应用于非线性模型。

具体而言，首先使用非线性函数，对训练输入样本的特征空间进行描述，适用于线性SVN。通过这种方式得到的特征空间内为线性分类器，而原始的输入空间是非线性分类器。

如果选择笔原始的输入维度d维度更高的控件作为特征空间，则训练样本为线性可分的可能性就比较高，然而，如果特征空间的维度过大的话，计算时间夜会相应增加。

核映射实现非线性的支持向量机分类器

这种情况下，最常用的就是核函数映射的方法。在SVM学习算法中，训练输入样本只存在xiTxj=<xi,xj>这种内积形式。同样，在非线性的支持向量机分类器中，特征空间中的训练输入样本只存在<f(x),f(x)>这种內积的形式。

通过采用核映射方法，如果核函数的值与特征空间的维度无关、相互独立的话，非线性支持向量机的全体学习时间就完全不依赖特征空间的维数了。像这样的核函数有很多，比如多项式核函数、高斯核函数：

下图展示的就是利用高斯核函数的非线性支持向量机分类器的例子：

高斯核函数的支持向量机分类器的例子

通过上例，我们能够发现：利用非线性的支持向量机分类器，即使非常复杂的数据也得到了正确的分类。