Online classification for complex problems using simultaneous projections

Yonatan Amit, Shai Shalev-Shwartz, Yoram Singer

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

4 Scopus citations

Abstract

We describe and analyze an algorithmic framework for online classification where each online trial consists of multiple prediction tasks that are tied together. We tackle the problem of updating the online hypothesis by defining a projection problem in which each prediction task corresponds to a single linear constraint. These constraints are tied together through a single slack parameter. We then introduce a general method for approximately solving the problem by projecting simultaneously and independently on each constraint which corresponds to a prediction sub-problem, and then averaging the individual solutions. We show that this approach constitutes a feasible, albeit not necessarily optimal, solution for the original projection problem. We derive concrete simultaneous projection schemes and analyze them in the mistake bound model. We demonstrate the power of the proposed algorithm in experiments with online multiclass text categorization. Our experiments indicate that a combination of class-dependent features with the simultaneous projection method outperforms previously studied algorithms.

Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference
Pages17-24
Number of pages8
StatePublished - Dec 1 2007
Externally publishedYes
Event20th Annual Conference on Neural Information Processing Systems, NIPS 2006 - Vancouver, BC, Canada
Duration: Dec 4 2006Dec 7 2006

Other

Other20th Annual Conference on Neural Information Processing Systems, NIPS 2006
CountryCanada
CityVancouver, BC
Period12/4/0612/7/06

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint Dive into the research topics of 'Online classification for complex problems using simultaneous projections'. Together they form a unique fingerprint.

  • Cite this

    Amit, Y., Shalev-Shwartz, S., & Singer, Y. (2007). Online classification for complex problems using simultaneous projections. In Advances in Neural Information Processing Systems 19 - Proceedings of the 2006 Conference (pp. 17-24)