Sum-product networks: A survey <s> Definition 15. <s> We have recently proposed a tractable logical form, known as deterministic, decomposable negation normal form (d-DNNF). We have shown that d-DNNF supports a number of logical operations in polynomial time, including clausal entailment, model counting, model enumeration, model minimization, and probabilistic equivalence testing. In this paper, we discuss another major application of this logical form: the implementation of multi-linear functions (of exponential size) using arithmetic circuits (that are not necessarily exponential). Specifically, we show that each multi–linear function can be encoded using a propositional theory, and that each d-DNNF of the theory corresponds to an arithmetic circuit that implements the encoded multi–linear function. We discuss the application of these results to factoring belief networks, which can be viewed as multi–linear functions as has been shown recently. We discuss the merits of the proposed approach for factoring belief networks, and present experimental results showing how it can handle efficiently belief networks that are intractable to structure–based methods for probabilistic inference. <s> BIB001 </s> Sum-product networks: A survey <s> Definition 15. <s> The key limiting factor in graphical model inference and learning is the complexity of the partition function. We thus ask the question: what are general conditions under which the partition function is tractable? The answer leads to a new kind of deep architecture, which we call sum-product networks (SPNs). SPNs are directed acyclic graphs with variables as leaves, sums and products as internal nodes, and weighted edges. We show that if an SPN is complete and consistent it represents the partition function and all marginals of some graphical model, and give semantics to its nodes. Essentially all tractable graphical models can be cast as SPNs, but SPNs are also strictly more general. We then propose learning algorithms for SPNs, based on backpropagation and EM. Experiments show that inference and learning with SPNs can be both faster and more accurate than with standard deep networks. For example, SPNs perform image completion better than state-of-the-art deep networks for this task. SPNs also have intriguing potential connections to the architecture of the cortex. <s> BIB002
Let n i be a sum node having m children and V ∈ sc(n i ) a variable with m states. Let σ be a one-to-one function σ : {1, . . . , m} → ch(i). If for every m ∈ {1, . . . , m} either I vj is a child of n σ(j) (and hence a grandchild of n i ) or I vj = n σ(j) (i.e., the indicator itself is a child of n i ), we then say that n i represents variable V . Example 16. Node n 14 in Figure 1 represents variable C, with σ(1) = 17, σ(2) = 18, because I c1 = I +c = n 17 = n σ BIB002 , and I c2 = I ¬c = n 18 = n σ BIB001 . Nodes 15, 16, and 17 also represent C for the same reason. Node n 6 represents variable B with σ(1) = 8 and σ(2) = 9 because I b1 = I +b is a child of n σ(1) = n 8 and I b2 = I ¬b is a child of n σ(2) = n 9 . For analogous reasons node n 7 also represents B and n 1 represents A. In Appendix B we prove that when the root node of an SPN represents a variable V , this node can be interpreted as the weighted average of the conditional probabilities given V , with w i,σ(j) = P (v j ). Similarly, if every ancestor of a sum node n i represents a variable, then n i can be interpreted as the weighted average of the conditional probabilities given the context defined by the ancestors of n i . Proposition 17. If a sum node n i represents a model variable V , then n i is selective. This proposition is useful because it establishes a sufficient condition for concluding that an SPN is selective by just observing its graph, without analyzing its weights. For example, we can see that, according to Definition 15, 