Efficient Revised Simplex Method for SVM Training

• Published in: IEEE transaction on neural networks and learning systems 2011-10, Vol.22 (10), p.1650-1661
• Main Authors: Sentelle, C., Anagnostopoulos, G. C., Georgiopoulos, M.
• Format: Article
• Language: English
• Subjects: Active set method; Algorithms; Applied sciences; Artificial Intelligence; Computational efficiency; Computer science; control theory; systems; Data processing. List processing. Character string processing; Equations; Exact sciences and technology; Indexes; Integrated circuits; Kernel; Memory organisation. Data processing; Models, Neurological; Neural networks; Neural Networks (Computer); null space method; Pricing; quadratic programming; revised simplex method; Searching; Simplex method; Singularities; Software; Software - standards; Software Design; Software Validation; Studies; support vector machine; Support vector machines; Training
• ISSN: 1045-9227; 2162-237X; 1941-0093; 2162-2388
• DOI: 10.1109/TNN.2011.2165081

Existing active set methods reported in the literature for support vector machine (SVM) training must contend with singularities when solving for the search direction. When a singularity is encountered, an infinite descent direction can be carefully chosen that avoids cycling and allows the algorithm to converge. However, the algorithm implementation is likely to be more complex and less computationally efficient than would otherwise be required for an algorithm that does not have to contend with the singularities. We show that the revised simplex method introduced by Rusin provides a guarantee of nonsingularity when solving for the search direction. This method provides for a simpler and more computationally efficient implementation, as it avoids the need to test for rank degeneracies and also the need to modify factorizations or solution methods based upon those rank degeneracies. In our approach, we take advantage of the guarantee of nonsingularity by implementing an efficient method for solving the search direction and show that our algorithm is competitive with SVM-QP and also that it is a particularly effective when the fraction of nonbound support vectors is large. In addition, we show competitive performance of the proposed algorithm against two popular SVM training algorithms, SVMLight and LIBSVM.