标题： 马洛斯模型与学习距离度量：采样和最大似然估计 显示英文标题

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

摘要： \textit{马洛斯模型}是一种广泛使用的从排序数据中学习的概率框架，其应用范围从推荐系统和投票到对齐语言模型与人类偏好~\cite{chen2024mallows, kleinberg2021algorithmic, rafailov2024direct}。 在该模型中，观察到的排序是对中心排序$\sigma$的噪声扰动，似然函数随着距离$\sigma$的增加呈指数衰减，即$P (\pi) \propto \exp\big(-\beta \cdot d(\pi, \sigma)\big),$，其中$\beta > 0$控制离散度，$d$是一个距离函数。 现有方法主要关注固定距离（如Kendall的$\tau$距离），没有从数据中直接学习距离度量的原则性方法。 在实践中，排名自然会因上下文而异；例如，在一些运动中我们经常看到远距离交换（低排名队伍击败高排名队伍），而在其他运动中此类事件很少见。 受此启发，我们提出了一种Mallows模型的推广，该模型直接从数据中学习距离度量。 具体来说，我们专注于$L_\alpha$距离： $d_\alpha(\pi,\sigma):=\sum_{i=1} |\pi(i)-\sigma(i)|^\alpha$。 对于任何$\alpha\geq 1$和$\beta>0$，我们开发了一个完全多项式时间近似方案（FPTAS），以高效生成与真实分布在总变分距离上$\epsilon$接近的样本。 即使在$L_1$和$L_2$的特殊情况，这也推广了之前需要消失分散性（$\beta\to0$）的结果。 使用这种采样算法，我们提出了一种高效的最大似然估计（MLE）算法，该算法联合估计中心排序、分散参数和最优距离度量。 我们证明了我们的估计量的强一致性结果（对于$\alpha$和$\beta$的任何值），并且我们使用体育排名数据集对我们的方法进行了实证验证。 显示英文摘要

摘要： \textit{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~\cite{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, $P (\pi) \propto \exp\big(-\beta \cdot d(\pi, \sigma)\big),$ where $\beta > 0$ controls dispersion and $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_\alpha$ distances: $d_\alpha(\pi,\sigma):=\sum_{i=1} |\pi(i)-\sigma(i)|^\alpha$. For any $\alpha\geq 1$ and $\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$ and $L_2$, this generalizes prior results that required vanishing dispersion ($\beta\to0$). 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 (for any values of $\alpha$ and $\beta$), and we validate our approach empirically using datasets from sports rankings.