We propose the Probabilistic Sentential Decision Dia-gram (PSDD): A complete and canonical representation of probability distributions defined over the models of a given propositional theory. Each parameter of a PSDD can be viewed as the (conditional) probability of mak-ing a decision in a corresponding Sentential Decision Diagram (SDD). The SDD itself is a recently proposed complete and canonical representation of propositional theories. We explore a number of interesting properties of PSDDs, including the independencies that underlie them. We show that the PSDD is a tractable represen-tation. We further show how the parameters of a PSDD can be efficiently estimated, in closed form, from com-plete data. We empirically evaluate the quality of PS-DDs learned from data, when we have knowledge, a priori, of the domain logical constraints.

@inproceedings{KisaKR14,
  author = "Kisa, Doga and Van den Broeck, Guy and Choi, Arthur and Darwiche, Adnan",
  title = "Probabilistic sentential decision diagrams",
  booktitle = "Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR)",
  location="Vienna, Austria",
  month = Jul,
  year = "2014",
  url = "http://starai.cs.ucla.edu/papers/KisaKR14.pdf",
  keywords   = {conference,selective}
}