title: Online ranking by projecting.
abstract: We discuss the problem of ranking instances. In our framework, each instance is associated with a rank or a rating, which is an integer in 1 to k. Our goal is to find a rank-prediction rule that assigns each instance a rank that is as close as possible to the instance's true rank. We discuss a group of closely related online algorithms, analyze their performance in the mistake-bound model, and prove their correctness. We describe two sets of experiments, with synthetic data and with the EachMovie data set for collaborative filtering. In the experiments we performed, our algorithms outperform online algorithms for regression and classification applied to ranking.
authors.affiliation: School of Computer Science and Engineering, Hebrew University, Jerusalem 91904, Israel. kobics@cs.huji.ac.il
authors.forename: Koby
authors.initials: K
authors.lastname: Crammer
authors.forename: Yoram
authors.initials: Y
authors.lastname: Singer
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D008433:Mathematics; D008962:Models, Theoretical; D016571:Neural Networks, Computer; D015588:Observer Variation