Timezone: »
We consider the problem of finding the M assignments with maximum probability in a probabilistic graphical model. We show how this problem can be formulated as a linear program (LP) on a particular polytope. We prove that, for tree graphs (and junction trees in general), this polytope has a particularly simple form and differs from the marginal polytope in a single inequality constraint. We use this characterization to provide an approximation scheme for nontree graphs, by using the set of spanning trees over such graphs. The method we present puts the Mbest inference problem in the context of LP relaxations, which have recently received considerable attention and have proven useful in solving difficult inference problems. We show empirically that our method often finds the provably exact M best configurations for problems of high tree width.
Author Information
Menachem Fromer (Hebrew University)
Amir Globerson (Tel Aviv University, Google)
Amir Globerson is senior lecturer at the School of Engineering and Computer Science at the Hebrew University. He received a PhD in computational neuroscience from the Hebrew University, and was a Rothschild postdoctoral fellow at MIT. He joined the Hebrew University in 2008. His research interests include graphical models and probabilistic inference, convex optimization, robust learning and natural language processing.
Related Events (a corresponding poster, oral, or spotlight)

2009 Oral: An LP View of the MBest MAP Problem »
Wed Dec 9th 11:00  11:20 PM Room None
More from the Same Authors

2021 Poster: A Theoretical Analysis of Finetuning with Linear Teachers »
Gal Shachaf · Alon Brutzkus · Amir Globerson 
2020 Poster: Regularizing Towards Permutation Invariance In Recurrent Models »
Edo CohenKarlik · Avichai Ben David · Amir Globerson 
2018 Poster: Mapping Images to Scene Graphs with PermutationInvariant Structured Prediction »
Roei Herzig · Moshiko Raboh · Gal Chechik · Jonathan Berant · Amir Globerson 
2017 Poster: Robust Conditional Probabilities »
Yoav Wald · Amir Globerson 
2016 Poster: Optimal Tagging with Markov Chain Optimization »
Nir Rosenfeld · Amir Globerson 
2012 Poster: Convergence Rate Analysis of MAP Coordinate Minimization Algorithms »
Ofer Meshi · Tommi Jaakkola · Amir Globerson 
2011 Session: Spotlight Session 3 »
Amir Globerson 
2011 Session: Oral Session 3 »
Amir Globerson 
2011 Tutorial: Linear Programming Relaxations for Graphical Models »
Amir Globerson · Tommi Jaakkola 
2010 Spotlight: More data means less inference: A pseudomax approach to structured learning »
David Sontag · Ofer Meshi · Tommi Jaakkola · Amir Globerson 
2010 Poster: More data means less inference: A pseudomax approach to structured learning »
David Sontag · Ofer Meshi · Tommi Jaakkola · Amir Globerson 
2009 Workshop: Approximate Learning of Large Scale Graphical Models »
Russ Salakhutdinov · Amir Globerson · David Sontag 
2008 Workshop: Approximate inference  how far have we come? »
Amir Globerson · David Sontag · Tommi Jaakkola 
2008 Poster: Clusters and Coarse Partitions in LP Relaxations »
David Sontag · Amir Globerson · Tommi Jaakkola 
2008 Spotlight: Clusters and Coarse Partitions in LP Relaxations »
David Sontag · Amir Globerson · Tommi Jaakkola 
2007 Poster: Convex Learning with Invariances »
Choon Hui Teo · Amir Globerson · Sam T Roweis · Alex Smola 
2007 Spotlight: Convex Learning with Invariances »
Choon Hui Teo · Amir Globerson · Sam T Roweis · Alex Smola 
2007 Poster: Fixing MaxProduct: Convergent Message Passing Algorithms for MAP LPRelaxations »
Amir Globerson · Tommi Jaakkola 
2006 Talk: Approximate inference using planar graph decomposition »
Amir Globerson · Tommi Jaakkola 
2006 Poster: Approximate inference using planar graph decomposition »
Amir Globerson · Tommi Jaakkola