Approximate Inference Algorithms in Markov Random Field with Their Applications
Kyomin Jung
KAIST
SWS Colloquium
Kyomin Jung is an assistant professor at KAIST CS department. He has
joint appointments in KAIST EE and Math departments. He received his
Ph.D. at MIT Mathematics in 2009. His main research interest includes
graphical models, complex network modeling and analysis, and machine
learning. During summers of his Ph.D., he worked at Microsoft Research
Cambridge (2008), IBM Watson Research (2007), Bell Labs Murray Hill
(2006), and Samsung Advanced Institute of Technology (2005)
respectively as research internships. He received his B.Sc. at Seoul
National Univ. Mathematics in 2003, and he won a gold medal in
IMO(International Mathematical Olympiad) 1995.
Markov Random Field (MRF) provides an elegant and succinct abstraction
to capture inter-dependency between a large number of random variables
- applications abound in communication networks, signal processing,
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 structure of the MRF for efficient computation. Popular
approaches like Belief Propagation (and its variants) work well when
the underlying graph has large girth, eg. sparse graphical codes like
LDPC codes.
In many applications of interest, graphs do have lots of short cycles,
but they naturally posses some ``geometry''. We develop a new class of
approximation algorithms that utilize geometry, which is called
polynomially growing, of the underlying graph to obtain efficient
approximation with provable guarantee for the inference problem.
In this talk, I will describe the main idea of the Belief Propagation,
and our new algorithm based on simple local updates. I will describe
their applications to wireless network and image processing.