----------------------------

DATE:  Tuesday, November 24

TIME:  3 pm

PLACE: 303 Mudd

SPEAKER: Tony Jebara

TITLE: MAP Estimation with Perfect Graphs

ABSTRACT: A graphical model is an undirected graph representing the factorization of a probability distribution function of many random variables. Efficiently finding the maximum a posteriori (MAP) configuration of such probability functions is an important problem in machine learning and statistics. Therein, MAP estimation is often implemented using message passing algorithms or linear programming. Unfortunately, these algorithms are only optimal for singly-connected graphs such as trees. We have recently shown that matching and b-matching problems also admit exact MAP estimation under message passing even though the corresponding graphical models are loopy. Upgrading beyond trees and matchings leads us to the fascinating family of so-called perfect graphs. While MAP estimation in general loopy graphical models is NP, some can be converted into perfect graphs where the problem is in P. This result leverages recent progress in defining perfect graphs (the strong perfect graph theorem), linear programming relaxations of MAP estimation and recent convergent message passing schemes. In particular, we convert any graphical model into a so-called nand Markov random field. This model is straightforward to relax into a linear program whose integrality can be established by testing for graph perfection. This perfection test is performed efficiently using a recent polynomial time algorithm. Alternatively, known decomposition tools from perfect graph theory may be used to prove perfection in some cases. Thus, a general graph framework is provided for determining when MAP estimation in any graphical model is in P, has an integral linear programming relaxation and is exactly recoverable by message passing.