Constructing Multiclass Learners from Binary Learners: A Simple Black-Box Analysis of the Generalization Errors Authors: Jittat Fakcharoenphol and Boonserm Kijsirikul Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 135 - 147, Springer 2005. Abstract. Multiclass learning is widely solved by reducing to a set of binary problems. By considering base binary classifiers as black boxes, we analyze generalization errors of various constructions, including Max-Win, Decision Directed Acyclic Graphs, Adaptive Directed Acyclic Graphs, and the unifying approach based on coding matrix with Hamming decoding of Allwein, Schapire, and Singer, using only elementary probabilistic tools. Many of these bounds are new, some are much simpler than previously known. This technique also yields a simple proof of the equivalences of the learnability and polynomial-learnability of the multiclass problem and the induced pairwise problems. ©Copyright 2005, Springer