Poster ID: T 47

Efficient Exact Inference in Planar Ising Mo dels
Nicol N. Schraudolph and Dmitry Kamenetsky, NICTA & ANU
r ¨ ¨ Ising mo del: binary no des, no de p otentials r edges to bias no de

cut(planar Ising mo del)  p erfect matching(expanded dual)
bias
0

 p olynomial-time exact inference: ground states (MAP, margin viol.) · like graph cuts: fast & scalable r ¨ ¨ · need submo dularity r planarity partition function and marginals · improving earlier algorithms max-margin CRF: 100×100 grid

0

1

0

1