关于支持向量机(SVM)的文章在互联网上当真不知凡几,各人理解不同所呈现的方式也各有不同,当然其中也不乏很多写的非常精彩的文章,如:
支持向量机通俗导论(理解SVM的三层境界)
在这里我也想写一写自己从函数优化的角度对SVM的理解,以此来和其他文章互为参补。首先还是回顾一下SVM算法的一些基础概念:
一、SVM算法回顾
一般来说支持向量机可以分为线性可分支持向量机(线性SVM)和线性不可分支持向量机(非线性SVM),它们之间的区别也正如字面上的意思:当数据在输入空间上线性可分时就将其称之为线性SVM,否则就是非线性SVM。往往前者较为简单,而后者则需要运用一些核技巧将输入空间映射到特征空间来得到特征向量,然后进行分类学习。
1、线性SVM
对于线性可分SVM算法的核心思想是通过构造一个线性分类器,在特征空间内找到一个超平面将分属两类的数据进行分割,一般超平面方程可以表示为:
。譬如在一个二维平面上就是通过一条直线将离散数据点分割:
从上图我们可以看出来数据点被直线分为两类,那么怎么定义一个分类函数呢?通常来说我们会定义一个分类函数
,我们可以简单的定义:
又或者定义它为一个sigmoid函数,那么它就转变为一个LR算法了,总之它所扮演的就是一个分类器的角色。
函数间隔和几何间隔
当我们定义完超平面之后,一个很自然的想法就是:怎样找到这个超平面?以及什么样的超平面才是一个好的超平面?
带着上面的问题我们首先抛出一个衡量标准:函数间隔
我们用函数间隔来衡量分类的正确性以及确信程度。对于样本
,当 与 同号时函数间隔给出的就是一个正反馈,相反则给出的是负反馈。同时 也可以相对衡量数据点 到超平面的距离,距离越远则分类的确信程度越高。
对于用于训练的数据集T,所有样本中最小的函数间隔可以定义如下:
但是函数间隔存在一个问题就是当我们成比例改变
和 的大小时,函数间隔的大小也会成比例的改变,但是超平面却没有变化,因此我们还要对超平面的参数向量 进行规范化约束,这时函数间隔就转变为几何间隔:
其中
是 的 范数, ,因此几何间隔可以近似表示样本点距离超平面的距离,也因此最小几何间隔就变成:
间隔最大化
找到了衡量超平面优劣的方法,接下来要做的就是如何通过优化的方法找到这个超平面,对于线性可分SVM,我们也将其称之为硬间隔最大化,其处理思想就是最大化最小几何间隔理解起来有些绕口,但是仔细一想就能明白:对于最小的几何间隔我们都将其最大化,自然其他样本点的几何间隔也就是被最大化了。
具体来说我们可以将上述问题转化为一个带约束的优化问题:
对于上面的式子我们进一步简化,事实上函数间隔
的大小对于上述的优化问题是没有影响的,因为不论我们改变它为多少, 和 的值也会成比例地改变,所以为了方便计算,我们不妨设 ,同时最大化 与最小化 是一样的,这样一来优化问题就转化为了:
很显然,这是一个凸二次规划问题,通过对其求解我们就可以得到一个线性SVM模型,并且我们也可以证明所得到的超平面的存在性与唯一性,这里就不再展开证明,感兴趣的话可以参照李航老师的《统计学习方法》。
对偶问题求解
对于(7)中的带约束的二次优化问题,我们同样可以通过拉格朗日乘子
将其转化为对偶问题求解,首先写出其对应的拉格朗日函数:
对于一般的对偶问题我们通常是通过最大化拉格朗日函数的下界来求解(具体过程可以参照我的文章:拉格朗日对偶):
首先求
对于参数 的下界,我们对其分别求导并令其为0:
从而可得:
将公式(10)带入公式(8)并根据公式(11)可得下界:
然后我们对
求最大,即为下面的对偶问题:
假设对于式(13)我们存在一组最优解:
,那么我们就可以根据式(10)、(11)得到参数 的最优解为:
其中具体的证明过程同样参照李航老师的书。
将公式(14)中的结果带入原来超平面可以将超平面方程写作:
而分类决策函数就是:
总结一下,对于对偶方法求最大化间隔,我们通常先通过式(13)求得最优的
之后,再从中选择一个正的分量 将其带入到(14)中得到 的最优解,最终由此构造出一个超平面用于数据的分类。
2、线性不可分SVM
所谓的非线性,其实指的是数据的线性不可分,在上一节中我们讨论的是在数据空间中我们可以用一条线性函数将数据点分开,那如果是没办法使用线性函数区分数据点,如下图:
很明显,图中的数据点被一个圆形曲线所分,因此这类分类问题被称之为非线性可分问题。
那么如何解决这个问题呢,这就需要引入核技巧,这是一种将数据从一个空间映射到另一个空间的方法,举个例子来说,对于上述用于分割数据点的圆的方程为:
我们引入一个新的变量空间
,且定义变换 ,那么原方程就可以表示为:
这样一来经过变换的数据在新的变量空间中就是线性可分的了,这应用的SVM中的基本思想就是通过一个非线性变换将输入空间(欧氏空间
或者离散集合)对应到一个特征空间(希尔伯特空间 )
核函数
关于核函数的定义为: 设
为输入空间, 为特征空间,如果存在一个从 到 的映射: ,使得所有 ,函数 满足条件:
那么则称
为核函数, 为映射函数,其中 为内积。譬如 这种核函数叫做多项式核函数,在之后还会介绍更多的核函数种类以及选择核函数需要满足的条件。
举个例子来说,对于图二中的数据,我们将其映射到特征空间
,记 , , 由于:
所以我们可以取映射:
映射之后数据在三维空间的表示为:
从图中可以看到原本二维空间的数据映射到三维特征空间后,不同类别的数据之间有了很明显的界限,这时候我们可以通过线性SVM的方法找到一个超平面对其进行分割:
这里需要注意的是:核函数并非是用于映射,很多人会误解核函数与映射的关系,其实核函数的作用是为了方便计算映射后高维向量的点积。
SVM中的核函数应用
根据上一部分的内容可知,在线性SVM的对偶问题中,无论是目标函数还是决策函数都只涉及到实例之间的内积。所以我们将公式(13)中的内积
使用核函数 来代替,此时原问题就等价为对输入进行映射之后的高维特征空间的线性SVM的问题,其对偶问题的目标函数为:
其分类决策函数也就成为:
这一转换使我们可以利用解线性分类问题的方法求解非线性分类问题的支持向量机,这种技巧也称之为核技巧。在实际应用中往往要依赖领域知识选择合适的核函数,这也类似于DL中的调参。
常用核函数
一般对于核函数的选择要满足Mercer's condition,下面我主要列举一些常用的核函数:1、多项式核函数(polynomial kernel function)
在这种核函数选择下,分类决策函数为:
2、高斯核函数(Gaussian kernel function)
其对应的支持向量机为高斯径向基函数(radial basis function)分类器,在此情形下,分类决策函数为:
3、字符串核函数(string kernel function)
此类核函数不是定义在欧式空间上,而是定义在离散数据集上,主要用于文本分类,信息检索等方面。
(算法流程)非线性支持向量机学习算法
输入:训练数据集 ,其中 , ;输出:分类决策函数。(1)选取适当的核函数 和适当的参数 ,构造并求解最优化问题:
求得最优解(2)选择 的一个正分量 ,计算(3)构造决策函数:
Conclusion
总结来说,SVM的本质就是一个二分类器,其核函数的技巧引入使其能够处理线性不可分的输入,最终我们需要求解(19)中的凸二次规划问题,有许多优化算法可供选择。但是当样本容量非常大时这种方法可能就会变得低效,所以为了高效支持SVM学习,也有很多算法被提出,如序列最小最优化(SMO)算法,在下一篇文章中我会接着具体讲解。
Reference:
[1]李航《统计学习方法》
[2]支持向量机通俗导论(理解SVM的三层境界)