Revisiting MAP Estimation, Message Passing and Perfect Graphs

James Foulds, Nicholas Navaroli, Padhraic Smyth, Alexander Ihler
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:278-286, 2011.

Abstract

Given a graphical model, one of them ost useful queries is to find the most likely configuration of its variables. This task, known as the maximum a posteriori (MAP) problem, can be solved efficiently via message passing techniques when the graph is a tree, but is NP-hard for general graphs. Jebara (2009) shows that the MAP problem can be converted into the stable set problem, which can be solved in polynomial time for a broad class of graphs known as perfect graphs via a linear programming relaxation technique. This is a result of great theoretical interest. However, the article additionally claims that max-product linear programming (MPLP) message passing techniques of Globerson and Jaakkola (2007) are also guaranteed to solve these problems exactly and efficiently. We investigate this claim, show that it does not hold, and repair it with alternative message passing algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-foulds11a, title = {Revisiting MAP Estimation, Message Passing and Perfect Graphs}, author = {Foulds, James and Navaroli, Nicholas and Smyth, Padhraic and Ihler, Alexander}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {278--286}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/foulds11a/foulds11a.pdf}, url = {https://proceedings.mlr.press/v15/foulds11a.html}, abstract = {Given a graphical model, one of them ost useful queries is to find the most likely configuration of its variables. This task, known as the maximum a posteriori (MAP) problem, can be solved efficiently via message passing techniques when the graph is a tree, but is NP-hard for general graphs. Jebara (2009) shows that the MAP problem can be converted into the stable set problem, which can be solved in polynomial time for a broad class of graphs known as perfect graphs via a linear programming relaxation technique. This is a result of great theoretical interest. However, the article additionally claims that max-product linear programming (MPLP) message passing techniques of Globerson and Jaakkola (2007) are also guaranteed to solve these problems exactly and efficiently. We investigate this claim, show that it does not hold, and repair it with alternative message passing algorithms.} }
Endnote
%0 Conference Paper %T Revisiting MAP Estimation, Message Passing and Perfect Graphs %A James Foulds %A Nicholas Navaroli %A Padhraic Smyth %A Alexander Ihler %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-foulds11a %I PMLR %P 278--286 %U https://proceedings.mlr.press/v15/foulds11a.html %V 15 %X Given a graphical model, one of them ost useful queries is to find the most likely configuration of its variables. This task, known as the maximum a posteriori (MAP) problem, can be solved efficiently via message passing techniques when the graph is a tree, but is NP-hard for general graphs. Jebara (2009) shows that the MAP problem can be converted into the stable set problem, which can be solved in polynomial time for a broad class of graphs known as perfect graphs via a linear programming relaxation technique. This is a result of great theoretical interest. However, the article additionally claims that max-product linear programming (MPLP) message passing techniques of Globerson and Jaakkola (2007) are also guaranteed to solve these problems exactly and efficiently. We investigate this claim, show that it does not hold, and repair it with alternative message passing algorithms.
RIS
TY - CPAPER TI - Revisiting MAP Estimation, Message Passing and Perfect Graphs AU - James Foulds AU - Nicholas Navaroli AU - Padhraic Smyth AU - Alexander Ihler BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-foulds11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 278 EP - 286 L1 - http://proceedings.mlr.press/v15/foulds11a/foulds11a.pdf UR - https://proceedings.mlr.press/v15/foulds11a.html AB - Given a graphical model, one of them ost useful queries is to find the most likely configuration of its variables. This task, known as the maximum a posteriori (MAP) problem, can be solved efficiently via message passing techniques when the graph is a tree, but is NP-hard for general graphs. Jebara (2009) shows that the MAP problem can be converted into the stable set problem, which can be solved in polynomial time for a broad class of graphs known as perfect graphs via a linear programming relaxation technique. This is a result of great theoretical interest. However, the article additionally claims that max-product linear programming (MPLP) message passing techniques of Globerson and Jaakkola (2007) are also guaranteed to solve these problems exactly and efficiently. We investigate this claim, show that it does not hold, and repair it with alternative message passing algorithms. ER -
APA
Foulds, J., Navaroli, N., Smyth, P. & Ihler, A.. (2011). Revisiting MAP Estimation, Message Passing and Perfect Graphs. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:278-286 Available from https://proceedings.mlr.press/v15/foulds11a.html.

Related Material