Online Learning by Projecting: From Theory to Lrge Scale Web-spam Filtering

Yoram Singer (Google Inc.)

A unified algorithmic framework and corresponding analysis for numerous problems in online learning is presented.  The basic algorithm works by projecting an instantaneous hypothesis onto a single hyperplane which forms the basis for the next instantaneous hypothesis.  The analysis is based on simple convexity properties combined with mistake bound techniques. After describing the basic algorithmic setup we discuss a few extensions to more complex problems.  We conclude with a description of an implementation of the algorithms for the purpose of (very) large scale web-spam filtering.