Online Classification for Complex Problems Using Simultaneous Projections
Yonatan Amit, Shai Shalev‐Shwartz, Yoram Singer · The MIT Press eBooks · 2007
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 by defining an instantaneous projection problem in which all the prediction tasks are tied through a single slack parameter. We then introduce a general method for approximately solving the problem by projecting simultaneously and independently each constraint which corresponds to a prediction subproblem, and then average 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 variants 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 previous algorithms for this task. 1