支持向量机(SVM)（五）— SMO算法详解

来源：http://blog.csdn.net/u011067360/article/details/26503719

一、我们先回顾下SVM问题。

A、线性可分问题

1、SVM基本原理：

SVM使用一种非线性映射，把原训练数据映射到较高的维。在新的维上，搜索最佳分离超平面，两个类的数据总可以被超平面分开。

2、问题的提出：

3、如何选取最优的划分直线f(x)呢？

4、求解：凸二次规划

建立拉格朗日函数：

求偏导数：

B、线性不可分问题

1、核函数

如下图：横轴上端点a和b之间红色部分里的所有点定为正类，两边的黑色部分里的点定为负类.

设：

g(x)转化为f(y)=

g(x)=f(y)=ay

在任意维度的空间中，这种形式的函数都是一个线性函数（只不过其中的a和y都是多维向量罢了），因为自变量y的次数不大于1。

下图w，x都是1000维，w’和x’分别是由w，x变换得到的2000维向量

g(x)=K(w,x)+b

K(w,x)被称作核函数

基本作用：接受两个低维空间里的向量，能够计算出经过某个变换后在高维空间里的向量内积值。

2、松弛变量

3、软间隔C-SVM：

C是一个由用户指定的系数，表示对分错的点加入多少的惩罚，当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确

总结：

SVM算法优点：

