上节中我们得出了原问题的对偶问题为:
公式(4.1)
那如何求解公式4.1呢?即解出,求出w和b即可得到原型:(公式4.2)
显然,公式4.1是二次规划(QP)问题,可使用二次规划算法进行求解。然而,该问题的规模正比于训练样本数,这会在实际任务中造成很大的开销。为了避免这个障碍,人们利用问题本身的特性,研究出很多高效的算法,其中SMO算法就是一个典型的代表。
讲解SMO算法之前,就必须先了解什么是KTT条件?
一般有等式约束条件时,常常使用拉格朗日乘子法,即把等式约束函数用一个系数与目标函数写为一个式子,称为拉格朗日函数,通过对拉格朗日函数对各变量求导,令其为零,得到候选值集合,然后验证求得最优值。
一般有不等式约束条件时,常常使用的就是KTT条件。同样地,把所有等式、不等式约束与目标函数写成一个式子,也叫拉格朗日函数,通过一些条件,可以求出最优值的必要条件,这个条件称为KTT条件。假设不等式约束的优化问题,可以写为:
那么,拉格朗日函数为
KTT条件是说最优值必须满足以下条件:
1. L(a,b,x)对x求导等于零;
2.a*g(x)=0
3. g(x) ≤0
4. ai≥0,b≥0
5. h(x)=0
到此为止,我们就能得出公式4.1的KTT条件为:
那么,对任意训练样本,总有或对。若,则该样本将不会出现在公式4.2求和公式中,所以也不会对f(x)有任何影响。若,则必有,所对应的样本点位于最大间隔边界上,是一个支持向量。
这总结出支持向量机一个重要的性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关。
回到正题,求解公式4.1用到的SMO算法是什么?
SMO基本思路是先固定之外的所有参数,然后求上的极值。由于存在约束,若固定之外的其它变量,则可由其它变量导出。于是SMO算法每次选择两个变量和并固定其它参数。这样,在参数初始化后,SMO不断进行如上操作即可。
由上面的KTT条件注意到,满足KTT的和就是在最大间隔上,如果不满足KTT条件,就会使得目标函数在迭代后减小。即:KTT条件违背的程度越大,则变量更新后可能导致的目标函数值减幅越大。于是,SMO会选取违背KTT条件程度最大的变量,第二个变量选择使一个目标函数值减小最快的变量,但由于其计算过程的复杂程度过高,因此,SMO采用一个启发式:使选取的两变量对应样本之间的间隔最大。
具体来说,仅考虑和时,公式4.1的约束可重写为:
,其中是使成立的常数。
用去消除公式4.1中的变量,则得到一个关于的单变量二次规划问题,仅有的约束就是,这样的很容易就能求解出和
那如何求出公式4.2中的参数b呢?
注意到对任意支持向量(xs,ys),都有ysf(s)=1,即
为所有支持向量的下标集。
理论上,可选取任意支持向量并通过求解上述式子得到b。
但在现实任务中,常采用一种更鲁棒的做法:使用所有支持向量求解的平均值,即:
下节讲解核函数。
如果觉得《机器学习算法——支持向量机SVM4(SMO算法及KTT条件)》对你有帮助,请点赞、收藏,并留下你的观点哦!