Martin J. Wainwright, Tommi S. Jaakkola and Alan S. Willsky

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1269
August 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1269.pdf

We develop and analyze methods for computing provably optimal maximum a posteriori (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is met with equality if and only if the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: (a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and (b) a tree-reweighted message-passing algorithm that is related to but distinct from the max-product (min-sum) algorithm. Finally, we discuss the conditions that govern when the relaxation is tight, in which case the MAP configuration can be obtained. The analysis described here generalizes naturally to convex combinations of hypertree-structured distributions.

BibTeX citation:

@techreport{Wainwright:CSD-03-1269,
    Author = {Wainwright, Martin J. and Jaakkola, Tommi S. and Willsky, Alan S.},
    Title = {MAP Estimation via Agreement on (hyper)trees: Message-passing and Linear Programming Approaches},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5806.html},
    Number = {UCB/CSD-03-1269},
    Abstract = {We develop and analyze methods for computing provably optimal maximum a posteriori (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is met with equality if and only if the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: (a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and (b) a tree-reweighted message-passing algorithm that is related to but distinct from the max-product (min-sum) algorithm. Finally, we discuss the conditions that govern when the relaxation is tight, in which case the MAP configuration can be obtained. The analysis described here generalizes naturally to convex combinations of hypertree-structured distributions.}
}

EndNote citation:

%0 Report
%A Wainwright, Martin J.
%A Jaakkola, Tommi S.
%A Willsky, Alan S.
%T MAP Estimation via Agreement on (hyper)trees: Message-passing and Linear Programming Approaches
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1269
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5806.html
%F Wainwright:CSD-03-1269