支持向量机基本模型
支持向量机的基本思想是，在如下的样本集中：
基于训练集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）
引入松弛变量后可以重写为：
依然可以使用对偶问题求解
全文参考：周志华 著 《机器学习》
转载请注明出处，本文永久更新链接：小天才的杂货铺-个人博客
