Multiclass support vector machines using reordering adaptive directed acyclic graphs

Abstract

The problem of extending binary support vector machines (SVMs) for multiclass classification is still an ongoing research issue. The Decision Directed Acyclic Graph (DDAG) method reduces training and evaluation time, while maintaining accuracy compared to the Max Wins, which is probably the currently most accurate method for multiclass SVMs. The Adaptive Directed Acyclic Graph (ADAG) approach is proposed to alleviate the problem of the DDAG structure. However, different sequences of binary classifiers in nodes in the ADAG may provide different accuracy. In this research we present a new method, Reordering Adaptive Directed Acyclic Graph (RADAG), which is the modification of the original ADAG method. We propose an algorithm to choose an optimal sequence of binary classifiers in nodes in the ADAG by considering the generalization error bounds of all classifiers. We apply minimum-weight perfect matching with the reordering algorithm in order to select binary classifiers which have small generalization errors to be used in data classification and in order to find the best sequence of binary classifiers in polynomial time. We then compare the performance of our method with previous methods including the DDAG, the ADAG and the Max Wins. Experiments denote that our method gives higher accuracy. Moreover it runs faster than Max Wins, especially when the number of classes and/or the number of dimensions are relatively large. In this research we also present alternative ways to enhance the performance of the RADAG and the DDAG as well