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

Proceedings of the international workshop on data-mining and statistical science (DMSS2007), pp. 149–160

Authors:

Yuichi Shiraishi
Kenji Fukumizu
Shiro Ikeda

URL:

Abstract:

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 paper, we analyze theoretically the ECOC approach, which is a standard combining method. We discuss the problem of combining binary classifiers from 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.