Ultraconservative online algorithms for multiclass problems

Koby Crammer, Yoram Singer

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

16 Scopus citations

Abstract

In this paper we study online classification algorithms for multiclass problems in the mistake bound model. The hypotheses we use maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and then sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label’s prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems.

Original languageEnglish (US)
Title of host publicationComputational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings
EditorsDavid Helmbold, Bob Williamson
PublisherSpringer Verlag
Pages99-115
Number of pages17
ISBN (Print)9783540423430
DOIs
StatePublished - Jan 1 2001
Event14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 - Amsterdam, Netherlands
Duration: Jul 16 2001Jul 19 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2111
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001
CountryNetherlands
CityAmsterdam
Period7/16/017/19/01

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Ultraconservative online algorithms for multiclass problems'. Together they form a unique fingerprint.

  • Cite this

    Crammer, K., & Singer, Y. (2001). Ultraconservative online algorithms for multiclass problems. In D. Helmbold, & B. Williamson (Eds.), Computational Learning Theory - 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001, Proceedings (pp. 99-115). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2111). Springer Verlag. https://doi.org/10.1007/3-540-44581-1_7