Effective sampling and learning for mallows models with pairwise-preference data
Effective sampling and learning for mallows models with pairwise-preference data
复制标题
DOI：
10.5555/2627435.2750366
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Tyler Lu;Craig Boutilier
中科院分区：
文献类型：
--
作者：
Tyler Lu;Craig Boutilier
在许多领域（例如，推荐系统，IR，社会选择），学习偏好分布是一个关键问题。但是，许多现有的学习和推理方法对可以作为证据的用户偏好形式施加了限制性假设。我们通过将替代方案的数据任意成对比较来放大这些限制，这代表了序数排名的基本构件。我们从成对比较数据中开发了学习锤模型（以及其混合物）的第一个算法。我们技术的核心是一种新的算法，即广义重复插入模型（GRIM），该模型允许从任意排名分布中进行采样，尤其是有条件的摩洛群模型。虽然我们表明，从一般而言，来自成对证据的绿木匠模型的采样在计算上很困难，但我们开发了近似的采样器，这些采样器对于许多重要的特殊情况|具有可证明的范围，并具有成对证据的可证明的界限 - 并得出用于评估对数类样的算法，学习算法，学习，学习，学习，学习，学习，学习，学习。绿色混合物和非参数估计。现实世界数据集的实验证明了我们方法的有效性。
Learning preference distributions is a critical problem in many areas (e.g., recommender systems, IR, social choice). However, many existing learning and inference methods impose restrictive assumptions on the form of user preferences that can be admitted as evidence. We relax these restrictions by considering as data arbitrary pairwise comparisons of alternatives, which represent the fundamental building blocks of ordinal rankings. We develop the first algorithms for learning Mallows models (and mixtures thereof) from pairwise comparison data. At the heart of our technique is a new algorithm, the generalized repeated insertion model (GRIM), which allows sampling from arbitrary ranking distributions, and conditional Mallows models in particular. While we show that sampling from a Mallows model with pairwise evidence is computationally difficult in general, we develop approximate samplers that are exact for many important special cases|and have provable bounds with pairwise evidence--and derive algorithms for evaluating log-likelihood, learning Mallows mixtures, and non-parametric estimation. Experiments on real-world data sets demonstrate the effectiveness of our approach.