(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；

(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；

(3)支持向量是SVM的训练结果,在SVM分类决策中起决定性作用。因此，模型需要存储空间小，算法鲁棒性（ Robust ）强。

SVM算法缺点：

(1) SVM算法对大规模训练样本难以实施

由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。

(2) 用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。

基于以上问题，我们现在讨论SOM（Sequential Minimal Optimization algorithm）算法。

1、SMO算法的原理

这一被称为“顺次最小优化”的算法和以往的一些SVM改进算法一样，是把整个二次规划问题分解为很多易于处理的小问题，所不同的是，只有SMO算法把问题分解到可能达到的最小规模：每

次优化只处理两个样本的优化问题，并且用解析的方法进行处理。我们将会看到，这种与众不同的方法带来了一系列不可比拟的优势。

对SVM来说，一次至少要同时对两个样本进行优化（就是优化它们对应的Lagrange乘子），这是因为等式约束的存在使得我们不可能单独优化一个变量。

所谓“最小优化”的最大好处就是使得我们可以用解析的方法求解每一个最小规模的优化问题，从而完全避免了迭代算法。

当然，这样一次“最小优化”不可能保证其结果就是所优化的Lagrange乘子的最终结果，但会使目标函数向极小值迈进一步。我们再对其它Lagrange乘子做最小优化，直到所有乘子都符合KKT

条件时，目标函数达到最小，算法结束。

这样，SMO算法要解决两个问题：一是怎样解决两个变量的优化问题，二是怎样决定先对哪些Lagrange乘子进行优化。

2、两个Lagrange乘子的优化问题

我们在这里不妨设正在优化的两个Lagrange乘子对应的样本正是第一个和第二个，对两个Lagrange乘子α₁和α₂，在其他乘子不改变的情况下，它们的约束条件应表达为正方形内的一条线段。（如图）

在这条线段上求一个函数的极值，相当于一个一维的极值问题。我们可以把α₁用α₂表示，对α₂求无条件极值，如果目标函数是严格上凹的，最小值就一定在这一极值点（极值点在区间内）或在区间端点（极值点在区间外）。α₂确定后，α₁也就确定下来了。因此我们先找到α₂优化区间的上下限制，再在这个区间中对α₂求最小值。

由图1我们容易得到α₂的上下限应为：

L=max(0,α₂－α₁)，H=min(C,C+α₂ –α₁), 若y₁与y₂异号；

L=max(0,α₂ +α₁－C), H=min(C, α₂ +α₁) ,若y₁与y₂同号；

令s=y₁y₂标志这两个样本是否同类，则有

L=max(0, α₂+sα₁－ 1/2 (s+1)C), H=min(C, α₂ +sα₁ –1/2 (s－1)C)

而α₁和α₂在本次优化中所服从的等式约束为：

α₁＋sα₂=α⁰₁+sα⁰₂=d

下面我们推导求最小值点α₂的公式：由于只有α₁，α₂两个变量需要考虑，目标函数可以写成

Wolfe(α₁,α₂)=1/2K₁₁α²₁+1/2 K₂₂α²₂+ sK₁₂α₁α₂ + y₁α₁v₁+y₂α₂v₂ －α₁ －α₂+常数

其中K_ij=K(x_i,x_j), v_i=y₃α⁰₃K_i3+…+y_lα⁰_lK_il = u_i+b⁰－ y₁α⁰₁K_1i – y₂α⁰₁K_2i

上标为0的量表示是本次优化之前Lagrange乘子的原值。

将α₂用α₁表示并代入目标函数：

Wolfe（α₂）=1/2 K₁₁(d-sα₂)²+1/2K₂₂α²₂+sK₁₂(d-sα₂) α₂+y₁(d-sα₂)v₁– d+sα₂+y₂α₂v₂－α₂+常数

对α₂求导：

dWolfe(α₂)/dα₂=－sK₁₁(d－sα₂)+K₂₂α₂－K₁₂α₂+sK₁₂(d－sα₂)－y₂v₂+s+y₂v₂－1 ＝0

如果Wolfe函数总是严格上凹的，即二阶导数K₁₁+K₂₂－2K₁₂>0, 那么驻点必为极小值点，无条件的极值点就为

α₂＝[s(K₁₁－K₁₂)d+y₂(v₁－v₂)＋1－s] / (K₁₁＋K₂₂－2K₁₂)

将d,v与α⁰,u之间关系代入，就得到用上一步的α⁰₂，u₁,u₂表示的α₂的无条件最优点：

α₂＝[α⁰₂(K₁₁＋K₂₂－2K₁₂)+y₂(u₁－u₂＋y₂－y₁)] / (K₁₁＋K₂₂－2K₁₂)

令η=K₁₁＋K₂₂－2K₁₂为目标函数的二阶导数，E_i=u_i－y_i为第i个训练样本的“误差”，这个式子又可以写为

α₂＝α⁰₂＋y₂(E₁－E₂)/η

除非核函数K不满足Mercer条件（也就是说不能作为核函数），η不会出现负值。但η=0是可以出现的情况。这时我们计算目标函数在线段两个端点上的取值，并将Lagrange乘子修正到目标函数较小的端点上：

f₁=y₁(E₁+b)－α₁K(x₁,x₁)­－sα₂K(x₁,x₁)

f₂=y₂(E₂+b)－sα₁K(x₁,x₂)­－α₂K(x₂,x₂)

L₁=α₁+s(α₂－L)

H₁=α₁+s(α₂－H)

WolfeL=L₁f₁+Lf₂+1/2 L²₁K(x₁,x₁)+1/2L²K(x₂,x₂)+sLL₁K(x₁,x₂)

WolfeH=H₁f₁+Hf₂+1/2 H²₁K(x₁,x₁)+1/2H²K(x₂,x₂)+sHH₁K(x₁,x₂)

当两个端点上取得相同的目标函数值时，目标函数在整条线段上的取值都会是一样的（因为它是上凹的），这时不必对α₁，α₂作出修正。

α₂的无条件极值确定后，再考虑上下限的限制，最终的α₂为

最后，由等式约束确定α₁：

α₁=α₁+s(α₂－α₂)

3、SMO算法

3.1、SMO算法的目的无非是找出一个函数f(x)，这个函数能让我们把输入的数据x进行分类

将一个凸二次规划问题转换成下列形式（KKT条件）

这里的ai是拉格朗日乘子(问题通过拉格朗日乘法数来求解)

对于（a）的情况，表明ai是正常分类，在边界内部（我们知道正确分类的点yi*f(xi)>=0）

对于（b）的情况，表明了ai是支持向量，在边界上

对于（c）的情况，表明了ai是在两条边界之间 而最优解需要满足KKT条件，即满足（a）（b）（c）条件都满足

3.2、以下几种情况出现将会出现不满足：

yiui<=1但是ai<C则是不满足的,而原本ai=C

yiui>=1但是ai>0则是不满足的而原本ai=0

yiui=1但是ai=0或者ai=C则表明不满足的，而原本应该是0<ai<C

所以要找出不满足KKT的这些ai，并更新这些ai，但这些ai又受到另外一个约束，即

通过另一个方法，即同时更新ai和aj，满足以下等式

就能保证和为0的约束。

利用上面的式子消去ai

得到一个关于单变量aj的一个凸二次规划问题，不考虑其约束0<=aj<=C,可以得其解为：

其中：

aj表示旧值，然后考虑约束0<=aj<=C可得到a的解析解为：

其中：

输入是x，是一个数组，组中每一个值表示一个特征。输出是A类还是B类。（正类还是负类）

4、SMO算法的特点和优势SMO算法和以往流行的SVM优化算法如块算法、固定工作样本集法相比，既有共同点，又有自己的独特之处。

共同点在于它们都是把一个大的优化问题分解为很多小问题来处理。块算法在每一步中将新加入样本中违反KKT条件的样本与原有的支持向量一起组成小问题的样本集进行优化，优化完毕后

只保留其中的支持向量，再加进来新的样本进入下一步。固定工作样本集法是每一步只收集新加入样本中“最坏”的样本，并将原来保留的支持向量集中“较好”的替换出去，以保持样本集大小不

变。SMO则是把每一步的优化问题缩减到了最小，它可以看作是固定工作样本集法的一种特殊情况：把工作样本集的大小固定为2，并且每一步用两个新的Lagrange乘子替换原有的全部乘子。

SMO的最大特色在于它可以采用解析的方法而完全避免了二次规划数值解法的复杂迭代过程。这不但大大节省了计算时间，而且不会牵涉到迭代法造成的误差积累（其它一些算法中这种误差

积累带来了很大的麻烦）。理论上SMO的每一步最小优化都不会造成任何误差积累，而如果用双精度数计算，舍入误差几乎可以忽略，于是所有的误差只在于最后一遍检验时以多大的公差要

求所有Lagrange乘子满足KKT条件。可以说SMO算法在速度和精度两方面都得到了保证。

SMO在内存的节省上也颇具特色。我们看到，由于SMO不涉及二次规划数值解法，就不必将核函数矩阵整个存在内存里，而数值解法每步迭代都要拿这个矩阵作运算。（4000个样本的核函

数矩阵需要128M内存！）于是SMO使用的内存是与样本集大小成线性增长的，而不象以往的算法那样成平方增长。在我们的程序中SMO算法最多占用十几兆内存。SMO使得存储空间问题不

再是SVM应用中的另一个瓶颈。

SMO算法对线性支持向量机最为有效，对非线性则不能发挥出全部优势，这是因为线性情况下每次最小优化后的重置工作都是很简单的运算，而非线性时有一步加权求和，占用了主要的时

间。其他算法对线性和非线性区别不大，因为凡是涉及二次规划数值解的算法都把大量时间花在求数值解的运算中了。

当大多数Lagrange乘子都在边界上时，SMO算法的效果会更好。尽管SMO的计算时间仍比训练集大小增长快得多，但比起其它方法来还是增长得慢一个等级。因此SMO较适合大数量的样本。

原文: https://wizardforcel.gitbooks.io/dm-algo-top10/content/svm-5.html