第7章 序列最小最优化算法

SMO,sequential minimal optimization

SMO的使用场景

SMO用于解决非线性支持向量机的对偶问题:

minai=1Nj=1NaiajyiyjK(xi,xj)i=1Nais.t.i=1Naiyi=00aiC,i=1,2,,N1\begin{aligned} \min_a \quad \sum_{i=1}^N\sum_{j=1}^Na_ia_jy_iy_jK(x_i, x_j) - \sum_{i=1}^Na_i \\ s.t. \quad \sum_{i=1}^Na_iy_i=0 \quad \quad 0 \le a_i \le C, i=1,2,\cdots,N && {1} \end{aligned}

SMO的原理

如果所有变量aia_i都满足此问题的KKT条件。 否则,选两个变量,固定其他变量,针对这两个变量构建一个二次规划问题。 由于这两个变量是互相制约的,可以用一个变量来表示另一个变量,因此只有一个自变量。 解二次规划问题并更新变量。

SMO的过程

  1. 选择两个变量link,假设两个变量为a1a_1a2a_2

  2. 把公式(1)中的变量a1a_1a2a_2和常量分开来写link,成为公式(2)

    L(a1,a2)=f(1,1)+2f(1,2)+f(2,2)+2j=3Nf(1,j)+2j=3Nf(2,j)a1a2+常数项2\begin{aligned} L(a_1, a_2) = f(1,1)+2f(1,2)+f(2,2) \\ +2\sum_{j=3}^Nf(1,j) +2\sum_{j=3}^Nf(2,j) \\ -a_1 - a_2 + \text{常数项}&& {2} \end{aligned}

其中:

f(i,j)=aiajyiyjK(xi,xj)f(i, j) = a_ia_jy_iy_jK(x_i,x_j)
  1. 根据a1a_1a2a_2的关系,消息公式(2)中的变量a1a_1,留下变量a2a_2,得到公式(3)link

  2. 公式(3)对a2a_2求导,并令导数为0,得到a2a_2的值link

  3. 第4步得到的a2a_2没有考虑到公式(1)的限制条件,需要对a2a_2做一些修剪link

  4. 根据a2a_2得到a1a_1

    a1=ξa2y2y1a_1 = \frac {-\xi - a_2y_2}{y_1}
  5. 根据新的a1a_1a2a_2更新blink

  6. 回到第1步,直至没有a可以更新

Last updated