TY - GEN
T1 - Probabilistic inference over repeated insertion models
AU - Kenig, Batya
AU - Ilijasić, Lovro
AU - Kimelfeld, Benny
AU - Ping, Haoyue
AU - Stoyanovich, Julia
N1 - Funding Information:
The authors thank Rina Dechter for insightful discussions and comments. This work was supported in part by the US National Science Foundation (NSF) Grants No. 1464327 and 1539856, by the US-Israel Binational Science Foundation (BSF) Grant No. 2014391, and by the Israel Science Foundation (ISF) Grant No. 1295/15. Benny Kimelfeld is a Taub Fellow, supported by the Taub Foundation.
Publisher Copyright:
Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85060489949&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85060489949&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85060489949
T3 - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
SP - 1897
EP - 1904
BT - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
PB - AAAI press
T2 - 32nd AAAI Conference on Artificial Intelligence, AAAI 2018
Y2 - 2 February 2018 through 7 February 2018
ER -