Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
On MAP Inference by MWSS on Perfect Graphs
Adrian Weller, Tony Jebara
Abstract:
Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a maximum weight stable set (MWSS) on a derived weighted graph, which if perfect, allows inference in polynomial time. We derive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which binary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, improves our toolbox and expands the range of tractable models.
Keywords:
Pages: 684-693
PS Link:
PDF Link: /papers/13/p684-weller.pdf
BibTex:
@INPROCEEDINGS{Weller13,
AUTHOR = "Adrian Weller and Tony Jebara",
TITLE = "On MAP Inference by MWSS on Perfect Graphs",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "684--693"
}


hosted by DSL   •   site info   •   help