Abstract
Probabilistic graphical models provide a general and flexible framework for reasoning about complex dependencies in noisy domains with many variables. Among the various types of probabilistic graphical models, sum-product networks (SPNs) have recently generated some interest because exact inference can always be done in linear time with respect to the size of the network. This is particularly attractive since it means that learning an SPN from data always yields a tractable model for inference. However, existing parameter learning algorithms for SPNs operate in batch mode and do not scale easily to large datasets. In this work, we explore online algorithms to ensure that parameter learning can also be done tractably with respect to the amount of data. More specifically, we propose a new Bayesian moment matching (BMM) algorithm that operates naturally in an online fashion and that can be easily distributed. We demonstrate the effectiveness and scalability of BMM in comparison to online extensions of gradient descent, exponentiated gradient and expectation maximization on 20 classic benchmarks and 4 large scale datasets.
Introduction
Sum-Product Networks (SPNs) are deep probabilistic models that guarantee exact inference in linear time. While this tractability makes them highly desirable for real-world applications, the bottleneck remains the learning phase. Traditional parameter learning algorithms for SPNs typically rely on batch processing, which becomes computationally prohibitive as datasets scale to millions of records. Existing online alternatives, such as Stochastic Gradient Descent (SGD) or online Expectation Maximization (oEM), often struggle with local optima or overfitting in the non-convex landscape of SPN optimization.
Bayesian Moment Matching
This paper introduces Online Bayesian Moment Matching (oBMM), a framework that treats parameter learning as a Bayesian inference problem. Instead of seeking a single point estimate for weights, oBMM maintains a posterior distribution over parameters.
To maintain tractability, the authors address the exponential growth of mixture components inherent in exact Bayesian updates for SPNs. By employing a moment matching technique, the complex posterior resulting from a new data point is approximated by a simpler product of Dirichlet distributions. This approximation preserves the first and second moments (mean and variance) of the original distribution, ensuring the learning process remains efficient and stable. Furthermore, the incremental nature of these Bayesian updates allows for a distributed implementation (oDMM), where computations are parallelized across multiple nodes and merged periodically.
Experimental Results
The proposed algorithms were evaluated against 20 standard benchmarks and 4 large-scale datasets (KOS, NIPS, ENRON, NYTIMES).
As shown in the benchmark results above, oBMM achieved superior log-likelihood scores compared to online gradient-based and EM methods on 19 out of 20 benchmarks. Notably, oBMM with a fixed random structure often matched the performance of structure-learning algorithms like LearnSPN, highlighting the robustness of the Bayesian parameter updates even when the network architecture is sub-optimal.
In terms of scalability, the distributed approach provides substantial benefits. On the KOS dataset, while the batch algorithm LearnSPN required over 1,400 minutes, the distributed oDMM completed training in just 8.6 minutes—a 166x speedup. On the massive NYTIMES dataset, which contains over 100,000 variables, oDMM reduced training time from hundreds of hours to just 27 hours while maintaining competitive accuracy.
Conclusion
Online Bayesian Moment Matching provides a scalable and robust alternative for SPN parameter learning. By leveraging the stability of Bayesian updates and the efficiency of moment matching, oBMM overcomes the limitations of batch learning and the local optima issues of standard optimization techniques. Future work will explore integrating these Bayesian updates with online structure learning to create fully autonomous, large-scale probabilistic systems.
Summary updated