Publication: Support vector machine tools for multi-class classification problems
Loading...
Identifiers
Publication date
2016-03
Defense date
2016-05-05
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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 e↵ectiveness 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 di↵erent costs of di↵erent misclassifications
nor the users’ preferences. To overcome these drawbacks, we have two approaches. A
direct way is to give di↵erent 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 Multiobjective
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 di↵erent 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-o↵ 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 di↵erent 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.
Description
Keywords
Artificial intelligent, Machine learning, Multiclass multiobjective SVM, Weakly Pareto-optimal solution, Multi-objective approach (PM), Single-objective approach (PPPA)