从超平面到SVM（三）

上期我们已经讲了从《超平面到SVM（二）》中关于对偶算法和核技巧的部分，不过，这是SVM算法中纯理论的部分，在进行算法的实现的时候会发现使用理论中推导的公式按部就班的去实现算法不太现实，因为SVM算法的时间复杂度太高了，目前，SVM算法的实现当属SMO（sequentialminimal optimization，序列最小化优化），本文将接着上期，结束《从超平面到SVM》的算法讲解。

一、固定两个拉格朗日乘子

上期引入核函数以后，原来的优化目标函数就变成了如下的形式：

在上面的优化目标函数中，变量为拉格朗日乘子，一个变量a_i对应于一个样本点(x_i,y_i)，变量的总数等于训练样本容量N。从公式中可以看出，在求解过程中，上述公式的优化过程实际上是一个二次函数的求解问题。然而，由于一个a_i对应一个样本，在样本非常多的时候这个优化过程涉及到的变量会非常多导致优化过程及其缓慢，为了解决这个问题，可以采取启发式方法，启发式方法可以认为是根据经验得到的解决问题的办法，启发式方法是在有限的空间内，大大减少尝试的数量，迅速达到解决问题的目的。解决此问题，可以通过减少变量的个数来实现，比如在上述公式中有：

即在所有样本上，a_i与y_i的乘积之和为0，根据这个特点，可以认为认为所有a的和等于常量0，因为y的值仅在-1和1之间选择，且在训练集中是已知的。于是，可以选择其中两个a作为变量，然后这两个变量的和都可以用其他变量来描述。因为这两个变量的和可以认为是定值，所以，只要确定了其中一个变量，另一个变量也就随之确定了，即只有一个变量是自由变量，只要确定自由变量，另一个也就确定了，如下公式：

假设，选择的两个变量为a₁与a₂，其他变量可以用a_i(i=3,4,…,N)来表示，可以认为是固定的，于是上述目标函数的最优化问题可以如下的公式表示：

为了求解以上两个变量的最优化约束问题，首先要分析约束条件，然后在约束条件的基础上再进行求极小值。

                                                                      

从上面的公式与图像的对应关系可以看出，当对应的两个分类结果异号时这两个变量构成的直线为斜率为正的直线，当二者对应的两个分类结果同号时这两个变量构成的直线为斜率为负的直线，因为a₁和a₂都要满足大于等于0小于等于C的条件，所以这条绿色的直线只有落在黑色矩形范围内的线段才满足条件，于是此问题又转化为了在绿色直线落在黑色矩形内的线段上找一个点对应的(a₁,a₂)满足最优化条件，由于此线段斜率为1和-1，所以，其中一个变量的变化确定了，另一个变量的变化也就确定了。

如上图，可以设定a₁和a₂在如上的矩阵限定的范围内取值，二者均在0到C之间，于是可以根据上面一系列条件来找到其中一个变量如a₂的取值范围，显然的a₂的取值分别在上面两幅图中的四条线段（即四种情况）上移动，这四条线段四个端点构成的取值边界就是a₂的取值边界，把这些边界组成的边界作为a₂的边界就变成了的取值范围。例如：

得到以上取值范围后，在求解该目标函数最优化解的时候可以分两步进行，第一步就是先不考虑该目标函数的约束条件，求出所有的可行性解，第二步就是在得到的所有可行性解里面选择满足a₂和a₁约束条件的解，假设第一步所求的解

第二步所求的解为

，其中new表示在原来初始解

基础上得到的新的迭代优化解，unc表示这个解是未经剪辑的，即第一步所求的结果，未考虑约束条件，如果把约束条件加上以后就是第二步得到的结果，记为

。

假设已经求得最终的预测函数，记作g(x),于是有：

令

其中g(x_i)和y_i的差值就是对于输入样本x_i的预测值g(x_i)与真实标记值y_i的差值。

此处引入一个新的定理，最优化问题沿着约束方向未经剪辑的解是:

其中，

是输入空间到特定空间到映射，

时可以根据前面得到的限制条件来得到剪辑后的a₂即加入限制条件后的a₂为：

此定理的证明过程较为复杂，对于证明部分需要深入学习的可以参考《统计学习方法》第127页的证明部分。

二、两个拉格朗日乘子选择方法

在上面一节中已经通过推导得到了

的求解公式，但是在求解的过程中，如何选择初始化

也是非常重要的，从拉格朗日乘子法中可以看出，有多少个样本就有多少个对应的a与之对应，一般在训练数据时样本数目都会很多，那此时再进行优化时就会出现迭代次数过多的问题，导致优化及其缓慢，为了解决这个问题，需要对初始化参数和两个拉格朗日乘子在优化过程中的选择找到一个尽可能快的方法。

1、 第一个变量的选择

SMO算法一般认为第一个变量为外层循环，因为函数优化的目的就是使得该目标函数

能够取得最小值，所以当所有的样本对应的a都能满足约束条件时，即得到了所有可行解，然后在所有可行解里面就可以找到使得目标函数最小的解。不过，在选择a的时候很难一开始就选择合适的值使其满足KKT条件，往往需要多次迭代才能找到更好的值，为了使得迭代的速度更快，优化过程更快，要想到一种选择a的方法能够尽快进行迭代优化，此时可以考虑优先选择一个a使其不满足KKT条件，并且违反KKT条件较为严重，这样，在后期迭代过程中a即便是再不符合优化条件，也比刚开始要好，起码会朝着满足KKT条件的方向迭代，这样的话，就可以通过设置迭代的步长使其尽快到达满足KKT条件的优化范围内。

2、 第二个变量的选择

SMO算法选择第二个变量的过程称之为内层循环，如果在外层循环中已经找到了一个a₁那么在选择内层循环a₂的时候就要尽量两个变量的差别要大一些，这样才能保证迭代的幅度会变大，迭代更快，并且根据公式

可知，

依赖于

，为了加快迭代的过程可以选择使其

最大的值，因为外层a₁和

已定，所以在选择a₂的时候只要根据

来选择

即可，这样也就得到了合适的a₂。

三、两个拉计算阈值b和差值Ei

每次计算优化完两个a后，需要重新计算阈值b，当

时由

可知：

经变换后：

    同样地，如

，那么，

另外，每次优化完变量后还需更新原来的

值，此时需要用到所有的支持向量对应的a_j和b^new即：

其中，S为所有支持向量

的集合。

以上就是SMO算法的基本内容，基本讲解了此算法中各个变量的求解方法，不过在具体写程序实现的时候还有很多编程方面的技巧，这方面的技巧可以参考相关实现的书籍自己亲自动手试一下，将会对此理解更加深刻。

版权声明：本文为小象原创文章，转载请联系后台。