Probabilistic Sentential Decision Diagrams

ABSTRACT. In this paper, we propose the Probabilistic Sentential Decision Diagram (PSDD), which is a canonical representation for probability distributions that are defined over the models of a propositional theory. Each parameter of a given PSDD can be viewed as the (conditional) probability of making a decision in a corresponding Sentential Decision Diagram (SDD), which itself is a recently proposed canonical representation of propositional theories. We explore a number of interesting properties of PSDDs, including the context-specific independencies that underlie them. We further show how the parameters of a PSDD can be efficiently estimated, in closed form, from complete data. We finally empirically evaluate the quality of PSDDs learned from data, when we have knowledge, a priori, of the logical theory supporting an otherwise unknown probability distribution.