支持向量机（support vector machine）

2018-12-06 本文已影响5人井底蛙蛙呱呱呱

SVM是一种二分类模型，他的基本模型是定义在特征空间上的间隔最大的线性分类器。当使用不同的核函数时，可以使得SVM成为一个非线性分类器。支持向量机的学习策略是间隔最大化，可转化为一个求解二次函数凸优化的问题。

支持向量机又可分为线性可分支持向量机（硬间隔最大化，硬间隔支持向量机），线性支持向量机（软间隔最大化，软间隔支持向量机）和非线性支持向量机（核函数）。

线性可分支持向量机

首先，让我们来看看最简单的情况——线性可分支持向量机。

给定线性可分数据集，通过间隔最大化可得到一个分离超平面可将数据集分为两类，分割超平面可表示为：

相应的分类决策函数为：

φ(x)是某个确定的特征空间转换函数，他的作用是将x映射到更高维度的空间。最简单的φ(x)=x。
w为权重向量，b为偏置项。

sign是指示函数。目标值yi∈（-1,1）。

对于任何一个数据集，都有无数个超平面可将数据集分为两类，我们的目标是要寻找最大间隔分离超平面。

寻找最大间隔分离超平面即寻找w,b = argmax_j min_i(W_iX_j+b_j)，简言之就是最小样本的最大距离。

对于每一个超平面，都能找到离这个超平面距离最小的点(上式中最小的i)，这个距离就是间隔，而比较所有的超平面（上式中的j）的的间隔寻找最大的间隔的超平面也即是我们要找的超平面。

要使得所有样本都被正确分类，则需要满足：

当所有样本都被正确分类时，根据解析几何中点到平面的距离公式，每个样本点离超平面的距离为：

其中||w||是权重向量w的L2范数，即：

因此，我们寻找最大间隔超平面的目标函数可转化为：

也即转化为带约束条件的最优化问题：

取倒转化为求二次函数的最优化问题：

凸优化问题
这个优化问题我们很熟悉，可以使用拉格朗日乘子法，如下：

转化为对偶问题：

对里面的极小先求导计算：

然后将上面求导得到的结果带入原拉格朗日函数中：

添加负号将求最大值转化为最小值：

到了这里就可以用SMO算法求的α的值了，将阿尔法分别带入w中可求得w的值

为什么b可以由代入yj表示？因为这是监督学习啊，确定了α不为零的i后，对应的几个样本的数据就确定了，这些都是已知的而又由w,b的表达式可知他们只依赖于训练数据中对应于α_i大于0的样本点（x_i, y_i）,而其他样本对于w,b没有影响。而这些训练数据中对应于α_i大于0的样本点称为支持向量。

线性支持向量机与软间隔最大化

线性可分问题的支持向量机学习方法，对线性不可分数据是不适用的，因为这时上述方法中的不等式约束并不能都成立。怎么才能将其扩展到线性不可分问题呢？这就需要修改硬间隔最大化，使其成为软间隔最大化。

当数据线性不可分时，我们可以对每个样本X_i引入一个松弛变量ξ_i，使得函数间隔加上松弛变量后大于等于1，也即约束条件变为：

目标函数也变为：

这里C称为惩罚因子，一般由应用问题决定，C值大时，对误分类的惩罚增加，C值小时对误分类的惩罚减小，上面加了松弛变量后的目标函数有两层含义：使1/2||w||²尽量小，即间隔尽量大，同时使误分类点的个数尽量小，C是调和二者的系数。

更直白的说，惩罚因子C决定了你有多重视离群点带来的损失，当所有离群点的松弛变量的和一定时，C越大，目标函数的损失也就越大，这意味着你非常不愿意放弃这些离群点。当你把C定为无穷大时，只要有一个离群点，目标函数的值也会变得无穷大，使得我们无法放弃任何一个离群点，这时其实就退化成了硬间隔问题，这也意味着模型容易过拟合，泛化能力差。

于是线性不可分的线性支持向量机的学习问题变成了如下的凸二次规划（converx quadratic programming）问题：