Efficient and Exact MAP-MRF Inference using Branch and Bound

Min Sun, Murali Telaprolu, Honglak Lee, Silvio SavareseAISTATS 2012 · OpenReview

Abstract

We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states $H$ per variable. By organizing the data in a suitable structure, specifically a Range Maximum Query (RMQ) data structure, the authors reduce the per-branch complexity of evaluating bounds from $O(H^2)$ to $O(H)$. This enables exact inference in large-scale problems such as human pose estimation and protein design, where traditional methods struggle due to quadratic scaling with the state space size.

Introduction

Markov Random Fields (MRFs) are a cornerstone of computer vision and computational biology, used to model complex interactions between discrete variables. A fundamental task is MAP inference: finding the single most likely configuration of all variables. Unfortunately, for general MRFs, this is NP-hard. While researchers often use Linear Programming Relaxation (LPR) to approximate the solution, these approximations frequently fail to provide the exact answer in real-world scenarios. Exact methods exist, such as Cluster Pursuit (CP) or standard Branch-and-Bound, but they struggle when variables have a large number of possible states ($H$). For instance, in human pose estimation, standard methods become prohibitively slow because their inner loops scale quadratically ($O(H^2)$) with the number of states.

Methodology

The authors propose two novel BB methods, with the "Efficient BB" being the primary contribution. Their approach rests on three pillars:

1. Complexity Reduction via RMQ

The core bottleneck in BB is calculating the upper bound at each branch. By fixing the dual potentials after an initial optimization phase, the authors show that the bound calculation can be treated as a series of range queries. They use a Range Maximum Query (RMQ) data structure (a "max-tree") to answer these queries in constant time. This reduces the per-branch complexity from $O(H^2)$ to $O(H)$.

The RMQ data structure allows for constant-time maximum queries over a range of states, drastically reducing per-branch complexity.

2. Guided Variable Selection (GVS)

To decide which variable to split (branch) on, they introduce a new heuristic called Node-wise Local Primal Dual Gap (NLPDG). This metric identifies which variables contribute most to the gap between the current upper and lower bounds, prioritizing them for branching to prune the search space faster.

3. Variable State Ordering (VSO)

Since RMQ operates on contiguous ranges of states, the order of states matters. The authors use domain knowledge—such as spatial proximity in images—to order states so that "likely" or "related" states are grouped together, making the pruning process much more effective.

Experimental Evaluation

The methods were evaluated on three distinct types of problems:

  • Synthetic Data: MRFs with varying sparsity patterns (Main-Band, Stripes, and Dense) to test scalability against the number of variables ($N$) and states ($H$).
  • Human Pose Estimation (HPE): Using the Buffy dataset, which involves estimating the 2D locations and orientations of six body parts in video frames.
  • Protein Design: A dataset of protein side-chain placement problems, characterized by very large state spaces (up to 180 states per variable).

Key Results

The proposed "Efficient BB" method significantly outperformed state-of-the-art exact inference algorithms:

Scalability and Speed

In synthetic tests, the method consistently solved problems with thousands more states than competing methods within a fixed time budget. On the Buffy human pose dataset, the method was 10x faster on average than Cluster Pursuit (CP), and up to 600x faster on difficult instances.

Performance on dense synthetic MRFs shows that the proposed method (Our+GVS) maintains efficiency as the number of variables increases, unlike traditional baselines.

Protein Design

The method solved more protein design problems than CP within the same time limit and was 5.8x faster on average when solving the same number of problems.

Conclusion

By leveraging efficient data structures like RMQ, this work demonstrates that exact MAP-MRF inference can be scaled to problems with large state spaces. The reduction of per-branch complexity from $O(H^2)$ to $O(H)$ is a significant algorithmic advancement, enabling the use of exact methods in domains where they were previously considered impractical.

Summary updated

Abstract

We propose two novel Branch-and-Bound (BB) methods to efficiently solve exact MAP-MRF inference on problems with a large number of states (per variable) H. By organizing the data in a suitable stru...
BibTeX
@inproceedings{sun2012efficient,
  author = {Min Sun and Murali Telaprolu and Honglak Lee and Silvio Savarese},
  title = {{Efficient and Exact MAP-MRF Inference using Branch and Bound}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=3VCHhogAB3T},
}
Figure