Introduction
Sum-Product Networks (SPNs) have emerged as a powerful class of deep probabilistic models, primarily due to their ability to provide tractable inference. Unlike many deep learning architectures where calculating exact probabilities or marginals is computationally prohibitive, SPNs allow these operations to be performed efficiently. However, the primary bottleneck in utilizing SPNs is the difficulty of learning their structure from data. Traditional top-down approaches often rely on greedy searches for independent variables or instance clusters, which can lead to inefficient, bloated networks that miss complex, context-specific dependencies.
The SPN-SVD Approach: Finding Coherence
This paper introduces SPN-SVD, a novel algorithm that shifts the focus from finding independence to identifying coherence. The core idea is to search for "atoms" of highly correlated data using Singular Value Decomposition (SVD). Specifically, the algorithm looks for submatrices that are approximately rank-1, representing groups of instances that exhibit strong correlation across a specific set of variables.
Recursive Structure Learning
Instead of splitting by variables or instances in isolation, SPN-SVD performs simultaneous splitting. When a rank-1 "atom" is identified, the data matrix is decomposed into components representing the correlated atom and the remaining data. This process is applied recursively to build the SPN structure, alternating between sum nodes (clustering instances) and product nodes (partitioning variables).
By identifying these coherent blocks, the algorithm can represent them compactly using Multivariate Leaf Nodes (MVLNs). This significantly reduces the depth and complexity of the resulting graph, leading to substantial improvements in both training speed and query performance.
Discriminative Learning with DSPN-SVD
For classification tasks, the authors propose DSPN-SVD. This discriminative variant incorporates the Hilbert-Schmidt Independence Criterion (HSIC) to perform feature selection before building the SPN. By extracting features ($Z$) that are most dependent on the labels ($Y$), the model can more effectively target the conditional distribution $P(Y|X)$.
Key Results and Performance
The effectiveness of the SVD-based approach was validated across multiple benchmarks, including image datasets (Caltech-101, Olivetti), binary datasets, and handwritten digits (MNIST, USPS).
- Efficiency: SPN-SVD demonstrated a massive speedup, processing the Caltech-101 and Olivetti datasets in just 2.5 hours, compared to 13.5 hours for the state-of-the-art SPN-Gens—a 4.5x improvement.
- Generative Accuracy: In generative tasks, SPN-SVD achieved superior test-set log-likelihood values on 42 out of 101 Caltech categories compared to existing methods like ID-SPN and WinMine.
- Classification Excellence: DSPN-SVD set new benchmarks for SPNs in handwritten digit recognition, reaching 97.6% accuracy on MNIST and 92.4% on USPS.
- Image Completion: Qualitative evaluations showed that the learned structures effectively captured spatial correlations, allowing the model to accurately "fill in" missing portions of facial images.
Conclusion
By leveraging SVD to find rank-1 atoms of correlation, SPN-SVD provides a more global and efficient way to learn the structure of Sum-Product Networks. This approach not only accelerates the training process but also results in more compact and accurate models for both generative and discriminative tasks. Future work aims to improve robustness to noise and extend the discriminative framework to regression and structured-output learning.
Summary updated