Timezone: »

Multiclass Learning Approaches: A Theoretical Comparison with Implications
Amit Daniely · Sivan Sabato · Shai Shalev-Shwartz

Wed Dec 05 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor #None
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.

Author Information

Amit Daniely (Hebrew University and Google Research)
Sivan Sabato (Ben Gurion University)
Shai Shalev-Shwartz (Mobileye & HUJI)

More from the Same Authors