Inference Through Self-Avoiding Walk
Devavrat Shah
Department of Electrical Engineering and Computer Science
Massachusetts Institute of Technology
Tuesday, October 31, 2006
4:30 - 5:30 PM
Terman Engineering Center, Room 453
Abstract:
Inference in Markov Random Field has many applications including
coding, computer vision, discrete optimization and networks. In this
talk, we will present the following surprising equivalence for any
binary pair-wise Markov Random Field (MRF) on a graph G: the
max-marginal (resp. marginal probability) of a node, say v, in G is
the same as the max-marginal (resp. marg. prob.) of the root node of
the tree MRF obtained by performing a self-avoiding walk on G starting
from v. This can be seen as a generalization of a recent result of
D. Weitz (2006) for hard-core model for computing marginal
probability.
We will present three important implications of this result for
inference. First, we present corrections of the Max-product (MP) and
Sum-product (BP) algorithms in the presence of cycles to obtain exact
MAP or marg. prob. by means of a message-passing algorithm unlike the
complicated centralized junction-tree algorithm. Second, we present a
natural heuristic based on the algorithm for exact
inference. Representative experimental results show that it is more
effective than the TRW algorithm in many cases. Third, we present
analytic error bounds on the performance of BP for graphs with cycles
in terms of structural properties of the MRF G. We will also present
results about size of self-avoiding walk tree for sparse graphs.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html