Strudel: Learning Structured-Decomposable Probabilistic Circuits

Meihua Dang, Antonio Vergari, Guy Van den Broeck

Introduction: The Challenge of Tractable Probabilistic Modeling

In modern machine learning, researchers often face a fundamental trade-off between expressivity and tractability. While deep generative models like Variational Autoencoders (VAEs) can fit complex data distributions, they often struggle with exact inference. Answering queries like "What is the probability that this event satisfies a specific logical constraint?" typically requires slow, approximate methods.

Probabilistic Circuits (PCs) offer a solution by representing distributions as computational graphs with specific structural properties. One such property, structured decomposability, allows for advanced queries—such as computing expectations under missing data—to be answered exactly in linear time. However, learning these structures from data has historically been a major bottleneck. Previous state-of-the-art methods like LearnPSDD were computationally expensive and failed to scale to large datasets. Strudel (STRUctured-DEcomposable Learner) was developed to overcome these limitations through efficient initialization and vectorized learning.

The Strudel Algorithm: Efficient Structure Learning

Strudel introduces a streamlined approach to building structured-decomposable PCs by focusing on three primary innovations:

1. Smart Initialization via Chow-Liu Trees

Rather than starting from a blank slate, Strudel begins by learning a Chow-Liu Tree (CLT)—the optimal tree-structured model for the given data. This tree is then compiled into an initial PC. This ensures the model starts with a high-quality representation of the most significant variable dependencies.

Figure 2: The relationship between a probabilistic model (a), its tree structure (b), the corresponding variable hierarchy or vtree (c), and the resulting compiled probabilistic circuit (d).

2. Greedy Structure Refinement

Strudel grows the circuit using a "split" operation guided by two novel heuristics:

  • eFLOW: This identifies edges where the most data "flows" through the circuit, highlighting high-impact areas for refinement.
  • vMI: This uses pairwise Mutual Information to select variables with the strongest dependencies, ensuring that new splits capture meaningful relationships.

3. Vectorization and Shared-Structure Ensembles

By exploiting determinism (a property where only one path through the circuit is active for a given input), Strudel represents data paths as bit-vectors. This allows the algorithm to use fast bit-vector arithmetic for parameter learning and inference. Furthermore, Strudel utilizes shared-structure ensembles, where multiple mixture components share the same graph structure but have different parameters. This allows the "flow" to be calculated once for the entire ensemble, dramatically increasing scalability.

Key Results and Insights

Strudel was evaluated against 20 standard density estimation benchmarks and several regression tasks involving missing data. The results highlight several key advantages:

  • Exceptional Speed: Strudel is consistently 10x to 100x faster per iteration than previous methods. On the 'msnbc' dataset, the flow-based approach was over 4,500 times faster than classical evaluation methods.
  • Improved Accuracy: Strudel achieved superior or equivalent test log-likelihoods compared to LearnPSDD on 16 out of 20 benchmarks.
  • Scalability to Large Ensembles: While earlier methods struggled to scale beyond a few dozen components, Strudel seamlessly handles ensembles of 100+ components due to its shared-structure design.
  • Robustness: In "Expected Prediction" tasks, Strudel-based ensembles significantly outperformed standard baselines like median imputation, particularly as the percentage of missing values increased.

Conclusion and Future Directions

Strudel demonstrates that structured-decomposable PCs can be learned both quickly and accurately by leveraging existing dependency information (CLTs) and modern computational techniques like vectorization. While the current implementation focuses on discrete variables and shared structures, future work may explore extending these flow-based techniques to continuous domains and investigating more complex variable hierarchies to further push the boundaries of tractable probabilistic modeling.

Summary updated

Abstract

Probabilistic circuits (PCs) represent a probability distribution as a computational graph. Enforcing structural properties on these graphs guarantees that several inference scenarios become tractable. Among these properties, structured decomposability is a particularly appealing one: it enables the efficient and exact computations of the probability of complex logical formulas, and can be used to reason about the expected output of certain predictive models under missing data. This paper proposes Strudel, a simple, fast and accurate learning algorithm for structured-decomposable PCs. Compared to prior work for learning structured-decomposable PCs, Strudel delivers more accurate single PC models in fewer iterations, and dramatically scales learning when building ensembles of PCs. It achieves this scalability by exploiting another structural property of PCs, called determinism, and by sharing the same computational graph across mixture components. We show these advantages on standard density estimation benchmarks and challenging inference scenarios.
BibTeX
@inproceedings{dang2020strudel,
  author = {Meihua Dang and Antonio Vergari and Guy Van den Broeck},
  title = {{Strudel: Learning Structured-Decomposable Probabilistic Circuits}},
  booktitle = {PGM},
  year = {2020},
  url = {https://openreview.net/forum?id=VGehIYxsnY},
}
Figure