统计机器学习-序列最小最优化算法（SMO）

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-26 21:51 被阅读0次

启发式算法
SVM（支持向量机）笔记-SMO算法、核函数，代码实现
统计机器学习-序列最小最优化算法（SMO）
机器学习之SMO算法
12 SVM - SMO - 初始β变量的选择、总结
序列最小优化算法（SMO）浅析
11 SVM - SMO - 序列最小优化算法
机器学习
序列最小最优算法(SMO算法)
SVM算法（支持向量机）

SMO算法要解如下凸二次规划的对偶问题：
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i\tag1$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0\tag2$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N\tag3$

在这个问题中，变量是拉格朗日乘子，一个变量 $\alpha_i$ 对应于一个样本点 $(x_i,y_i)$ 。变量的总数等于训练样本的容量 $N$ 。

SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的 $KKT$ 条件，那么这个最优化问题的解就得到了，因为 $KKT$ 条件是该最优化问题的充分必要条件。于是，每次只选择两个变量进行优化，使其满足 $KKT$ 条件，然后不断迭代，直至所有变量满足 $KKT$ 条件，得到最优解。在优化变量的选取上，一般一个是违反 $KKT$ 条件最严重的一个，另一个由约束条件自动决定。

两个变量二次规划的求解方法

根据SMO算法，公式(1)-(3)的问题可以通过多次选择变量 $\alpha_1$ ， $\alpha_2$ ，求解下列子问题得到：
$\min_{\alpha_1,\alpha_2}W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}\tag4$

$\mathrm{s.t.}\ \ \alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^Ny_i\alpha_i=\varsigma\tag5$

$0\leq\alpha_i\leq C,\ \ i=1,2\tag6$

上述优化问题，因为可以通过公式(5)可以用 $\alpha_2$ 来表示 $\alpha_1$ ，所以可以考虑为对 $\alpha_2$ 的最优化问题。如果 $y_1\neq y_2$ ，则 $\alpha_1-\alpha_2=k$ ， $k$ 为常数：

y1!=y2

根据公式(6)， $\alpha_1$ ， $\alpha_2$ 在正方形内部，加上公式(5)，所以 $\alpha_1$ ， $\alpha_2$ 为直线和正方形交线上的点。同理，如果 $y_1=y_2$ ，则 $\alpha_1+\alpha_2=k$ ，如下图：

y1=y2

假设问题(4)-(6)优化前 $\alpha_1$ ， $\alpha_2$ 的值为 $\alpha_1^{old}$ ， $\alpha_2^{old}$ ，优化后的最优解为 $\alpha_1^{new}$ ， $\alpha_2^{new}$ ，并且假设在沿着约束方向未经剪辑时 $\alpha_2$ 的最优解为 $\alpha_2^{new,unc}$ 。

$\alpha_2^{new}$ 需要满足不等式
$L\leq\alpha_2^{new}\leq H$
其中， $L$ 和 $H$ 是 $\alpha_2^{new}$ 所在对角线段的界，如果 $y_1\neq y_2$ ，则
$L=\max(0,\alpha_2^{old}-\alpha_1^{old}),\ \ H=\min(C,C+\alpha_2^{old}-\alpha_1^{old})$
因为 $\alpha_1^{new}-\alpha_2^{new}=k=\alpha_1^{old}-\alpha_2^{old}$ ，所以 $\alpha_2^{new}$ 在直线 $\alpha_1^{new}-\alpha_2^{new}=\alpha_1^{old}-\alpha_2^{old}$ 和正方形的交线段上，通过上下平移就能够得到上面 $\alpha_2^{new}$ 的界。同理，如果 $y_1=y_2$ ，则
$L=\max(0,\alpha_2^{old}+\alpha_1^{old}-C),\ \ H=\min(C,\alpha_2^{old}+\alpha_1^{old})$
于是通过公式(5)得到 $\alpha_1$ 用 $\alpha_2$ 的表示：
$\alpha_1=(\varsigma-y_2\alpha_2)y_1$
代入公式
$W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2}$
并求导等于0便可以得到未经剪辑时 $\alpha_2$ 的最优解 $\alpha_2^{new,unc}$ ，最后根据上述 $L$ 和 $H$ 裁剪得到 $\alpha_2^{new}$ 。

