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