Abstract
Sum-Product Networks (SPNs) are deep probabilistic models that allow for exact and efficient inference. Traditionally, SPNs required complex structure learning algorithms to ensure tractability. This paper introduces Random and Tensorized SPNs (RAT-SPNs), demonstrating that random structures, when properly tensorized and optimized with standard deep learning techniques, can achieve state-of-the-art performance. RAT-SPNs exhibit superior robustness to missing data and provide well-calibrated uncertainty estimates for anomaly detection, outperforming traditional deep learning models in these critical areas.
Introduction
Deep learning has seen immense success, yet many popular generative models like VAEs and GANs struggle with tractable inference. Tasks such as calculating marginal probabilities or conditioning on evidence often require expensive approximations. Sum-Product Networks (SPNs) were proposed to address this by guaranteeing exact inference in linear time. However, the requirement for the network structure to be complete and decomposable led to the development of intricate structure-learning algorithms. This research explores whether such complexity is necessary, proposing that random structures can be equally effective.
Methods: Random and Tensorized SPNs (RAT-SPNs)
The authors propose RAT-SPNs, which simplify the construction of SPNs through two main innovations:
- Random Region Graphs: Instead of learning the graph from data, a random structure is generated by recursively partitioning input variables. This ensures the necessary structural constraints are met by design.
- Tensorization: The SPN structure is mapped onto efficient tensor operations, enabling implementation in modern frameworks like TensorFlow and execution on GPUs.
Parameters are learned using generative (EM algorithm), discriminative (Adam with cross-entropy), or hybrid objectives. A key feature is "Probabilistic Dropout," where dropping an input during training corresponds to exact marginalization, naturally preparing the model for missing data.
Key Results and Discussion
The effectiveness of RAT-SPNs was evaluated across generative benchmarks, classification tasks, and anomaly detection.
Generative and Classification Performance
On 20 standard generative benchmarks, RAT-SPNs matched the performance of previous state-of-the-art structure learners. In classification, they remained competitive with standard Multi-Layer Perceptrons (MLPs) while offering additional probabilistic benefits.
Robustness to Missing Data
One of the most significant advantages of RAT-SPNs is their resilience to missing information. Unlike standard neural networks that require data imputation, SPNs can marginalize out missing features exactly.
As shown in the figure above, RAT-SPNs maintain high accuracy even when a large portion of the input is missing. For instance, on MNIST with 80% missing pixels, hybrid RAT-SPNs significantly outperform MLPs. This robustness is a direct consequence of the model's ability to perform exact marginalization.
Anomaly Detection and Uncertainty
RAT-SPNs avoid the "likelihood mirage" common in other deep generative models, where out-of-distribution samples are assigned erroneously high likelihoods. They successfully distinguished between MNIST digits and SEMEION digits, providing reliable uncertainty estimates that are crucial for safety-critical applications.
Conclusion
RAT-SPNs demonstrate that the power of Sum-Product Networks lies not in complex structure learning, but in their inherent probabilistic constraints. By leveraging random structures and modern optimization, RAT-SPNs provide a simple yet effective bridge between deep learning and probabilistic modeling, offering a robust solution for tasks involving missing data and uncertainty quantification.
Summary updated