Sum-product networks: A survey <s> IX. Extensions of 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> BIB001 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> Sum-product networks are a relatively new and increasingly popular class of (precise) probabilistic graphical models that allow for marginal inference with polynomial effort. As with other probabilistic models, sum-product networks are often learned from data and used to perform classification. Hence, their results are prone to be unreliable and overconfident. In this work, we develop credal sum-product networks, an imprecise extension of sum-product networks. We present algorithms and complexity results for common inference tasks. We apply our algorithms on realistic classification task using images of digits and show that credal sum-product networks obtained by a perturbation of the parameters of learned sum-product networks are able to distinguish between reliable and unreliable classifications with high accuracy. <s> BIB002 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> We present a novel tractable generative model that extends Sum-Product Networks (SPNs) and significantly boost their power. We call it Sum-Product-Quotient Networks (SPQNs), whose core concept is to incorporate conditional distributions into the model by direct computation using quotient nodes, e.g. $P(A|B){=}\frac{P(A,B)}{P(B)}$. We provide sufficient conditions for the tractability of SPQNs that generalize and relax the decomposable and complete tractability conditions of SPNs. These relaxed conditions give rise to an exponential boost to the expressive efficiency of our model, i.e. we prove that there are distributions which SPQNs can compute efficiently but require SPNs to be of exponential size. Thus, we narrow the gap in expressivity between tractable graphical models and other Neural Network-based generative models. <s> BIB003 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> Convolutional neural networks (convnets) have achieved impressive results on recent computer vision benchmarks. While they benefit from multiple layers that encode nonlinear decision boundaries and a degree of translation invariance, training convnets is a lengthy procedure fraught with local optima. Alternatively, a kernel method that incorporates the compositionality and symmetry of convnets could learn similar nonlinear concepts yet with easier training and architecture selection. We propose compositional kernel machines (CKMs), which effectively create an exponential number of virtual training instances by composing transformed sub-regions of the original ones. Despite this, CKM discriminant functions can be computed efficiently using ideas from sum-product networks. The ability to compose virtual instances in this way gives CKMs invariance to translations and other symmetries, and combats the curse of dimensionality. Just as support vector machines (SVMs) provided a compelling alternative to multilayer perceptrons when they were introduced, CKMs could become an attractive approach for object recognition and other vision problems. In this paper we define CKMs, explore their properties, and present promising results on NORB datasets. Experiments show that CKMs can outperform SVMs and be competitive with convnets in a number of dimensions, by learning symmetries and compositional concepts from fewer samples without data augmentation. <s> BIB004 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> Sum-product networks (SPNs) represent an emerging class of neural networks with clear probabilistic semantics and superior inference speed over graphical models. This work reveals a strikingly intimate connection between SPNs and tensor networks, thus leading to a highly efficient representation that we call tensor SPNs (tSPNs). For the first time, through mapping an SPN onto a tSPN and employing novel optimization techniques, we demonstrate remarkable parameter compression with negligible loss in accuracy. <s> BIB005 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> This paper introduces a probabilistic architecture called sum–product graphical model (SPGM). SPGMs represent a class of probability distributions that combines, for the first time, the semantics of probabilistic graphical models (GMs) with the evaluation efficiency of sum–product networks (SPNs): Like SPNs, SPGMs always enable tractable inference using a class of models that incorporate context specific independence. Like GMs, SPGMs provide a high-level model interpretation in terms of conditional independence assumptions and corresponding factorizations. Thus, this approach provides new connections between the fields of SPNs and GMs, and enables a high-level interpretation of the family of distributions encoded by SPNs. We provide two applications of SPGMs in density estimation with empirical results close to or surpassing state-of-the-art models. The theoretical and practical results demonstrate that jointly exploiting properties of SPNs and GMs is an interesting direction of future research. <s> BIB006 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> Sum-Product Networks (SPNs) are hierarchical, probabilistic graphical models capable of fast and exact inference that can be trained directly from high-dimensional, noisy data. Traditionally, SPNs struggle with capturing relationships in complex spatial data such as images. To this end, we introduce Deep Generalized Convolutional Sum-Product Networks (DGC-SPNs), which encode spatial features through products and sums with scopes corresponding to local receptive fields. As opposed to existing convolutional SPNs, DGC-SPNs allow for overlapping convolution patches through a novel parameterization of dilation and strides, resulting in significantly improved feature coverage and feature resolution. DGC-SPNs substantially outperform other convolutional and non-convolutional SPN approaches across several visual datasets and for both generative and discriminative tasks, including image completion and image classification. In addition, we demonstrate a modificiation to hard EM learning that further improves the generative performance of DGC-SPNs. While fully probabilistic and versatile, our model is scalable and straightforward to apply in practical applications in place of traditional deep models. Our implementation is tensorized, employs efficient GPU-accelerated optimization techniques, and is available as part of an open-source library based on TensorFlow. <s> BIB007 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> We give conditions under which convolutional neural networks (CNNs) define valid sum-product networks (SPNs). One subclass, called convolutional SPNs (CSPNs), can be implemented using tensors, but also can suffer from being too shallow. Fortunately, tensors can be augmented while maintaining valid SPNs. This yields a larger subclass of CNNs, which we call deep convolutional SPNs (DCSPNs), where the convolutional and sum-pooling layers form rich directed acyclic graph structures. One salient feature of DCSPNs is that they are a rigorous probabilistic model. As such, they can exploit multiple kinds of probabilistic reasoning, including marginal inference and most probable explanation (MPE) inference. This allows an alternative method for learning DCSPNs using vectorized differentiable MPE, which plays a similar role to the generator in generative adversarial networks (GANs). Image sampling is yet another application demonstrating the robustness of DCSPNs. Our preliminary results on image sampling are encouraging, since the DCSPN sampled images exhibit variability. Experiments on image completion show that DCSPNs significantly outperform competing methods by achieving several state-of-the-art mean squared error (MSE) scores in both left-completion and bottom-completion in benchmark datasets. <s> BIB008 </s> Sum-product networks: A survey <s> IX. Extensions of SPNs <s> Bayesian networks are a central tool in machine learning and artificial intelligence, and make use of conditional independencies to impose structure on joint distributions. However, they are generally not as expressive as deep learning models and inference is hard and slow. In contrast, deep probabilistic models such as sum-product networks (SPNs) capture joint distributions in a tractable fashion, but use little interpretable structure. Here, we extend the notion of SPNs towards conditional distributions, which combine simple conditional models into high-dimensional ones. As shown in our experiments, the resulting conditional SPNs can be naturally used to impose structure on deep probabilistic models, allow for mixed data types, while maintaining fast and efficient inference. <s> BIB009
In recent years there have been several extensions of SPNs to more general models. In this section we briefly comment on some of them. Sum-product-max networks (SPMNs)  generalize SPNs to the class of decision making problems by including two new types of nodes, max and utility, like in influence diagrams. These networks can compute the expected utility and the optimal policy in time proportional to the number of links. Autoencoder SPNs (AESPNs)  combine two SPNs with an autoencoder between them. This model produces better samples than SPNs by themselves. Tan and Peharz  designed a mixture model of VAE pieces over local subsets of variables combined via an SPN. This combination yields better density estimates, smaller models and improved data efficiency with respect to VAEs. In credal sum-product networks (CSPNs) BIB002 the weights of each sum node do not have a fixed value, but vary inside a set (a product of probability simplexes) in such a way that each choice of the weights defines an SPN. Sum-product graphical models (SPGMs) BIB006 join the semantics of probabilistic graphical models with the evaluation efficiency and expressiveness of SPNs by allowing the nodes associated to variables to appear in any part of the network, not only in the leaf nodes. Their LearnSPGM algorithm outperformed both LearnSPN and ID-SPN on the 20 real-world datasets previously used in BIB001 . Sum-product-quotient networks (SPQNs) BIB003 introduce quotient nodes, which take two inputs and output their quotient, allowing these models to represent conditional probabilities explicitly. Tensor SPNs (tSPNs) BIB005 are an alternative representation of SPNs. Their main advantage is an important reduction in the number of parameters-between 24 and 569 times in the experiments-with little loss of modeling accuracy. Additionally, tSPNs allow for faster inference and a deeper and more narrow neural-network architecture. Convolutional SPNs (ConvSPNs or CSPN) were developed independently in BIB007 and BIB008 . The first model exploits the inherent structure of spatial data in a similar way to convolutional neural networks by using the sum and product operations of SPNs. The second one finds a criterion for seeing when a convolutional neural network is an SPN. Submodular SPNs (SSPNs)  are an extension of SPNs for scene understanding, whose weights can be defined by submodular energy functions. Compositional kernel machines (CKMs) BIB004 are an instance-based method closely related to SPNs. They have been successfully applied to image processing tasks, mainly to object recognition. Conditional SPNs (CSPNs) BIB009 extend SPNs to conditional probability distributions. They include a new type of node, called a gating node, which computes a convex combination of the conditional probability of its children with non-fixed weights. The tutorial by Vergari, Choi, Peharz and Van den Broek at AAAI-2020 offers an excellent review of probabilistic circuits, including arithmetic circuits, SPNs, cutset networks (CNets), probabilistic sentential decision diagrams (PSDDs), with many references for inference, learning, applications, hardware implementations, etc. 10