Sum-product networks: A survey <s> I. Introduction <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> I. Introduction <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> I. Introduction <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> I. Introduction <s> Copyright 2015 by the authors. Sum-product networks (SPNs) are a promising avenue for probabilistic modeling and have been successfully applied to various tasks. However, some theoretic properties about SPNs are not yet well understood. In this paper we fill some gaps in the theoretic foundation of SPNs. First, we show that the weights of any complete and consistent SPN can be transformed into locally normalized weights without changing the SPN distribu-tion. Second, we show that consistent SPNs cannot model distributions significantly (ex-ponentially) more compactly than decompos-able SPNs. As a third contribution, we ex-tend the inference mechanisms known for SPNs with finite states to generalized SPNs with arbitrary input distributions. <s> BIB004 </s> Sum-product networks: A survey <s> I. Introduction <s> One of the central themes in Sum-Product networks (SPNs) is the interpretation of sum nodes as marginalized latent variables (LVs). This interpretation yields an increased syntactic or semantic structure, allows the application of the EM algorithm and to efficiently perform MPE inference. In literature, the LV interpretation was justified by explicitly introducing the indicator variables corresponding to the LVs' states. However, as pointed out in this paper, this approach is in conflict with the completeness condition in SPNs and does not fully specify the probabilistic model. We propose a remedy for this problem by modifying the original approach for introducing the LVs, which we call SPN augmentation. We discuss conditional independencies in augmented SPNs, formally establish the probabilistic interpretation of the sum-weights and give an interpretation of augmented SPNs as Bayesian networks. Based on these results, we find a sound derivation of the EM algorithm for SPNs. Furthermore, the Viterbi-style algorithm for MPE proposed in literature was never proven to be correct. We show that this is indeed a correct algorithm, when applied to selective SPNs, and in particular when applied to augmented SPNs. Our theoretical results are confirmed in experiments on synthetic data and 103 real-world datasets. <s> BIB005
S UM-PRODUCT networks (SPNs) were proposed by Poon and Domingos BIB003 in 2011 as a modification of Darwiche's BIB001 ,  arithmetic circuits. Every SPN consists of a directed graph that represents a probability distribution resulting from a hierarchy of distributions combined in the form of mixtures (sum nodes) and factorizations (product nodes), as shown in Figure 1 . SPNs, like arithmetic circuits, can be built by transforming a probabilistic graphical model BIB002 , such as a Bayesian network or a Markov network, but they can also be learned from data. The main advantage of SPNs is that several inference tasks can be performed in time proportional to the number of links in the graph. In this decade there has been great progress: numerous algorithms have been proposed for inference and learning, and SPNs have been successfully applied to many problems, including computer vision and natural language processing, in which probabilistic models could not compete with neural networks. The understanding of SPNs has also improved and some aspect can now be explained more clearly than in the original publications. For example, the first two papers about SPNs BIB003 ,  presented them as an efficient representation of network polynomials, while most of the later references, beginning with  , define them as the composition of probability distributions, which is, in our view, more intuitive and much easier to understand. Consistency was initially one of the defining properties of SPNs, which made them more general than arithmetic circuits, but it later became clear that decomposability, a stronger but much more intuitive property, suffices to build SPNs for practical applications. In contrast, selectivity (called determinism in arithmetic circuits), which was not mentioned in the original paper BIB003 , proved to be relevant for some inference tasks and for parameter learning BIB005 , BIB004 . Additionally, some of the algorithms for SPNs are only sketched in BIB003 , without much detail or formal proofs, and one of them turned out to be correct only for selective SPNs. Other basic algorithms are scattered over several papers, each using a different mathematical notation. For these reasons we decided to write a survey explaining the main concepts and algorithms for SPNs with mathematical rigor. We have intentionally avoided any reference to network polynomials, which has forced us to develop new proofs for some algorithms and propositions, alternative to those found in other references, such as  . We have also reviewed the literature on SPNs, with arXiv:2004.01167v1 [cs. LG] 2 Apr 2020 especial emphasis on their applications. However, we are aware that some relevant references may have been omitted, especially those published recently in this thriving research area. The rest of this paper is structured as follows. The two subsections of this introduction highlight the significance of SPNs by comparing them with probabilistic graphical models and neural networks respectively. After some mathematical preliminaries (Sec. II), we introduce the basic definitions of SPNs (Sec.III) and the main algorithms for inference (Sec.IV), parameter learning (Sec. V), and structural learning (Sec. VI). We then review some applications in several areas (Sec. VII), a few open-source packages (Sec. VIII), and some extensions of SPNs (Sec. IX). Section X contains the conclusions, Appendix A compares SPNs with arithmetic circuits, Appendix B analyzes the interpretation of sum nodes as weighted averages of conditional probabilities, and Appendix C contains the proofs of all the propositions.