支持向量机基本模型

支持向量机的基本思想是,在如下的样本集中:

基于训练集D在样本空间中找到一个划分超平面,将不同类别的样本分开

划分超平面可以表示成如下的线性方程:

其中w为法向量,b为位移项,空间内任意一点到以上超平面的距离为:

则有

距离超平面最近的几个训练样本点使得上式的等号成立,它们被称为支持向量(support vector),两个异类支持向量到超平面的距离之和为:

称之为间隔(margin)

支持向量机的目的即找到最大间隔(maximum margin)的划分超平面,即解如下的不等式约束的凸优化问题:

等价于:

上述模型即支持向量机(Support Vector Machine,SVM)的基本模型

SMO算法

对偶问题求解

支持向量机的基本模型是一个凸二次规划(convex quadratic programming)问题,可以使用拉格朗日乘子得到其对偶问题(dual problem)从而求解

对于式子:

对每一条约束增加拉格朗日乘子,得到该问题的拉格朗日函数:

从而得到对偶问题为:

上述过程的KKT(Karush-Kuhn-Tucker)方程为:

可以求解支持向量机的模型

支持向量机有一个重要性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关

SMO算法

为了求解该对偶问题,SMO(Sequential Minimal Optimization)算法是一个很高效的算法,其基本思路是,先固定 ai 之外的所有参数,然后求 ai 上的极值。由于存在约束 Σaiyi=0 ,若固定 ai 之外的其他变量,则 ai 可由其他变量导出。于是,SMO每次选择两个变量 ai 和 aj ,并固定其他参数。在参数初始化后,SMO不断执行如下两个步骤直至收敛:

  • 选取一对需更新的变量 ai 和 aj
  • 固定 ai 和 aj 以外的参数,求解对偶问题获得更新后的 ai 和 aj

支持向量机的超平面中的偏移量 b 的求算方式为:

软间隔与正则化

软间隔支持向量机

并不是每一组训练集在特种空间内都是线性可分的,为了缓解该问题,在有些时候可以允许支持向量机在一些样本上出错,使用软间隔(soft margin)的方式:

软间隔指允许某些样本不满足如下的约束条件:

但在最大化间隔的同时也使得不满足约束的样本应该尽可能的少,于是优化目标可以写为:

其中,C>0,为常数,C为无穷大时,上式要求所有样本均满足约束条件,C取有限值时,上式允许一些样本不满足约束条件。

l0/1是“0/1损失函数”:

一些替代损失(surrogate loss)如下:

图像如下:

引入松弛变量(slack variables)可以改写式子成为:

解以上的二次规划问题,依然使用对偶函数法,得到其拉格朗日函数为:

对偶问题为:

KKT方程为:

优化目标的一般形式

优化目标的一般形式为:第一项用来描述划分超平面的间隔大小,另一项用来表述训练集上的误差:

  • 第一项称为结构风险(structural risk),用于描述模型的某些性质
  • 第二项称为经验风险(empirical risk),用于描述模型与训练数据的契合程度
  • C用于对二者进行折中

支持向量回归

考虑回归问题,给定样本

希望得到一个回归模型:

使得y和f(x)尽可能接近,w和b是待定参数

支持向量回归(Support Vector Rrgression,SVR)假设能容忍f(x)和y之间有一个偏差,当f(x)和y之间的差别大于该偏差的时候才计算损失,相当于以f(x)为中心构建了一个宽度为两倍偏差的间隔带,若训练样本落入此间隔带则认为模型预测正确

SVR问题可以表示为:

其中的l为不敏感损失函数(insensitive loss function)

引入松弛变量后可以重写为:

依然可以使用对偶问题求解

全文参考:周志华 著 《机器学习》