We propose the Probabilistic Sentential Decision Diagram (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 making 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 representation. We further show how the parameters of a PSDD can be efficiently estimated, in closed form, from complete data. We empirically evaluate the quality of PSDDs learned from data, when we have knowledge, a priori, of the domain logical constraints.

@inproceedings{KisaLTPM14,
  author = "Kisa, Doga and Van den Broeck, Guy and Choi, Arthur and Darwiche, Adnan",
  title = "Probabilistic sentential decision diagrams: {L}earning with massive logical constraints",
  booktitle = "ICML Workshop on Learning Tractable Probabilistic Models (LTPM)",
  location="Beijing, China",
  month = Jun,
  year = "2014",
  url = "http://starai.cs.ucla.edu/papers/KisaLTPM14.pdf",
  keywords   = {workshop}
}