Abstract
Maximum-a-Posteriori (MAP) inference is a fundamental task in graphical models and structured prediction. While Linear Programming (LP) relaxations provide a powerful framework for approximate inference, they often become computationally intractable when the output domain is large. This paper introduces GDMM (Greedy Direction Method of Multiplier), an algorithm that combines Augmented Lagrangian methods with an active-set strategy and greedy variable selection. GDMM achieves orders-of-magnitude speedups and significant memory savings compared to traditional LP solvers by focusing on a small, relevant fraction of labels.
Introduction
In fields such as computer vision and computational biology, MAP inference is used to find the most likely configuration of a system. For instance, in protein folding, the goal is to determine the most probable 3D orientation for each amino acid. However, as the number of possible labels per variable grows, the complexity of pairwise factors increases quadratically, often leading to intractable memory requirements and slow convergence for standard optimization algorithms.
Methodology: The GDMM Approach
GDMM addresses the scalability bottleneck by treating MAP inference through the lens of the Augmented Lagrangian Method (ALM). The core innovations include:
- Active Set Strategy: Instead of optimizing over the entire label space, GDMM maintains a small "active set" of currently relevant labels for each variable.
- Greedy Direction Updates: The algorithm employs greedy optimization techniques, such as variants of Frank-Wolfe and Block-Greedy Coordinate Descent, to efficiently select new labels for the active set.
- Sublinear Search: By utilizing pre-built data structures like sorted lists of local scores, GDMM identifies the most promising greedy directions in sublinear time, avoiding exhaustive scans of the label space.
- On-Demand Variable Instantiation: Variables and factors are introduced only when required by the optimization process, maintaining a sparse internal representation.
The authors provide two algorithmic variants: one optimized for large label sets per variable and another for problems with a massive number of binary factors, such as multi-label prediction.
Experimental Evaluation
GDMM was evaluated across five diverse benchmarks:
- Protein Folding: Dense interactions with 404 states per variable.
- Graph Matching: Social network data with 1,034 states per variable.
- Segmentation & Image Alignment: Standard computer vision tasks from the PASCAL challenge.
- MultiLabel Prediction: The EurLex dataset, featuring over 7.5 million factors.
Key Results
GDMM demonstrated superior performance, particularly on large-domain problems where traditional solvers often fail.
Speed and Scalability
On the Protein Folding task, GDMM reached the best objective in 661 seconds, significantly outperforming competitors like TRWS and MPLP, which either took over 10,000 seconds or failed to reach comparable solution quality. In the MultiLabel dataset with millions of factors, GDMM was the fastest to reach the optimal primal objective.
Memory Efficiency
Memory usage is a critical bottleneck for large-scale matching. While traditional solvers like AD3 or MPLP required over 100GB of RAM for the Graph Matching task, GDMM solved the same problem using only 260MB. This efficiency allows GDMM to run on standard hardware where other methods are unusable.
Conclusion
GDMM provides a highly efficient and scalable framework for MAP inference in graphical models with massive label spaces. By mathematically exploiting the natural sparsity of real-world problems, it achieves significant gains in both speed and memory usage. Future research may explore hybridizing GDMM with tree-based message-passing algorithms to further improve performance on grid-structured problems.
Summary updated