【机器学习-西瓜书】六、支持向量机:核技巧;软间隔;惩罚因子C;松弛变量
推荐阅读: 核技巧;惩罚因子C
关键词:核技巧;软间隔;惩罚因子C;松弛变量
6.3核函数
关键词:核函数;核技巧
上一节讲到,SVM寻找的是使得间隔最大的那一个超平面作为分类器,这还是一个线性分类器,然而很多情况下是非线性可分的,SVM是如何解决这个问题的呢?SVM是将样本从原始空间映射到一个更高维度的特征空间,使得样本在特征空间中线性可分。例如简单的异或问题在二维空间中线性不可分,但是映射到三维空间就线性可分,如图:
所以当任务是线性不可分(绝大多数任务都是线性不可分的)时,SVM就将样本从原始空间映射到特征空间(高维空间),在特征空间中分类器(划分超平面)还是一个线性模型,在特征空间该超平面可表示为: ,其中w,b是模型参数, 表示将x映射到特征空间中的特征向量。则SVM的基本型变成:
上一节也说过,求原问题不如求其对偶问题来得方便,那我们来看看其对偶问题是什么:
对比上一节的对偶问题,可以发现,唯一的变化就是 线性可分时,要计算的是原始空间当中输入样本的内积 ,而处理线性不可分,需要计算特征空间(高维空间)当中样本的内积 。然而,特征空间维数可能很高,甚至是无穷维,直接计算 是相当困难的。为了避开这个障碍,可以设想这样一个函数:
,即 与 在特征空间的内积等于它们在原始样本空间通过函数 计算的结果。这个函数就称为核函数,通过核函数来避免在高维空间中求内积的技巧,称之为核技巧(kernel trick)
一句话总结:核技巧就是通过核函数去避免高维空间中的内积计算。
常用的核函数有:
6.4 软间隔与正则化
关键词:软间隔;惩罚因子C;松弛变量
上一小节讲了SVM通过空间变换(原始空间变换到高维空间)把线性不可分问题转换成线性可分,并且是完美的线性可分(所有训练样本不允许出错)。通常来说,找到这么完美的映射是很难的,即使找到了,也很难说这个貌似线性可分的结果不是由于过拟合(overfitting)造成的。
缓解这一问题的一个办法就是允许支持向量机在一些样本上出错,如下图当中,红色圈圈的那些样本,就是错误分类的样本,在这里,总共有5个样本错误分类。
那这个软间隔如何体现到目标方程当中呢?原目标方程是要最小化 ,要在这上面加一项,这一项要能表示错误样本所带来的分数,这个分数也就是通常所说的loss。假设我允许出错5个样本(5个是假设的,一开始压根不可能知道会出错几个),一个样本出错我就记为1分,那么就是5分。而5要和 这个值相加得到总的loss,从而去更新参数,进行训练,那么就会涉及到一个权衡问题,假如 的数量级是10e-5的话,那么loss完全由 错误样本所带来的分数所主导,反之亦然。很显然,我们并不希望这样,于是乎,要找一个因子C来权衡 与错误样本所带来的分数,也称之为惩罚因子。所以,我们的目标方程就可以变为:
其中惩罚因子C是用来权衡模型复杂度( )和样本允许出错的大小的。而 是计算错误样本所带来的分数的函数,这个函数通常用一下三种 (不用0,1损失,是因为它是非凸的,不好求极值,而我们的最小化问题就是一个求极值的问题):
若采用hinge损失,我们的目标方程就是:
max后面那一堆看着岂不是很烦? 引入一个名为松弛变量(slack variables)的东西 ,(松弛变量呢,是用来表征样本不满足约束的程度, 即:, 越大,表示该样本离分类平面越远,并且是在错误分类的情况下)
引入了松弛变量,那么目标方程就很简洁了:
这个形式就是软间隔支持向量机了。
在这里讨论一下惩罚因子C,当C无穷大的时候,会发生什么呢?C无穷大的时候,还要最小化 ,很显然,需要 等于零,也就是一个样本也不允许出错。所以说,C越大,允许出错的样本越小,模型的复杂度越高,越容易过拟合。所以当SVM过拟合的时候,适当的减小惩罚因子C,可以缓解过拟合问题。