SMO算法框架

基本求解问题

其中

<=>

算法框架：

初始条件如果没有其他信息往往选10；这时f(1)e 算法的关键步骤：

1． 工作集的选择——采用简单的“Maximal violating pair”

kk2. 停止条件——m()M()，

其中

3. 子问题的求解：

分别与i, j对应；

L、U不容易确定：需分4种情况! 我建议如下推导过程——更简单： 令iikti，jkjtj，则(2) 等价于

1mintiti,tj2s..tQiiQijtiktjf()QQitjjjijyitiyjtj0,0ikti,kjtjCtikf()jtj

将tiyiyjtj代入上式，有

minf()f(k)ti,tj1Qii2yiyjQijQjjtj2f(k)yiyjf(k)tjji2s..t12atjbtj2LtjU

其中yi与yj异号时Lmax(ik,jk)、Umin(Cik,Cjk)；yi与yj同号时Lmax(ikC,jk)、Umin(ik,Cjk)。

tjmin(max(L,b/a),U)，该规划的解为： tiyiyjtj，其中a, b 为

上面二次函数的二次系数和一次系数。 4. 迭代更新

1) 2)

1k1k; kik1ikti，kNjjtj，Nf(k1)f(k)tiQ.,itjQ.,j;（如用第一种L、U确定方法，可以直接迭代计算

。 y.*f(k1)，省了一些算）

1f(k1)f(k)atjbtj;

25. 加速技巧——

Caching数据结构：定义矩阵KRlT为零矩阵，T是cache规模，用来存储核矩阵；初始化IRl为0向量，用来记录相应训练样本对应核矩

阵的列的位置；

举例：如果首先i、jk(x1,xj)k(x1,xi)、K(:,2)进入工作集，K(:,1)，k(xl,xj)k(xl,xi)而相应地I(i)1、I(j)2，依次类推，以后当某i进入工作集时，要用到其核矩阵相应列时先检查I(i)是否为零，为零表示此列没有计算，非零时K(:,I(i))就是要的已计算好核向量。

进一步可以采用shring策略降低cache规模！——自己尝试应用。 6. 应用推广——参阅文献 (1) 不定核矩阵； (2) (3) 7. 算法推广 1) 二次信息

2)工作集改为3个、4个，但一定要求相应二次规划有解析解！ 3) 其他

单个人独立完成：依据所给例子，修改用quadprog求解小规模非线性SVM训练问题，二维数据出图形，并编写随机生成测试数据的测试错分率计算代码。

依小组完成SMO算法编写，包括SMO函数文件和一个测试脚本文件： 具体刘老师学生编写所讲的标准SMO；

要求实现基于核函数的非线性问题求解，并实现caching策略；详细参阅所给资料介绍。

结课考试前个人以邮件形式发给我，附上所画图形。