在SVM的前三篇里,我们优化的目标函数最终都是一个关于向量的函数。而怎么极小化这个函数,求出对应的向量,进而求出分离超平面我们没有讲。本篇就对优化这个关于向量的函数的SMO算法做一个总结。
1. 回顾SVM优化目标函数
我们首先回顾下我们的优化目标函数:
2. SMO算法的基本思想
3. SMO算法目标函数的优化
为了求解上面含有这两个变量的目标优化问题,我们首先分析约束条件,所有的都要满足约束条件,然后在约束条件下求最小。
根据上面的约束条件,又由于均只能取值1或者-1, 这样在[0,C]和[0,C]形成的盒子里面,并且两者的关系直线的斜率只能为1或者-1,也就是说的关系直线平行于[0,C]和[0,C]形成的盒子的对角线,如下图所示:
4. SMO算法两个变量的选择
SMO算法需要选择合适的两个变量做迭代,其余的变量做常量来进行优化,那么怎么选择这两个变量呢?
4.1 第一个变量的选择
SMO算法称选择第一个变量为外层循环,这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点,要满足的KKT条件我们在第一节已经讲到了:
一般来说,我们首先选择违反这个条件的点。如果这些支持向量都满足KKT条件,再选择违反 和 的点。
4.2 第二个变量的选择
SMO算法称选择第二一个变量为内层循环,假设我们在外层循环已经找到了, 第二个变量的选择标准是让有足够大的变化。由于定了的时候,也确定了,所以要想最大,只需要在为正时,选择最小的作为, 为负时,选择最大的E作为,可以将所有的保存下来加快迭代。
如果内存循环找到的点不能让目标函数有足够的下降, 可以采用遍历支持向量点来做,直到目标函数有足够的下降, 如果所有的支持向量做都不能让目标函数有足够的下降,可以跳出循环,重新选择
4.3 计算阈值b和差值
. SMO算法总结
输入是m个样本,其中x为n维特征向量。y为二元输出,值为1,或者-1.精度e。
输出是近似解
1)取初值
2)按照4.1节的方法选择,接着按照4.2节的方法选择,求出新的
SMO算法终于写完了,这块在以前学的时候是非常痛苦的,不过弄明白就豁然开朗了。希望大家也是一样。写完这一篇, SVM系列就只剩下支持向量回归了,胜利在望!
评论(0)
您还未登录,请登录后发表或查看评论