Colloquia, Seminars and Conference News
Title : Approximate inference algorithms for pair-wise Markov Random Fields
Date : December 5, 2008. (2:00 pm) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Kyomin Jung
Abstract:
Computing MAP(Maximum a-posteriori) assignemt and log-partition function are of central inference problems for pair-wise Markov Random Fields(MRF)
with applications including coding, statistical physics, and computer vision.
We present a new local approximation algorithm for these problems for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), on a graph G. 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 is either polynomially growing or excluding some finite-sized graph as its minor (e.g. Planar graph), 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.
We also propose an approximate algorithm for computation of MAP assignment with global counting constraint. This optimization problem is encountered in many low-level vision problems including image segmentation.
This is joint work with Pushmeet Kohli and Devavrat Shah.
Bio:Kyomin Jung is a Ph.D student at MIT department of mathematics and a member of LIDS(Laboratories for Information and Decision Systems) since Fall 2004. His thesis advisor is Devavrat Shah. His main research interest includes optimization problems
on statistical inference and learning, and design of routing and scheduling algorithm for wireless networks. He received B.Sc. in the department of mathematics, Seoul National Univ in 2003. He won a gold medal in IMO(International Mathematical Olympiad) 1995. During his Ph.D, he did reserach internship at Microsoft Research, Cambridge UK (2008), IBM T.J. Waston Research Center(2007), and Bell Labs (2006). In winter 2003-2004, He was a visiting scholar at Microsoft Research Theory group, Redmond.
[Back]
