Extending the Decomposition Algorithm for Support Vector Machines Training

Abstract

The Support Vector Machine (SVM) is found to be a capable learning machine. It has the ability to handle difficult pattern recognition tasks such as speech recognition, and has demonstrated reasonable performance. The formulation in a SVM is elegant in that it is simplified to a convex Quadratic Programming (QP) problem. Theoretically the training is guaranteed to converge to a global optimal. The training of SVM is not as straightforward as it seems. Numerical problems will cause the training to give non-optimal decision boundaries. Using a conventional optimizer to train SVM is not the ideal solution. One can design a dedicated optimizer that will take full advantage of the specific nature of the QP problem in SVM training. The decomposition algorithm developed by Osuna et al. (1997a) reduces the training cost to an acceptable level. In this paper we have analyzed and developed an extension to Osuna’s method in order to achieve better performance. The modified method can be used to solve the training of practical SVMs, in which the training might not otherwise converge.