文章目录

支持向量机概述

支持向量机(support vector machine,SVM)由Cortes和Vapnik于1995年首次提出,虽然诞生只有短短二十多年,但是自一诞生便由于它良好的性能席卷了机器学习领域。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折中,以期获得最好的泛化能力。

SVM是一种有监督学习算法,最常用于二分类任务,对线性分类和非线性分类都支持,经过扩展,也可以支持多分类任务和回归任务。它在文本分类、手写文字识别、图像分类、生物序列分析等实际应用中表现出非常好的性能。

支持向量机的基本思想,简单地说,是通过某种事先选择的非线性映射,将输入向量映射到一个高维特征空间中,在这个空间里构造最优分类超平面,将不同类别的样本分开。所谓超平面,就是一个比原特征空间少一个维度的子空间,在二维情况下就是一条直线,在三维情况下就是一个平面。

从二分类到SVM

我们从最简单的二分类问题开始说起。支持向量机可以想象成一个超平面,用超平面对高维空间中的样本进行分类。在二维空间下,这样的超平面就是一条直线。

那么问题来了,我们可以画出无数条直线将样本完全分隔开,选择哪一条直线呢?这个选择的方法就是支持向量机的核心:它希望找到这样的一条线,使得正负样本之间的间隙越大越好,这是因为距离分类超平面越近的样本,分类的置信度越低,如果能将这些最难分类的点也尽可能地分开,那么预测的效果会更好。SVM算法的目标就是最大化最接近分类超平面的样本距离超平面的距离,即最大化分类间隔。

如图所示,H表示分类线,$H_1$、$H_2$分别是经过各类样本中距离分类线最近的样本并且平行于分线的直线,它们之间的间隔叫做分类间隔(margin)。最优分类线不仅能把所有样本正确分类,并且使得分类间隔最大,这样的分类线只有一个。推广到多维空间,最优分类线就变成了最优分类超平面。其中,$H_1$、$H_2$这两条直线对应的向量即支持向量。

算法过程

我们依然以线性支持向量机为基础,简单介绍一下SVM的算法过程。

首先,定义超平面的数学表达式。我们设n维超平面由以下的方程描述: $$W_Tx + b = 0$$
其中,W和x都是n维列向量,x是平面上的点,W是平面上的法向量,在空间中决定了超平面的方向,b是一个实数,代表超平面到原点的距离。因此,只要确定了w和b的值,就得到了一个唯一的超平面。

由于分类超平面必须对所有训练样本都能正确分类,因此对于所有样本$x_i$而言,如果标签$y_i = +1$,则$W_Tx + b > 0$,如果标签$y_i = -1$,则$W_Tx + b < 0$。

接下来,我们需要计算每个样本点到超平面的距离(也称为几何间距),定义公式为: $$\gamma = \frac{y(W_Tx + b)}{||W||_2}$$
我们令分类器满足以下约束: $$W_Tx + b \ge +1, y_i = +1$$ $$W_Tx + b \le -1, y_i = -1$$
即使得距离超平面最近的两类样本点落在直线$W_Tx + b = 1$与$W_Tx + b = -1$上,这样两类支持向量到超平面的距离之和(即分类间隔)为: $$\gamma = \frac{(+1)*(+1)}{||W||_2} + \frac{(-1)*(-1)}{||W||_2} = \frac{2}{||W||_2}$$
这样,我们的目标就可以表示为找到最能满足约束的参数w和b,使得分类间隔最大,即: $$\max_{w,b}\frac{2}{||W||_2}s.t.y_i(W_Tx_i+b) \ge 1 (i = 1,2,…,m)$$

使用核函数解决线性不可分问题

我们已经知道了SVM分类处理线性数据的远离,但是现实世界的数据大量是非线性的,为了使得SVM能被更好地利用,核函数的方法被引进,从而使得SVM具有处理非线性数据的能力。

简单地说,在低位都不可分的数据,在映射到高纬度后,就变成了线性可分的数据。经过这步映射,我们就可以再运用之前的线性可分SVM的算法思想来继续求解了。常被应用于SVM的核函数主要有线性核函数、多项式核函数、高斯核函数和sigmoid核函数。其中高斯核函数最为常用,可以将数据映射到无限维。

线性核函数

$$K(x,x_i) = (x,z)$$ 线性核函数,主要用于线性可分的情况,其特点是特征空间到输入空间的维度是一样的,其参数少、速度快,对于线性可分数据,其分类效果很理想。

多项式核函数

$$K(x,x_i) = (\gamma+r)^d$$ 多项式核函数可以将低维的输入空间映射到高纬的特征空间,但是多项式核函数参数多,当多项式的阶数比较高的时候,核矩阵的元素值将趋于无穷大或无穷小,计算复杂度会大到无法计算。

高斯核函数

$$K(x,x_i) = e^{(-\gamma ||x-x_i||^2)}$$ 高斯核函数(也称为径向基核函数,radial basis function,RBF)是一种局部性强的核函数,可以将一个样本映射到一个更高维的空间内,该核函数是应用最广的一个,无论大样本还是小样本都有比较好的性能,而且相对于多项式核函数参数更少。它是非线性分类SVM最主流的核函数。

Sigmoid核函数

$$K(x,x_i) = sigmoid(tanh(\gamma+r))$$ 若采用sigmoid核函数,支持向量机实现的就是一种多层神经网络。

算法优缺点

优点:

  1. 可以解决小样本下的机器学习问题。
  2. 模型鲁棒性能强,SVM最终的分类效果只由少数支持向量决定,增删数据集中的非支持向量样本对分类结果不会有影响。
  3. 可以处理线性和非线性数据。

缺点:

  1. 对大规模训练样本需消耗大量内存。
  2. 模型可解释能力弱。
  3. 对多分类问题的处理比较困难。

 

扩展

支持向量机分类是一个二元分类器,但是实际分类任务经常是一个多分类的情况,那么如何将二元分类的支持向量机扩展成可以进行多类别分类的分类器?主要方法如下:

直接法

直接在目标函数上进行修改,将多个分类面的参数求解合并到一个优化问题中,通过求解该优化问题,“一次性”实现多酚类,此方法看似简单,实则计算复杂度较高、实现困难,只适用于小型问题。

间接法

主要通过组合多个二元分类器来实现多分类的效果,该方法也是常见将SVM扩展成多类别分类器的方法,常见的有one-against-one(一对一)和one-against-all(一对多)两种方式。

一对一

在任意两类样本之间设计一个SVM二元分类器,因此K个类别的样本就需要$K(K-1)/2$个SVM分类器。当对一个未知样本进行分类时,最后得票最多的类别即为该未知样本的类别。例如,假设有四类A、B、C、D的多类别分类任务,在训练时,选择(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)所对应的向量作为训练集,然后得到六个训练结果,在预测时,把对应的向量分别对6个结果进行测试,然后采取投票形式,得到最终结果。但是当分类任务类别很多的时候,模型的个数为$N(N-1)/2$,代价还是相当大的。

一对多

训练时依次把某个类别的样本归为一类,其余样本归为另一类,这样k个类别的样本就构造出K个分类器,分类时将未知样本归为具有最大分类函数值的那个类别中。