Analysis of Rank Data

Confluence of Social Choice, Operations Research,
and Machine Learning

Workshop@NIPS-2014, Montreal
December 13, 2014

Overview  |  Schedule  |  Call for Papers  |  Important Dates  |  Invited Speakers  |  Award  |  Organization  |  Sponsors

Overview

The mathematical analysis and understanding of rank data has been a fascinating topic for centuries, and has been investigated in disciplines as wide-ranging as social choice/voting theory, decision theory, probability, statistics, and combinatorics. In modern times, huge amounts of data are generated in the form of rankings on a daily basis: restaurant ratings, product ratings/comparisons, employer ratings, hospital rankings, doctor rankings, and an endless variety of rankings from committee deliberations (including, for example, deliberations of conference program committees such as NIPS!). These applications have led to several new trends and challenges: for example, one must frequently deal with very large numbers of candidates/alternatives to be ranked, with partial or missing ranking information, with noisy ranking information, with the need to ensure reliability and/or privacy of the rank data provided, and so on.

Given the increasing universality of settings involving large amounts of rank data and associated challenges as above, powerful computational frameworks and tools for addressing such challenges have emerged over the last few years in a variety of areas, including in particular in machine learning, operations research, and computational social choice. Despite the fact that many important practical problems in each area could benefit from the algorithmic solutions and analysis techniques developed in other areas, there has been limited interaction between these areas. Given both the increasing maturity of the research into ranking in these respective areas and the increasing range of practical ranking problems in need of better solutions, it is the aim of this workshop to bring together recent advances in analyzing rank data in machine learning, operations research, and computational social choice under one umbrella, to enable greater interaction and cross-fertilization of ideas.

Schedule

Session 1
08:30 - 09:20 Invited talk:
Craig Boutilier
Addressing the Practical Challenges of Group Decision Support in a Data-rich World
09:20 - 09:40 Lirong Xia Generalized Outcome Scoring Rules   [pdf]
09:40 - 09:50 Yinan Zhang, Parikshit Sondhi,
Anjan Goswami, Chengxiang Zhai
A Bayesian Framework for Modeling Price Preference in Product Search   [pdf]
09:50 - 10:00 Marina Meila, Christopher Meek Inversion Models beyond Sufficient Statistics   [pdf]
10:00 - 10:30 Coffee break
Session 2
10:30 - 11:20 Invited talk:
Garrett J. Van Ryzin
Automatic Model Selection of Rank-based Models from Data   [Talk slides]
11:20 - 11:40 Weicong Ding, Prakash Ishwar,
Venkatesh Saligrama
A Topic Modeling Approach to Rank Aggregation   [pdf]
11:40 - 11:50 Justin Bedo, Cheng Soon Ong Multivariate Spearman's Rho for Rank Aggregation   [pdf]
11:50 - 12:00 Ekhine Irurozki, Josu Ceberio,
Borja Calvo, Jose A. Lozano
Mallows Model Under Ulam Distance:
A Feasible Combinatorial Approach   [pdf]
12:00 - 15:00 Lunch break
Session 3
15:00 - 15:50 Invited talk:
Eyke Hullermeier
Online Preference Learning with Bandit Algorithms   [Talk slides]
15:50 - 16:10 Eric Sibony Borda Count Approximation of Kemeny's Rule and Pairwise Voting Inconsistencies   [pdf]
16:10 - 16:20 Issei Matsumoto, Kohei Hatano,
Eiji Takimoto
Online Prediction with Bradley-Terry Models   [pdf]
16:20 - 16:30 Sougata Chaudhuri, Ambuj Tewari Generalization Bounds for Convex Surrogates in Learning to Rank   [pdf]
16:30 - 17:20 Coffee Break, Posters, and Discussions
Session 4
17:20 - 17:40 Arun Rajkumar Ranking from Pairwise Comparisons: Role of the Pairwise Preference Matrix
17:40 - 18:00 Guy Bresler Collaborative Filtering with Low Regret
18:00 - 18:20 Sewoong Oh Choice Modeling from Pairwise Comparisons
18:20 - 18:30 Concluding remarks


