Sum-product networks: A survey <s> B. SPNs vs. neural networks <s> An important question in neuroevolution is how to gain an advantage from evolving neural network topologies along with weights. We present a method, NeuroEvolution of Augmenting Topologies (NEAT), which outperforms the best fixed-topology method on a challenging benchmark reinforcement learning task. We claim that the increased efficiency is due to (1) employing a principled method of crossover of different topologies, (2) protecting structural innovation using speciation, and (3) incrementally growing from minimal structure. We test this claim through a series of ablation studies that demonstrate that each component is necessary to the system as a whole and to each other. What results is significantly faster learning. NEAT is also an important contribution to GAs because it shows how it is possible for evolution to both optimize and complexify solutions simultaneously, offering the possibility of evolving increasingly complex solutions over generations, and strengthening the analogy with biological evolution. <s> BIB001 </s> Sum-product networks: A survey <s> B. SPNs vs. neural networks <s> We have recently proposed a tractable logical form, known as deterministic, decomposable negation normal form (d-DNNF). We have shown that d-DNNF supports a number of logical operations in polynomial time, including clausal entailment, model counting, model enumeration, model minimization, and probabilistic equivalence testing. In this paper, we discuss another major application of this logical form: the implementation of multi-linear functions (of exponential size) using arithmetic circuits (that are not necessarily exponential). Specifically, we show that each multi–linear function can be encoded using a propositional theory, and that each d-DNNF of the theory corresponds to an arithmetic circuit that implements the encoded multi–linear function. We discuss the application of these results to factoring belief networks, which can be viewed as multi–linear functions as has been shown recently. We discuss the merits of the proposed approach for factoring belief networks, and present experimental results showing how it can handle efficiently belief networks that are intractable to structure–based methods for probabilistic inference. <s> BIB002 </s> Sum-product networks: A survey <s> B. SPNs vs. neural networks <s> This paper reviews the use of evolutionary algorithms (EAs) to optimize artificial neural networks (ANNs). First, we briefly introduce the basic principles of artificial neural networks and evolutionary algorithms and, by analyzing the advantages and disadvantages of EAs and ANNs, explain the advantages of using EAs to optimize ANNs. We then provide a brief survey on the basic theories and algorithms for optimizing the weights, optimizing the network architecture and optimizing the learning rules, and discuss recent research from these three aspects. Finally, we speculate on new trends in the development of this area. <s> BIB003 </s> Sum-product networks: A survey <s> B. SPNs vs. neural networks <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> BIB004 </s> Sum-product networks: A survey <s> B. SPNs vs. neural networks <s> The need for consistent treatment of uncertainty has recently triggered increased interest in probabilistic deep learning methods. However, most current approaches have severe limitations when it comes to inference, since many of these models do not even permit to evaluate exact data likelihoods. Sum-product networks (SPNs), on the other hand, are an excellent architecture in that regard, as they allow to efficiently evaluate likelihoods, as well as arbitrary marginalization and conditioning tasks. Nevertheless, SPNs have not been fully explored as serious deep learning models, likely due to their special structural requirements, which complicate learning. In this paper, we make a drastic simplification and use random SPN structures which are trained in a"classical deep learning manner", i.e. employing automatic differentiation, SGD, and GPU support. The resulting models, called RAT-SPNs, yield prediction results comparable to deep neural networks, while still being interpretable as generative model and maintaining well-calibrated uncertainties. This property makes them highly robust under missing input features and enables them to naturally detect outliers and peculiar samples. <s> BIB005
SPNs can be seen as a particular type of feedforward neural networks because there is a flow of information from the input nodes (the leaves) to the output node (the root), but in this paper we reserve the term "neural network" (NN) for the models structured in layers connected by the standard operators: sigmoid, ReLU, softmax, etc. The main difference is that SPNs have a probabilistic interpretation while standard NNs do not. Inference is also different: computing a posterior probability requires two passes, and finding a the most probable explanation (MPE) requires a backtrack from the root to the leaves, as explained in Section IV. Additionally, SPNs can do inference with partial information (i.e., when the values of some of the variables are unknown), while in a NN it is necessary to assign a value to each input node. From the point of view of parameter learning, NNs are usually trained with gradient descent or variations thereof, while SPNs can also be trained with several probabilistic algorithms, such as EM and Bayesian methods, which are much more efficient and have lower risk of overfitting (cf. Sec. V). When building practical applications, the main difference is the possibility of determining the structure of an SPN from data, looking for a balance between model complexity and accuracy. In contrast, NNs are usually designed by hand and it is necessary to examine different architectures of different sizes with different hyperparameters, in a trial-and-error approach, until a satisfactory model is found. For this reason, NNs that have succeeded in practical applications are usually very big and training them requires huge computational power. There are some proposals to learn the structure of NNs using evolutionary computation, which yields more efficient graphs, but this also requires immense computational power BIB001 , BIB003 . In spite of these advantages, NNs are still superior to SPNs in many tasks. For example, in 2012 an SPN by Gens and Domingos BIB004 achieved a classification accuracy of 84% for the CIFAR-10 image dataset, one of the highest scores at the time. However, deep NNs have amply surpassed that result, reaching an impressive 99.3% accuracy. BIB002 Nevertheless, in Section VII we mention several applications in which SPNs are competitive with NNs and superior in some aspects. For instance, random tensorized SPNs (RAT-SPNs) BIB005 have recently attained a classification accuracy comparable to deep NNs for MNIST and other image datasets, with the advantages of being interpretable as a probabilistic generative model and much more robust to missing features. For another recent example, Stelzner et al.  proved that the attend-infer-repeat (AIR) framework used for object detection and location is much more efficient when the variational autoencoders (VAEs) are replaced by SPNs: they achieved an improvement in speed of an order of magnitude, with slightly higher accuracy, as well as robustness against noise. Other examples can be found in Sections VII and IX. For a more detailed comparison of SPNs with NNs, VAEs, generative adversarial networks (GANs), and other models, see BIB005 .