Approximate Inference Algorithms for Doubling Dimensional Graphs and Minor Excluded Graphs
2008/01/29 Tue, 4PM-5PM
A Markov Ramdom Fields(MRF) is an n-dimensional random variable defined on a graph G such that the probability distribution of each node(assigned with one random variable) depends only on the value of its negihbors. Application of MRF includes Ising model in statistical physics, statistical language modelling in linguistics, and vision and graphics in computer science.
We present a new local approximation algorithm for computing MAP(Maximum a-posteriori) assignemt and log-partition function for arbitrary exponential family distribution represented by a pair-wise MRF. Our algorithm is based on decomposition of G into appropriately chosen small components; computing estimates locally in each of these components and then producing a global solution. Specifically, we show that if the underlying graph G either has finite doubling dimension or excludes some finite-sized graph as its minor (e.g. Planar graph) and has a finite degree bound, then our algorithm will produce solution for both questions within arbitrary accuracy. The running time of the algorithm is Theta(n) (n is the number of nodes in G), with constant dependent on accuracy and either doubling dimension or, maximum vertex degree and the size of the graph that is excluded as a minor (e.g. 3 for all Planar graphs).
As a (somewhat unexpected) consequence of our algorithmic result, we show that the normalized log-partition function (known as free-energy) for a class of regular MRFs (e.g. Ising model on 2-dimensional grid) will converge to a limit, that is computable, as the size of the MRF goes to infinity. This method may be of interest in its own right.
This work is a joint work with Devavrat Shah and appeared in NIPS(The Neural Information Processing Systems) 2007.