Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain.

Area of Science:

• Machine Learning
• Artificial Intelligence
• Computer Vision

Background:

• Maximum-a-Posteriori (MAP) inference is crucial for Graphical Models and Structured Prediction.
• Existing LP relaxation methods struggle with large output domains due to computational complexity.
• Efficient MAP inference is vital for applications like image segmentation and protein folding.

Purpose of the Study:

• To develop an effective MAP inference method for problems with large output domains.
• To address the scalability limitations of current LP relaxation techniques.
• To improve the efficiency and applicability of MAP inference in complex scenarios.

Main Methods:

• An alternating minimization of an Augmented Lagrangian is employed, leveraging message sparsity.
• Greedy optimization techniques introduce variables on-demand using a data structure over local factors.
• A single-loop algorithm with sublinear cost per iteration and O(log(1/ε)) complexity is proposed.
• A variant of Generalized Dual Decomposition Method (GDMM) is introduced for binary MAP inference.

Main Results:

• The proposed method achieves ε sub-optimality efficiently.
• Empirical results show orders of magnitude speedup over state-of-the-art MAP inference techniques.
• The algorithms perform well on diverse problems including Segmentation, Protein Folding, Graph Matching, and Multilabel prediction.

Conclusions:

• The novel MAP inference method effectively handles large output domains.
• The greedy, on-demand variable introduction significantly enhances computational efficiency.
• The approach offers a substantial improvement for various structured prediction tasks.