Loading...
墨滴

blue吖

2021/09/14  阅读:33  主题:自定义主题1

机器学习算法——SMO算法求解支持向量机

阅读提示:1.文章中的斜体符号表示单个元素,加粗斜体表示向量。2.本篇文章公式大多较长,手机端需要左右滑动查看。3.文章中只给出了部分关键代码,如需全部代码可访问我的Github获取:https://github.com/luliu-fighting/Statistical-Learning-Method。代码为之前复现李航的《统计学习方法》的代码,注释没改。

1.前言

  在前一篇文章中我们推导出了非线性可分支持向量机最优化问题的数学表达式:

其中变量 的个数与样本点 的个数 是相等的,也就是求解的复杂度与训练集的样本个数是成正比的,当训练数据集容量很大时,求解过程会变得十分复杂。为了提高支持向量机的求解效率,Platt在1998年提出了序列最小最优化(sequential minimal optimization, SMO)算法。
  SMO算法的基本思路是:将原来的最优化问题分解为若干个子最优化问题,每个子问题都是两个变量的最优化问题,其他变量是固定的可以看作是常量;子问题的求解是比较简单的,因为子问题可以通过解析方法求得具体的值。当所有的变量的解都满足此最优化问题的KKT条件时,那么此时的解就是要求的最优化问题的解。对于SMO算法为什么高效,我的理解是:SMO算法不是每次都对所有的变量进行优化,而是每次按照某种规则选择两个变量进行优化,当所有的解都满足KKT条件时,问题就求解完成了,无论训练样本个数即变量个数有多少,SMO算法每次都只优化更新两个变量。
  SMO算法可以分为两个部分,一个是每次如何选取子问题的两个变量,另一个是选取的两个变量的子最优化问题的求解。下文将先讲子问题的求解,再讲变量的选取。

2.两个变量的子最优化问题的求解

2.1 的求解

  假设此时已经根据变量的选择规则选出了变量 ,注意这里的索引1并不是指 的第一个分量,而是指被第一个选择出来要进行优化的分量,也就是说 可以是 中的任意分量。此时,其他变量可以视为常量,所以有:

其中 为常数,于是我们可以写出子最优化问题的表达式:

在目标函数中, 代表一些不含 的常数项,不影响最优化问题的求解。
  由约束条件 可得:

将目标函数中的 全部用 代替可得:

为对样本 的预测标签值,即分离决策函数 去掉了符号函数输出:

由此可以得出:

求导数并令其等于0:

代入上式:

令:

则:

此时求得的 仅仅是根据求导并令导数等于0得到的,还并未考虑到最优化问题的约束条件,其有可能不在约束条件的取值范围内,所以要得到最后的 ,还应该知道 根据约束条件的取值范围。
  根据约束条件 可知, 的取值范围不仅与其本身有关,而且与 有关。
(1)当 时,因为有 ,所以有:

再结合 自己的约束 取交集可得:

其中:

(2)当 时,有:

再结合 自己的约束 取交集可得:

其中:

将根据约束条件求得的 的取值范围与前面求导得到的 结合,就可以得到 的更新公式:

根据公式:

可得 的更新公式为:

至此,子最优化问题的解 就得到了。
的更新过程代码如下:

            alpha2_new = self.alpha[i2] + self.trainlabel[i2]*(E1 - E2)/eta
            if alpha2_new < L:
                alpha2_new = L
            elif alpha2_new > H:
                alpha2_new = H
            #式(7.109)
            alpha1_new = self.alpha[i1] + self.trainlabel[i1]*self.trainlabel[i2]*(self.alpha[i2] - alpha2_new)

2.2 常数b的求解

  当 时,根据KKT条件可知:

所以:

可得:

于是可得:

同样,当 时可以得到: