深入理解支持向量机-SVM
秋招在即,发现最近一直在做的都是深度学习里的一些项目。机器学习里的一些经典算法快忘光了。想重新再对一些经典的算法整理下,更好的面对即将到来的秋招。今天要总结的是机器学习里比较火的一种算法:支持向量机(Support Vector Machine)。
1. 结构风险最小原理
在对支持向量机算法介绍之前,我们需要了解一下在传统的统计学里的一个概念“结构风险最小原理”。
首先我们回想一下,在机器学习中,我们一般都是去提出一个模型,然后通过一些手段(可以理解为一些优化方法),让我们提出的这个模型不断的去逼近真实的模型。但是我们如何去衡量我们的模型与真实模型之间的差距呢?最直接的办法就是用模型的结果与真实结果之间的差值来表示它,这个差值在统计上称之为经验风险
也许你会想到,把样本分成训练集和测试集呀。用训练集去优化我们的模型,测试集来判断模型的误差大小。可是我们要知道,我们能获取的数据对于现实世界的总体来说是十分渺小的,我们只能去保证在这个小的总体内,我们的模型的正确率是很高的,但是在实际上可能会出现一些我们样本中没有体现出的情况。此时我们的模型也许就不再有效了。
因此,统计学中引入了泛化误差(
经验风险(
Remp(W) ):代表了分类器在给定的样本上的误差;置信风险(
ϕ(n/h) ):代表了我们在多大的程度上可以信任分类器在未知样本上的分类结果;
我们优化的目标就从经验风险最小化变为了经验风险与置信风险之和最小化,也就是结构风险最小化。而支持向量机就是寻求结构风险最小化的一种算法。
2.支持向量机理论
2.1 支持向量机的目标
支持向量机的主要核心思想就是在面对一个二分类问题时,我们不仅想要去找到一个超平面能很好的去划分样本,而且我们要使这个超平面到达样本的间隔达到最大。(注意:这里说的样本是指在所有的正负样本中离超平面最近的正样本与负样本)。
如上图所示,实心点代表了正样本,空心点代表了负样本。我们可以看出绿色的线代表的超平面
我们将能够正确划分正负样本的超平面的表达式定义为:
注意,这里的
其中
当我们使用
- 当
f(x)>0 时,此时样本点位于我们超平面的上方,我们将其划分为正样本,即y=1 ; - 当
f(x)<0 时,此时样本点位于我们超平面的下方,我们将其划分为负样本,即y=−1 ; - 当
f(x)=0 时,此时样本点位于我们超平面的上,此时我们无法将其划分;
2.2 函数间隔(function margin)
由于我们定义了:当样本为正样本时,我们的分类函数
这里有人也许会有疑惑,我们在上一节不是定义了一个距离了么?为什么这里还要去定义一个函数间隔。个人理解为之前定义的距离中包含了绝对值,在后续的求解或者计算中不是很方便,因此对距离进行改进了一下得到了我们的函数间隔。由于距离必须大于0,因而我们可以将原来定义的距离去掉绝对值乘上样本的类别标签
为了简化之后的计算,我们定义正负样本中离超平面最近的那两个点到超平面的距离为1(听起来好绕口,可以借鉴2.1节的图,图上在虚线上的点到超平面的距离,我们把它规定为1)。 因此两条虚线的函数表达式为:
因为我们定义了距离超平面最近的正负样本到超平面的距离为1,因此其他点到超平面的距离均大于1。因此上式可以转化为:
也就是只要保证样本点的函数间隔大于1,那么该样本点一定是被正确分类的。但是函数间隔存在着一个缺陷:就是如果我们同时成倍的扩大
2.3 几何间隔(geometrical margin)
定义样本点到超平面的距离为
这里简单的进行推导一下几何间隔
而
又映射
因此我们得到了样本点到超平面的距离,注意这里定义的距离也是带有正负号的,我们对其做与函数间隔相同的处理,即定义
2.4 最大间隔分类器
在支持向量机中,我们不仅想要找到一个能够正确划分正负样本的超平面,还想要样本点到超平面的几何间隔达到最大,这样我们的分类器才能有更强的鲁棒性和泛化能力。因此可以通过上述想法提出一个优化问题:在能正确划分正负样本的情形下,使得样本点到超平面的几何间隔达到最大。优化目标用公式来表达就是:
由于之前定义了
而
而优化条件是要正确划分正负样本,这个在之前我们就已经定义了:
因此整个优化问题可以用公式来表达就是:
而在面对优化问题时,我们一般习惯求最小值,因此我们将上述问题转为求最小值问题就是:
通过观察上述优化问题,我们不难发现它是一个凸二次优化问题,在处理这种问题时,有一个特定的套路:就是引入拉格朗日乘子,把这个凸二次优化问题转化为其对偶问题,再对对偶问题进行求解。说道这里,可能有人要问为什么要引入拉格朗日乘子,将其转化为对偶问题呢?因为对偶问题通常比原问题更好求解,而且更容易我们引入核函数。下面我们就来讲述关与最优间隔分类器的求解过程。
2.5 对偶问题
其实如果你只是想使用SVM去解决一个分类问题的话,上面的介绍已经算是对SVM的一个初步的了解了。但是对于还想要对它进行深入的了解的话就需要你去对其求解过程有所了解,这样才可以明白SVM的一个最重要的东西,就是核函数。先简单的说一下个人对核函数的一个理解吧。我所理解的核函数就是一种映射关系,将在低维空间中的点映射到高维空间中,这样在低维空间中线性不可分的在高维空间中就可以变成线性可分的了。此时再将高维空间中把样本点线性切分的超平面映射回低维空间就是我们所要求的。
对于2.4节最后的优化问题,我们引入拉格朗日乘子
然后我们取
- 当样本点不满足优化问题的条件时:即
(wTxi+b)∗yi−1<0 ,此时仅需要令αi=+∞ ,这样就有θ(w)=+∞ ; - 当样本点满足优化问题的条件时:即
(wTxi+b)∗yi−1≥0 ,此时如果要使θ(w) 达到最大,我们需要令αi=0 ,此时θ(w) 达到最大为12||w||2 ;
因此通过上面分析的,我们可以将优化问题做进一步的转化为:
而
在对上述的优化问题进行求解时,由于
此时我们就得到了原始问题的对偶问题,对于求解对偶问题的求解,我们可以分成三步:
- 固定
α ,调整w,b 让L(w,b,α) 达到最小值; - 求对
α 的极大化; - 通过使用SMO求解
αi ;
按照上诉步骤来进行求解对偶问题,首先我们先要计算
将求出的结果带入到拉格朗日函数中,可以得到:
因此,优化问题可以写成:
通过求解上述问题,求出
2.6 核函数
在面对分类问题中,我们的样本不可能总是线性可分的,当我们在原有的样本空间中无法对我们的样本使用超平面进行划分时,我们可以定义一种映射,将原样本空间映射到更高维的特征空间中,在这个高维的特征空间中我们的样本点就可以被线性划分了。
我们首先可以定义一种映射
使用映射
s.t.
此时我们可以在映射过后的特征空间中找到一个超平面将样本点分隔开。但是,这样虽然我们可以使用超平面划分样本点了,但是付出的代价是要在高维空间中计算内积,当映射的特征空间是无限维时,我们很难去计算内积。此时核函数就产生了,使用核函数,我们就可以不用显式的去计算高维空间的内积,而在原始的样本空间中进行计算,这样大大减小了计算的复杂性。我们将核函数记为
多项式核
高斯核
那么普通的映射与核函数有什么区别呢?
- 普通的映射是将样本点从低维空间映射到高维空间,再在高维空间上计算内积;
- 核函数还是在原有的样本空间中计算内积,不用显式的计算出高维映射后的内积结果;
2.7 松弛变量
上诉介绍的是数据可以通过一个超平面对样本点进行划分的,即使在原有的样本空间中无法进行划分,但是在将样本空间映射到高维中后,还是可以使用一个超平面对样本进行合理的划分的。但是,现实的情况并非总是如此,即便映射到高维空间后可以线性划分,然而你将面对的是在支持向量机中最常见的一个问题,那就是过拟合。如何去避免在使用支持向量机中产生过拟合呢?一个常用的办法就是引入松弛变量。
在引入松弛变量前,我们需要介绍一个概念“软间隔”。为了避免支持向量机产生过拟合,我们对之前的限制条件作出了一些退让,不再要求有
在上图中我们可以看出,有两个点
原始的约束条件
引入松弛变量后为
其中
此时,引入松弛变量后的支持向量机优化问题为:
s.t.
与硬间隔的SVM类似,我们引入拉格朗日乘子后拉格朗日函数为
原问题的对偶问题为:
同样对
将求导结果带入到拉格朗日函数当中可以得到:
但是此时需要注意一点就是,我们得到的