Abstract: Maximum-a-Posteriori (MAP) inference lies at the heart of Graphical Models and Structured Prediction. Despite the intractability of exact MAP inference, approximate methods
based on LP relaxations have exhibited superior performance across a wide range of applications. Yet for problems involving large output domains (i.e., the state space
for each variable is large), standard LP relaxations can easily give rise to a large number of variables and constraints which are beyond the limit of existing optimization algorithms. In this paper, we introduce an effective MAP inference method for problems with
large output domains. The method builds upon alternating minimization of an Augmented Lagrangian that exploits the sparsity of messages through greedy optimization
techniques. A key feature of our greedy approach is to introduce variables in an on demand manner with a pre-built data structure over local factors. This results in a
single-loop algorithm of sublinear cost per iteration
and O(log(1/eps))-type iteration complexity to achieve eps sub-optimality. In addition, we introduce a variant of GDMM
for binary MAP inference problems with a large number of factors. Empirically, the proposed algorithms demonstrate orders of magnitude speedup over state-of-the-art MAP inference techniques on MAP inference problems
including Segmentation, Protein Folding, Graph Matching, and Multilabel prediction with pairwise interaction.
Download: pdf
Citation
- Greedy Direction Method of Multiplier for MAP Inference of Large Output Domain (pdf, software)
X. Huang, I. Yen, R. Zhang, Q. Huang, P. Ravikumar, I. Dhillon.
In International Conference on Artificial Intelligence and Statistics (AISTATS), April 2017.
Bibtex: