SMO,sequential minimal optimization
SMO的使用场景
SMO用于解决非线性支持向量机的对偶问题:
amini=1∑Nj=1∑NaiajyiyjK(xi,xj)−i=1∑Nais.t.i=1∑Naiyi=00≤ai≤C,i=1,2,⋯,N1 SMO的原理
如果所有变量ai都满足此问题的KKT条件。
否则,选两个变量,固定其他变量,针对这两个变量构建一个二次规划问题。
由于这两个变量是互相制约的,可以用一个变量来表示另一个变量,因此只有一个自变量。
解二次规划问题并更新变量。
SMO的过程
选择两个变量link,假设两个变量为a1和a2
把公式(1)中的变量a1、a2和常量分开来写link,成为公式(2)
L(a1,a2)=f(1,1)+2f(1,2)+f(2,2)+2j=3∑Nf(1,j)+2j=3∑Nf(2,j)−a1−a2+常数项2
其中:
f(i,j)=aiajyiyjK(xi,xj) 根据a1和a2的关系,消息公式(2)中的变量a1,留下变量a2,得到公式(3)link
公式(3)对a2求导,并令导数为0,得到a2的值link。
第4步得到的a2没有考虑到公式(1)的限制条件,需要对a2做一些修剪link
根据a2得到a1
a1=y1−ξ−a2y2 根据新的a1和a2更新blink