Single sequential minimal optimization: an improved SVMs training algorithm

摘要

We introduce homogeneous coordinates to represent support vector machines (SVMs) and develop a corresponding training algorithm: single sequential minimal optimization (SSMO). By this simple trick (homogeneous coordinates representation), linear constrains will not appear in quadratic programming (QP) optimization problem. So unlike the most popular used SVM training algorithm sequential minimal optimization (SMO) which solves the QP subproblem containing minimal two Lagrange multipliers, SSMO can analytically update only one Lagrange multiplier at every step. Because of avoiding double loops in heuristically choosing the two Lagrange multipliers in SMO, both CPU time and iterations can be decreased greatly. Experiments on MNIST database, under mild KKT conditions accuracy requirement, shows SSMO can be more than 2 times faster than SMO.