Sequential Rank and Preference Learning with the Bayesian Mallows Model

Øystein Sørensen, Anja Stein, Waldir Leoncio Netto, David S. Leslie · 2024

Read Sequential Rank and Preference Learning with the Bayesian Mallows Model by Øystein Sørensen, Anja Stein, Waldir Leoncio Netto, David S. Leslie (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-13644.txt.

Introduction

Sørensen, Stein, Leoncio Netto, and Leslie present a fast way to keep learning from rankings as new results arrive. Rankings and pairwise choices pour in over time in sports, shopping, and surveys, yet most fitting methods restart from scratch. Their 2024 algorithm updates belief about the true order step by step for the Bayesian Mallows model, a flexible model of rankings.

The method needs little hand tuning, splits well across processors, and yields a key model score as a byproduct. Tests on simulated data check its accuracy. A real case tracks Formula 1 drivers across three seasons of races, updating after each event. The authors offer the tool for live preference learning tasks.

Catalog record

CREATORØystein Sørensen, Anja Stein, Waldir Leoncio Netto, David S. Leslie
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-13644

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sequential Rank and Preference Learning with the Bayesian Mallows Model Øystein Sørensen, Anja Stein, Waldir Leoncio Netto, David S. Leslie Abstract The Bayesian Mallows model is a flexible tool for analyzing data in the form of complete or partial rankings, and transitive or intransitive pairwise preferences. In many potential applications of preference learning, data arrive sequentially and it is of practical interest to update posterior beliefs and predictions efficiently, based on the currently available data. Despite this, most algorithms proposed so far have focused on batch inference. In this paper we present an algorithm for sequentially estimating the posterior distributions of the Bayesian Mallows model using nested sequential Monte Carlo. The algorithm requires minimal user input in the form of tuning parameters, is straightforward to parallelize, and returns the marginal likelihood as a direct byproduct of estimation. We evaluate its performance in simulation experiments, and illustrate a real use case with sequential ranking of Formula 1 drivers throughout three seasons of races. 1 Introduction Data in the form of rankings and preferences arise naturally across a variety of domains. Examples include content recommendation based on click data ( Liu et al., 2019b ) , algorithm comparison ( Rojas-Delgado et al., 2022 ) , consumer preferences ( Courcoux and Semenou, 1997 ; Kamishima, 2003 ; Krivulin et al., 2022 ; Manuel et al., 2015 ) , grant panel reviews ( Pearce and Erosheva, 2022 ) , genome-wide transcriptomic analyses ( Eliseussen et al., 2022 ; Vitelli et al., 2023 ) , analysis of mutual funds’ preferences for governance structures ( Yi, 2021 ) , social hierarchies ( Nicholls et al., 2022 ) , and reinforcement learning from human feedback ( Hwang et al., 2023 ) . An early model for analyzing rankings ( Thurstone, 1927 ) assumed a judge ranks m items by assigning a score to each item, and then ordering them according to the score. Further developments of this approach include the Plackett-Luce model ( Luce, 1959 ; Plackett, 1975 ) , the Babington Smith model ( Babington Smith, 1950 ) , and the Bradley-Terry model ( Bradley and Terry, 1952 ) , all of which are based on assigning real-valued utilities to each item, yielding a large number of parameters to be estimated. Now consider a collection of items \mathcal{A}=\{A_{1},A_{2},\dots,A_{m}\} , and let \bm{\rho} be a permutation of the integers [m]:=\{1,2,\dots,m\} denoting the items’ modal ranking in the population of interest, such that \rho_{i} denotes the modal ranking of item A_{i} . For a particular individual, let A_{i}\succ A_{j} imply that the individual prefers A_{i} to A_{j} , and let \bm{r} be the permutation of [m] encoding the individual’s rankings. Mallows, 1957 showed that if the probability that an individual ranks a pair of items in agreement with their relative position in \bm{\rho} is given by P\left(A_{i}\succ A_{j}|\rho_{i}<\rho_{j}\right)=0.5+0.5~\text{tanh}\left\{(\rho_{j}-\rho_{i})\log\theta+\log\phi\right\} we obtain an exponential model P(\bm{r}|\bm{\rho})\propto\exp\{-\alpha d(\bm{\rho},\bm{r})\} for the observed ranking \bm{r} . When \phi=1 , d(\cdot,\cdot) is Spearman’s rank correlation ( Spearman, 1904 ) and when \theta=1 , d(\cdot,\cdot) is the Kendall distance ( Kendall, 1938 ) . The precision parameter \alpha quantifies how far observed rankings typically are from the modal ranking. Advantages of the Mallows model over utility-based models include a lower number of parameters ( \alpha and \bm{\rho} ) and the fact that its support is defined on the space of rankings. The model has later been extended to incorporate additional distance functions ( Diaconis, 1988 ) and to item-dependent precision parameters ( Fligner and Verducci, 1986 ) . We refer to the reviews by Liu et al., 2019a and Yu et al., 2019 and the monograph by Marden, 1995 for further details. Vitelli et al., 2017 proposed a Bayesian Mallows model and a Markov chain Monte Carlo (MCMC) algorithm for its estimation. Compared to other approaches focusing on the Kendall or Cayley distances ( Irurozki et al., 2018 ; Lu and Boutilier, 2014 ; Meila and Bao, 2010 ) , Vitelli et al., 2017 ’s algorithm works naturally with any of the distance functions proposed by Diaconis, 1988 for the Mallows model, and it incorporates data in the form of partial rankings or pairwise preferences. Its fully Bayesian approach allows predicting users’ preferences of items they have not yet seen, allowing the model to be used as a probabilistic recommender system ( Liu et al., 2019b ) . The MCMC algorithm of Vitelli et al., 2017 has some drawbacks, however. The user has to set tuning parameters for the proposal distributions for precision parameters, modal rankings, and latent rankings. It hence may require several pilot runs for obtaining sufficient acceptance probabilities. Second, in settings where data arrive sequentially, updating the posteriors requires running the full algorithm from scratch. The goal of this paper is to alleviate these issues. To this end, we propose a nested sequential Monte Carlo (SMC 2 ) algorithm ( Chopin et al., 2013 ; Fulop and Li, 2013 ) , which requires minimum user input and efficiently updates posterior distributions when new data arrive. The algorithm is straightforward to parallelize and is an extension of the work by Stein, 2023 , who proposed a sequential Monte Carlo (SMC) algorithm using a resample-move scheme ( Berzuini and Gilks, 2001 ; Chopin, 2002 ; Gilks and Berzuini, 2001 ) . A motivating example is shown in Figure 1 , showing race results from the Formula 1 seasons 2022-2024. 1 1 1 Data were downloaded from https://github.com/toUpperCase78/formula1-datasets . We included the 16 drivers who completed 50 or more of the total 68 races, and computed rankings from the results of each race. If we assume that the underlying skills of the drivers – as well as the performance of the cars and teams – are relatively stable across the three seasons, the results of each race can be viewed as a noisy assessment of the underlying true ranking. Using the SMC 2 algorithm proposed in this paper we can easily update the posterior distribution for the ranking of the drivers after each race. We will revisit these data in Section 6 . Figure 1: Rankings of drivers based on race results in Formula 1 seasons 2022, 2023, and 2024. Vertical dashed lines indicate the start of a season. Traces for the three drivers with best mean ranking across all races are shown in color. The paper proceeds as follows. In Section 2 we provide necessary background on the Bayesian Mallows model. In Section 3 we propose an SMC 2 algorithm for the Bayesian Mallows model with partial rankings or pairwise preference data. In Section 4 we investigate the computational requirements for computing topological orderings – an essential part of the algorithms. In Section 5 we report the results of simulation experiments and in Section 6 we revisit the Formula 1 data. We conclude and discuss further developments in Section 7 . An R ( R Core Team, 2024 ) package providing an API to our C++ implementation is available from GitHub 2 2 2 https://github.com/osorensen/BayesMallowsSMC2 and R code for reproducing all the results in the paper is available from our OSF repository. 3 3 3 https://osf.io/pquk4/ 2 Background and Model Setup We now introduce the Bayesian Mallows model as it was defined in Vitelli

Read the complete text