nips nips2001 nips2001-147 nips2001-147-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Koby Crammer, Yoram Singer
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 from 1 to k. Our goal is to find a rank-prediction rule that assigns each instance a rank which is as close as possible to the instance's true rank. We describe a simple and efficient online algorithm, analyze its performance in the mistake bound model, and prove its correctness. We describe two sets of experiments, with synthetic data and with the EachMovie dataset for collaborative filtering. In the experiments we performed, our algorithm outperforms online algorithms for regression and classification applied to ranking. 1
[1] William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Int elligence Research, 10:243- 270 , 1999.
[2] K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass problems. Proc. of the Fourteenth Annual ConI on Computational Learning Theory, 200l.
[3] Y. Freund, R. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. Machine Learning: Proc. of the Fifteenth Inti. ConI, 1998.
[4] Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine Learning, 37(3): 277-296, 1999.
[5] R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. Advances in Large Margin Classifiers. MIT Press, 2000.
[6] J. Kemeny and J . Snell. Mathematical Models in the Social Sciences. MIT Press, 1962.
[7] Paul McJones. EachMovie collaborative filtering data set. DEC Systems Research Center, 1997. http://www.research.digital.com/SRC/eachmoviej.
[8] Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998.
[9] Bernard Widrow and Marcian E. Hoff. Adaptive switching circuits. 1960 IRE WESCON Convention Record, 1960. Reprinted in Neurocomputing (MIT Press, 1988).