Sum-product networks: A survey <s> A. SPNs vs. probabilistic graphical models (PGMs) <s> Compiling Bayesian networks has proven an effective approach for inference that can utilize both global and local network structure. In this paper, we define a new method of compiling based on variable elimination (VE) and Algebraic Decision Diagrams (ADDs). The approach is important for the following reasons. First, it exploits local structure much more effectively than previous techniques based on VE. Second, the approach allows any of the many VE variants to compute answers to multiple queries simultaneously. Third, the approach makes a large body of research into more structured representations of factors relevant in many more circumstances than it has been previously. Finally, experimental results demonstrate that VE can exploit local structure as effectively as state-of-the-art algorithms based on conditioning on the networks considered, and can sometimes lead to much faster compilation times. <s> BIB001 </s> Sum-product networks: A survey <s> A. SPNs vs. probabilistic graphical models (PGMs) <s> Most tasks require a person or an automated system to reason -- to reach conclusions based on available information. The framework of probabilistic graphical models, presented in this book, provides a general approach for this task. The approach is model-based, allowing interpretable models to be constructed and then manipulated by reasoning algorithms. These models can also be learned automatically from data, allowing the approach to be used in cases where manually constructing a model is difficult or even impossible. Because uncertainty is an inescapable aspect of most real-world applications, the book focuses on probabilistic models, which make the uncertainty explicit and provide models that are more faithful to reality. Probabilistic Graphical Models discusses a variety of models, spanning Bayesian networks, undirected Markov networks, discrete and continuous models, and extensions to deal with dynamical systems and relational data. For each class of models, the text describes the three fundamental cornerstones: representation, inference, and learning, presenting both basic concepts and advanced techniques. Finally, the book considers the use of the proposed framework for causal reasoning and decision making under uncertainty. The main text in each chapter provides the detailed technical development of the key ideas. Most chapters also include boxes with additional material: skill boxes, which describe techniques; case study boxes, which discuss empirical cases related to the approach described in the text, including applications in computer vision, robotics, natural language understanding, and computational biology; and concept boxes, which present significant concepts drawn from the material in the chapter. Instructors (and readers) can group chapters in various combinations, from core topics to more technically advanced material, to suit their particular needs. <s> BIB002 </s> Sum-product networks: A survey <s> A. SPNs vs. probabilistic graphical models (PGMs) <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> BIB003 </s> Sum-product networks: A survey <s> A. SPNs vs. probabilistic graphical models (PGMs) <s> Bayesian networks provide a language for qualitatively representing the conditional independence properties of a distribution, This allows a natural and compact representation of the distribution, eases knowledge acquisition, and supports effective inference algorithms. It is well-known, however, that there are certain independencies that we cannot capture qualitatively within the Bayesian network structure: independencies that hold only in certain contexts, i.e., given a specific assignment of values to certain variables, In this paper, we propose a formal notion of context-specific independence (CSI), based on regularities in the conditional probability tables (CPTs) at a node. We present a technique, analogous to (and based on) d-separation, for determining when such independence holds in a given network. We then focus on a particular qualitative representation scheme--tree-structured CPTs-- for capturing CSI. We suggest ways in which this representation can be used to support effective inference algorithms, in particular, we present a structural decomposition of the resulting network which can improve the performance of clustering algorithms, and an alternative algorithm based on outset conditioning. <s> BIB004 </s> Sum-product networks: A survey <s> A. SPNs vs. probabilistic graphical models (PGMs) <s> In this paper, we establish some theoretical connections between Sum-Product Networks (SPNs) and Bayesian Networks (BNs). We prove that every SPN can be converted into a BN in linear time and space in terms of the network size. The key insight is to use Algebraic Decision Diagrams (ADDs) to compactly represent the local conditional probability distributions at each node in the resulting BN by exploiting context-specific independence (CSI). The generated BN has a simple directed bipartite graphical structure. We show that by applying the Variable Elimination algorithm (VE) to the generated BN with ADD representations, we can recover the original SPN where the SPN can be viewed as a history record or caching of the VE inference process. To help state the proof clearly, we introduce the notion of {\em normal} SPN and present a theoretical analysis of the consistency and decomposability properties. We conclude the paper with some discussion of the implications of the proof and establish a connection between the depth of an SPN and a lower bound of the tree-width of its corresponding BN. <s> BIB005
SPNs are similar to PGMs, such as Bayesian networks (BNs) and Markov networks (also called Markov random fields)  , BIB002 , in their ability to compactly represent probability distributions. The main difference is that in a PGM every node represents a variable androughly speaking-links represent probabilistic dependencies, sometimes due to causal influences, while in an SPN every node represents a probability function. PGMs and other factored probability distributions can be compiled into arithmetic circuits or SPNs BIB001 . In general a PGM is more compact than an equivalent SPN, as shown in Figure 1 . Inference in BNs and Markov networks is an NP-problem and existing exact algorithms have worst-case exponential complexity BIB002 , while SPNs can do inference in time proportional to the number of links in the graph. In principle this would not be an advantage for SPNs, because the conversion of a BN or a Markov network into an SPN may create an exponential number of links. However, context-specific independencies in BNs BIB004 can reduce the size of the corresponding SPN, as shown in Figure 2 . In fact, any problem solvable in polynomial time with tabular BNs (i.e., those whose conditional probabilities are given by tables) can be solved in polynomial time with arithmetic circuits or SPNs  , but the converse is not true-see the example in BIB003 . BIB003 More importantly, while PGMs learned from data are usually intractable-except for small problems or for specific types of models with limited expressiveness, such as the naïve Bayes-the algorithms presented in Section VI can build tractable SPNs that yield excellent approximations both for generative and discriminative tasks. BIB003 However, every SPN of finite-state variables can be converted into a BN whose conditional probabilities are encoded as algebraic decision diagrams (ADDs), in time and space proportional to the network size, and it is possible to recover the original SPN with the variable elimination algorithm BIB005 . In contrast, BNs can be built using causal knowledge elicited from human experts and there is a large body of recent research on building causal BNs from experimental and/or observational data, under certain conditions [14] . It is also possible to combine causal knowledge and data, and even to build BNs interactively  . All these options are currently impossible with SPNs. Additionally, the independencies in a BN or in a Markov model are easier to read than those in an SPN. On the other hand, the graph of an SPN can sometimes be built from human knowledge to represent part/subpart and class/subclass hierarchiessee BIB003 Sec. 5] for an example. In conclusion, each type of model has advantages and disadvantages, and the choice for a real-world application must take into account the size of the problem, the amount of knowledge and data available, and the explanations required by the user.