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

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

十五、初始β变量的选择

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

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

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

1、第一个β变量的选择

SMO算法在选择第一个β变量的时候，需要选择在训练集上违反KKT条件最严重的样本点。一般情况下，先选择0<β

2、第二个β变量的选择

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

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

3、计算阈值b和差Ei

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

同样的当β2的取值为: 0<β2

最终计算出来的b为：

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

十六、SMO算法流程总结

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

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

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

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

按照β1k和β2k的关系，求出β1k+1的值：

按照公式计算bk+1和Ei的值；

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

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