Strudel: Learning Structured-Decomposable Probabilistic Circuits

Meihua Dang, Antonio Vergari, Guy Van den Broeck

TL;DR

This paper introduces STRUDEL, a new algorithm for learning structured-decomposable probabilistic circuits (PCs). STRUDEL is significantly faster and more accurate than previous methods, especially for learning ensembles of PCs, by leveraging circuit flows and a greedy search strategy. This work makes advanced probabilistic reasoning more accessible and scalable.

What Problem Does This Paper Address?

Many real-world applications, such as decision-making in sensitive domains like healthcare and finance, require exact and efficient probabilistic reasoning. Traditional probabilistic models like Bayesian networks often struggle with these demands. Tractable probabilistic models (TPMs) offer a solution by guaranteeing exact and efficient inference. Probabilistic Circuits (PCs) are a unifying framework for various TPMs, and a key structural property, "structured decomposability," enables a wide range of advanced queries. However, learning these structured-decomposable PCs from data has been a bottleneck, with existing methods being slow and difficult to scale, especially for learning multiple PCs (ensembles). This paper addresses this gap by proposing STRUDEL, a faster and more accurate learning algorithm for structured-decomposable PCs.

Methods

STRUDEL introduces several key innovations to overcome the limitations of prior work:

  • Greedy Structure Learning: Instead of computationally expensive likelihood-based search, STRUDEL employs a greedy approach. It starts with a structured-decomposable PC derived from a Chow-Liu tree (a type of Bayesian network) and iteratively refines it using a "split" operation. This significantly speeds up the learning process.
  • Efficient Splitting Heuristics: STRUDEL uses novel heuristics, EFLOW and vMI, to guide the splitting process. EFLOW selects edges that are frequently traversed by data samples, while vMI selects variables that are highly dependent on others within the scope of a node. These heuristics are more efficient than traditional methods and lead to better circuit structures.
  • Circuit Flows for Parameter Learning and Inference: The paper leverages "circuit flows," a mechanism that exploits the deterministic property of PCs. Circuit flows allow for vectorized computation of likelihoods and closed-form parameter estimation, dramatically speeding up both inference and learning, especially for ensembles.
  • Shared-Structure Ensembles: For learning mixtures of PCs, STRUDEL proposes a strategy where all components share the same learned structure. This drastically reduces the computational cost of learning ensembles, as structure learning is performed only once.

Datasets

The paper evaluates STRUDEL on 20 standard density estimation benchmark datasets. Specific datasets mentioned include: NLTCS, MSNBC, KDD, PLANTS, AUDIO, JESTER, NETFLIX, ACCIDENTS, RETAIL, PUMSB-STAR, DNA, KOSAREK, MSWEB, BOOK, EACHMOVIE, WEBKB, ROUTERS-52, 20NEWS-GRP, BBC, and AD. Additionally, the paper uses datasets for evaluating expected predictions of regression models, specifically mentioning "Abalone," "Delta," "Elevators," and "Insurance."

Key Insights and Ideas

  • Chow-Liu Trees as a Strong Starting Point: Initializing STRUDEL with a PC derived from a Chow-Liu tree (a tree-structured Bayesian network) provides a much better starting point for learning structured-decomposable PCs compared to a fully-factorized distribution. This significantly improves accuracy and reduces learning time.
  • Greedy Search Outperforms Expensive Search: The paper demonstrates that a fast, greedy search strategy can achieve competitive or even superior accuracy compared to more computationally intensive methods that rely on penalized likelihood scores.
  • Circuit Flows are Key to Scalability: The efficient computation enabled by circuit flows is crucial for scaling learning to large ensembles of PCs. This technique allows for significant speedups in both inference and parameter learning.
  • Shared Structure for Ensembles is Effective: Learning ensembles where all components share the same PC structure is a highly effective and efficient strategy for improving performance without the prohibitive cost of learning independent structures for each component.

Key Results

  • Accuracy: STRUDEL consistently learns more accurate single PCs than its main competitor, LEARNPSDD, on 10 out of 20 datasets and achieves comparable accuracy sooner.
  • Speed: STRUDEL is dramatically faster than LEARNPSDD, requiring a fraction of the time per iteration and total learning time. For example, it takes at least an order of magnitude less time per iteration.
  • Ensembles: STRUDEL-EM and STRUDEL-BEM (ensemble variants) outperform LEARNPSDD-EM and LEARNPSDD-BEM on most datasets. The shared-structure approach significantly reduces learning times for large mixtures.
  • Circuit Flows Speedup: The circuit flow approach for evaluating ensembles is orders of magnitude faster (up to 4591 times faster on one dataset) than classical bottom-up evaluation.
  • Advanced Queries: STRUDEL-learned PCs are shown to be effective for advanced probabilistic queries, such as computing expected predictions of regressors with missing data, outperforming imputation schemes.

Limitations and Future Work

  • Circuit Size: STRUDEL tends to learn larger circuits than LEARNPSDD because it does not explicitly penalize circuit size during learning. However, the paper argues this increase is often on the same order of magnitude and a negligible price for the speedup.
  • Heuristics Impact: While EFLOW-vMI is chosen as the default heuristic, the paper notes that EFLOW-vRAND can lead to slightly more accurate PCs but at the cost of significantly larger circuits and slower learning.
  • Future Work: The paper suggests STRUDEL can serve as an initial stepping stone for learning PCs in various applications requiring advanced probabilistic inference, implying its potential for further development and application in new domains. The authors also mention that their shared-structure ensemble strategy is compatible with classical ensembling schemes like EM, bagging, and boosting, suggesting further exploration in these areas.

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},
}

Loading related content...

Figure