Sum-product networks: A survey <s> E. Improvements to LearnSPN <s> Random forests are a combination of tree predictors such that each tree depends on the values of a random vector sampled independently and with the same distribution for all trees in the forest. The generalization error for forests converges a.s. to a limit as the number of trees in the forest becomes large. The generalization error of a forest of tree classifiers depends on the strength of the individual trees in the forest and the correlation between them. Using a random selection of features to split each node yields error rates that compare favorably to Adaboost (Y. Freund & R. Schapire, Machine Learning: Proceedings of the Thirteenth International conference, aaa, 148–156), but are more robust with respect to noise. Internal estimates monitor error, strength, and correlation and these are used to show the response to increasing the number of features used in the splitting. Internal estimates are also used to measure variable importance. These ideas are also applicable to regression. <s> BIB001 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <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 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <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> BIB003 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <s> Learning the structure of sum-product networks (SPNs) - arithmetic circuits over latent and observed variables - has been the subject of much recent research. These networks admit linear time exact inference, and thus help alleviate one of the chief disadvantages of probabilistic graphical models: accurate probabilistic inference algorithms are often computationally expensive. Although, algorithms for inducing their structure from data have come quite far and often outperform algorithms that induce probabilistic graphical models, a key issue with existing approaches is that they induce tree SPNs, a small, inefficient sub-class of SPNs. In this paper, we address this limitation by developing post-processing approaches that induce graph SPNs from tree SPNs by merging similar sub-structures. The key benefits of graph SPNs over tree SPNs include smaller computational complexity which facilitates faster online inference, and better generalization accuracy because of reduced variance, at the cost of slight increase in the learning time. We demonstrate experimentally that our merging techniques significantly improve the accuracy of tree SPNs, achieving state-of-the-art performance on several real world benchmark datasets. <s> BIB004 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <s> We present a unified approach for learning the parameters of Sum-Product networks (SPNs). We prove that any complete and decomposable SPN is equivalent to a mixture of trees where each tree corresponds to a product of univariate distributions. Based on the mixture model perspective, we characterize the objective function when learning SPNs based on the maximum likelihood estimation (MLE) principle and show that the optimization problem can be formulated as a signomial program. We construct two parameter learning algorithms for SPNs by using sequential monomial approximations (SMA) and the concave-convex procedure (CCCP), respectively. The two proposed methods naturally admit multiplicative updates, hence effectively avoiding the projection operation. With the help of the unified framework, we also show that, in the case of SPNs, CCCP leads to the same algorithm as Expectation Maximization (EM) despite the fact that they are different in general. <s> BIB005 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <s> Sum-Product Networks (SPNs) are recent deep probabilistic models providing exact and tractable inference. SPNs have been successfully employed as density estimators in several application domains. However, learning an SPN from high dimensional data still poses a challenge in terms of time complexity. This is due to the high cost of determining independencies among random variables (RVs) and sub-populations among samples, two operations that are repeated several times. Even one of the simplest greedy structure learner, LearnSPN, scales quadratically in the number of the variables to determine RVs independencies. In this work we investigate approximate but fast procedures to determine independencies among RVs whose complexity scales in sub-quadratic time. We propose two procedures: a random subspace approach and one that adopts entropy as a criterion to split RVs in linear time. Experimental results prove that LearnSPN equipped by our splitting procedures is able to reduce learning and/or inference times while preserving comparable inference accuracy. <s> BIB006 </s> Sum-product networks: A survey <s> E. Improvements to LearnSPN <s> Abstract Sum-Product Network (SPN) are recently introduced deep tractable Probabilistic Graphical Models providing exact and tractable inference. SPN have been successfully employed as density estimators in some artificial intelligence fields, however, most of the proposed structure learning algorithms focus on improving the performance of a certain aspect of model, at the cost of reducing other performance. This is due to the fact that there is no effective balance between network width and depth during learning process. In this paper, we propose two clustering analysis algorithms to replace the clustering part of LearnSPN. We improve the structure quality of the generated model by deepening the network while adjusting the network width adaptively, trying to find a balance between the expressive power, representation ability, inference accuracy and simplicity. Experimental results prove that LearnSPN equipped by our clustering method has different degrees of improvement in various performances. <s> BIB007
Even though LearnSPN is not the best performing algorithm, it is still widely used owing to its simplicity and modularity  and has led to several variants. 1) Algorithm of Vergari et al. BIB003 : It consists of three modifications to LearnSPN: 1) Binary splits. Every split cuts the data matrix into only two pieces. This avoids creating too complex structures at early stages (which often occurs when learning from noisy data) and favors deep structures over shallow ones. This is not a limitation in the number of children of product nodes because consecutive splits can be applied if necessary. 2) Chow-Liu trees (CLTs) in the leaves. The naïve Bayes factorization used as the base case of LearnSPN (see Algorithm 1) can be replaced by the creation of Chow-Liu trees  , which are equivalent to treeshaped Bayesian networks or Markov networks. Every tree is built by linking the variables with higher mutual information until there is a path between every pair of variables. CLTs are more expressive than the naïve Bayes factorization (which is a particular case of CLT) without adding computational complexity. LearnSPN stops earlier when using CLTs as leaves because each tree can accommodate more instances, thus yielding simpler SPN structures (with fewer edges) with lower risk of overfitting. 3) Bagging. This technique, originally used to build random forests BIB001 , consists in taking several random samples from a dataset, each consisting of several instances, and building a classifier for each sample. The overall classification can be the average of the outputs of the individual classifiers (for continuous variables) or the mode (for finite-state variables). In SPN learning, it extracts-with replacementn samples of the dataset and produces a sum node with n children, setting every weight to 1/n, as shown in Figure 6 . Each child represents one of the individual classifiers and the sum node averages the n results. Since the network size would grow exponentially if bagging were applied before every clustering, it is applied only before the first Learn-SPN operation-which is a clustering-in order to achieve the widest effect on the resulting structure. The experiments showed that (1) binary splits yield deeper and simpler SPNs and generally reduce the number of edges and parameters, (2) using Chow-Liu trees attains the same effect and generally increases the likelihood, and (3) bagging also increases the likelihood, especially in datasets with a low number of instances. With these modifications, LearnSPN achieved the same performance as ID-SPN. 2) Beyond tree SPNs: One of the main disadvantages of both LearnSPN and ID-SPN is that they always produce trees (except when the leaves are Markov networks). In order to generate more compact SPNs, Dennis and Ventura  designed SearchSPN, an algorithm that produces SPNs in which nodes may have several parents. It selects the product node that contributes less to the likelihood and greedily searches for candidate structures using modified versions of the clustering methods of LearnSPN. The resulting likelihood is significantly better than that of LearnSPN for the majority of datasets and comparable with that of ID-SPN, but on average the execution is 7 times faster and the number of nodes 10 times smaller. In the same vein, Rahman and Gogate BIB004 created a post-processing algorithm that, after applying LearnSPN with CLTs in the leaves, merges similar sub-SPNs. Similarity is measured with a Manhattan distance; if two sub-SPNs are closer than a certain threshold, the pieces of the data matrix from which they come are combined and the algorithm chooses the sub-SPN with the higher likelihood for the combined data. This modification of LearnSPN increases the likelihood and reduces the number of parameters of the SPN; additionally, it dramatically increases the learning time for some datasets. In combination with bagging, it outperformed other algorithms-including ID-SPN BIB002 -for high-dimensional datasets. 3) Further improvements to LearnSPN: As mentioned in Section V-A5, Zhao et al. BIB005 showed that learning the parameters with the CCCP algorithm improves the performance of LearnSPN. Di Mauro et al. BIB006 proposed approximate splitting methods to accelerate LearnSPN, thus trading speed for quality (likelihood). Butz et al.  studied the different combinations of algorithms for LearnSPN. They compared mutual information and the G-test for splitting, and k-means and Gaussian mixture models for clustering. The best results were obtained when using the G-test and either k-means or Gaussian mixture models, both for the standard Learn-SPN and for the version that generates CLTs in the leaves. Liu et al. BIB007 proposed a clustering method that decides the number of instance clusters adaptively, i.e., depending on each piece of data matrix evaluated. Their goal was to generate more expressive SPNs, in particular deeper ones with controlled widths. When compared previous algorithms (namely, standard LearnSPN  , LearnSPN with binary splits BIB003 , and LearnSPN with approximate splitting BIB006 ), their method achieved higher likelihood in 20 binary datasets and generated deeper networks (i.e., more expressive SPNs) while maintaining a reasonable size.