If you are interested in getting updates/other info about the workshop, join our google group

Call for Papers

We welcome submissions to the workshop in topics of interest which include but are not limited to

- discrete choice modeling and revenue management
- voting and social decision making, preference elicitation
- social choice (rank aggregation)
- Individual choice (recommendation systems)
- stochastic versus active sampling of preferences
- statistical/learning-theoretic guarantees
- effects of computational approximations

Late-breaking submissions should be 2-4 pages long excluding references and in NIPS 2014 format (submitted papers need not be anonymized). They should be sent by email to nips14-ranking@csa.iisc.ernet.in. Accepted submissions will be presented as posters (and possibly as short spotlight talks).

Important Dates

Paper submission October 9, 2014 (deadline has passed)
Acceptance notification: October 24, 2014 (updated)
Late breaking paper submission: November 7, 2014
Late breaking paper acceptance notification: November 17, 2014
Workshop: 8:30am to 6:30pm, Saturday, December 13, 2014

Invited Speakers

Eyke Hullermeier (Marburg university)
Online Preference Learning with Bandit Algorithms

Abstract:
In machine learning, the notion of multi armed bandit (MAB) refers to a class of online learning problems, in which an agent is supposed to simultaneously explore and exploit a given set of choice alternatives in the course of a sequential decision process. In the standard setting, the agent learns from stochastic feedback in the form of real­valued rewards. In many applications, however, numerical reward signals are not readily available; instead, only weaker information is provided, such as relative preferences in the form of qualitative comparisons between pairs of alternatives. This observation has motivated the study of variants of the multi armed bandit problem, in which more general representations are used both for the type of feedback to learn from and the target of prediction. This talk will start with a short survey of the state of the art in this field, that we refer to as preference based multi armed bandits (PB MAB). The main part of the talk will then be devoted to novel approaches for online learning with PB MABs, which are based on statistical models for rank data.

Biography of the speaker:
Eyke Hullermeier is a full professor in the Department of Computer Science at the University of Paderborn, Germany, where he heads the Intelligent Systems group. He studied mathematics and business computing, received his PhD in computer science from the University of Paderborn in 1997, and a Habilitation degree in 2002. Prior to returning to Paderborn in 2014, he spent two years as a post-doctoral researcher at the IRIT in Toulouse (France) and held professorships at the Universities of Dortmund, Magdeburg and Marburg. His research interests are centered around methods and theoretical foundations of intelligent systems, with a specific focus on machine learning and reasoning under uncertainty. He has published more than 200 articles on these topics in top-tier journals and major international conferences, and several of his contributions have been recognized with scientific awards. Professor Hullermeier is Co-Editor-in-Chief of Fuzzy Sets and Systems, one of the leading journals in the field of Computational Intelligence, and serves on the editorial board of several other journals, including Machine Learning, the International Journal of Approximate Reasoning, and the IEEE Transactions on Fuzzy Systems. He is a coordinator of the EUSFLAT working group on Machine Learning and Data Mining and head of the IEEE CIS Task Force on Machine Learning. In recent years, he was involved in the organization of several international conference. This year, he was PC Co-Chair of ECML/PDKK, the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (Nancy, France).

Garrett Van Ryzin (Columbia University)
Automatic Model Selection of Rank-based Models from Data

