机器学习之SVM支持向量机（一）

支持向量机(SVM)入门

1 摘要

支持向量机是一种二类分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，所以模型的学习策略就是间隔最大化，因此形式可化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题，支持向量机的学习算法是求解凸二次规划的最优化算法。

对于入门支持向量机，可以先不用看懂上面的摘要，通过逐步理解下面的公式推导，再回过来看摘要，才能彻底掌握支持向量机。

2 线性可分支持向量机原理

考虑一个二类分类问题，比如金融业的是否违约问题，假定给定一个特征空间上的训练数据集T={(x1,y1),(x2,y2),……,(xn,yn)}.X为第i个样本的特征向量，y即是对应的分类标记，当y=+1时，称这个样本为正例，当y=-1时，该样本为负例。对应金融业的信用卡违约问题，+1就代表该人没有违约，-1代表该人违约。再假设训练数据集T是线性可分的。

模型的学习目标就是在特征空间中找到一个分离超平面，能将实例分到不同的类中，分离超平面对应于方程ωx+b=0，该超平面由法向量ω和截距b决定，分离超平面将特征空间划分为两部分，一部分是正例，一部分是负例，法向量指向的一侧为正例，另一侧为负例。用图表示如下所示：

得到分离超平面后，我们也得到了相应的分类决策函数f(x)=sign(ωx+b)，对于以后的未知分类的特征数据集X，我们将X代入该函数即可知道其分类结果。因此该函数称为线性可分支持向量机。

下面来推导如何找到分离超平面：

3 支持向量机的推导过程

如何找到两个集合的最优分割超平面，使得两集合尽量分开。

支持向量机的学习策略就是通过间隔最大化得到分割超平面。先定义分离超平面的形式为

φ(x)是某个确定的特征空间转换函数，它的作用是将x映射到更高的空间维度中。最简单直接的就是令φ(x)=x，就得到了线性的超平面，这里的φ(x)对后面理解核函数（非线性的支持向量机）有帮助，所以在公式推导中先用φ(x)代替x。

整理符号有：

首先，考虑下图的二维特征空间（即样本只有两个特征）中的分类问题，有A,B,C三点，表示三个样本，均在一个类别中，A距离超平面较远，若预测该点为正例，就比较确定预测是正确的，C距离超平面较远，若预测该点为正例，就不那么确信，B的确信度在A,C之间。因此一个点距离分离超平面的远近可以表示分类预测的确信程度，而点到直线的距离可表示为ωx+b，ωx+b与y的符号是否一致表示分类是否正确。所以y(ωx+b)来表示分类的正确性及确信度。

但是对于y(ωx+b)，要是成比例地改变ω和b，那么此时的间隔就成为原来的2倍，但是超平面没有改变，因此我们规范化超平面法向量ω，使得间隔是确定的。这样点到直线的距离就是 y(ωx+b)/ω。

通过对训练数据集找到间隔最大的超平面意味着以充分大的确信度对训练数据进行分类，也就是说，不仅要将正负例点分开，还要对最难分的样本点也要有足够大的确信度分开。所以间隔最大化的原理就是将距离超平面最近的点的间隔最大化。所以支持向量机中的支持向量就是距离超平面最近的那些点。我们只要找到了这些点，就可以确定出分离超平面的法向量ω和截距b，反过来想，距离分离超平面最近的点形成的线就为ωx+b=±1，即距离超平面最近的点到超平面的距离是1，对于一般情况，y(ωx+b)≥1。

通过上面的分析建立以下模型：

约束条件为：

上面的规划问题等价于如下形式：

进一步可等价于：

这是一个凸二次规划问题，运用拉格朗日乘子法使上面的有约束规划转变为无约束规划问题，拉格朗日函数为：

原始问题为极小极大问题min max L(ω,b,α)，根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题max min L(ω,b,α)，当具有强对偶性时，对偶问题的解即是原始问题的解。因为格式的限制，具体关于拉格朗日对偶性的推导参考我的博客：http://blog.csdn.net/pylady/article/details/78855554

对对偶问题的无约束求解先求解minL(ω,b,α)问题。将拉格朗日函数L(ω,b,α)分别对ω,b求偏导，并令其等于0：

将上面的结论代入拉格朗日函数为：

此时上面的L(ω,b,α)=min L，那么求解对偶问题接下来是求解max问题：

等价于求：

那么要求解得到分离超平面，需要求解出最优的α，即是求解上面的规划问题。之所以要最后变为最小化问题，是因为求解该问题需要采用SMO序列最小最优化方法。

4 支持向量机和感知机的区别

当训练数据集线性可分时，存在无穷个分离超平面可将两类数据正确分开，感知机利用误分类最小的策略求得超平面，不过这时的解有无穷多个，但是线性可分支持向量机利用间隔最大化策略求最优超平面，这时的解是唯一的。

待更新：SMO求解方法、软间隔最大化、非线性支持向量机（核函数）