Abstract
Rankings and permutations have become, nowadays, ubiquitous. They appear in numerous areas of computer systems: information retrieval, recommender systems, identity tracking or chemical compound classification, etc. Dealing with rankings, and particularly with rankings of many objects is a complex computational task as the number of permutations of n objects scales factorially in n. Recently a number of approaches have come to the machine learning arena to address this kind of data. Most of these approaches are based on the building of a probability distribution over the space of rankings. However, given the complexity of storing, learning and making inference on this kind of models, different simplifying assumptions have been considered: the use of parametric models, models based on low-order statistics, models based on kernels and the definition and use of notions of independence and conditional independence in the space of permutations. In this tutorial we will review the literature on the topic, explaining the different approaches in detail that have emerged in the literature, putting them in relation with other non-probabilistic ranking models and giving a collection of open problems in the area. In addition we will present the most relevant applications in the field as well as the most common benchmark datasets and software.
professor of Robotics and Computer Science at the School of Computer Science, Carnegie Mellon University. My main research interest is data mining...
During my teaching at CMU I've accumulated quite a number of introductory and advanced teaching materials about Data Mining, Machine Learning and Algorithms for AI. Click here for a set of Data Mining tutorials. In addition, some of the course links below can take you to additional teaching and learning materials.
This list is intended to introduce some of the tools of Bayesian statistics and machine learning that can be useful to computational research in cognitive science.
A. Badanidiyuru, J. Langford, и A. Slivkins. (2014)cite arxiv:1402.6779Comment: This is the full version of a paper in COLT 2014. Version history: (V2) Added some details to one of the proofs, (v3) a big revision following comments from COLT reviewers (but no new results).