Online learning of complex prediction problems using simultaneous projections

Yonatan Amit, Shai Shalev-Shwartz, Yoram Singer

Research output: Contribution to journalArticle

2 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 predictor 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 of 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 synthetic data and with multiclass text categorization tasks.

Original languageEnglish (US)
Pages (from-to)1399-1435
Number of pages37
JournalJournal of Machine Learning Research
Volume9
StatePublished - Jul 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Keywords

  • Mistake bounds
  • Online learning
  • Parallel computation
  • Structured prediction

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

  • Cite this