M. Pawan Kumar
 
 

HOME

RESEARCH

PUBLICATIONS

GROUP

TALKS

TEACHING

CV

 

 

 

 

 

 

IMPROVED MOVES FOR TRUNCATED CONVEX MODELS

M. Pawan Kumar and P. Torr

 

Overview

We develop a new st-MINCUT based move making method for MAP estimation of discrete MRFs with arbitrary unary potentials and truncated convex pairwise potentials. We prove that our method provides the best known multiplicative bounds (same as the bounds obtained by solving the standard linear programming relaxation followed by randomized rounding) for these problems in polynomial time. We demonstrate the efficacy of our approach using synthetic and real data experiments.

The MAP Estimation Problem

A pairwise MRF is specified by the following: (i) a set of random variables V (shown as circles); (ii) a set of discrete labels (shown as trellises); and (iii) a neighborhood relationship over V (neighbors are shown connected to each other).

The energy of a labeling is the sum of two types of potentials: (i) unary potential of random variable Va taking a label li; and (ii) pairwise potential of neighboring random variables Va and Vb taking labels li and lj respectively.

MAP estimation (or energy minimization) requires us to obtain the lowest energy labeling, and is known to be NP-hard in general.

Truncated Convex Models

In this work, we are interested in the special case of the MAP estimation problem with arbitrary unary potentials and truncated convex pairwise potentials. Specifically, the pairwise potential of variables Va and Vb taking labels li and lj respectively is equal to wabmax{d(|i-j|),M}. Here wab > 0, d(.) is a convex function and M is the truncation factor.

Our Method

Given an MRF characterized by arbitrary unary potentials and truncated convex pairwise potentials, we develop an accurate st-MINCUT based algorithm to obtain its MAP labeling. The main steps of our algorithm are summarized below.

Initialization

• Choose an initial labeling for the MRF. For example, assign the label li to all random variables.

Iteration

• Set im = -1.
• While im < h-1 (where h is the number of labels)

- Define an interval of labels Im = [im+1,jm] where jm = min{im + L, h-1} and d(L) ≥ M. Here L is referred to as the length of the interval.
- Move from current labeling to new labeling such that the energy is minimized under the condition that each random variable can either retain its old label or choose a new label from the interval Im. If the corresponding energy function is non-submodular, then minimize a submodular upper bound instead.
- Set im = im + 1.

Termination

• Stop if the energy does not decrease for any interval Im, otherwise repeat Iteration.

Current Labeling
st-MINCUT
New Labeling

Note that, since we minimize a pairwise submodular function, each iteration of our algorithm only requires a single st-MINCUT for which several efficient algorithms exist.

Theoretical Properties

Our algorithm provides the best known worst-case multiplicative bounds for truncated convex models in polynomial time. Specifically,
• For the truncated linear model, when the interval length L = √2M we obtain a bound of 2 + √2.
• For the truncated quadratic model, when the interval length L = √M we obtain a bound of O(√M).
Note that the above bounds are equal to the multiplicative bounds obtained by the standard linear programming relaxation using randomized rounding. See [1] for more details on the properties of the linear programming relaxation.

Results

The graphs below show the results of various energy minimization algorithms, averaged over 100 randomly generated instances. Our approach, and the related range swap algorithm of [2], provide more accurate results than loopy belief propagation and other move making algorithms such as α expansion and αβ swap, and are more efficient than TRW-S, which attempts to solve the dual of the linear programming relaxation. We also note that, unlike our approach, the range swap algorithm does not provide any multiplicative bounds.

See our publications for more results.

Resources

All the datasets used in our experiments are publicly available. The code is available for download.

Publications

M. Pawan Kumar, O. Veksler and P. Torr
Improved Moves for Truncated Convex Models
In Journal of Machine Learning Research (JMLR), 2011

M. Pawan Kumar and P. Torr
Improved Moves for Truncated Convex Models
In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2008

Related Work

Also see our paper on obtaining the best worst-case multiplicative bounds for the metric labeling problem using an st-MINCUT based move making algorithm.

M. Pawan Kumar and D. Koller
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts
In Proceedings of Conference on Uncertainity in Artificial Intelligence (UAI), 2009

References

[1] C. Chekuri, S. Khanna, J. Naor and L. Zosin. Approximation algorithms for the metric labeling problem via a new linear programming formulation. In SODA, 2001.
[2] O. Veksler. Graph cut based optimization for MRFs with truncated convex priors. In CVPR, 2007.