SVM原理简介

时间:2022-03-30 09:00:56

本文只是简单介绍一下SVM的理论框架,想要详细了解当中细节问题处理可以参看后续章节或者网上各种详细资料。推荐Andrew Ng的斯坦福大学机器学习课程。

年代中期发展起来的基于统计学习理论的一种机器学习方法,通过寻求结构化风险最小来提高学习机泛化能力,实现经验风险和置信范围的最小化,从而达到在统计样本量较少的情况下,亦能获得良好统计规律的目的。

简单的讲支持向量机(SVM)是一种分类模型,对于待分类的数据,我们总能找到一种超平面把它分割开来,当确立了这一超平面(下图a)后,我们要做的是最大化最近邻样例到平面的几何间隔γ(如下图b),这正是整个SVM算法所要解决的核心问题,即maxγ,我们列出了超平面的一般方程y=wx+b。

  SVM原理简介

  B点所在的SVM原理简介分割面。任何其他一点,比如A到该面的距离以SVM原理简介表示。

SVM原理简介

  上文已经有提到我们的最终目的是最大化最小几何间隔minSVM原理简介,那我们怎么找到这个几何间隔呢? 根据上面得到的条件,我们可以得出这样一个优化式子:

  SVM原理简介

  这里的SVM原理简介是最小函数间隔,即任意点的函数间隔都要大于SVM原理简介,为了计算方便,我们调整w和b来规约SVM原理简介=1(这样做不会对计算结果有影响)。因此我们的式子改写成:

  SVM原理简介

  现在我们把问题转换成了二次规划带有线性约束的问题,我们来讨论拉格朗日对偶问题。

  这是个不等式约束的极值问题求法

  SVM原理简介

  我们列出上述问题的一般化的拉格朗日公式:

  SVM原理简介

  SVM原理简介

  这里的αβ是拉格朗日乘子, P代表primal。假设SVM原理简介或者SVM原理简介,那么我们总是可以调整SVM原理简介SVM原理简介来使得SVM原理简介有最大值为正无穷。而只有g和h满足约束时,SVM原理简介为f(w)。这个函数的精妙之处在于SVM原理简介,而且求极大值。

因此我们可以写作

SVM原理简介

这样我们原来要求的min f(w)可以转换成求SVM原理简介了。

SVM原理简介

我们使用SVM原理简介来表示SVM原理简介。如果直接求解,首先面对的是两个参数,而SVM原理简介也是不等式约束,然后再在w上求最小值。这个过程不容易做,那么怎么办呢?

我们先考虑另外一个问题SVM原理简介

D的意思是对偶,SVM原理简介将问题转化为先求拉格朗日关于w的最小值,将SVM原理简介SVM原理简介看作是固定值。之后在SVM原理简介求最大值的话:

SVM原理简介

这个问题是原问题的对偶问题,相对于原问题只是更换了min和max的顺序,而一般更换顺序的结果是Max Min(X) <= MinMax(X)。然而在这里两者相等。用SVM原理简介来表示对偶问题如下:

SVM原理简介

下面解释在什么条件下两者会等价。假设f和g都是凸函数,h是仿射的(affine,SVM原理简介)。并且存在w使得对于所有的i,SVM原理简介。在这种假设下,一定存在SVM原理简介使得SVM原理简介是原问题的解,SVM原理简介是对偶问题的解。还有SVM原理简介另外,SVM原理简介满足 Karush-Kuhn-Tucker( KKT condition),该条件如下:

SVM原理简介

所以如果SVM原理简介满足了KKT,那么他们就是原问题和对偶问题的解。让我们再次审视公式(5),这个条件称作是KKT dual complementarity条件。这个条件隐含了如果SVM原理简介,那么SVM原理简介。也就是说,SVM原理简介时,w处于可行域的边界上,这时才是起作用的约束。而其他位于可行域内部(SVM原理简介的)点都是不起作用的约束,其SVM原理简介。这个KKT双重补足条件会用来解释支持向量和SMO的收敛测试。

介绍完对偶问题后,再回过头来看找出最优间隔分类器的问题:

  SVM原理简介

  从KKT条件得知只有函数间隔是1(离超平面最近的点)的线性约束式前面的系数SVM原理简介,也就是说这些约束式SVM原理简介,对于其他的不在线上的点(SVM原理简介),极值不会在他们所在的范围内取得,因此前面的系数SVM原理简介.注意每一个约束式实际就是一个训练样本。如下图虚线上的三个点支撑整个超平面的构成,故称它们为支持向量。

  SVM原理简介

  我们提出对偶问题的关键点是为了导出一个只包含内积SVM原理简介(输入特征空间中点的内积也可以表示成SVM原理简介)的公式,这一算法将在解决非线性分类时引用核函数(下文会有提及)其关键作用。

  我们首先构建这个优化问题的拉格朗日公式

  SVM原理简介

  再来得出这一问题的对偶形式,先要最小化SVM原理简介,因此得到SVM原理简介关于w和b的偏导(固定拉格朗日乘子)

  SVM原理简介

  SVM原理简介

  把上述结论带入原方程得到:

  SVM原理简介

  别忘了我是要最大化上面的这个方程:

  SVM原理简介

  因此:

  SVM原理简介

  这也达到了我们先前提到的目标,导出一个只包含内积SVM原理简介这一位置量的公式,其中y为类型的标签,如:要分类的类别为两类则y取+1或-1,至于拉格朗日乘子的求解涉及到后续文章所要提及的内容,所以索性放在后面讲了。