Average Performance Analysis of Multi-Class Classification Based on Error-Correcting Output Codes

In machine learning, one of the methods to solve multiclass classification problems is a framework called Error-Correcting Output Codes (ECOC), which constructs a multiclass classifier by combining a lot of binary classifiers. ECOC assigns binary codewords to each category, and the multiclass classification performance varies depending on the code. In this study, we treat each element of the codeword as a random variable and evaluate the average performance of ECOC. As a result, for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$M$</tex> class classification if the number of binary classifiers is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log M)$</tex>, then the average error probability of various codes approaches that of MAP estimation. We show that the important points are the ratio between the number of binary classifiers and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\log M$</tex> and the difference between the maximum posterior probability and the second highest posterior probability for the categories.