Multiclass Learning Approaches: A Theoretical Comparison with Implications
This work provides theoretical foundations for multiclass learning, which is incremental but offers practical guidance for researchers and practitioners in machine learning.
The paper theoretically analyzes and compares five multiclass classification methods, including One vs. All and Multiclass SVM, by examining both estimation and approximation errors using VC theory, revealing practical insights into their performance under various conditions.
We theoretically analyze and compare the following five popular multiclass classification methods: One vs. All, All Pairs, Tree-based classifiers, Error Correcting Output Codes (ECOC) with randomly generated code matrices, and Multiclass SVM. In the first four methods, the classification is based on a reduction to binary classification. We consider the case where the binary classifier comes from a class of VC dimension $d$, and in particular from the class of halfspaces over $\reals^d$. We analyze both the estimation error and the approximation error of these methods. Our analysis reveals interesting conclusions of practical relevance, regarding the success of the different approaches under various conditions. Our proof technique employs tools from VC theory to analyze the \emph{approximation error} of hypothesis classes. This is in sharp contrast to most, if not all, previous uses of VC theory, which only deal with estimation error.