No. 1050

Title:

Game theoretical analysis of combining binary classifiers for multi-class classification problems

Author(s):

Yuichi, Shiraishi (Department of Statistical Science, The Graduate University for Advanced Studies; The Institute of Statistical Mathematics);
Kenji, Fukumizu (The Institute of Statistical Mathematics)

Key words:

classification; error correcting output code; game theory; linear programming; feasible flow

Abstract:

    Combining binary classifiers for multi-class classification problems has been very popular after the inventions of SVM and ada-boost, which are known to be very effective for binary classification. In this paper, we discuss the methods of combining binary classifiers from the game-theoretical point of view. The problem to duscuss is how the code matrix, which expresses the scheme of dividing and combining the classification task, has an influence on Nature's family. We represent the Nature's family by directed graphs and develop a general theorem for the condition of minimaxity, which is closely related to the network flow theory. Applying this theorem, we compare the one-vs-one and one-vs-all schemes, which are very typical. The result shows that the minimaxity of the ECOC approach holds under a milder condition in the one-vs-all case than in the one-vs-one.