연사: 정교민
일시: 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 1271
183 학부생 콜로퀴엄 제2회 (한상근 교수) 상일 2008.03.10 1458
182 수리과학과 Colloquium(3/19(수),16:00) 과사무실 2008.03.07 1283
181 수리과학과 Colloquium (3/5(수),16:00) 과사무실 2008.03.03 1107
180 Discrete Math Seminar (김은정) 상일 2008.03.03 2140
179 Discrete Math Seminar (강미현) 상일 2008.03.03 1547
178 Discrete Math Seminar (Otfried Cheong) 상일 2008.03.03 1546
177 Combinatorics seminar 김장수36 2008.02.16 1093
176 Discrete Math Seminar 김장수36 2008.02.16 1215
175 수리과학과 Colloquium 과사무실 2008.02.15 1203
174 Special ColloquiumⅡ(Prof. Zhou Jian) 과사무실 2008.02.14 1135
173 Special ColloquiumⅠ(Prof. Zhou Jian) 과사무실 2008.02.14 1032
172 사영대수기하학 & 계산대수기하학 워크샵 III 과사무실 2008.02.12 1065
171 사영대수기하학 & 계산대수기하학 워크샵 II 과사무실 2008.02.12 1098
170 사영대수기하학 & 계산대수기하학 워크샵 I 과사무실 2008.02.12 1621
169 Isabelle Liousse교수 세미나 IV 과사무실 2008.01.30 1254
168 Isabelle Liousse교수 세미나 III 과사무실 2008.01.30 1165
167 Isabelle Liousse교수 세미나 II 과사무실 2008.01.30 1073
166 Isabelle Liousse교수 세미나 I 과사무실 2008.01.30 1136
» 응용수학 및 그래프이론 세미나 - 정교민(1.29(화), 16:00-17:00) 과사무실 2008.01.22 2607