On the learnability and design of output codes for multiclass problems

Koby Crammer, Yoram Singer

Research output: Contribution to journalArticlepeer-review

346 Scopus citations


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 languageAmerican English
Pages (from-to)201-233
Number of pages33
JournalMachine Learning
Issue number2-3
StatePublished - May 2002

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


  • Multiclass categorization
  • Output coding
  • SVM


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