연사: 정교민
일시: 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.

댓글 0

번호 제목 글쓴이 날짜 조회 수
184 계산수학및과학계산세미나(3/14(금),16:30) 과사무실 2008.03.11 1379
183 학부생 콜로퀴엄 제2회 (한상근 교수) 상일 2008.03.10 1539
182 수리과학과 Colloquium(3/19(수),16:00) 과사무실 2008.03.07 1379
181 수리과학과 Colloquium (3/5(수),16:00) 과사무실 2008.03.03 1216
180 Discrete Math Seminar (김은정) 상일 2008.03.03 2219
179 Discrete Math Seminar (강미현) 상일 2008.03.03 1643
178 Discrete Math Seminar (Otfried Cheong) 상일 2008.03.03 1643
177 Combinatorics seminar 김장수36 2008.02.16 1199
176 Discrete Math Seminar 김장수36 2008.02.16 1323
175 수리과학과 Colloquium 과사무실 2008.02.15 1324
174 Special ColloquiumⅡ(Prof. Zhou Jian) 과사무실 2008.02.14 1267
173 Special ColloquiumⅠ(Prof. Zhou Jian) 과사무실 2008.02.14 1146
172 사영대수기하학 & 계산대수기하학 워크샵 III 과사무실 2008.02.12 1173
171 사영대수기하학 & 계산대수기하학 워크샵 II 과사무실 2008.02.12 1197
170 사영대수기하학 & 계산대수기하학 워크샵 I 과사무실 2008.02.12 1710
169 Isabelle Liousse교수 세미나 IV 과사무실 2008.01.30 1361
168 Isabelle Liousse교수 세미나 III 과사무실 2008.01.30 1258
167 Isabelle Liousse교수 세미나 II 과사무실 2008.01.30 1173
166 Isabelle Liousse교수 세미나 I 과사무실 2008.01.30 1246
» 응용수학 및 그래프이론 세미나 - 정교민(1.29(화), 16:00-17:00) 과사무실 2008.01.22 2709
OCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN"> 404 Not Found

Not Found

The requested URL was not found on this server.