Approximate Inference: Decomposition Methods with Applications to Computer Vision

Abstract

Markov Random Field (MRF) provides an elegant and succinct abstraction to capture inter-dependency between a large number of random variables - applications abound in signal processing, computer vision, statistical physics, combinatorics, biology, etc. In most of these applications, the key task pertains inferring the most likely assignment (aka MAP). This problem is computationally hard in general. Therefore, various approximations have been developed that utilize graph structures of the MRF for efficient computation. For example, popular approaches like Belief Propagation (and its variants) work well when the underlying graph has large girth.

In the application of MRF to computer vision, graphs do have lots of short cycles, but they naturally posses some "geometry". We develop a new class of approximation algorithms that utilize "geometry" of the underlying graph to obtain efficient approximation with provable guarantees for the MAP inference problem. In this talk, I will explain basic ideas of the MRF model, and describe our algorithm based on simple local updates, that runs in essentially linear time in the size of the MRF. I will then describe its applications to image denoising and image segmentation.

Short bio

Kyomin Jung is an assistant professor at KAIST Computer Science department. He received his Ph.D. at MIT Mathematics in June 2009. During summers of his Ph.D., he has worked in Microsoft Research Cambridge (2008), IBM Watson Research (2007), Bell Labs (2006), and Samsung Advanced Institute of Technology (2005) respectively. His main research interest includes optimization problems in statistical inference, computational learning theory, and resource allocation in communication networks. He received B.Sc. in Mathematics from Seoul National Univ. in 2003, and he was an IMO(International Mathematical Olympiad) gold medalist in 1995.

Resources

• talk slide