Sum-product networks: A survey <s> B. MPE inference <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> BIB001 </s> Sum-product networks: A survey <s> B. MPE inference <s> In Bayesian networks, a Most Probable Explanation (MPE) is a complete variable instantiation with the highest probability given the current evidence. In this paper, we discuss the problem of finding robustness conditions of the MPE under single parameter changes. Specifically, we ask the question: How much change in a single network parameter can we afford to apply while keeping the MPE unchanged? We will describe a procedure, which is the first of its kind, that computes this answer for all parameters in the Bayesian network in time O(n exp(w)), where n is the number of network variables and w is its treewidth. <s> BIB002 </s> Sum-product networks: A survey <s> B. MPE inference <s> Sum-product networks (SPNs) are a class of probabilistic graphical models that allow tractable marginal inference. However, the maximum a posteriori (MAP) inference in SPNs is NP-hard. We investigate MAP inference in SPNs from both theoretical and algorithmic perspectives. For the theoretical part, we reduce general MAP inference to its special case without evidence and hidden variables; we also show that it is NP-hard to approximate the MAP problem to $2^{n^\epsilon}$ for fixed $0 \leq \epsilon < 1$, where $n$ is the input size. For the algorithmic part, we first present an exact MAP solver that runs reasonably fast and could handle SPNs with up to 1k variables and 150k arcs in our experiments. We then present a new approximate MAP solver with a good balance between speed and accuracy, and our comprehensive experiments on real-world datasets show that it has better overall performance than existing approximate solvers. <s> BIB003
The MPE configuration for an SPN is (see Sec. II-C) Let us assume that S is selective. Then X ∪ E = sc(S) implies that xe ∈ conf(S) and, because of Proposition 21, the sub-SPN induced by xe is a tree in which every sum node has only one child. Therefore, the MPE can be found by examining all the trees for the configurations xe in which e is fixed and x varies. It is possible to compare all those trees at once with a single pass in S, by computing S max i (e) for each node as follows: • otherwise S max i (e) = S i (e) (cf. Eqs. 13 and 15). Then the algorithm backtracks from the root to the leaves, selecting for each sum node the child that led to S max (e) and for each product node all its children. When arriving at a terminal node for variable V , the algorithm selects the value v = arg max v P (v ). In particular, if the terminal node is an indicator, . A tie means that there are two or more configurations having the same probability P (x, e); these ties can be broken arbitrarily. The backtracking phase is equivalent to pruning the SPN in order to obtain a tree in which every sum node has only one child and there is exactly one terminal node for each variable; the v values selected at the terminal nodes make up the configuration x = MPE (e). Example 26. Figure 4 shows the MPE inference for the SPN in Figure 2 when e = +c. The MPE is obtained by backtracking from the root to the leaves: x = MPE (e) = (+a, ¬b). We can check that S max 1 (e) = P (xe) = P (+a, ¬b, +c) = 0.144. For any other configuration x of X = V \ E = {A, B}, we have S(xe) < S(xe), in accordance with Equation 19 . We can also check that the nodes selected by the backtracking phase are those of the tree induced byxe-see Def.  and Prop. 21. Note that, as mentioned in Section II-C, the MPE cannot be determined by selecting the most probable value for each variable. In this example P (¬a | e) = 0.57 > P (+a | e) and P (¬b | e) = 0.68 > P (+b | e), so we would obtain the configuration (¬a, ¬b), which is not the MPE. This algorithm was proposed by Chan and Darwiche BIB002 for arithmetic circuits, adapted to SPNs by Poon and Domingos BIB001 , and later called Best Tree (BT) in BIB003 . Peharz [7, Theorem 2] proved that when an SPN is selective, BT computes the true MPE. However, when a network is not selective, the sub-SPN induced by a configuration xe is not necessarily a tree, so the value S max (e) computed by BT-which only considers the probability that flows along trees with one child for each sum node-may be different from max x S(xe) and, consequently, the configuration returned by BT may be different from the true MPE. Therefore, even though the MPE can be found in time proportional to the size of the graph for selective SPNs, MPE is NP-complete for general SPNs [9, Theorem 5.3]. 4