Sum-product networks: A survey <s> 4) Expectation-Maximization (EM): a) Standard EM: <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> 4) Expectation-Maximization (EM): a) Standard EM: <s> Sum-product networks have recently emerged as an attractive representation due to their dual view as a special type of deep neural network with clear semantics and a special type of probabilistic graphical model for which inference is always tractable. Those properties follow from some conditions (i.e., completeness and decomposability) that must be respected by the structure of the network. As a result, it is not easy to specify a valid sum-product network by hand and therefore structure learning techniques are typically used in practice. This paper describes the first {\em online} structure learning technique for continuous SPNs with Gaussian leaves. We also introduce an accompanying new parameter learning technique. <s> BIB002
We have seen how to learn the parameters of a selective SPN from a complete dataset. However, many real-world problems have missing values. We denote by H t the variables missing (hidden) in the tth instance of the database. Additionally, when learning the parameters of S , an augmented SPN, the database is always incomplete, even if it contains all the values for the the model variables in S, because it does not contain the latent variables Z, added when augmenting the SPN, so Z ⊆ H t for every t. In this situation we can apply the expectationmaximization (EM) algorithm, designed to estimate the parameters of probabilistic models from incomplete datasets. The problem is as follows. If we had a complete database, we would be able to estimate its parameters as explained in the previous section. Alternatively, if we knew the parameters, we would be able to generate a complete database by sampling from the probability distribution. The EM algorithm proceeds by iteratively applying two steps. The E-step (expectation) computes the probability P (h t | v t ) for each configuration of the variables missing in v t in order to impute the missing values. More precisely, instead of assigning a single value to each missing cell, we create a virtual database in which all the configurations of H t are present, each with probability P (h t | v t ). The Mstep (maximization) uses this virtual complete database to adjust the parameters of the model by MLE, as in Section V-A1. The two steps are repeated until the parameters (the weights) converge. The problem is that initially we have neither a complete database nor parameters for sampling the values of the missing variables. The algorithm can be initialized by assigning arbitrary values to the parameters or by assigning arbitrary values to the variables in Z. Unfortunately, a bad choice of the initial values may cause the algorithm to converge to a local maximum of the likelihood, which may be quite different from the global maximum. The n ij 's required by the M-step are obtained by counting the number of instances in the database for which the link (i, j) belongs to the tree induced by v t h t . These are the n ij 's introduced in Equation 23 , which in the case of the virtual database are and can be efficiently computed by applying the following result: Proposition 28. Given a database D with T instances and a selective SPN, the n ij 's in Equation 32 are Once we have the n ij 's, the weights can be updated using Equation 24 or 25. The time required by each iteration of EM is proportional to the size of the network and the number of instances in the dataset. b) Hard EM: The EM algorithm needs the value of S ∂ i , which is proportional to ∂S/∂w ij and may thus be very small when the link (n i , n j ) is in a deep position, i.e., far from the root. Therefore this algorithm may suffer from the vanishing gradients problem in the same way as GD. To avoid it, Poon and Domingos BIB001 proposed a hard version of EM for SPNs that selects for each hidden variable H ∈ H t the most probable state. Thus, in the E-step of each iteration, every instance of the dataset contributes to the update of just one weight per sum node, instead of contributing to all of them proportionally. Hsu et al. BIB002 proposed a variant of hard EM for SPNs with Gaussian leaves. This method proceeds top-down. It starts at the top sum node and distributes the instances among its children by maximum likelihood. Every other sum node receives only the instances distributed to its parents and redistributes them in the same fashion. This way it updates the weights of the sum nodes locally. The process is similar to the automatic parameter learning in LearnSPN (cf. Sec. VI-B). These authors also provide formulas for updating the parameters of Gaussian leaves.