Multiclass Classification Method Implemented In LIBSVM
Initially, Support vector machines (SVMs) were originally designed for binary classification. For binary classification to be extended to multiclass classification is still an ongoing research issue. Several methods has been proposed where typically we construct a multiclass classifier by combining several binary classifiers [4]. The two present methods for multiclass SVM are by constructing and combining a lot of binary classifiers while the other is by directly considering all data in one optimization formulation. In essence, for multiclass SVM methods, several binary classifiers has to be constructed or a larger optimization problem would be needed. It is computationally more costly to solve a multiclass problem than a binary problem with the same number of data. The different methods for multiclass SVM are:
- One Against All Method (WTA_SVM): It is probably the primitive method used for implementation for SVM multiclass classification. The WTA_SVM constructs M binary classifiers. The ith classifier output function ρi is trained taking the examples from ωi as positive while all the examples from all other classes as negative. For a new example x, WTA SVM strategy will assigns it to the class with the largest value of ρi.
- One Against One (MWV_SVM): It constructs one binary classifier for each pair of distinct classes, therefore all together M(M−1)/2 binary classifiers are constructed. For the binary classifier Cij, Cij is trained using the examples from ωi to be positive and the examples from ωj as negative. For a new example y, if the classifier Cij says y is in class ωi, then one is added to the vote for class ωi . Otherwise, the vote for class ωj will be increased by one. At the end of theM(M −1)/2 binary classifiers makes its vote, MWV strategy will assigns x to the class with the biggest number of votes.
- DAGSVM: It has the same training phase as the one-against-one method by solving binary SVMs. In the testing phase, a rooted binary directed acyclic graph is used which has internal nodes and leaves. Each node is a binary SVM of th and th classes.
For a given test sample, starting from the root node, the binary decision function is evaluated, then depending on the output value, it moves to either left or right. Therefore, we go through a path before reaching a leaf node which indicates the predicted class. One of the advantages of DAG is that some analysis of generalization can be established [7].
Figure 1: Multiclass Classification[12]
LIBSVM software tool has been modified by implementing all the three methods listed above. Another method used for implementing SVM as an extension of and LIBSVM is “a method by which all data are considered at once and a decomposing implementation”. It’s idea is similar to the one against all method [3]. In conclusion, all the methods stated above and bases on the experiments performed by [3] and [7], it is better to use one against one method and the DEG method for large problem of experiments.
