Timezone: »

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

Wed Dec 05 10:26 AM -- 10:30 AM (PST) @ Harveys Convention Center Floor, CC
in Spotlight Session 5 »
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 of the Negev)
Shai Shalev-Shwartz (Mobileye & HUJI)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors