@77qingliu
2018-05-11T10:14:12.000000Z
字数 7442
阅读 6242
machine-learning
本文主要介绍SVM的原理以及相关算法的简单推导,其中包括SVM原理,最初表达式,标准形式以及对偶形式(二次规划问题),核函数以及软间隔。
对于线性可分的数据,支持向量机就是条直线(对于高维数据点就算一个超平面),将不同类别的样本分开。但是能讲样本分开的平面有很多,怎样才算最完美的呢?最直观的想法是寻找对样本局部扰动容忍度最好的的超平面,这样的超平面可以通过下面条件找到。
1. 我们需要找到数据点中距离分割超平面距离最近的点(找最小)
2. 然后尽量使得距离超平面最近的点的距离的绝对值尽量的大(求最大)
这里数据点到超平面的距离就是间隔(margin),当间隔越大,分类器就越稳健。
那些距离分割屏幕最近的点就是支持向量(Support Vectors),如下图所示:
这部分总结如何求得超平面
在样本空间中,划分超平面可通过如下线性方程来描述:
我们现在已经有了间隔的公式,我们需要找到一组最好的和确定的分割超平面使得支持向量距离此平面的间隔最大。
直接使用公式表示:
直接优化上面的式子很困难,我们需要做一些处理,使得同样的优化问题可以使我们用方便的优化算法来求解。
首先看下分割超平面的一个性质。当我们等比例的扩大或缩小和并不会改变超平面的位置。例如对于位于三维空间中的二维平面, , ,我们扩大或者缩小和并不会影响平面,即与原始平面相同。
但是成比例改变后,间隔也成比例的改变。
函数间隔:
几何间隔:
这里给函数间隔的法向量除以,以规范化,使得间隔确定。
这里定义超平面关于训练数据集的几何间隔为超平面关于所有样本点的几何间隔最小值,即
为了求解线性可分支持向量机的最优化问题,将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题得到原始问题的最优解,这就是线性可分支持向量的对偶算法。这样的优点:
首先构建拉格朗日函数。为此,对每个不等式约束引进拉格朗日乘子,定义拉格朗日函数:
根据拉格朗日函数对偶性,原始问题的对偶问题是极大极小问题:
将拉格朗日函数分别对求偏导数令其等于0:
那么如何求解式(5)不难发现,这是一个二次规划问题,可使用通用的二次规划算法求解;然而,该问题的规模正比于训练样本数,这会在实际任务中造成很大的开销。为了避开这个障碍,人们通过利用问题本身的特性,提出了很多高校的算法,SMO(Sequential Minimal Optimization)是其中一个著名的代表。详细的算法原理参看这篇文章
在上面的讨论中,我们都是假设训练样本是线性可分的。即存在一个划分超平面能将训练样本正确分类。然而现实任务中,原始样本空间中也许并不存在一个能正确划分两类样本的超平面。
对这一点问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个空间内线性可分。
令表示将映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可表示为
举一个例子来说明。,我们定义,将原始数据从三维空间映射到九维空间中,让我们来计算:
显然,如果知道合适映射的具体形式,则可写出核函数,但在现实任务中我们通常不知道是什么形式,什么样的函数能做核函数呢?这里有一个定理:只要一个对称函数所对应的核矩阵是半正定的,它就能作为核函数使用。下表列出了几种常用的核函数。
名称 | 表达式 | 参数 |
---|---|---|
线性核 | ||
多项式核 | d >=1 为多项式的次数 | |
高斯核 | 为高斯核的带宽 | |
拉普拉斯核 | ||
Sigmoid核 | 为双曲正切函数, |
我们注意到在线性支持向量机的对偶问题中,无论是目标函数还是决策函数都只涉及到输入与训练数据的内积。在对偶问题的目标函数中的内积可用核函数来替代。此时的对偶的目标函数为
在前面的讨论中,我们一直假定训练样本在样本空间或者特征空间中是线性可分的,即存在一个超平面能将不同类的样本完全划分开。然而,现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。也有可能造成线性不可分的原因可能是存在一些噪声点的影响,完全按照原始的约束条件
缓解办法是允许支持向量机在一些样本上出错。为此,要引入“软间隔”的概念。具体来说,前面介绍的支持向量机形式是要求所有样本均满足约束,即所有样本都必须划分正确,这成为“硬间隔”,而软间隔则是允许某些样本不满足约束。为了能让达到此目的,我们可以引入一个松弛变量来允许错误的分类发生,也就是允许有间隔小于1的数据点出现, 即:
加入惩罚后,目标最优化间隔函数变为:
这仍是一个二次规划问题,于是,通过拉格朗日乘子法可得到下列朗格朗日函数
令对的偏导为零可得
然后将上式回代,我们求此问题的对偶问题:
可见,软间隔SVM的目标函数形式同硬间隔的形式相同,唯一不同的就在于的范围。