jmlr jmlr2008 jmlr2008-80 jmlr2008-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tzu-Kuo Huang, Chih-Jen Lin, Ruby C. Weng
Abstract: This paper proposes new approaches to rank individuals from their group comparison results. Many real-world problems are of this type. For example, ranking players from team comparisons is important in some sports. In machine learning, a closely related application is classification using coding matrices. Group comparison results are usually in two types: binary indicator outcomes (wins/losses) or measured outcomes (scores). For each type of results, we propose new models for estimating individuals’ abilities, and hence a ranking of individuals. The estimation is carried out by solving convex minimization problems, for which we develop easy and efficient solution procedures. Experiments on real bridge records and multi-class classification demonstrate the viability of the proposed models. Keywords: ranking, group comparison, binary/scored outcomes, Bradley-Terry model, multiclass classification
Erin L. Allwein, Robert E. Schapire, and Yoram Singer. Reducing multiclass to binary: a unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113–141, 2001. ISSN 1533-7928. Adam L. Berger, Vincent J. Della Pietra, and Stephen A. Della Pietra. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71, 1996. 2214 R ANKING I NDIVIDUALS BY G ROUP C OMPARISONS Bernhard E. Boser, Isabelle Guyon, and Vladimir Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144–152. ACM Press, 1992. Ralph A. Bradley and Milton E. Terry. The rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324–345, 1952. Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A Library for Support Vector Machines, 2001. Software available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm. John N. Darroch and Douglas Ratcliff. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470–1480, 1972. Herbert A. David. The Method of Paired Comparisons. Oxford University Press, second edition, 1988. Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995. Arpad E. Elo. The Rating of Chessplayers, Past and Present. Arco Pub., New York, 2nd edition, 1986. Mark E. Glickman. Paired Comparison Models with Time-varying Parameters. PhD thesis, Department of Statistics, Harvard University, 1993. Joshua Goodman. Sequential conditional generalized iterative scaling. In ACL, pages 9–16, 2002. Trevor Hastie and Robert Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(1):451–471, 1998. Ralf Herbrich and Thore Graepel. TrueSkillTM : A Bayesian skill rating system. In Advances in Neural Information Processing Systems 19. MIT Press, Cambridge, MA, 2007. Tzu-Kuo Huang, Chih-Jen Lin, and Ruby C. Weng. Ranking individuals by group comparisons. In Proceedings of the Twenty Third International Conference on Machine Learning (ICML), 2006a. Tzu-Kuo Huang, Ruby C. Weng, and Chih-Jen Lin. Generalized Bradley-Terry models and multiclass probability estimates. Journal of Machine Learning Research, 7:85–115, 2006b. URL http://www.csie.ntu.edu.tw/˜cjlin/papers/generalBT.pdf. David R. Hunter. MM algorithms for generalized Bradley-Terry models. The Annals of Statistics, 32:386–408, 2004. Edwin T. Jaynes. Information theory and statistical mechanics. Physical Review, 106(4):620–630, 1957a. Edwin T. Jaynes. Information theory and statistical mechanics ii. Physical Review, 108(2):171–190, 1957b. Hsuan-Tien Lin, Chih-Jen Lin, and Ruby C. Weng. A note on Platt’s probabilistic outputs for support vector machines. Machine Learning, 68:267–276, 2007. URL http://www.csie.ntu. edu.tw/˜cjlin/papers/plattprob.pdf. 2215 H UANG , L IN AND W ENG Joshua E. Menke and Tony R. Martinez. A Bradley-Terry artificial neural network model for individual ratings in group competitions. Neural Computing and Applications, 2007. To appear. Thomas Minka. A Family of Algorithms for Approximate Bayesian Inference. PhD thesis, MIT, 2001. Stephen Della Pietra, Vincent Della Pietra, and John Lafferty. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393, 1997. John Platt. Probabilistic outputs for support vector machines and comparison to regularized likeli¨ hood methods. In A.J. Smola, P.L. Bartlett, B. Scholkopf, and D. Schuurmans, editors, Advances in Large Margin Classifiers, Cambridge, MA, 2000. MIT Press. Bianca Zadrozny. Reducing multiclass to binary by coupling probability estimates. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems 14, pages 1041–1048. MIT Press, Cambridge, MA, 2002. 2216