让排序模型自动学距离度量，提升推荐与投票系统准确性
Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation
- 用可学习的Lα距离替代固定距离，更灵活捕捉排序差异
- 提出FPTAS采样算法，可在任意参数下高效生成近似真实分布样本
- 联合估计中心排序、分散度和最优距离，理论保证强一致性
Mallows模型是学习排名数据的常用概率框架，广泛应用于推荐系统、投票和对齐语言模型与人类偏好等领域。该模型假设观测到的排名是中心排名σ的噪声扰动，其概率随与σ的距离指数衰减：P(π) ∝ exp(−β·d(π, σ))，其中β > 0控制分散程度，d为距离函数。现有方法多采用固定距离（如Kendall's τ），缺乏从数据中直接学习距离度量的合理方法。实践中，不同场景下排名行为差异显著——例如某些体育赛事常见低排名队击败高排名队，而另一些则极少发生。为此，我们提出一种推广的Mallows模型，直接从数据中学习距离度量。具体地，考虑Lα距离：dα(π,σ):=∑_{i=1}^n |π(i)−σ(i)|^α，针对任意α≥1和β>0，我们设计了一个全多项式时间近似方案（FPTAS），能以ε精度（总变差距离）高效生成接近真实分布的样本。即使在L₁和L₂的特例下，该方法也超越了以往需β→0（分散度趋零）才能成立的结果。基于此采样算法，我们提出一种高效的极大似然估计（MLE）算法，联合估计中心排名、分散参数及最优距离度量。我们证明了所有参数估计量的强一致性（对任意α、β值均成立），并在体育排名数据集上进行了实证验证。
原文摘要 · Abstract (English)
\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 $σ$, with likelihood decaying exponentially in distance from $σ$, i.e, $P (π) \propto \exp\big(-β\cdot d(π, σ)\big),$ where $β> 0$ controls dispersion and $d$ is a distance function. Existing methods mainly focus on fixed distances (such as Kendall's $τ$ 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_α$ distances: $d_α(π,σ):=\sum_{i=1} |π(i)-σ(i)|^α$. For any $α\geq 1$ and $β>0$, we develop a Fully Polynomial-Time Approximation Scheme (FPTAS) to efficiently generate samples that are $ε$- 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 ($β\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 $α$ and $β$), and we validate our approach empirically using datasets from sports rankings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。