Focussed Inference in Markov Random Fields with Local Primal-Dual Gaps

Tuesday, January 10, 2012 - 3:45pm


Wednesday, January 18, 2012
3:30 – 4:30 PM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: B.S. Manjunath

SPEAKER: Dhruv Batra
Research Assistant Professor, Toyota Technological Institute at Chicago

Title: Focussed Inference in Markov Random Fields with Local Primal-Dual


A large number of problems in computer vision, computational biology and
robotics can formulated as the search for the most probably state under
a discrete probabilistic model — known as the MAP inference problem in
Markov Random Fields (MRFs).

While a lot of progress has been made on the “static” version of this
problem, a number of situations require dynamic inference algorithms
that must adapt and reorder computation to focus on “important” parts of
the problem. In this talk I will describe one measure for identifying
such important parts of the problem — called Local Primal Dual Gaps
(LPDG). LPDG is based on complementary slackness conditions in the
Primal-Dual pair of Linear Programs (LP) in the LP relaxation of MAP
inference. We have found LPDG to be useful in a number of situations –
speeding-up message-passing algorithms by re-ordering message
computations (Tarlow et al. ICML ’11), speeding up alpha-expansion by
re-ordering label sweeps (Batra & Kohli CVPR ’11) and adaptive
tightening of the standard LP relaxation by choosing important
constraints to add (Batra et al. AISTATS ’11).

Time permitting, I will also talk about our recent work on the
M-Best-Mode problem, which involves extracting not just the most
probable solution, but also a /diverse/ set of top M most probable
solutions in discrete graphical models.

The talk is meant to be accessible to a broad audience. No background in
MRFs or discrete optimization is assumed.

Joint work with Pushmeet Kohli (MSRC), Vladimir Kolmogorov (IST),
Sebastian Nowozin (MSRC), Greg Shakhnarovich (TTIC), Daniel Tarlow
(UToronto) and Payman Yadollahpour (TTIC).


Dhruv Batra is a Research Assistant Professor at Toyota Technological
Institute at Chicago (TTIC), a philanthropically endowed academic
computer science institute affiliated with the University of Chicago. He
received his M.S. and Ph.D. degrees from Carnegie Mellon University in
2007 and 2010 respectively, advised by Tsuhan Chen. In the past, he has
held visiting positions at Cornell University and MIT.

His research interests include machine learning, computer vision and
applications of combinatorial optimization algorithms to learning and
vision tasks. Specifically, he is interested in structured prediction,
MAP inference in MRFs, max-margin methods, co-segmentation in multiple
images, and interactive 3D modelling.