【机器学习－西瓜书】六、支持向量机：核技巧；软间隔；惩罚因子C；松弛变量

推荐阅读： 核技巧；惩罚因子C

关键词：核技巧；软间隔；惩罚因子C；松弛变量

6.3核函数

关键词：核函数；核技巧

上一节讲到，SVM寻找的是使得间隔最大的那一个超平面作为分类器，这还是一个线性分类器，然而很多情况下是非线性可分的，SVM是如何解决这个问题的呢？SVM是将样本从原始空间映射到一个更高维度的特征空间，使得样本在特征空间中线性可分。例如简单的异或问题在二维空间中线性不可分，但是映射到三维空间就线性可分，如图：

所以当任务是线性不可分（绝大多数任务都是线性不可分的）时，SVM就将样本从原始空间映射到特征空间（高维空间），在特征空间中分类器（划分超平面）还是一个线性模型，在特征空间该超平面可表示为： f(x)=wT∅(x)+b ，其中w，b是模型参数， ∅(x) 表示将x映射到特征空间中的特征向量。则SVM的基本型变成：
上一节也说过，求原问题不如求其对偶问题来得方便，那我们来看看其对偶问题是什么：
对比上一节的对偶问题，可以发现，唯一的变化就是 线性可分时，要计算的是原始空间当中输入样本的内积 xTixj ，而处理线性不可分，需要计算特征空间（高维空间）当中样本的内积 ∅(xTi)∅(xj) 。然而，特征空间维数可能很高，甚至是无穷维，直接计算 ∅(xTi)∅(xj) 是相当困难的。为了避开这个障碍，可以设想这样一个函数： k(xi,xj)=<∅(xTi),∅(xj)>=∅(xTi)∅(xj)
，即 xi 与 xj 在特征空间的内积等于它们在原始样本空间通过函数 k(∗,∗) 计算的结果。这个函数就称为核函数，通过核函数来避免在高维空间中求内积的技巧，称之为核技巧（kernel trick）
一句话总结：核技巧就是通过核函数去避免高维空间中的内积计算。
常用的核函数有：

6.4 软间隔与正则化

关键词：软间隔；惩罚因子C；松弛变量
上一小节讲了SVM通过空间变换（原始空间变换到高维空间）把线性不可分问题转换成线性可分，并且是完美的线性可分（所有训练样本不允许出错）。通常来说，找到这么完美的映射是很难的，即使找到了，也很难说这个貌似线性可分的结果不是由于过拟合（overfitting）造成的。

缓解这一问题的一个办法就是允许支持向量机在一些样本上出错，如下图当中，红色圈圈的那些样本，就是错误分类的样本，在这里，总共有5个样本错误分类。
之前所讨论的，要求所有样本均满足约束条件（ yi(wTx+b)⩾1 ），这称为“硬间隔”（hard margin），而软间隔（Soft margin）是允许某些样本不满足约束（ yi(wTx+b)⩾1 ）
那这个软间隔如何体现到目标方程当中呢？原目标方程是要最小化 12∥w∥2 ，要在这上面加一项，这一项要能表示错误样本所带来的分数，这个分数也就是通常所说的loss。假设我允许出错5个样本（5个是假设的，一开始压根不可能知道会出错几个），一个样本出错我就记为1分，那么就是5分。而5要和 12∥w∥2 这个值相加得到总的loss，从而去更新参数，进行训练，那么就会涉及到一个权衡问题，假如 12∥w∥2 的数量级是10e-5的话，那么loss完全由 错误样本所带来的分数所主导，反之亦然。很显然，我们并不希望这样，于是乎，要找一个因子C来权衡 12∥w∥2 与错误样本所带来的分数，也称之为惩罚因子。所以，我们的目标方程就可以变为：
，其中惩罚因子C是用来权衡模型复杂度（ 12∥w∥2 ）和样本允许出错的大小的。而 l（.） 是计算错误样本所带来的分数的函数，这个函数通常用一下三种：
若采用hinge损失，我们的目标方程就是：

，max后面那一堆看着岂不是很烦？ 引入一个名为松弛变量（slack variables）的东西 ξi⩾0 ，（松弛变量呢，是用来表征样本不满足约束的程度）
那么目标方程就很简洁了：

这个形式就是软间隔支持向量机了。
在这里讨论一下惩罚因子C，当C无穷大的时候，会发生什么呢？C无穷大的时候，还要最小化 12∥w∥2+C∑mi=1ξi ，很显然，需要 ∑mi=1ξi 等于零，也就是一个样本也不允许出错。所以说，C越大，允许出错的样本越小，模型的复杂度越高，越容易过拟合。所以当SVM过拟合的时候，适当的减小惩罚因子C，可以缓解过拟合问题。