Abstract:
Rank-based choice models are appealing because they are non-parametric and provide great generality in modeling preferences. However, this generality comes at the cost of model complexity; with O(n!) possible rankings of n alternatives, the dimension of rank-based choice models quickly becomes unwieldy for even modest numbers of alternatives, making full-dimension rank-based models impractical in many important applications such as revenue management and assortment optimization. Ideally, one would like methods to automatically construct low-complexity rank-based choice models from data that both fit historical data well and provide good predictive performance. In this talk, we discuss a novel estimation method that requires as input only a realistic dataset consisting of a series of offer sets and observed choice outcomes. The method starts with an initial parsimonious set of rankings and enlarges this set by progressively and automatically generating new rankings that provably improve the likelihood function. The approach is based on column generation ideas from mathematical programming and requires solving a mixed integer program (MIP) at each stage to identify new rankings to add. Our numerical experiments confirm the potential of our estimation method to rapidly identify good yet parsimonious rank-based models from realistic choice data. [This work is joint with Gustavo Vulcano, NYU]

Biography of the speaker:
Garrett van Ryzin is the Paul M. Montrone Professor of Decision, Risk and Operations at the Columbia University Graduate School of Business and Chair of the Decision, Risk and Operations Division of the School. His research interest includes analytical pricing, stochastic modeling and operations management. He is coauthor of the book The Theory and Practice of Revenue Management, which won the 2005 Lanchester prize for best published work in operations research. He is an INFORMS and MSOM Fellow. Garrett received the B.S.E.E. degree from Columbia University, and the degrees of S.M. in Electrical Engineering and Computer Science and Ph.D. in Operations Research from MIT.

Craig Boutilier (University of Toronto)
Addressing the Practical Challenges of Group Decision Support in a Data-rich World

Abstract:

In a variety of social, business, political and economic contexts, decision making often involves groups of people or multiple stakeholders. Automated decision support for groups is considerably more difficult than for a single stakeholder since it requires aggregating the preferences of members of the group to determine optimal decisions. This brings with it the need to assess far more preference information, and often demands sophisticated mechanisms and optimization techniques to limit opportunities for manipulation. These problems are widely studied with the field of computational social choice. In this talk, I'll outline some of the models and methods my group has been developing to address the informational and computational challenges needed to make decision support for groups more practical and widely applicable. This includes: robust optimization methods for handling partial preference infomation; interactive elicitation techniques to minimize the amount of preference information needed to compute optimal decisions; optimization methods for combinatorial group decisions; preference learning from choice data; and optimization and elicitation techniques that exploit probabilistic preference models derived from data. I'll conclude with a discussion of some emerging opportunities, and associated challenges, in group decision support.

Biography of the speaker:
Craig Boutilier is a Professor, and Canada Research Chair in Adaptive Decision Making for Intelligent Systems, in the Department of Computer Science at the University of Toronto, His is also co-founder of Granata Decision Systems. He received his Ph.D. in Computer Science from the University of Toronto in 1992, and worked as an Assistant and Associate Professor at the University of British Columbia from 1991 until his return to Toronto in 1999. His current research efforts focus on various aspects of decision making under uncertainty: preference elicitation, mechanism design, game theory and multiagent decision processes, economic models, social choice, computational marketing and advertising, Markov decision processes, reinforcement learning and probabilistic inference. Boutilier is currently Editor-in-Chief of the Journal of Artificial Intelligence Research (JAIR) and was Program Chair of the 16th Conference on Uncertainty in Artificial Intelligence (UAI-2000) and the 21st International Joint Conference on Artificial Intelligence (IJCAI-09). He is a Fellow of the Royal Society of Canada (RSC), Association for Computing Machinery (ACM) and the Association for the Advancement of Artificial Intelligence (AAAI).

Award

The Best student paper award is awarded to Weicong Ding for the paper 'A Topic Modeling Approach to Rank Aggregation' by Weicong Ding, Prakash Ishwar and Venkatesh Saligrama.

Organization

Shivani Agarwal (Indian Institute of Science)
Hossein Azari (Harvard)
Guy Bresler (MIT)
Sewoong Oh (UIUC)
David Parkes (Harvard)
Arun Rajkumar (Indian Institute of Science)
Devavrat Shah (MIT)

Sponsors