jmlr jmlr2006 jmlr2006-34 jmlr2006-34-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tzu-Kuo Huang, Ruby C. Weng, Chih-Jen Lin
Abstract: The Bradley-Terry model for obtaining individual skill from paired comparisons has been popular in many areas. In machine learning, this model is related to multi-class probability estimates by coupling all pairwise classification results. Error correcting output codes (ECOC) are a general framework to decompose a multi-class problem to several binary problems. To obtain probability estimates under this framework, this paper introduces a generalized Bradley-Terry model in which paired individual comparisons are extended to paired team comparisons. We propose a simple algorithm with convergence proofs to solve the model and obtain individual skill. Experiments on synthetic and real data demonstrate that the algorithm is useful for obtaining multi-class probability estimates. Moreover, we discuss four extensions of the proposed model: 1) weighted individual skill, 2) home-field advantage, 3) ties, and 4) comparisons with more than two teams. Keywords: Bradley-Terry model, probability estimates, error correcting output codes, support vector machines
A. Agresti. Categorical Data Analysis. Wiley, New York, 1990. E. L. Allwein, R. 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. C. L. Blake and C. J. Merz. UCI repository of machine learning databases. Technical report, University of California, Department of Information and Computer Science, Irvine, CA, 1998. Available at http://www.ics.uci.edu/~mlearn/MLRepository.html. B. Boser, I. Guyon, and V. 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. R. A. Bradley and M. Terry. The rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39:324–345, 1952. G. W. Brier. Verification of forecasts expressed in probabilities. Monthly Weather Review, 78:1–3, 1950. C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm. C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273–297, 1995. H. A. David. The method of paired comparisons. Oxford University Press, New York, second edition, 1988. R. R. Davidson and P. H. Farquhar. A bibliography on the method of paired comparisons. Biometrics, 32:241–252, 1976. T. G. Dietterich and G. Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2:263–286, 1995. URL citeseer.ist.psu.edu/dietterich95solving.html. L. R. Jr. Ford. Solution of a ranking problem from binary comparisons. American Mathematical Monthly, 64(8):28–33, 1957. T. Hastie and R. Tibshirani. Classification by pairwise coupling. The Annals of Statistics, 26(1):451–471, 1998. T.-K. Huang, R. C. Weng, and C.-J. Lin. A generalized Bradley-Terry model: From group competition to individual skill. In Advances in Neural Information Processing Systems 17. MIT Press, Cambridge, MA, 2005. J. J. Hull. A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550–554, May 1994. 114 Generalized Bradley-Terry Models and Multi-Class Probability Estimates D. R. Hunter. MM algorithms for generalized Bradley-Terry models. The Annals of Statistics, 32:386–408, 2004. Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, November 1998. MNIST database available at http://yann.lecun.com/exdb/mnist/. H.-T. Lin, C.-J. Lin, and R. C. Weng. A note on Platt’s probabilistic outputs for support vector machines. Technical report, Department of Computer Science, National Taiwan University, 2003. URL http://www.csie.ntu.edu.tw/~cjlin/papers/plattprob.ps. P. McCullagh and J. A. Nelder. Generalized Linear Models. CRC Press, 2nd edition, 1990. D. Michie, D. J. Spiegelhalter, and C. C. Taylor. Machine Learning, Neural and Statistical Classification. Prentice Hall, Englewood Cliffs, N.J., 1994. Data available at http://www.ncc.up.pt/liacc/ML/statlog/datasets.html. R. N. Pendergrass and R. A. Bradley. Ranking in triple comparisons. In Ingram Olkin, editor, Contributions to Probability and Statistics. Stanford University Press, Stanford, CA, 1960. R. L. Placket. The analysis of permutations. Applied Statistics, 24:193–202, 1975. J. Platt. Probabilistic outputs for support vector machines and comparison to regularized likelihood methods. In A.J. Smola, P.L. Bartlett, B. Sch¨lkopf, and D. Schuurmans, o editors, Advances in Large Margin Classifiers, Cambridge, MA, 2000. MIT Press. URL citeseer.nj.nec.com/platt99probabilistic.html. P. V. Rao and L. L. Kupper. Ties in paired-comparison experiments: A generalization of the Bradley-Terry model. Journal of the American Statistical Association, 62:194–204, 1967. [Corrigendum J. Amer. Statist. Assoc. 63 1550-1551]. G. Simons and Y.-C. Yao. Asymptotics when the number of parameters tends to infinity in the Bradley-Terry model for paired comparisons. The Annals of Statistics, 27(3): 1041–1060, 1999. T.-F. Wu, C.-J. Lin, and R. C. Weng. Probability estimates for multi-class classification by pairwise coupling. Journal of Machine Learning Research, 5:975–1005, 2004. URL http://www.csie.ntu.edu.tw/~cjlin/papers/svmprob/svmprob.pdf. B. 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. E. Zermelo. Die berechnung der turnier-ergebnisse als ein maximumproblem der wahrscheinlichkeitsrechnung. Mathematische Zeitschrift, 29:436–460, 1929. T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56–134, 2004. 115