Sum-product networks: A survey <s> Proposition 27. <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> Proposition 27. <s> Sum-product networks (SPNs) are a deep probabilistic representation that allows for efficient, exact inference. SPNs generalize many other tractable models, including thin junction trees, latent tree models, and many types of mixtures. Previous work on learning SPN structure has mainly focused on using top-down or bottom-up clustering to find mixtures, which capture variable interactions indirectly through implicit latent variables. In contrast, most work on learning graphical models, thin junction trees, and arithmetic circuits has focused on finding direct interactions among variables. In this paper, we present ID-SPN, a new algorithm for learning SPN structure that unifies the two approaches. In experiments on 20 benchmark datasets, we find that the combination of direct and indirect interactions leads to significantly better accuracy than several state-of-the-art algorithms for learning SPNs and other tractable models. <s> BIB002
When an SPN is selective and its weights are all different from 0, where n ij is the number of instances in the dataset for which (i, j) ∈ T v t and c is a value that does not depend on w. The n ij 's can be computed by having a counter for every link in the SPN. For each instance v t in the dataset, we compute S(v t ) and then backtrack from the root to the leaves: for each product node we select all its children and for each sum node n i we select the only child for which S j (v t ) > 0 and increase by 1 the counter n ij . It is then necessary to obtain the configuration w that maximizes the likelihood, defined in Equation  . The only constraint is j∈ch(i) w ij = 1 for every i, which implies that the parameters for one node can be optimized independently of those for other nodes. The values that maximize the i-th term in Equation  are There is a special case in which j∈ch(i) n ij = 0. This occurs when S i (v t ) = 0 for every t, i.e., when none of the instances in the dataset propagates through the sum node n i . In this case, the weights of this node can be set uniformly: Alternatively, it is possible to use a Laplace-like smoothing parameter α, so that with 0 < α ≤ 1. 2) Partial derivatives of S: For every node n i we define For the root node we have If n j is not the root, where pa(j) is the set of indices for the parents of n j . If n i is a sum node, if it is a product node, These equations mean that, for every node n j , S ∂ j (x) can be computed once we have the S ∂ i (x)'s of its parents and the S j (x)'s of its siblings. Therefore, after computing S i (x) for every node with an upward pass, S ∂ i (x) can be computed with a downward pass, both in linear time. This algorithm is similar to backpropagation for neural networks and can be implemented using software packages that support automatic differentiation. 3) Gradient descent: a) Standard gradient descent: Gradient descent (GD), a well known optimization method, was proposed for SPNs for both generative and discriminative models in BIB001 and  , respectively.  The algorithm is initialized by assigning an arbitrary value to each parameter, w (0) ij . and in every iteration, s, this value is updated, in order to increase the likelihood of the model: where γ is the learning rate (a hyperparameter). It may be necessary to renormalize the weights for each i after each update. The partial derivative for L D can be efficiently computed using the S ∂ i 's defined above, as follows. Because of Equation BIB002 , which together with Equations 14 and 26 leads to and, finally, This equation allows us to perform each iteration of GD in time proportional to the size of the SPN and the number of instances in the database. b) Stochastic GD and mini-batch GD: In the stochastic version of GD, each iteration s uses only one instance of the database, randomly chosen, so that until the algorithm converges. Another possibility is to use mini-batches to update the weights, that is, to divide the dataset in batches of L randomly drawn instances, where L < T (usually L T ), and update the weights as follows: This version is the most popular when applying GD. c) Hard GD: The application of GD to deep networks, either neural networks or SPNs, suffers from the vanishing gradients problem: the deeper the layer, the lower the contribution of its weights to the model output, so the influence of the parameters in the deepest layers may be imperceptible. The hard version of GD for SPNs solves this problem by replacing the sum nodes with max nodes and reparametrizing the weights so that the gradient of the log-likelihood function remains constant. This method was introduced for SPNs by Gens and Domingos  for discriminative learning.