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