Learning intransitive reciprocal relations with kernel methods |
| |
Authors: | Tapio Pahikkala Willem Waegeman Evgeni Tsivtsivadze Tapio Salakoski Bernard De Baets |
| |
Institution: | 1. Turku Centre for Computer Science (TUCS), University of Turku, Department of Information Technology, Joukahaisenkatu 3-5 B, FIN-20520 Turku, Finland;2. KERMIT, Department of Applied Mathematics, Biometrics and Process Control, Ghent University, Coupure Links 653, B-9000 Ghent, Belgium;3. Institute for Computing and Information Sciences, Radboud University, Heyendaalseweg 135, 6525 AJ Nijmegen, The Netherlands |
| |
Abstract: | In different fields like decision making, psychology, game theory and biology, it has been observed that paired-comparison data like preference relations defined by humans and animals can be intransitive. Intransitive relations cannot be modeled with existing machine learning methods like ranking models, because these models exhibit strong transitivity properties. More specifically, in a stochastic context, where often the reciprocity property characterizes probabilistic relations such as choice probabilities, it has been formally shown that ranking models always satisfy the well-known strong stochastic transitivity property. Given this limitation of ranking models, we present a new kernel function that together with the regularized least-squares algorithm is capable of inferring intransitive reciprocal relations in problems where transitivity violations cannot be considered as noise. In this approach it is the kernel function that defines the transition from learning transitive to learning intransitive relations, and the Kronecker-product is introduced for representing the latter type of relations. In addition, we empirically demonstrate on two benchmark problems, one in game theory and one in theoretical biology, that our algorithm outperforms methods not capable of learning intransitive reciprocal relations. |
| |
Keywords: | Transitivity Reciprocal relations Utility functions Kernel methods Preference learning Decision theory Game theory |
本文献已被 ScienceDirect 等数据库收录! |
|