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.

@inproceedings{ChoiIJCAI15,
  author = {Choi, Arthur and Van den Broeck, Guy and Darwiche, Adnan},
  title = {Tractable Learning for Structured Probability Spaces: A Case Study in Learning Preference Distributions},
  booktitle = {Proceedings of 24th International Joint Conference on Artificial Intelligence (IJCAI)},
  year      = {2015},
  url = {http://starai.cs.ucla.edu/papers/ChoiIJCAI15.pdf},
  keywords   = {conference,selective}
}