最优化问题(4)-(6)沿着约束方向未经剪辑时的解是
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}\tag7$
其中，
$\eta=K_{11}+K_{22}-2K_{12}=||\Phi(x_1)-\Phi(x_2)||^2\tag8$
$\Phi(x)$ 是输入空间到特征空间的映射， $E_i$ ， $i=1,2$ 为
$E_i=g(x_i)-y_i=\bigg(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\bigg)-y_i,\ \ i=1,2\tag9$
表示对输入 $x_i$ 的预测值与真实输出 $y_i$ 之差，其中
$g(x)=\sum_{i=1}^N\alpha_iy_iK(x_i,x)+b\tag{10}$
经剪辑后 $\alpha_2$ 的解是
$\alpha_2^{new}= \begin{cases} H,&\alpha_2^{new,unc}\gt H\\ \alpha_2^{new,unc},&L\leq\alpha_2^{new,unc}\leq H\\ L,&\alpha_2^{new,unc}\lt L \end{cases}$
然后根据公式
$\alpha_1^{new}=(\varsigma-y_2\alpha_2^{new})y_1\tag{11}$
计算 $\alpha_1^{new}$ 。

变量的选择方法

SMO算法每次都要选择两个变量进行优化，其中至少一个变量是违反 $KKT$ 条件的。

第一个变量的选择

SMO称选择第1个变量的过程为外层循环。外层循环在训练样本中选取违反 $KKT$ 条件最严重的样本点，并将其对应的变量作为第1个变量，具体的，检验训练样本点 $(x_i,y_i)$ 是否满足 $KKT$ 条件，即
$\alpha_i=0\Leftrightarrow y_ig(x_i)\geq1\tag{12}$

$0\lt\alpha_i\lt C\Leftrightarrow y_ig(x_i)=1\tag{13}$

$\alpha_i=C\Leftrightarrow y_ig(x_i)\leq1\tag{14}$

其中， $g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_i,x_j)+b$ 。

该检验是在 $\varepsilon$ 范围内进行的。在检验过程中，外层循环首先遍历所有满足条件 $0\lt\alpha_i\lt C$ 的样本点，即间隔边界上的支持向量点，检验它们是否满足 $KKT$ 条件，如果这些样本点都满足 $KKT$ 条件，那么遍历整个训练集，检验它们是否满足 $KKT$ 条件。

第二个变量的选择

SMO称选择第2个变量的过程为内层循环。第2个变量的选择标准是希望能使 $\alpha_2$ 有足够大的变化。由于
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}$
所以 $\alpha_2$ 的变化依赖于 $|E_1-E_2|$ 。于是选择使 $|E_1-E_2|$ 最大的 $\alpha_2$ ，当 $E_1$ 是正的，选择最小的 $E_i$ 作为 $E_2$ ，如果 $E_1$ 是负的，选择最大的 $E_i$ 作为 $E_2$ ，为了节省计算时间，将所有的 $E_i$ 值保存在一个列表中。

如果这种内层循环找不到一个有足够下降的 $\alpha_2$ ，则遍历在间隔边界上的支持向量点，依次将其对应的变量作为 $\alpha_2$ 试用，直到有足够的下降，如果还不可以，则遍历训练集。再不可以，换一个 $\alpha_1$ 。

计算阈值 $b$ 和差值 $E_i$

更新完 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 的值，都需要重新计算阈值 $b$ ，当 $0\lt\alpha_1^{new}\lt C$ 时，由 $KKT$ 条件可知
$\sum_{i=1}^N\alpha_iy_iK_{i1}+b=y_1$
所以
$b_1^{new}=y_1-\sum_{i=1}^N\alpha_iy_iK_{i1}=y_1-\sum_{i=3}^N\alpha_iy_iK_{i1}-\alpha_1^{new}y_1K_{11}-\alpha_2^{new}y_2K_{2,1}\tag{15}$
由于未更新的 $E_1$ 为
$E_1=\sum_{i=3}^N\alpha_iy_iK_{i1}-y_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{21}+b^{old}$
移项得到
$y_1-\sum_{i=3}^N\alpha_iy_iK_{i1}=-E_1+\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{21}+b^{old}$
代入公式(15)得到 $b_1^{new}$ 的更新公式
$b_1^{new}=-E_1-y_1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{21}(\alpha_2^{new}-\alpha_2^{old})+b^{old}\tag{16}$
同理，当 $0\lt\alpha_2^{new}\lt C$ 时，可以推出 $b_2^{new}$ 的更新公式
$b_2^{new}=-E_2-y_1K_{12}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b^{old}\tag{17}$
如果 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 同时满足条件 $0\lt\alpha_i^{new}\lt C$ ， $i=1,2$ ，那么 $b_1^{new}=b_2^{new}$ ，如果 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 是0或者 $C$ ，那么 $b_1^{new}$ 和 $b_2^{new}$ 以及它们之间的数都是符合 $KKT$ 条件的阈值，这时选择它们的中点作为 $b^{new}$ 。

