Deep Bucket Elimination

Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, Rina Dechter

Abstract

Deep Bucket Elimination (DBE) is a hybrid approach that integrates neural network approximations into the classical Bucket Elimination algorithm for probabilistic graphical models. By replacing memory-intensive tabular messages with compact neural networks, DBE overcomes the exponential spatial complexity bottleneck of exact inference. We introduce MaskedNet, a specialized architecture to handle deterministic constraints, and demonstrate that DBE provides significantly more accurate estimates of the partition function compared to state-of-the-art approximation methods like Weighted Mini-Bucket on complex benchmarks.

Introduction

Computing the partition function ($Z$) is a fundamental task in Probabilistic Graphical Models (PGMs), such as Bayesian networks and Markov random fields. It is essential for normalizing probabilities in applications ranging from genetic linkage analysis to protein design. The standard exact algorithm, Bucket Elimination (BE), processes variables sequentially, but its spatial complexity is exponential in the graph's induced-width. For highly interconnected models, the resulting tabular messages quickly exceed available RAM.

Approximate methods like Weighted Mini-Bucket (WMB) mitigate this by splitting large messages, but they face a hard accuracy ceiling once memory limits are reached. Deep Bucket Elimination (DBE) addresses this by shifting the bottleneck from memory to computation.

Methodology: Neural Message Approximation

DBE replaces large tabular messages with neural network approximations. When a message's scope exceeds a predefined threshold (the $i$-bound), the algorithm generates samples from the bucket and trains a neural network to approximate the resulting function.

MaskedNet for Deterministic Constraints

Standard feedforward networks often struggle with "hard" logic—situations where probabilities are exactly zero. To handle these deterministic constraints common in real-world datasets, the authors developed MaskedNet. This architecture features a dual-path design: one path predicts a binary mask (indicating if the output is zero), while the other predicts the real value.

The MaskedNet architecture uses a dual-path approach to handle deterministic constraints by predicting both a binary mask and a real value.

These trained networks are integrated back into the elimination process as "virtual" buckets, allowing the algorithm to scale to problems with high induced-width without crashing due to memory exhaustion.

Experimental Evaluation

The authors evaluated DBE on 25 instances from the UAI repository, including Grid models, Pedigree analysis, and Dynamic Bayesian Networks (DBNs).

Key Results on Grid Benchmarks

On challenging Grid instances where the induced-width significantly exceeds the $i$-bound, DBE demonstrated superior accuracy over WMB. For instance, on a grid with an induced-width of 27, WMB's log-error was 122.91, whereas DBE achieved a much lower error of 17.8.

Comparative performance of DBE and WMB on Grid instances (i-bound=10). DBE consistently achieves lower average error on high-width models.

Discussion and Conclusion

DBE represents a significant shift in PGM inference, trading training time for memory efficiency. While WMB is faster, its accuracy is physically bounded by RAM. DBE continues to improve as training time increases. The primary limitation is the computational overhead of training multiple neural networks per instance. Future work aims to reduce this overhead through transfer learning and more efficient sampling strategies.

Summary updated

Abstract

Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly. However, it often requires exponentially high levels of memory (in the induced-width) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE. The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function. We provide a proof-of-concept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current state-of-the-art approaches for approximating BE (e.g. the mini-bucket schemes), especially when problems are sufficiently hard.
BibTeX
@inproceedings{razeghi2021deep,
  author = {Yasaman Razeghi and Kalev Kask and Yadong Lu and Pierre Baldi and Sakshi Agarwal and Rina Dechter},
  title = {{Deep Bucket Elimination}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/582},
}
Figure