关于机器学习算法的程序，在我的Github上，欢迎大家follow：

Github地址：https://github.com/xuesongjaybluce

 

SVM在之前的很长一段时间内是性能最好的分类器，它有严密而优美的数学基础作为支撑。在各种机器学习算法中，它是最不易理解的算法之一，要真正掌握它的原理有一定的难度。在本文中，我将带领大家通过一张图来理清SVM推导过程的核心过程。

简介：SVM由Vapnik等人在1995年提出，在出现之后的20多年里它一直是学术界和工业界最具影响力的机器学习算法之一。在深度学习技术出现之前，使用高斯核的SVM在很多问题上一度取得了最好的效果。SVM不仅可以用于分类问题，还可以用于回归问题。它具有泛化性能好，适合小样本等优点，被广泛应用于各种实际问题。

最简单的SVM从线性分类器导出，根据最大化分类间隔的目标，我们可以得到线性可分问题的SVM训练时求解的问题。但现实应用中很多数据是线性不可分的，通过加入松弛变量和惩罚因子，可以将SVM推广到线性不可分的情况，具体做法是对违反约束条件的训练样本进行惩罚，得到线性不可分的SVM训练时优化的问题。这个优化问题是一个凸优化问题，并且满足Slater条件，因此强对偶成立，通过拉格朗日对偶可以将其转化成对偶问题求解。

到这里为止，支持向量机还是一个线性模型，只不过允许有错分的训练样本存在。通过核函数，可以将它转化成非线性模型，此时的对偶问题也是一个凸优化问题。这个问题的求解普遍使用的是SMO算法，这是一种分治法，它每次选择两个变量进行优化，这两个变量的优化问题是一个带等式和不等式约束条件的二次函数极值问题，可以求出公式解，并且这个问题也是凸优化问题。优化变量的选择通过KKT条件来确定。
 

支持向量机的主要思想可以概括如下：给定训练样本，支持向量机建立一个超平面作为决策曲面，使得正例和反例之间的隔离边缘被最大化。

在处理更加复杂的线性不可分的模式时，我们原则性的对算法的基本思想进行扩展。引入内积的思想，加入核技巧，使线性不可分的数据在高维空间中线性可分。

1  线性可分模式的最优超平面

考虑训练样本{(,)},其中是输入模式的第i个样例，是对应的期望响应（目标输出）。首先假设由子集=+1代表的模式（类）和代表的模式是“线性可分的”。用于分离的超平面形式的决策曲面方程是：

其中是输入向量，是可调的权值向量，是偏置。因此可以写成：

对于一个给定的权值向量和偏置，支持向量机的目标是找到一个特殊的超平面，这个超平面的分离边缘最大。在这种条件下，决策曲面称为最优超平面（optimal hyperlane）。如下图所示：中间的红线为最优超平面

 

点到超平面的距离定义：几何间隔 Geometrical margin

尤其，从原点（即）到最优超平面的距离由给定。如果b>0,原点在最优超平面的上部，如果b<0,原点在下部。如果b=0，最优超平面通过原点。

则支持向量x到最有超平面的倒数距离为：由条件知道，最大化两个类之间的分离边缘等于最小化权值向量的欧几里得范数。即：

再加上对参数的限制条件（因为是找数据中的支持向量），公式变为：

其中，上式中代价函数是关于的凸函数，约束条件是关于的线性函数。所以应用拉格朗日乘子方法去解决约束最优问题。

首先，建立拉格朗日函数：

约束最优问题的解由拉格朗日函数的鞍点决定。拉格朗日函数的鞍点具有实根但符号相反，这样的奇异点一定是不稳定的。鞍点关于必定最小化，同时关于a必定最大化，我们对同时求导：

并将结果带入拉格朗日函数得到：

具体推导公式如下：

我们引入对偶定理，所以上述最优化问题变为：

现在的问题是怎么求解这个最优化问题呢？我们下面引入SMO算法。

2 序列最小最优化 SMO 算法

细心的读者读至上节末尾处，怎么拉格朗日乘子a 的值可能依然心存疑惑。实 际上，关于的求解可以用一种快速学习算法即 SMO 算法，这里先简要介绍下。

SMO 算法的步骤：

那么在每次迭代中，如何更新乘子呢？引用两张 PPT 说明下：

 

参考资料：

周志华：《机器学习》