# A Generalized Model for Multidimensional Intransitivity

• Jiuding Duan
• Jiyi Li
• Yukino Baba
• Hisashi Kashima
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 10235)

## Abstract

Intransitivity is a critical issue in pairwise preference modeling. It refers to the intransitive pairwise preferences between a group of players or objects that potentially form a cyclic preference chain, and has been long discussed in social choice theory in the context of the dominance relationship. However, such multifaceted intransitivity between players and the corresponding player representations in high dimension are difficult to capture. In this paper, we propose a probabilistic model that joint learns the d-dimensional representation ($$d > 1$$) for each player and a dataset-specific metric space that systematically captures the distance metric in $$\mathbb {R}^d$$ over the embedding space. Interestingly, by imposing additional constraints in the metric space, our proposed model degenerates to former models used in intransitive representation learning. Moreover, we present an extensive quantitative investigation of the wide existence of intransitive relationships between objects in various real-world benchmark datasets. To the best of our knowledge, this investigation is the first of this type. The predictive performance of our proposed method on various real-world datasets, including social choice, election, and online game datasets, shows that our proposed method outperforms several competing methods in terms of prediction accuracy.

## Keywords

Representation learning Preference Matchup Intransitivity

## References

1. 1.
Bottou, L.: Large-scale machine learning with stochastic gradient descent. In: Lechevallier, Y., Saporta, G. (eds.) Proceedings of COMPSTAT 2010, pp. 177–186. Springer, Heidelberg (2010)
2. 2.
Bradley, R.A., Terry, M.E.: Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39(3/4), 324–345 (1952)
3. 3.
Cao, Z., Qin, T., Liu, T.Y., Tsai, M.F., Li, H.: Learning to rank: from pairwise approach to listwise approach. In: Proceedings of the 24th International Conference on Machine Learning, pp. 129–136. ACM (2007)Google Scholar
4. 4.
Cattelan, M., Varin, C., Firth, D.: Dynamic Bradley-Terry modelling of sports tournaments. J. Roy. Stat. Soc.: Ser. C (Appl. Stat.) 62(1), 135–150 (2013)
5. 5.
Causeur, D., Husson, F.: A 2-dimensional extension of the Bradley-Terry model for paired comparisons. J. Stat. Plan. Infer. 135(2), 245–259 (2005)
6. 6.
Chen, S., Joachims, T.: Modeling intransitivity in matchup and comparison data. In: Proceedings of the 9th ACM International Conference on Web Search and Data Mining, pp. 227–236. ACM (2016)Google Scholar
7. 7.
Chen, S., Joachims, T.: Predicting matchups and preferences in context. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, NY, USA, pp. 775–784. ACM, New York (2016)Google Scholar
8. 8.
Chen, X., Bennett, P.N., Collins-Thompson, K., Horvitz, E.: Pairwise ranking aggregation in a crowdsourced setting. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, NY, USA, pp. 193–202. ACM, New York (2013)Google Scholar
9. 9.
Dangauthier, P., Herbrich, R., Minka, T., Graepel, T.: Trueskill through time: revisiting the history of chess. In: Advances in Neural Information Processing Systems, pp. 337–344 (2007)Google Scholar
10. 10.
Davidson, R.R.: On extending the Bradley-Terry model to accommodate ties in paired comparison experiments. J. Am. Stat. Assoc. 65(329), 317–328 (1970)
11. 11.
Elo, A.E.: The Rating of Chess Players, Past and Present. Arco Pub., New York (1978)Google Scholar
12. 12.
Globerson, A., Chechik, G., Pereira, F., Tishby, N.: Euclidean embedding of co-occurrence data. J. Mach. Learn. Res. 8, 2265–2295 (2007)
13. 13.
Herbrich, R., Minka, T., Graepel, T.: Trueskill: a Bayesian skill rating system. In: Advances in Neural Information Processing Systems, pp. 569–576 (2006)Google Scholar
14. 14.
Herlocker, J.L., Konstan, J.A., Borchers, A., Riedl, J.: An algorithmic framework for performing collaborative filtering. In: Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 230–237. ACM (1999)Google Scholar
15. 15.
Huang, T.K., Lin, C.J., Weng, R.C.: Ranking individuals by group comparisons. J. Mach. Learn. Res. 9, 2187–2216 (2008)
16. 16.
Hunter, D.R.: MM algorithms for generalized Bradley-Terry models. Ann. Stat. 32, 384–406 (2004)
17. 17.
Jamali, M., Ester, M.: A transitivity aware matrix factorization model for recommendation in social networks. In: International Joint Conference on Artificial Intelligence (IJCAI) (2011)Google Scholar
18. 18.
Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77–84 (1975)
19. 19.
Kamishima, T.: Nantonac collaborative filtering: recommendation based on order responses. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 583–588. ACM (2003)Google Scholar
20. 20.
Keener, J.P.: The Perron-Frobenius theorem and the ranking of football teams. SIAM Rev. 35(1), 80–93 (1993)
21. 21.
May, K.O.: Intransitivity, utility, and the aggregation of preference patterns. Econometrica: J. Econ. Soc. 22, 1–13 (1954)
22. 22.
Menke, J.E., Martinez, T.R.: A Bradley-Terry artificial neural network model for individual ratings in group competitions. Neural Comput. Appl. 17(2), 175–186 (2008)
23. 23.
Ou, M., Cui, P., Pei, J., Zhang, Z., Zhu, W.: Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016, NY, USA, pp. 1105–1114. ACM, New York (2016)Google Scholar
24. 24.
Regenwetter, M., Dana, J., Davis-Stober, C.P.: Transitivity of preferences. Psychol. Rev. 118(1), 42 (2011)
25. 25.
Thurstone, L.L.: A law of comparative judgement. Psychol. Rev. 34(4), 273–286 (1927)
26. 26.
Tideman, N.: Collective Decisions and Voting: The Potential for Public Choice. Ashgate Publishing Ltd., Farnham (2006)Google Scholar

© Springer International Publishing AG 2017

## Authors and Affiliations

• Jiuding Duan
• 1
• Jiyi Li
• 1
• Yukino Baba
• 1
• Hisashi Kashima
• 1
1. 1.Department of Intelligence Science and TechnologyKyoto UniversityKyotoJapan
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7102039456367493, "perplexity": 11453.390702878232}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-13/segments/1521257648207.96/warc/CC-MAIN-20180323102828-20180323122828-00120.warc.gz"}