Loss bounds for online category ranking

Koby Crammer, Yoram Singer

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

3 Scopus citations

Abstract

Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking where the instances are revealed in a sequential manner. We describe additive and multiplicative updates which constitute the core of the learning algorithms. The updates are derived by casting a constrained optimization problem for each new instance. We derive loss bounds for the algorithms by using the properties of the dual solution while imposing additional constraints on the dual form. Finally, we outline and analyze the convergence of a general update that can be employed with any Bregman divergence.

Original languageEnglish (US)
Title of host publicationLearning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
PublisherSpringer Verlag
Pages48-62
Number of pages15
ISBN (Print)3540265562, 9783540265566
DOIs
StatePublished - 2005
Event18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy
Duration: Jun 27 2005Jun 30 2005

Publication series

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

Other

Other18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory
CountryItaly
CityBertinoro
Period6/27/056/30/05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Loss bounds for online category ranking'. Together they form a unique fingerprint.

  • Cite this

    Crammer, K., & Singer, Y. (2005). Loss bounds for online category ranking. In Learning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings (pp. 48-62). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3559 LNAI). Springer Verlag. https://doi.org/10.1007/11503415_4