Resumen de Support vector machine tools for multi-class classification problems
Ling Liu
Lately, Support Vector Machine (SVM) methods have become a very popular technique in the machine learning field for classification problems. It was originally proposed for classifications of two classes. The effectiveness of this method has not only been shown in hundreds of experiments, but also been proved in theory. In our real life, we usually have more than two classes. Various multi-class models with a single objective have been proposed mostly based on two families of methods: an all-together approach and a combination of binary classifiers. However, most of these single-objective models consider neither the different costs of different misclassifications nor the users’ preferences. To overcome these drawbacks, we have two approaches. A direct way is to give different weights to the penalties in the objective functions. The difficulty for this way is how to choose proper values for the weights. Alternatively, multi-objective approaches have been proposed. However, these multi-objective approaches need to solve a set of large Second-Order-Cone Programs (SOCPs) and gives us weakly Pareto-optimal solutions.
This thesis is comprised of two working papers on multi-class SVMs. We summarize the contributions of these two working papers as follows.
In the first article, we propose a multi-objective technique that we denominate Projected Multi-objective SVM (PM), which works in a higher dimensional space than the object space. For PM, we can characterize its Pareto-optimal solutions. And for classifications with large numbers of classes, PM significantly alleviates the computational bottlenecks. From our experimental results, and compared with the single-objective multi-class SVMs (based on an all-together method, one-against-all method and one-against-one method), PM obtains comparable values for the training classification accuracies, testing classification accuracies and training time, with the advantage of providing a wider set of options, each of them designed for different misclassification costs. Compared to other multi-objective methods, PM outperforms them in terms of the out-of-sample quality of the approximation of the Pareto frontier, with a considerable reduction of the computational burden.
In the second article, we focus on finding the appropriate values of the weight parameters for the single-objective multi-class SVM which considers all classes in one quadratic program (QP). We propose a partial parametric path algorithm (PPPA) taking advantage of the piecewise linearity of the optimal solutions of the weighted single-objective SVMs with respect to the trade-off parameter C. Compared to the traditional grid search method which needs repeatedly solving the QPs, using PPPA we need to solve only one QP and several linear equations. Thus we can save a lot of computation using PPPA. To systematically explore the different weights for the misclassification costs, we combine the PPPA with a variable neighborhood search method. Our numerical experiments shows the efficiency and reliability of PPPA.
