A game theoretical analysis of combining classifiers for multi-class classification problems


Combining binary classifiers for multi-class classification problems has been very popular after the invention of SVM and ada-boost, which are known to be very effective for binary classification. In this pater, we analyze theoretically the ECOC approach, which is a standard combining method. We discuss the problem of combining binary classifiers form the game-theoretical point of view. First, we develop a general theorem for the condition of minimaxity, which is closely related to the network flow theory. Applying this theorem, we show that the ECOC approach has the minimax property in the one-vs-one and one-vs-all case.

Proceedings of the international workshop on data-mining and statistical science (DMSS2007)