SVM学习

所需知识:

  • 对于一个平面:Ax+By+Cz+D=0

某点到面的距离:

  • 平面:Ax+By+Cz+D=0的法向量:w = [A; B; C]

 

 

支持向量机(SVM)

支持向量机(Support Vector Machine, SVM)的基本模型是在特征空间上找到最佳的分离超平面使得训练集上正负样本间隔最大。SVM是用来解决二分类问题的有监督学习算法,在引入了核方法之后SVM也可以用来解决非线性问题。如下图所示:

将不同的类别的训练样本分开的划分超平面可能有很多,但直观上看,我们应该去找位于两类训练样本“正中间”的划分超平面即途中红色的,因为该平面对样本的局部扰动(噪声等)的“容忍性最佳”。训练集以外的样本可能比上图的训练样本更接近超平面,这样一来,上图的许多超平面可能出现分类错误,而红色的这个超平面将两个类隔得足够远,收到的影响也最小,也就是说红色的这个超平面分类结果是最鲁棒了,对于未见的样本泛化能力最好。

我们用如下线性方程来表示超平面:

wTx + b = 0

其中:

w = [w1;w2;w3;…;wn],由上文所需知识可以知道,w为超平面的法向量,b为位移项。

此时,由上文所需知识可知,样本空间的任意点到超平面(w,b)的距离可以表示为:

r = | wTx + b |/||w||

当超平面(w,b)能将训练样本正确分类,则有:

wTxi + b ≥ +1, yi = +1

wTxi + b ≤ -1, yi = -1

如下图所示,距离到红色超平面最近的三个训练样本对应为:

wTxs + b = +1

wTxs + b = -1

他们被称之为“支持向量”,两个异类支持向量到红色超平面距离之和称之为为“间隔”,表示为:

r = 2/||w||

 

到这里,我们的问题就是:如何找到具有“最大间隔”的超平面,也就是找到一组w,b的参数,使得:

r = 2/||w|| 达到最大,但同时切记不要忘了求这个式子最大值的时候,是有约束条件的,也就是:

wTxi + b ≥ +1, yi = +1

wTxi + b ≤ -1, yi = -1

为了简化,我们可以将两个式子合并成如下:

yi wTxi + b ≥ +1

插个题外话,什么是在约束条件下求最大最小值?很多人可能看到直接求最大最小值还不虚,看到约束条件就有点晕了。其实你可以将问题类比为:找出你们班最高的人。这样相信你应该很好找,但如果我加上一句,找出你们班上,你喜欢的女生当中,最高的人,相信你也应该很好找,没错,这里你喜欢的女生当中也就是一个约束条件,他约束你在找最高的人的时候,一定要这些人满足

1)你喜欢;

2)是女生;

其实在求上述约束条件下,r = 2/||w||最大值时,对应着||w||-1最大化,也就等价于最小化|| w ||2,于是上式可写为:

min 1/2|| w ||2

并且满足:

yi (wTxi + b) ≥ +1,     i = 1,2,…,m       (原式)

以上就是支持向量机的基本型。在求解w,b时,我们需要用到拉格朗日对偶性来求解。对于上式求解问题,我们可以添加拉格朗日乘子αi≥0,以将该问题的拉格朗日函数写为:

L(w bα)=1/2||w||2∑αi yi (wTxi + b) −1          (1)

L(w bα)w 和b求偏导使得偏导为0,可得:

w = ∑αi yi xi                             (2)

0 = ∑αi yi                                  (3)

将(2)式带入(1)式,可以将w ,b消去,再考虑到式3的约束,以及αi≥0的约束,得到原式的对偶问题如下:

                                                                                                                                                                  (4)

此时,根据式(4)解出αi后,可以得到如下模型:

                                                                                                                                                                  (5)

特别注意,由于原式中有不等式约束,因此上述的求解过程需要满足KKT条件,也就是要求:

                                                                                                                                                                  (6)

也就是说,对于任意训练样本(xiyi),总有αi = 0或者yi (wTxi + b) = 1。

  • 若αi = 0,则该样本不会在式(5)的求和中出现,也不会对f(x)有任何影响
  • 若αi > 0,则必有yi (wTxi + b) = 1,此时所对应的样本点位于最大间隔边界,是一个支持向量。这显示出支持向量机的一个重要性质:训练完成后,大部分的样本都不需要保留,最终模型只与支持向量有关。

求解式(4)时,求解的复杂度和训练的样本数成正比,为了避开这个障碍,人们提出了很多高效的算法,SMO是一个著名的算法,可以不断迭代后,求得αi。

求偏移量b的过程中,我们可以发现,对于任意的支持向量,都有ys (wTxs + b) = 1,

所以:

b = 1/S Σ(1/ys ΣαiyixiTxs)

分类: Machine-Learning

发表评论

电子邮件地址不会被公开。 必填项已用*标注