• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

From Ranking to Intransitive Preference Learning: Rock-Paper-Scissors and beyond

Tapio Pahikkala, Willem Waegeman, Evgeni Tsivtsivadze, Tapio Salakoski, Bernard De Baets, From Ranking to Intransitive Preference Learning: Rock-Paper-Scissors and beyond. In: Eyke Hüllermeier, Johannes Fürnkranz (Eds.), Proceedings of the ECML/PKDD-Workshop on Preference Learning (PL-09), 84-100, 2009.

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. The relations may resemble the well-known game of rock-paper-scissors. In the game, rock defeats scissors and scissors defeat paper, but rock loses to paper. Intransitive relations cannot be modelled 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 in game theory and biology that our algorithm outperforms methods not capable of learning intransitive reciprocal relations.

Files:

Full publication in PDF-format

BibTeX entry:

@INPROCEEDINGS{inpPaWaTsSaDe09a,
  title = {From Ranking to Intransitive Preference Learning: Rock-Paper-Scissors and beyond},
  booktitle = {Proceedings of the ECML/PKDD-Workshop on Preference Learning (PL-09)},
  author = {Pahikkala, Tapio and Waegeman, Willem and Tsivtsivadze, Evgeni and Salakoski, Tapio and De Baets, Bernard},
  editor = {Hüllermeier, Eyke and Fürnkranz, Johannes},
  pages = {84-100},
  year = {2009},
  keywords = {Preference learning, kernel methods, nontransitive preferences, ranking, machine learning},
}

Belongs to TUCS Research Unit(s): Turku BioNLP Group

Edit publication