Campus Event Calendar
Event Entry
What and Who
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.
SWS, RG1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 19 July 2010
11:00
90 Minutes
E1 5
5th floor
Saarbrücken
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 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.
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.
Contact
Claudia Richter
9325 688
--email hidden
Video Broadcast
Yes
Kaiserslautern
G26
206
passcode not visible
logged in users only
Brigitta Hansen, 07/19/2010 16:12
Claudia Richter, 07/15/2010 13:39 -- Created document.
Claudia Richter, 07/15/2010 13:39 -- Created document.