Tractable Learning for structured probability spaces: A case study in learning preference distributions
Arthur Choi, Guy Van den Broeck, Adnan Y. Darwiche · Lirias · 2015
Probabilistic sentential decision diagrams (PSDDs) are a tractable representation of structured proba- bility spaces, which are characterized by complex logical constraints on what constitutes a possible world. We develop general-purpose techniques for probabilistic reasoning and learning with PSDDs, allowing one to compute the probabilities of arbi- trary logical formulas and to learn PSDDs from in- complete data. We illustrate the effectiveness of these techniques in the context of learning pref- erence distributions, to which considerable work has been devoted in the past. We show, analyti- cally and empirically, that our proposed framework is general enough to support diverse and complex data and query types. In particular, we show that it can learn maximum-likelihood models from partial rankings, pairwise preferences, and arbitrary pref- erence constraints. Moreover, we show that it can efficiently answer many queries exactly, from ex- pected and most likely rankings, to the probability of pairwise preferences, and diversified recommen- dations. This case study illustrates the effectiveness and flexibility of the developed PSDD framework as a domain-independent tool for learning and rea- soning with structured probability spaces.