Support Vector Machines - Part 3
支持向量机 - SVM(Support Vector Machines)Part 3
支持向量机 - SVM(Support Vector Machines)Part 1
- 线性可分支持向量机学习算法 - 最大间隔法
- 线性可分支持向量机的对偶算法
支持向量机 - SVM(Support Vector Machines)Part 2
- 线性支持向量机
- 核函数及非线性支持向量机
- 常用的核函数及其特点
支持向量机 - SVM(Support Vector Machines)Part 3
- 序列最小最优化(SMO)算法
支持向量机 - SVM(Support Vector Machines)Part 4
- 支持向量回归 - SVR
目录
- 序列最小最优化(SMO)算法
- SMO算法步骤
- 代码资料
1. 序列最小最优化(SMO)算法
先看一下SMO要解决的问题:
线性可分支持向量机(硬间隔)
线性支持向量机(软间隔)
其中$K_{ij}=K(x_i, x_j), i,j=1,2,…,n$
下面要解决的问题是: $ \alpha = \lbrace \alpha_1, \alpha_2, …, \alpha_n \rbrace $上求上述目标函数的最小化。SMO的基本思路是: 如果所有的变量的解都满足此最优化问题的$KKT$条件,那么这个最优化问题的解就得到了。否则,选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题, 这个二次规划问题关于这两个变量的解更接近于原始二次规划问题的解。整个SMO算法包括两部分:
- 求解这两个变量二次规划的解析方法
- 选择变量的启发式方法
1.1 两个变量二次规划的求解方法
随机选择两个变量$\alpha_1, \alpha_2$,其他变量固定。于是SMO的最优化问题$式(2)$可以写成:
其中$K_{ij}=K(x_i, x_j), i,j=1,2,…,n, \quad \varsigma$是常数,另外式$(5)$中省略了不含$\alpha_1, \alpha_2$的常数项。
这里,我们引入新的变量
其中$ f(x) = \sum_{i=1}^n \alpha_iy_i K(x_i, x) + b$,则式$(5)$中的目标函数可以重新写为
下面我们研究一下约束条件$式(6) \sim 式(7)$,由式$(7)$可知,两个变量均要落在[0,C]x[0,C]的一个矩阵中, 考虑$\alpha_2$单变量的最优化问题,设问题$式(5) \sim 式(7)$的初始可行解为$ \alpha_1^{old}, \alpha_2^{old}$,最优解为$ \alpha_1^{new}, \alpha_2^{new} $, 并且假设在沿着约束方向上未经剪辑时$\alpha_2$的最优解为$\alpha_2^{new,unc}$。假设$\alpha_2^{new}$的上下边界分别为$H和L$,那么有:
接下来综合约束条件$0 \leq \alpha_i \leq C,i=1,2,…,n和\alpha_1^{new}y_i+\alpha_2^{new}y_2=\alpha_1^{old}y_1+\alpha_2^{old}y_2=\varsigma$,求取上下边界的值。
以$y_1 \not= y_2$为例,由$\alpha_1^{new}y_i+\alpha_2^{new}y_2=\alpha_1^{old}y_1+\alpha_2^{old}y_2=\varsigma$可得:
所以,当$\alpha_1=0$时,$ L = max(0, -\varsigma) = max(0, \alpha_2^{old} - \alpha_1^{old}) [上方线段] $;
所以,当$\alpha_1=C$时,$ H = min(C, C-\varsigma) = min(C, C - (\alpha_1^{old} - \alpha_2^{old})) [下方线段] $;
二维图像如下图左图所示,右图为$y_1=y_2$时的图像。
如此,根据$y_1和y_2$异号或同号,可以得到如下$\alpha_2^{new}$的上下界分别为:
下面开始求沿着约束方向未经剪辑[即未考虑不等式约束$(7)$]时$\alpha_2$的最优解$\alpha_2^{new,unc}$;之后再求剪辑后$\alpha_2$的解$\alpha_2^{new}$。
由$ \alpha_1y_1 + \alpha_2y_2 = \varsigma及y_i^2 = 1 $可得,
将$式(15)$代入$式(9)$中,得:
之后对$\alpha_2$求导数[Notice: $ y_i^2 = 1 $]并令其等于零:
得:
将$ \varsigma = \alpha_1^{old}y_1 + \alpha_2^{old}y_2 $代入式$(20)$,得:
令$\eta = K_{11}+K_{22}-2K_{12}$,即得:
之后剪辑$\alpha_2^{new,unc}$得:
然后由$ \alpha_2^{new}求得 \alpha_1^{new} $为:
至此,我们选择的两个变量,固定其他变量的最优化过程结束。
1.2 选择变量的启发式方法
1.2.1 第1个变量的选择
SMO称选择第一个变量的过程为外层循环,外层循环在训练样本中选择违反$KKT$条件最严重的样本点,并将其对应的变量作为第一个变量。 具体地,检验样本点$ (x_i, y_i) $是否满足$KKT$条件,即:
其中$ f(x_i) = \sum_{j=1}^n \alpha_j y_j K(x_i, x_j) +b $。
以下几种情况出现将会导致$KKT$条件不满足:
- $y_if(x_i) \leq 1$但是$\alpha_i <C$不满足,原本$ \alpha_i=C$;
- $y_if(x_i) \geq 1$但是$\alpha_i > 0$不满足,原本$ \alpha_i=0$;
- $y_if(x_i) = 1$但是$\alpha_i=0或\alpha_i=C$不满足,原本$0 < \alpha_i < C$;
1.2.2 第2个变量的选择
SMO称选择第二个变量的过程为内层循环,第二个变量选择的标准是希望能使$\alpha_2$有足够大的变化。 所以,对于第二个变变量,通常选择满足下式的样本点对应的变量:
特殊情况下,如果内存循环通过以上方法选择的$ \alpha_2 $不能使目标函数有足够的下降,那么采用以下启发式规则继续选择$ \alpha_2 $。
- 遍历在间隔边界上的支持向量点,一次将其对应的变量作为$ \alpha_2 $试用,知道目标函数有足够的下降;
- 若找不到合适的$ \alpha_2 $,那么遍历训练数据集;
- 若仍找不到合适的$ \alpha_2 $,则放弃第一个$ \alpha_1 $,再通过外层循环寻求另外的$ \alpha_2 $。
1.2.3 计算阈值$b和差值E_i$
每次完成两个变量的优化后,都要重新计算阈值$b$。当$0<\alpha_i^{new}<C$时,由$KKT$条件可知:
于是,
同样,如果$ 0<\alpha_2^{new} < C $,那么
如果$\alpha_1^{new}, \alpha_2^{new}是0或C$,那么$b_1^{new}和b_2^{new}$以及它们之间的数都是符合$KKT$条件的阈值,此时选择它们的中点作为$b^{new}$。同时,每次完成两个变量的优化之后,还必须更新对应的$E_i$值。
其中,$S$是所有支持向量$x_j$的集合。
以上:
2. SMO算法步骤
输入:训练数据集$T=\lbrace (x_1,y_1), (x_2,y_2), …, (x_n,y_n) \rbrace$,其中, $ x_i \in \chi = R^n, \quad y_i \in \mathcal{y}=\lbrace -1, +1 \rbrace, \quad i=1,2,…,n $,精度$\epsilon$。
输出:近似解$ \hat{\alpha}$
- (1)取初值$ \alpha^{(0)}=0, \quad 令k=0 $;
- (2)选取最优变量$ \alpha_1^{(k)}, \alpha_2^{(k)} $,解析求解两个变量的最优化问题$式() \sim 式() $, 求的最优解$ \alpha_1^{(k+1)}, \alpha_2^{(k+1)} $,更新$ \alpha^{k}为 \alpha^{k+1} $;
- (3)若在精度$\epsilon$范围内满足停机条件其中, 满足则转(4);否则令$k=k+1$,转(2)。
- (4)取$\hat{\alpha} = \alpha^{k+1} $。
3. 代码资料
台湾的林智仁教授写了一个封装SVM算法的libsvm库, 此外上海交通大学模式分析与机器智能实验室有一个libsvm的注释文档
参考
李航 - 《统计学习方法》