The Multiple Pairs SMO: A modified SMO algorithm for the acceleration of the SVM training

摘要

The sequential minimal optimization (SMO) algorithm is known to be one of the most efficient solutions for the support vector machine training phase. It solves a quadratic programming (QP) problem by optimizing a set of coefficients whose size is the number of training examples. However, its execution time may be quite long due to its computational complexity: the algorithm executes many calculations per iteration as well as many iterations until a stop criterion is satisfied. Due to its importance, many improvements have been proposed in order to obtain faster solutions. These improvements keep unchanged the SMO basic characteristic: the optimization is always performed on one pair of coefficients per iteration. This paper presents the multiple pairs SMO (MP-SMO), a new solution for the SMO algorithm that consists of optimizing more than one pair of coefficients per iteration. We show that this algorithm improves the performance results obtained by other known SMO solutions. Our algorithm presents the following characteristics: a) it uses the previously adopted analytical solution; b) its working set selection heuristic has been adapted from known solutions in order to deal with multiple pairs; c) the monotonic convergence of the algorithm has been demonstrated. We applied our MP-SMO algorithm to a set of known benchmarks. We tested the algorithm optimizing two, three and four pairs per iteration. We always obtained better results than the original one pair SMO algorithm.