更新完 $\alpha_1^{new}$ ， $\alpha_2^{new}$ 后还需要更新对应的 $E_i$ 值，并保存在列表中， $E_i$ 的更新需要用到 $b^{new}$ 的值，以及所有支持向量对应的 $\alpha_j$ ：
$E_i^{new}=\sum_Sy_j\alpha_jK(x_i,x_j)+b^{new}-y_i\tag{18}$
其中 $S$ 是所有支持向量 $x_j$ 的集合。

SMO算法

输入：训练数据集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y= \{-1,+1\}$ ， $i=1,2,\cdots,N$ ，精度 $\varepsilon$ ；

输出：近似解 $\hat{\alpha}$ 。

（1）选取初值 $\alpha^{(0)}=0$ ，令 $k=0$ ；

（2）选取优化变量 $\alpha_1^{(k)}$ ， $\alpha_2^{(k)}$ ，解析求解两个变量的最优化问题(4)-(6)，求得最优解 $\alpha_1^{(k+1)}$ ， $\alpha_2^{(k+1)}$
$\alpha_2^{new,unc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}$

$\alpha_2^{new}= \begin{cases} H,&\alpha_2^{new,unc}\gt H\\ \alpha_2^{new,unc},&L\leq\alpha_2^{new,unc}\leq H\\ L,&\alpha_2^{new,unc}\lt L \end{cases}$

$\alpha_1^{new}=(\varsigma-y_2\alpha_2^{new})y_1=(-\sum_{i=3}^Ny_i\alpha_i-y_2\alpha_2^{new})y_1$

其中
$\eta=K_{11}+K_{22}-2K_{12}=||\Phi(x_1)-\Phi(x_2)||^2$

$E_i=g(x_i)-y_i=\bigg(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\bigg)-y_i,\ \ i=1,2$

如果 $y_1\neq y_2$
$L=\max(0,\alpha_2^{old}-\alpha_1^{old}),\ \ H=\min(C,C+\alpha_2^{old}-\alpha_2^{old})$
如果 $y_1=y_2$
$L=\max(0,\alpha_2^{old}+\alpha_1^{old}-C),\ \ H=\min(C,\alpha_2^{old}+\alpha_2^{old})$
更新 $\alpha$ 为 $\alpha^{(k+1)}$ ；

（3）若在精度 $\varepsilon$ 范围内满足停机条件
$\sum_{i=1}^N\alpha_iy_i=0$

$0\leq\alpha_i\leq C,\ \ i=1,2,\cdots,N$

$y_ig(x_i)= \begin{cases} \geq1,& \{x_i|\alpha_i=0\}\\ =1,& \{x_i|0\lt\alpha_i\lt C\}\\ \leq1,& \{x_i|\alpha_i=C\} \end{cases}$
其中
$g(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b$
则转(4)；否则令 $k=k+1$ ，转(2)；

（4）取 $\hat \alpha=\alpha^{(k+1)}$ 。

启发式算法
今天看李航博士《统计学习方法》中SVM的学习算法SMO（序列最小最优化算法）中，看到说SMO是一种启发式算法，然后...
SVM（支持向量机）笔记-SMO算法、核函数，代码实现
SMO算法 SMO表示序列最小优化（Sequential Minimal Optimization），是将大优化问...
统计机器学习-序列最小最优化算法（SMO）
SMO算法要解如下凸二次规划的对偶问题：在这个问题中，变量是拉格朗日乘子，一个变量对应于一个样本点。变量的总数等...
机器学习之SMO算法
SMO算法什么是SMO算法 SMO(Sequential Minmal Optimization)序列最小化算法...
12 SVM - SMO - 初始β变量的选择、总结
11 SVM - 序列最小优化算法 SMO 十五、初始β变量的选择回顾: 可以发现SMO算法中，是选择两个合适...
序列最小优化算法（SMO）浅析
写在前面有一个多月没有更新博客了，整个三月份都在忙项目的事，忙着各种扫尾解决一些“历史遗留问题”。终于到了清明节...
11 SVM - SMO - 序列最小优化算法
05 SVM - 支持向量机 - 概念、线性可分06 SVM - 线性可分模型算法和案例07 SVM - 软间隔模...
机器学习
机器学习等于矩阵+优化+算法+统计
序列最小最优算法(SMO算法)
本文来自我的个人博客 https://www.zhangshenghai.com/posts/3981/ 序列最小...
SVM算法（支持向量机）
SVM SVM有很多种实现，本文只关注其中最流行的一种实现，即序列最小优化（SMO）算法。支持向量机是一种分类器...