Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation

Yeganeh Alimohammadi, Kiana Asgari · 2025

Read Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation by Yeganeh Alimohammadi, Kiana Asgari (2025) 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-2507-08108.txt.

Introduction

Yeganeh Alimohammadi and Kiana Asgari let a ranking model learn its own yardstick. Their 2025 paper deals with the Mallows model, where rankings scatter around a central one with odds that fade by distance. Stock work fixes that distance in advance. Yet real fields differ: some sports see wild upsets, others few. Their variant learns the distance from data, within a family of power distances.

A fast sampling scheme draws near-true samples for any spread and power in that family. That sampler powers a joint estimator for the central ranking, the spread, and the best distance. Proofs back its consistency, and sports data back its fit.

Catalog record

CREATORYeganeh Alimohammadi, Kiana Asgari
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-08108

Browse the full library · About the Tower of Babel

Full text

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

Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation Yeganeh Alimohammadi, Kiana Asgari Abstract Mallows model is a widely-used probabilistic framework for learning from ranking data, with applications ranging from recommendation systems and voting to aligning language models with human preferences chen2024mallows ; kleinberg2021algorithmic ; rafailov2024direct . Under this model, observed rankings are noisy perturbations of a central ranking σ \sigma , with likelihood decaying exponentially in distance from σ \sigma , i.e, ℙ ( π ) ∝ exp ( − β ⋅ d ( π , σ ) ) , \mathbb{P}(\pi)\propto\exp\big(-\beta\cdot d(\pi,\sigma)\big), where β > 0 \beta>0 controls dispersion and d d is a distance function. Existing methods mainly focus on fixed distances (such as Kendall’s τ \tau distance), with no principled approach to learning the distance metric directly from data. In practice, however, rankings naturally vary by context; for instance, in some sports we regularly see long-range swaps (a low-rank team beating a high-rank one), while in others such events are rare. Motivated by this, we propose a generalization of Mallows model that learns the distance metric directly from data. Specifically, we focus on L α L_{\alpha} distances: d α ​ ( π , σ ) := ∑ i = 1 | π ⁡ ( i ) − σ ⁡ ( i ) | α d_{\alpha}(\pi,\sigma):=\sum_{i=1}|\pi(i)-\sigma(i)|^{\alpha} . For any α ≥ 1 \alpha\geq 1 and β > 0 \beta>0 , we develop a Fully Polynomial-Time Approximation Scheme (FPTAS) to efficiently generate samples that are ϵ \epsilon - close (in total variation distance) to the true distribution. Even in the special cases of L 1 L_{1} and L 2 L_{2} , this generalizes prior results that required vanishing dispersion ( β → 0 \beta\to 0 ). Using this sampling algorithm, we propose an efficient Maximum Likelihood Estimation (MLE) algorithm that jointly estimates the central ranking, the dispersion parameter, and the optimal distance metric. We prove strong consistency results for our estimators, and we validate our approach empirically using datasets from sports rankings. 1 Introduction Ranking tasks arise in many applications, from online recommendation systems, sports competitions, and voting, to more recently, the alignment of Large Language Models (LLMs) with human preferences chen2024mallows ; kleinberg2021algorithmic ; rafailov2024direct . A fundamental challenge is common to all these scenarios: given multiple observed rankings, how do we aggregate them into a single central ranking, learn how rankings vary around this center, and generate new rankings reflecting observed patterns? Probabilistic models offer natural tools to address these questions. Among them, the Mallows model mallows1957non stands out due to its conceptual simplicity and interpretability. Under this model, observed rankings are viewed as noisy perturbations of a central permutation 1 1 1 Throughout this paper, we use the terms ranking and permutation interchangeably. \sigma , with their likelihood decaying exponentially according to a chosen distance function d : \mathbb{P}(\pi)\;:=\;\frac{\exp\!\bigl(-\beta\,d(\pi,\sigma)\bigr)}{Z}, where \beta>0 controls the dispersion around \sigma , and Z is the normalizing constant (often referred to as the partition function). Due to its interpretability and desirable structural properties, Mallows model has found widespread adoption in recommendation systems, voting predictions, retail assortment optimization, and, more recently, post-training of large language models chen2024mallows ; desir2016assortment ; desir2021mallows ; lebanon2007non . Initially, Mallows mallows1957non proposed this model specifically with Kendall’s tau distance, and it was subsequently generalized by Diaconis diaconis1988group to any right-invariant distance metric. In this paper, we focus on the L_{\alpha} Mallows model , defined by the family of L_{\alpha} distances: d_{\alpha}(\pi,\sigma):=\sum_{i=1}^{n}|\pi(i)-\sigma(i)|^{\alpha}. Intuitively, the parameter \alpha controls the penalty for long-range swaps (e.g., changes from rank 1 to rank 100) versus local swaps, with larger values of \alpha penalizing long-range swaps more strongly. Our contributions focus on two complementary aspects: Parameter Estimation. We present an efficient Maximum Likelihood Estimation (MLE) algorithm that jointly estimates the central ranking \sigma , the dispersion parameter \beta , and the distance parameter \alpha . Unlike previous studies on the Mallows model –which assume a fixed distance metric– our estimator learns the distance metric jointly with other model parameters, marking the first such result in the literature. Further, we prove strong consistency of our estimators under general conditions \alpha>0,\beta>0 (see Theorem 2.4 ). Efficient Sampling. We develop a Fully Polynomial-Time Approximation Scheme (FPTAS) for sampling permutations within \epsilon -total variation distance of the true L_{\alpha} -Mallows distribution, valid for any \alpha\geq 1 and \beta>0 (Theorem 3.1 ). Our result generalizes previous sampling methods limited to special cases ( L_{1} , L_{2} ) that required vanishing dispersion ( \beta\to 0 ) zhong2021mallows ; mukherjee2016estimation . We validate our algorithms empirically using sports ranking datasets from American college football and basketball (Section 4 , codebase asgari2025code ). Our results reveal substantial differences between these two sports: basketball rankings yield a larger \alpha\approx 1.09 , reflecting a rapid decay in the probability of large inversions (e.g., low-ranked teams beating top-ranked teams). In contrast, football rankings yield a smaller \alpha\approx 0.44 , indicating a relatively higher likelihood of large inversions. Such domain-specific variations highlight the importance of learning distance metrics from data rather than fixing them a priori. Related Work Prior works on sampling and learning Mallows model assume a fixed distance function, with Kendall’s tau distance (counting inversions between permutations) kendall1938new being a particularly common choice due to its closed-form expression doignon2004repeated ; fligner1986distance ; irurozki2014sampling ; lu2014effective ; rubinstein2017sorting . However, it implicitly assumes equal probabilities for all inversions. For example, in a web search ranking, swapping the top two results has far more impact on user experience than swapping the 91st and 92nd, yet under Kendall’s tau distance the inversions appear with equal probabilities. This uniform penalty is misaligned with real-world tasks where the location of ranking errors matters—such as in recommendation systems, sports ranking, and preference learning tasks. Alternative metrics like Spearman’s footrule ( L_{1} ) and rank correlation ( L_{2} ) or more generally the L_{\alpha} model used in this paper, aim to mitigate the limitations of Kendall’s tau by assigning smaller penalties to long-range inversions. Exact sampling under these metrics is known to be NP-hard bartholdi1989voting , leading to the development of approximate methods such as Markov chain Monte Carlo (MCMC) algorithms zhong2021mallows ; vitelli2018probabilistic . While these methods represent significant progress, prior to this work, their computational efficiency was established only under the assumption of vanishing dispersion (\beta\to 0) . To address the limitations of Kendall’s tau in another direction, generalizations of the Mallows model have been proposed braverman2009sorting ; liu2018efficiently ; meilua2022recursive , introducing inversion penalties through graphical models or mixtures of multiple Mallows distributions. While these methods increase expressiveness, they often do so at the cost of substantial model complexity and reduced interpretability. In contrast, the L_{\alpha} -Mallows framework we study offers a principled and tunable way to learn the shape of the distribution through a single metric parameter. Although such extensions are beyond the scope of this work, the L_{\alpha} -Mallows model could similarly be adapted to mixture or hierarchical frameworks to further increase modeling flexibility. From the perspective of estimation, extensive research has examined consistency and convergence of Mallows model parameters vitelli2018probabilistic ; awasthi2014learning ; feng2022mallows ; mao2022learning ; busa2019optimal . In cases where the partition function is intractable (e.g., for L_{1} and

Read the complete text