Support Vector Machine

机器学习

线性支持向量机

现在有一个二维平面,平面上有两种不同的数据,分别用圈和叉表示。由于这些数据是线性可分的,所以可以用一条直线将这两类数据分开,这条直线就相当于一个超平面,超平面一边的数据点所对应的y全是-1 ,另一边所对应的y全是1。

这个超平面可以用分类函数 f(x) = W*x + b 表示,当f(x)等于0的时候,x便是位于超平面上的点,而f(x)大于0的点对应 y=1 的数据点,f(x)小于0的点对应y=-1的点。换言之,在进行分类的时候,遇到一个新的数据点x,将x代入f(x) 中,如果f(x)小于0则将x的类别赋为-1,如果f(x)大于0则将x的类别赋为1。

接下来的问题是,如何确定这个超平面呢?从直观上而言,这个超平面应该是最适合分开两类数据的直线。而判定最适合的标准就是这条直线离直线两边的数据的间隔最大。所以,得寻找有着最大间隔的超平面。

函数间隔Functional margin与几何间隔Geometrical margin

在超平面w*x+b=0确定的情况下,|w*x+b|能够表示点x到距离超平面的远近,而通过观察w*x+b的符号与类标记y的符号是否一致可判断分类是否正确,所以,可以用(y*(w*x+b))的正负性来判定或表示分类的正确性。于此,我们便引出了函数间隔(functional margin)的概念。定义函数间隔为:

functional margin

而超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值(其中,x是特征,y是结果标签,i表示第i个样本),便为超平面(w, b)关于训练数据集T的函数间隔:

= mini (i=1,…n)

但这样定义的函数间隔有问题,即如果成比例的改变w和b(如将它们改成2w和2b),则函数间隔的值f(x)却变成了原来的2倍(虽然此时超平面没有改变),所以只有函数间隔还远远不够。

事实上,我们可以对法向量w加些约束条件,从而引出真正定义点到超平面的距离–几何间隔(geometrical margin)的概念。

假定对于一个点 x ,令其垂直投影到超平面上的对应点为 x0 ,w 是垂直于超平面的一个向量,为样本x到超平面的距离,如下图所示:

根据平面几何知识,有

其中   w   为w的二阶范数(范数是一个类似于模的表示长度的概念),是单位向量(一个向量除以它的模称之为单位向量)。

几何间隔()定义为

从上述函数间隔和几何间隔的定义可以看出:几何间隔就是函数间隔除以   w   ,而且函数间隔y*(wx+b) = y*f(x)实际上就是 f(x) ,只是人为定义的一个间隔度量,而几何间隔 f(x) /   w   才是直观上的点到超平面的距离。

最大间隔分类器(Maximum Margin Classifier)

对一个数据点进行分类,当超平面离数据点的“间隔”越大,分类的确信度(confidence)也越大。所以,为了使得分类的确信度尽量高,需要让所选择的超平面能够最大化这个“间隔”值。这个间隔就是下图中的Gap的一半。

这里要找的最大间隔分类超平面中的“间隔”指的是几何间隔

于是最大间隔分类器(maximum margin classifier)的目标函数可以定义为:

根据几何间隔的定义,如果令函数间隔等于1,则上述函数转化为:

在约束条件下最大化1/||w||值,而1/||w||便是几何间隔。

如下图所示,中间的实线便是寻找到的最优超平面(Optimal Hyper Plane),其到两条虚线边界的距离相等,这个距离便是几何间隔,两条虚线间隔边界之间的距离等于2,而虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上,所以它们满足,而对于所有不是支持向量的点,则显然有

参考:


Original link:https://izhangzhihao.github.io//2017/12/04/SVM/

Search

    Table of Contents