Learning the Structure of Sum-Product Networks via an SVD-based Algorithm

Tameem Adel, David Balduzzi, Ali GhodsiUAI 2015 · OpenReview

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).

Recursive decomposition of the data matrix to identify rank-1 atoms and build the SPN structure.

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)$.

Discriminative feature extraction using HSIC to transform input variables X into label-dependent features Z.

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

BibTeX
@inproceedings{adel2015learning,
  author = {Tameem Adel and David Balduzzi and Ali Ghodsi},
  title = {{Learning the Structure of Sum-Product Networks via an SVD-based Algorithm}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=oTSiUJOnUA},
}

Loading related content...

Figure