支持向量机(Support Vector Machine,SVM)是一个经典两类分类算法,其找到的分割超平面具有更好的鲁棒性,因此广泛使用在很多任务上,并表现出了很强优势。

介绍

给定一个两分类数据集D={(x^n, y^n)},n属于N,其中y_n 属于{+1,-1},如果两类样本是线性可分的,即存在一个超平面(公式-1)

将两类样本分开,那么对于每个样本都有

数据集D中的每个样本x^n 到分隔超平面的距离为:

我们定义整个数据集D中所有样本到分隔超平面的最短距离为间隔(Margin)(公式-2)

如果间隔 gamma越大,其分隔超平面对两个数据集的划分越稳定,不容易受噪声等因素影响,支持向量机的目的是找到一个超平面(w^ , b^ )使得gamma最大,即(公式-3)

则(公式-3)等价于(公式-4)

数据集中所有满足 y^n (w^T x^n +b) =1 的样本点,都称为支持向量(support vertor)

对于一个线性可分数据集,其分隔的超平面有多个,但是间隔最大的超平面是唯一的。下图给定了支持最大间隔分隔超平面的示例,其红色样本点为支持向量。

![支持向量机示例](https://img-blog.csdnimg.cn/20190417110614374.png)

参数学习

凸函数 & 凹函数
关于凹凸函数的定义和性质可以参考下图:

![image](https://img-blog.csdnimg.cn/20190420165249483.jpg)

为了找到最大间隔分割超平面,将公式-4改写为凸优化问题(公式-5):

使用拉格朗日乘数法,公式-5的拉格朗日函数为(公式-6):

其中

为拉格朗日乘数。计算公式-6关于w和b的导数,并令其等于0得到(公式-7)

和(公式-8)

将公式-7代入公式-6,并利用公式-8,得到拉格朗日对偶函数(公式-9):

支持向量机的主优化问题为凸优化问题,满足强对偶性,即主优化问题可以通过最大化对偶函数

对偶函数 Gamma(lambda)是一个凹函数,因此最大化对偶数是一个凸优化问题,可以通过多种凸优化方法进行求解,得到拉格朗日乘数的最优值 lambda^* 。但由于其约束条件的数量为训练样本数量,一般的优化方法代价比较高,因此在实践中通常采样比较高效的优化方法,比如SMO(Sequential Minimal Optimization)算法等。

根据KKT条件中的互补松弛条件,最优解满足(公式-10)

如果样本x^n 不在约束边界上,(lambda_n)^,其约束失效;如果样本x^n在约束边界上,(lambda_n)^ >=0。这些在约束边界上的样本点称为支持向量(support vector),即离决策平面距离最近的点。

再计算出 lambda^后,根据公式-7计算出最优权重w^,最优偏置b^*可以通过任选一个支持向量(x,y)计算得到(公式-11)

最优参数的支持向量机的决策函数为(公式-12)

支持向量机的决策函数只依赖 lambda_n^*>0的样本点,即支持向量。

支持向量机的目标函数可以通过SMO等优化方法得到全局最优解,因此比其他分类器的学习效率更高。此外,支持向量机的决策函数只依赖与支持向量。与训练样本总数无关,分类速度比较快。

核函数

支持向量机还有一个重要的优点是可以使用核函数(kernal)隐式的将样本从原始特征空间映射到更高维的空间,并解决原始特征空间中的线性不可分问题。比如在一个变换后的特征空间中,支持向量机的决策函数为(公式-13)

其中

为核函数,通常不需要显式的给出φ(x)的具体形式,可以通过核技巧(kernel trick)来构造。比如以x,z属于R^2为例,我们可以构造一个核函数(公式-14)

来隐式的计算x,z在特征空间φ中的内积,其中:

软间隔

在支持向量机的优化问题中,约束条件比较严格。如果训练集中的样本在特征空间中不是线性可分的,就无法找到最优解。为了能够容忍部分不满足约束的样本,我们可以引入松弛变量,将优化问题变为(公式-15):

其中参数C>0用来控制间隔和松弛变量惩罚的平衡,引入松弛变量的间隔称为软间隔(soft margin)。公式-15也可以表示为经验风险+正则化项的形式(公式-16)。

其中

称为hinge损失函数,1/C可以看作是正则化系数。软间隔支持向量机的参数学习和原始支持向量机类似,其最终决策函数也只和支持向量有关,即满足

的样本。


打开微信扫一扫,关注微信公众号【搜索与推荐Wiki】