Probabilistic inference over repeated insertion models

Batya Kenig, Lovro Ilijasić, Benny Kimelfeld, Haoyue Ping, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish (US)
    Title of host publication32nd AAAI Conference on Artificial Intelligence, AAAI 2018
    PublisherAAAI press
    Pages1897-1904
    Number of pages8
    ISBN (Electronic)9781577358008
    StatePublished - 2018
    Event32nd AAAI Conference on Artificial Intelligence, AAAI 2018 - New Orleans, United States
    Duration: Feb 2 2018Feb 7 2018

    Publication series

    Name32nd AAAI Conference on Artificial Intelligence, AAAI 2018

    Other

    Other32nd AAAI Conference on Artificial Intelligence, AAAI 2018
    CountryUnited States
    CityNew Orleans
    Period2/2/182/7/18

    ASJC Scopus subject areas

    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'Probabilistic inference over repeated insertion models'. Together they form a unique fingerprint.

    Cite this