SVM是在1963年,由Vanpik领导的ATE-T Bell实验室研究小组提出来的。这种方法是基于模式识别方法和统计学习理论的一种分类技术,主要用于模式识别领域。SVM在解决小样本、非线性及高纬度的分类问题中,有许多优势。在文本分类、图像识别、生物信息学等领域中得到了成功的额应用。

一、基本几何知识

(1)向量加减

(2)向量的点乘:a * b

a * b = |a| * |b| * cosθ ,其几何意义是一个向量和它在另一个向量上的投影的长度的乘积,如下图所示,这里我们也可以理解为向量a到向量b的距离。

二、划分超平面

假设给定训练样本集,分类学习的基本想法就是基于训练集D在样本空间中找到一个划分超平面,将不同类别的样本分开。但是如下图所示,能划分训练样本的划分超平面很多,究竟要选择哪一个才合适呢?

我们应该要找的划分超平面,应该是鲁棒性最好,对未知数据泛化能力最强的划分超平面。

给定w=(w0,w1),x=(x,y)两个向量,在样本空间中,划分超平面可以通过如下线性方程来描述:

对于每一个向量xi和对应的分类yi(+1和-1),我们假设函数h:

等价于:

这个是我们在最终用于预测、分类的时候使用的分类决策函数。所以,我们要做的事情,就是怎么确定w和b。

三、支持向量和间隔

假设超平面(w,b)能将训练样本正确分类。通过上面第一节,我们可以得到,对于(xi,yi)∈D,当yi=+1,则有;当yi=-1,则有。我们令

如下图所示,距离超平面最近的几个训练样本点,使得等式的等号成立,这些点被成为“支持向量”。划分超平面两边的两个支持向量到超平面的距离之和,成为“间隔”,其和为:

这里,我们结合第一节部分的内容来说下间隔的推到。由于x+和x-是支持向量,则满足:等式,即:

如下图,间隔为:

所以,想要找到具有最大间隔ϒ的划分超平面,也就是要满足如下式子:

的最大值,也就是求||w||的最小值,这等价于最小化。所以,上式可以重写为:

这就是支持向量机(Support Vector Machine,简称SVM)的基本型。

四、对偶问题

上面,我们得到了SVM的基本型,通过求解该问题,我们就可以得到最大间隔划分超平面对应的模型:

,其中w和b是参数。下面,我们通过拉格朗日乘子法将其转换成“对偶问题”以更高效地求解。

该问题的拉格朗日函数为:

其中,令L(w,b,α)对w和b求导为0,可得:

将上式带入到(w,b,α)中,可以消去w和b变量,从而只剩下α变量。则最终可得到如下式:

解出后,求出w和b,就可以得到模型:

五、核函数

上面,我们假设训练样本是线性可分的,从而推到得到如下式子。

但是,在实际应用中,不可能所有样本都是线性可分的,如果碰上下面这种分线性分布的样本,如要和划分超平面呢?

下面就引用到核函数的概念。

假设,我们可以找到一个函数Φ(x)可以将样本进行映射,从非线性分布的低维空间,映射到线性可分的高维空间。那么就可以继续引用上面的结论进行分析。

我们令Φ(x)为映射后的特征向量,则在映射后的特征空间中,划分超平面对应的模型为:

则有:

其对偶问题为:

在上式中的计算由于涉及到,有可能映射后的特征空间维数很高,甚至无穷维,从而导致计算困难。为了简化计算,可以设想一个函数:

也就是xixj在特征空间的内积等于他们在原始样本空间中通过函数k()计算的结果,通过这样转换,我们就不必去计算高维特征空间中的内积,于是上式可以重新写为:

则求解后得到划分超平面模型如下:

这里函数k就是核函数。

下表是常用的核函数:

打赏

发表评论

电子邮件地址不会被公开。