Incremental region selection for mini-bucket elimination bounds
Sholeh Forouzan, Alexander Ihler · 2015
Region choice is a key issue for many approxi-mate inference bounds. Mini-bucket elimination avoids the space and time complexity of exact inference by using a top-down partitioning ap-proach that mimics the construction of a junc-tion tree and aims to minimize the number of re-gions subject to a bound on their size; however, these methods rarely take into account functions’ values. In contrast, message passing algorithms often use “cluster pursuit ” methods to select re-gions, a bottom-up approach in which a pre-defined set of clusters (such as triplets) is scored and incrementally added. In this work, we de-velop a hybrid approach that balances the advan-tages of both perspectives, providing larger re-gions chosen in an intelligent, energy-based way. Our method is applicable to bounds on a variety of inference tasks, and we demonstrate its power empirically on a broad array of problem types. 1