12 SVM - SMO - 初始β变量的选择、总结

11 SVM - 序列最小优化算法 SMO

十五、初始β变量的选择

回顾: 可以发现SMO算法中，是选择两个合适的β变量做迭代，其它变量作为常量来进行优化的一个过程，那么这两个变量到底怎么选择呢???

1、每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足初始限制条件中的等式约束条件了。

2、每次优化的两个分量应该是违反g(x)目标条件比较多的。也就是说，本来应当是大于等于1的，越是小于1违反g(x)目标条件就越多；

---

1、第一个β变量的选择

SMO算法在选择第一个β变量的时候，需要选择在训练集上违反KKT条件最严重的样本点。一般情况下，先选择0<β<C的样本点(即支持向量)，只有当所有的支持向量都满足KKT条件的时候，才会选择其它样本点。因为此时违反KKT条件越严重，在经过一次优化后，会让变量β尽可能的发生变化，从而可以以更少的迭代次数让模型达到g(x)目标条件。

先找0<β<C中，不等于1的点

2、第二个β变量的选择

在选择第一个变量β₁后，在选择第二个变量β₂的时候，希望能够按照优化后的β1和β2有尽可能多的改变来选择，也就是说让|E1-E2|足够的大，当E1为正的时候，选择最小的Ei作为E2；当E1为负的时候，选择最大的Ei作为E2。

PS：如果选择的第二个变量不能够让目标函数有足够的下降，那么可以通过遍历所有样本点来作为β2，直到目标函数有足够的下降，如果都没有足够的下降的话，那么直接跳出循环，重新选择β1；

3、计算阈值b和差E_i

在每次完成两个β变量的优化更新之后，需要重新计算阈值b和差值Ei。当0<β_new<C时，有：

化简上式

同样的当β2的取值为: 0<β2<C的时候，我们也可以得到：

最终计算出来的b为：

当更新计算阈值b后，就可以得到差值Ei为：

十六、SMO算法流程总结

输入线性可分的m个样本数据{(x1,y1),(x2,y2),...,(xm,ym)}，其中x为n维的特征向量，y为二元输出，取值为+1或者-1；精度为e；

取初值β0=0，k=0；

选择需要进行更新的两个变量: β₁^k和β₂^k，计算出来新的β₂^new,unt；

按照下列式子求出具体的β₂^k+1;

按照β₁^k和β₂^k的关系，求出β₁^k+1的值：

按照公式计算b^k+1和E_i的值；

检查函数y(i)*Ei的绝对值是否在精度范围内，并且求解出来的β解满足KKT相关约束条件，那么此时结束循环，返回此时的β解即可，否则继续迭代计算β₂^new,unt的值。

13 SVM - SVR（回归问题的SVM）