Sum-product networks: A survey <s> Appendix A. From arithmetic circuits to SPNs <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> Appendix A. From arithmetic circuits to SPNs <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 </s> Sum-product networks: A survey <s> Appendix A. From arithmetic circuits to SPNs <s> Graphical models are usually learned without regard to the cost of doing inference with them. As a result, even if a good model is learned, it may perform poorly at prediction, because it requires approximate inference. We propose an alternative: learning models with a score function that directly penalizes the cost of inference. Specifically, we learn arithmetic circuits with a penalty on the number of edges in the circuit (in which the cost of inference is linear). Our algorithm is equivalent to learning a Bayesian network with context-specific independence by greedily splitting conditional distributions, at each step scoring the candidates by compiling the resulting network into an arithmetic circuit, and using its size as the penalty. We show how this can be done efficiently, without compiling a circuit from scratch for each candidate. Experiments on several real-world domains show that our algorithm is able to learn tractable models with very large treewidth, and yields more accurate predictions than a standard context-specific Bayesian network learner, in far less time. <s> BIB003 </s> Sum-product networks: A survey <s> Appendix A. From arithmetic circuits to SPNs <s> The past decade has seen a significant interest in learning tractable probabilistic representations. Arithmetic circuits (ACs) were among the first proposed tractable representations, with some subsequent representations being instances of ACs with weaker or stronger properties. In this paper, we provide a formal basis under which variants on ACs can be compared, and where the precise roles and semantics of their various properties can be made more transparent. This allows us to place some recent developments on ACs in a clearer perspective and to also derive new results for ACs. This includes an exponential separation between ACs with and without determinism; completeness and incompleteness results; and tractability results (or lack thereof) when computing most probable explanations (MPEs). <s> BIB004
SPNs originated as a modification of arithmetic circuits (ACs)  . Both models consist of rooted ADG with three types of nodes: sum, product, and leaves, but a leaf node in an AC can only be a non-negative parameter or an indicator for a Boolean variable. In contrast, the numeric parameters of SPNs are placed in the links outgoing from sum nodes and leaf nodes can be any univariate distribution, not only indicators. BIB001 ACs are smooth (i.e., complete), decomposable, and deterministic (i.e., selective). SPN are complete and decomposable; decomposability might be replaced by a weaker condition, consistency BIB002 , but this generalization has no practical utility. So the main difference between both models is that SPNs are not necessarily selective (i.e., deterministic), which makes them capable of representing some problems with exponentially smaller networks than ACs [97, Sec. 5], but at the price of making much harder both exact MPE (cf. Sec. IV-B and BIB004 Sec. 4] ) and parameter learning (cf. Sec. V). ACs were initially proposed as an efficient representation of the polynomials of Bayesian networks (BNs), useful for some inference tasks  . Later Chavira and Darwiche BIB001 developed an alternative method for compiling BNss that may yield exponentially smaller ACs in some cases, and Choi and Darwiche BIB004 showed that ACs can represent arbitrary factors (called "potentials" in other publications), not only the conditional probability distributions of BNs. As we said in the introduction, the first papers about SPNs BIB002 ,  presented them as representations of network polynomials of probability distributions, just as in the case of ACs, while most posterior references, beginning with  , present them as combinations of probability distributions, which is a significant difference with respect to ACs. An important novelty in the area of ACs was the algorithm by Lowd and Domingos BIB003 for learning ACs directly from data, instead of compiling them from BNs. In contrast, SPNs were proposed from their start BIB002 as a method for building probabilistic models from data. Nowadays there are many algorithms for learning ACs and other types of probabilistic circuits. The references can be found in the tutorial by Vergari et al. that we recommended at the end of Section IX.