New Mini-Bucket Partitioning Heuristics for Bounding the Probability of Evidence

Emma Rollon, Rina DechterAAAI 2010 · DOI

Introduction

Reasoning in graphical models, such as Bayesian or Markov networks, frequently requires "weighted counting" tasks, including calculating the probability of evidence or the partition function. These tasks are known to be #P-complete, making exact computation infeasible for large, dense networks. Mini-Bucket Elimination (MBE) is a widely used approximation algorithm that provides upper and lower bounds for these values by partitioning complex "buckets" of functions into smaller, more manageable "mini-buckets."

Historically, MBE has relied on "scope-based" heuristics, which partition functions based solely on their shared variables. This paper introduces a new class of "content-based" partitioning heuristics that analyze the actual numerical values within probability tables. By leveraging this internal data, the proposed heuristics achieve significantly tighter upper bounds for the probability of evidence, often surpassing state-of-the-art methods.

Methodology: Greedy Heuristic Partitioning

The authors frame the partitioning task as a search problem within a lattice of all possible partitions of a bucket. A partition is considered "finer" than another if it can be obtained by further splitting the latter's mini-buckets.

The lattice of partitions for a bucket containing four functions.

To navigate this lattice efficiently, the paper proposes several greedy heuristics:

  • Log Relative Error (LRE): Derived from first principles, this metric is "greedily optimal," minimizing the log relative error of the approximation at each step.
  • LMRE and MRE1: Heuristics based on Maximum Log Relative Error, providing alternative strategies for tightening bounds.
  • Combined MBE: An ensemble strategy that executes multiple heuristics and selects the tightest resulting bound, ensuring robustness across different problem structures.

These content-based metrics measure the "distance" between the exact bucket and its mini-bucket approximation, allowing the algorithm to group functions whose values align to minimize error.

Experimental Evaluation

The heuristics were evaluated on three challenging benchmarks from the UAI 2008 evaluation:

  1. Coding Networks: Complex networks used in error-correction.
  2. Two-layer Noisy-OR Networks (bn2o): Common in medical diagnosis and fault detection.
  3. Linkage Analysis (Pedigree): Genetic networks used to trace trait inheritance.

These benchmarks represent real-world scenarios where exact inference is computationally prohibitive.

Results and Discussion

Experimental results demonstrate that content-based heuristics consistently outperform traditional scope-based methods and established algorithms like Tree-Reweighted Belief Propagation (TRW) and Any-Time Bounding (ATB).

Performance comparison across Coding, Noisy-OR (bn2o), and Pedigree networks, showing log upper bounds and computation time.

Key findings include:

  • Accuracy: On coding networks, content-based heuristics improved upper bounds by over 50% compared to the next best method, and by orders of magnitude on specific instances.
  • Efficiency: While content-based heuristics are 2 to 3 times slower than scope-based methods due to the overhead of processing table values, the resulting increase in precision justifies the small polynomial time cost.
  • Resource Management: When memory is constrained (limiting the "z-bound"), employing a smarter partitioning heuristic is often more effective than simply trying to increase the size of the mini-buckets.

Conclusion

This work demonstrates that the numerical content of probability tables is a critical, yet previously overlooked, resource for improving Mini-Bucket Elimination. By moving beyond structural analysis to content-aware partitioning, the proposed heuristics provide a powerful tool for approximating complex probabilistic queries. Future work may involve extending these principles to lower bounds and other query types, such as Maximum A Posteriori (MAP) estimation.

Summary updated

BibTeX
@inproceedings{rollon2010new,
  author = {Emma Rollon and Rina Dechter},
  title = {{New Mini-Bucket Partitioning Heuristics for Bounding the Probability of Evidence}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7761},
}
Figure