Probabilistic Inference Over Repeated Insertion Models
Probabilistic Inference Over Repeated Insertion Models
复制标题
重复插入模型的概率推理
DOI：
10.1609/aaai.v32i1.11541
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Julia Stoyanovich
中科院分区：
文献类型：
--
作者：
Batya Kenig;Lovro Ilijasic;Haoyue Ping;B. Kimelfeld;Julia Stoyanovich
排名上的分布用于在各种环境中对用户偏好进行建模，包括政治选举和电子商务。重复的插入模型（RIM）产生了对排名的各种已知概率分布，特别是流行的木棍模型。但是，对轮辋的概率推论在计算上具有挑战性，在一般情况下证明是棘手的。在本文中，我们提出了一种用于计算在RIM上设置的任意部分排序的边际概率的算法。我们根据模型的性质和部分顺序分析了算法的复杂性，该算法由一种称为“覆盖宽度”的新颖措施捕获。我们还对串行和并行实现的算法进行了实验研究。在推断与等级分布与线性扩展之间的关系的基础上，我们研究了推断问题，仅限于部分订单，以有效地计算其线性扩展。
Distributions over rankings are used to model user preferences in various settings including political elections and electronic commerce. The Repeated Insertion Model (RIM) gives rise to various known probability distributions over rankings, in particular to the popular Mallows model. However, probabilistic inference on RIM is computationally challenging, and provably intractable in the general case. In this paper we propose an algorithm for computing the marginal probability of an arbitrary partially ordered set over RIM. We analyze the complexity of the algorithm in terms of properties of the model and the partial order, captured by a novel measure termed the "cover width." We also conduct an experimental study of the algorithm over serial and parallelized implementations. Building upon the relationship between inference with rank distributions and counting linear extensions, we investigate the inference problem when restricted to partial orders that lend themselves to efficient counting of their linear extensions.