On the learnability and design of output codes for multiclass problems

Koby Crammer, Yoram Singer

Research output: Contribution to journalArticle

331 Scopus citations

Abstract

Output coding is a general framework for solving multiclass categorization problems. Previous research on output codes has focused on building multiclass machines given predefined output codes. In this paper we discuss for the first time the problem of designing output codes for multiclass problems. For the design problem of discrete codes, which have been used extensively in previous works, we present mostly negative results. We then introduce the notion of continuous codes and cast the design problem of continuous codes as a constrained optimization problem. We describe three optimization problems corresponding to three different norms of the code matrix. Interestingly, for the l2 norm our formalism results in a quadratic program whose dual does not depend on the length of the code. A special case of our formalism provides a multiclass scheme for building support vector machines which can be solved efficiently. We give a time and space efficient algorithm for solving the quadratic program. We describe preliminary experiments with synthetic data show that our algorithm is often two orders of magnitude faster than standard quadratic programming packages. We conclude with the generalization properties of the algorithm.

Original languageEnglish (US)
Pages (from-to)201-233
Number of pages33
JournalMachine Learning
Volume47
Issue number2-3
DOIs
StatePublished - May 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Keywords

  • Multiclass categorization
  • Output coding
  • SVM

Fingerprint Dive into the research topics of 'On the learnability and design of output codes for multiclass problems'. Together they form a unique fingerprint.

  • Cite this