Enhancements of Multi-class Support Vector Machine Construction from Binary Learners using Generalization Performance

We propose several novel methods for enhancing the multi-class SVMs by applying the generalization performance of binary classifiers as the core idea. This concept will be applied on the existing algorithms, i.e., the Decision Directed Acyclic Graph (DDAG), the Adaptive Directed Acyclic Graphs (ADAG), and Max Wins. Although in the previous approaches there have been many attempts to use some information such as the margin size and the number of support vectors as performance estimators for binary SVMs, they may not accurately reflect the actual performance of the binary SVMs. We show that the generalization ability evaluated via a cross-validation mechanism is more suitable to directly extract the actual performance of binary SVMs. Our methods are built around this performance measure, and each of them is crafted to overcome the weakness of the previous algorithm. The proposed methods include the Reordering Adaptive Directed Acyclic Graph (RADAG), Strong Elimination of the classifiers (SE), Weak Elimination of the classifiers (WE), and Voting based Candidate Filtering (VCF). Experimental results demonstrate that our methods give significantly higher accuracy than all of the traditional ones. Especially, WE provides significantly superior results compared to Max Wins which is recognized as the state of the art algorithm in terms of both accuracy and classification speed with two times faster in average. Introduction The support vector machine (SVM) [1, 2] is a high performance learning algorithm constructing a hyperplane to separate two-class data by maximizing the margin between them. There are two approaches for extending SVMs to multi-class problems, i.e., solving the problem by formulating all classes of data under a single optimization, and combining several two-class subproblems. However, the difficulty and complexity to solve the problem with the first method are due to the increase of the number of classes and the size of training data, so the second method is more suitable for practical use. In this paper, we focus on the second approach. For constructing a multi-class classifier from binary ones, the method called one-against-one trains each binary classifier on only two out ofN classes, and builds N (N 1)/ 2 possible classifiers. Several strategies have been proposed for combining the trained classifiers to make the final classification for an unseen data. Friedman [3] suggested the combination strategy called Max Wins .