Online multiclass learning by interclass hypothesis sharing

Michael Fink, Shai Shalev-Shwartz, Yoram Singer, Shimon Ullman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations


We describe a general framework for online multiclass learning based on the notion of hypothesis sharing. In our framework sets of classes are associated with hypotheses. Thus, all classes within a given set share the same hypothesis. This framework includes as special cases commonly used constructions for multiclass categorization such as allocating a unique hypothesis for each class and allocating a single common hypothesis for all classes. We generalize the multiclass Perceptron to our framework and derive a unifying mistake bound analysis. Our construction naturally extends to settings where the number of classes is not known in advance but, rather, is revealed along the online learning process. We demonstrate the merits of our approach by comparing it to previous methods on both synthetic and natural datasets.

Original languageEnglish (US)
Title of host publicationACM International Conference Proceeding Series - Proceedings of the 23rd International Conference on Machine Learning, ICML 2006
Number of pages8
StatePublished - 2006
Event23rd International Conference on Machine Learning, ICML 2006 - Pittsburgh, PA, United States
Duration: Jun 25 2006Jun 29 2006

Publication series

NameACM International Conference Proceeding Series


Other23rd International Conference on Machine Learning, ICML 2006
Country/TerritoryUnited States
CityPittsburgh, PA

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Online multiclass learning by interclass hypothesis sharing'. Together they form a unique fingerprint.

Cite this