연사: 정교민
일시: 1.29 (화) 16:00-17:00
장소: 자연과학동 1409호
제목: Approximate Inference Algorithms for Doubling Dimensional
Graphs and Minor Excluded Graphs
초록:
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.