目录

 

　　　　　　　Support Vector Machine(2) : Sequential Minimal Optimization　

 

1. Sequential Minimal Optimizaion 简介

　　我们在中已经将SVM的最优化问题使用KKT条件转化为其一个对偶问题，现在我们将对偶问题的表达形式重写在这里（这里我们考虑soft SVM）：

 

　　　　　　　　　max　$L^{*}(\mathbf{a}) = \sum_na_n - \frac{1}{2} \sum_n\sum_ma_na_mt_nt_mK(x_n,x_m)$     (1)

 

　　其中$\mathbf{a} 和 \mathbf{t}$ 满足：

 

　　　　　　　　　　$ C \geqslant a_n \geqslant 0$ for n = 1,2,...,N    (2)

　　　　　　　　　　$\sum_na_nt_n = 0$     (3)　　　　　　

　　其中最大化$L^*$等价于最小化其相反数，所以我们(1)式等价于：

　　　　　　　min　$\Psi(\mathbf{a}) = \frac{1}{2}\sum_n\sum_ma_na_mt_nt_mK(x_n,x_m) - \sum_na_n$　(4)

　　这是一个典型的二次规划（QP）问题，SMO就是为快速解决这个QP问题而提出来的。

 

2. SMO解法

　　本来是想自己写的，但是这篇博客写的实在是太好了。结合John Platt 的论文《Sequential Minimal Optimization : A Fast Algorithm for Training Support Vector Machines》去看，给人一种醍醐灌顶的感觉，是在是令人叹为观止，连自己写的欲望都没有了，以后等心情恢复了再来写吧。

 

L∗(a)=∑nan−1/2∑n∑manamtntmxnxm