Sum-product networks: A survey <s> III. Basic definitions of SPNs A. Structure of an SPN <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> BIB001 </s> Sum-product networks: A survey <s> III. Basic definitions of SPNs A. Structure of an SPN <s> The need for feasible inference in Probabilistic Graphical Models PGMs has lead to tractable models like Sum-Product Networks SPNs. Their highly expressive power and their ability to provide exact and tractable inference make them very attractive for several real world applications, from computer vision to NLP. Recently, great attention around SPNs has focused on structure learning, leading to different algorithms being able to learn both the network and its parameters from data. Here, we enhance one of the best structure learner, LearnSPN, aiming to improve both the structural quality of the learned networks and their achieved likelihoods. Our algorithmic variations are able to learn simpler, deeper and more robust networks. These results have been obtained by exploiting some insights in the building process done by LearnSPN, by hybridizing the network adopting tree-structured models as leaves, and by blending bagging estimations into mixture creation. We prove our claims by empirically evaluating the learned SPNs on several benchmark datasets against other competitive SPN and PGM structure learners. <s> BIB002 </s> Sum-product networks: A survey <s> III. Basic definitions of SPNs A. Structure of an SPN <s> It has been shown in recent work that Expectation-Maximization (EM) is an attractive way to learn the parameters of Sum-Product Networks (SPNs). However, previous derivations of EM do not easily extend to SPNs with general leaf distributions and shared parameters. In this paper we obtain a new derivation of EM for SPNs allowing to derive EM updates for \emph{arbitrary leaf distributions} and for \emph{shared parameters} between SPN nodes. Here, EM translates in a set of independent weighted maximum likelihood problems for each leaf distribution, and therefore \emph{any} distribution that can be trained with maximum likelihood (even approximately) fits in this framework. The ability of learning complex leaf distributions in a principled way makes SPN parameter learning more flexible than learning SPN weights only. We demonstrate the potential of this approach with extensive experiments on twenty widely used benchmark datasets, using tree graphical models as leaf distributions. <s> BIB003 </s> Sum-product networks: A survey <s> III. Basic definitions of SPNs A. Structure of an SPN <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> BIB004
An SPN S consists of a rooted acyclic directed graph such that: • every leaf node represents a univariate probability distribution, • all the other nodes are either of type sum or product, • all the parents of a sum node (if any) are product nodes, and vice versa, and • every link n i → n j outgoing from a sum node has an associated weight, w ij ≥ 0. Usually w ij > 0. We will assume, unless otherwise stated, that all SPNs are normalized, i.e., ∀i, The probability distribution of each leaf node is defined on a variable V , which can have finite states or be continuous. In the first case, the distribution is usually degenerate, i.e., there is a particular value v * of V such that P (v * ) = 1 and P (v) = 0 otherwise. In the graphical representation this leaf is denoted by the indicator I v * , sometimes written I(v * ), as in Figures 1 and 2 . When V is continuous, the probability distribution can be Gaussian  , BIB001 , Poisson  , piecewise polynomial  , etc. (SPNs can be further generalized by allowing each terminal node to represent a multivariate probability density-for example, a multivariate Gaussian BIB003 , BIB004 or a Chow-Liu tree BIB002 .) An SPN can be built bottom-up beginning with sub-SPNs of one node and joining them with sum and product nodes. All the definitions of SPNs can be established recursively, first for one-node SPNs, and then for sum and product nodes. Similarly, all the properties of SPNs can be proved by structural induction. If the probability distribution of a leaf node is defined on V , its scope is the set {V }. If n i is a sum or a product node, its scope is the union of the scopes of its children: The scope of an SPN, denoted by sc(S), is the scope of its root, sc(n r ). The variables in the scope of an SPN are sometimes called model variables-in contrast with latent variables, which we present below. We define conf(S) = conf(sc(S)) and conf * (S) = conf * (sc(S)). A sum node is complete if all its children have the same scope. An SPN is complete if all its sum nodes are complete. (In arithmetic circuits this property is called smoothness.) A product node is decomposable if its children have disjoint scopes. An SPN is decomposable if all its product nodes are decomposable.