Solving Large-Scale Multi-Label SVM Problems with A Tree Decomposition Approach
Fu Chang, Chan-Cheng Liu · 2011
We propose a tree decomposition approach for solving large-scale multi-label classication problems. In this approach, we follow a convention of rst transforming the problem into a number of one-against-others classication problems. Then, to solve each transformed problem, we use a decision tree to decompose the corresponding data space and train local SVMs on the decomposed regions. The resultant classier is called decision tree support vector machine (DTSVM). The approach has the following advantages. First, when nonlinear SVM is used as the learning machine, DTSVM requires much shorter training time than global SVM (gSVM) while achieving comparable test accuracy. Second, when linear SVM is used as the learning machine, DTSVM often achieves higher test accuracy than gSVM. Third, in textual applications, linear DTSVM plays the leading role among linear gSVM, non-linear gSVM, and non-linear DTSVM for the following reason. Linear DTSVM achieves higher test accuracy than linear gSVM; moreover, it achieves comparable test accuracy to, but requires much less training time than, non-linear gSVM and non-linear DTSVM.