支持向量机基本模型

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

image

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

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

image

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

image
则有
image

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

image
称之为间隔（margin） image

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

image

等价于：

image

上述模型即支持向量机（Support Vector Machine，SVM）的基本模型

SMO算法

对偶问题求解

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

对于式子：

image

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

image
从而得到对偶问题为：
image

上述过程的KKT（Karush-Kuhn-Tucker）方程为：

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

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

SMO算法

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

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

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

image

软间隔与正则化

软间隔支持向量机

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

image

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

image

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

image

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

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

image

一些替代损失（surrogate loss）如下：

image

图像如下：

image

引入松弛变量（slack variables）可以改写式子成为：

image

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

image

对偶问题为：

image
KKT方程为：
image

优化目标的一般形式

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

image

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

支持向量回归

考虑回归问题，给定样本

image

希望得到一个回归模型：

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

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

image

SVR问题可以表示为：

image

其中的l为不敏感损失函数（insensitive loss function）

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

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

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

---

转载请注明出处，本文永久更新链接：小天才的杂货铺-个人博客