支持向量机SVM

线性可分支持向量机与硬间隔最大化


线性可分支持向量机

考虑一个二分类问题,假设输入空间和特征空间为两个不同的空间。输入空间为欧式空间或离散集合,特征空间为欧式空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应,并将输入空间中的输入映射为特征空间中的特征向量。非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。所以输入都有输入空间转换到特征空间,支持向量机的学习是在特征空间进行的。

定义 线性可分支持向量机:给定线性可分训练数据集,通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为:

以及相应的分类决策函数:

函数间隔和几何间隔

一般来说,一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面$wx+b=0$确定的情况下,$|wx+b|$能够相对的表示点$x$距离超平面的远近。而$wx+b$的符号与类标记$y$的符号是否一致能够表示分类是否正确。所以可用量$y(wx+b)$来表示分类的正确性以及确信度,这就是函数间隔的概念。

为什么$|wx+b|$是相对的表示距离:首先这指的是函数距离,同一个函数内有比较价值。其次因为$b$的影响,真正距离并不是这个,但是距离的比较都有这个$b$,所以这里就不再考虑

定义 函数间隔:对于给定的训练数据集$T$和超平面$(w,b)$,定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为

定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的函数间隔之最小值(注意这里是指到平面最小距离的点的距离,其实就是支持向量到分离超平面的距离),即:

选择分离超平面时,只有函数间隔还不够,因为只要成比例的改变$w$和$b$,例如将它们改写为$2w$和$2b$,超平面并没有改变,但函数间隔却成为原来的$2$倍。所以可以对分离超平面的法向量$w$加某些约束,如规范化,$||w||=1$,使得间隔是确定的。这时函数间隔成为几何间隔。

定义 几何间隔:对于给定的训练数据集$T$和超平面$(w,b)$,定义超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔为:

定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的几何间隔之最小值(注意这里是指到平面最小距离的点的距离,其实就是支持向量到分离超平面的距离),即:

函数间隔和几何间隔的关系:

如果$||w||=1$,那么函数间隔和几何间隔相等。如果超平面参数$w$和$b$成比例的改变(超平面没有改变),函数间隔也按此比例改变,而几何间隔不变。

间隔最大化

间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着一充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

最大间隔分离超平面

求一个几何间隔最大的分离超平面可以表示为下面问题的最优化:

我们希望最大化几何间隔$\gamma$($\gamma$为所有点的中几何距离最短的点的几何距离,就是支持向量的几何距离),约束条件表示的是超平面关于每个训练样本点的几何间隔至少是$\gamma$。

考虑几何间隔与函数间隔的关系式$(1)$,可以将这个问题改写为(这里为了构造出$||w||$):

**函数间隔$\hat\gamma$的取值并不影响最优化问题的解。将$w,b$按比例变化为$\lambda w,\lambda b$,超平面并未发生改变,函数间隔变为$\lambda\hat\gamma $。所以函数间隔的改变只影响$w,b$的系数,不改变超平面。这样就可以去$\hat\gamma=1$,并带入以上最优化问题。注意到最大化$1\over ||w||$和最小化${1\over 2}||w||^2$是等价地。于是就得到了下面线性可分支持向量机学习的最优化问题:

SVM部分暂时弃更,东西差不多都是《统计学习方法上的》,关于自己理解的部分也都标注在了书上,手码实在太多了,这部分先看书把。。

0%