深入浅出SVM（PART II）

导读

今天是该系列第八篇文章，介绍支持向量机原理(PART II)。

支持向量机（Support Vector Machine）是由Vapnik等人于1995年提出来的，之后随着统计理论的发展，支持向量机SVM也逐渐受到了各领域研究者的关注，在很短的时间就得到了很广泛的应用。支持向量机是被公认的比较优秀的分类模型，同时，在支持向量机的发展过程中，其理论方面的研究得到了同步的发展，为支持向量机的研究提供了强有力的理论支撑。

本文为第二部分，介绍SVM原理第二章。

支持向量机的训练

对偶算法的引入

通过前一章文章"深入浅出SVM (PART I)"中可以看到，在SVM中，对分隔超平面的求解转化为对如下带约束的最小优化问题的求解：

拉格朗日乘数法是一种比较合适的求解带约束的优化问题的方法，可将其转化为无约束优化问题的求解。对于上述的带约束的优化问题，可以转换成如下的拉格朗日函数：

其中α和β为拉格朗日乘子向量，维度均为样本数量，每一维的值均不小于0。那么最小优化问题可变为：

由于拉格朗日的对偶性可得到原始问题的对偶问题，如下：

具体求解时先求解后半部分也就是minL，即对拉格朗日函数L(W，b，ξ ，α，β)中的W，b和ξ求偏导，并使偏导为0：

化简之后可得：

将化简之后的公式带入minL中，可得：

再对上式求关于α的极大值，最终可得到对偶问题的表达式：

由以上可得：

同时，将求解最大化问题转换为求解最小化问题，则上述的优化问题转换成:

其中αi满足上式的要求，假设α*为对偶问题最优解，根据上式可得原始问题的最优解为：

对于b的最优解，取α*的其中一个分量，代入可得：

线性向非线性的拓展

在该系列的“因子分解机算法原理及实现”一文中曾讲到为了使线性模型可以处理更加复杂的非线性问题，方法有两种：一是利用核函数的方法对特征进行处理，二是对模型本身进行扩展。本文选用第一种方法，介绍在支持向量机中如何引入核函数将非线性问题转变为近似线性问题，所用的核函数为高斯核函数：

同此时非线性支持向量机的优化目标为：

SMO算法

在第一小节由于对偶算法的引入使得带约束的原始问题转变为带约束的对偶问题。一般可以用二次规划的方法求解带约束的优化问题，但是如何更高效地求解此类优化问题是值得研究的问题，尤其在数据量很大的时候。SMO算法是一种序列最小最优化算法，比较适合快速求解此类优化问题。它的思想是将一个大问题划分为一系列小的子问题(这些子问题均只有两个变量)，通过对这些子问题的求解从而达到求解对偶问题的目的。 每次划分中取两个变量a1和a2，使其它的变量为固定的值，如果此时a2被确定了，那么由约束条件可得a1的表达式。那么接下来就需要解决两个关键问题：一是如何选择这两个变量，二是如何去更新这两个变量。

1.两个变量的更新

对于选择的两个变量，优化问题改写为：

其中Kij的表达式为：

M1和M2为常数项，使优化函数为：

此时优化函数可改写为：

由约束条件可得：

由于标签值的平方为1，上式可转换为：

将上式代入优化函数中可得：

此时优化函数变为只关于a2的优化函数，为了求minW(a2)，需要对a2求导，并使其为0，可得：

在这里假设：

可得：

根据迭代次数为第i次的约束条件，则上式在第i+1次可变为：

可得：

其中：

而每次迭代a1和a2所满足的约束条件都可用下图来形象地描述：

其中当y(1)和y(2)不相等时，满足：

相等时，则满足：

因此在第i+1次求解出的a2为：

而由约束条件可得a1：

2.两个变量的选择

由于带约束条件的优化问题一般在所有变量均满足KKT条件时，那么这个时候的解便是最优解。那么我们可以选择那么不满足KKT条件的变量为第一个变量。当a1满足该条件时可得：

由前面的g和E1假设可得：

因此可得不满足该条件的所有情况为：

这样通过遍历所有样本点，选出不满足该条件的第一个变量a1。那么选出第二个变量的原则是可使其有足够大的变化。由a2的更新公式可得，其在第i+1次的值依赖于E1-E2，所以当更新完a1和a2后，需要重新计算阈值b，根据：

可得第i+1次的b1和E1为：

而此时的b2也可表示为：

误差在重新计算后为：

到这里主要的求解过程基本就结束了~