[Colloquium] TTI-C Talk: Tamir Hazan (Hebrew University of Jerusalem)

[Julia MacGlashan]

When:              Wednesday, March 4 @ 11:00am (lunch will be provided
after talk)

Where:            TTI-C Conference Room #526, 6045 S Kenwood Ave, 5th Floor

Who:                Tamir Hazan (Hebrew University of Jerusalem)

Title:                 Convex Belief Propagation - Approximated inference
and LP-relaxations


We derive a one-parameter local message-passing algorithm, called
"norm-product",  which covers both the tasks of computing approximate
marginal probabilities and maximum a posteriori (MAP) assignment for general
graphical models. A parameter $\epsilon$ controls a perturbation term of a
"fractional entropy approximation" $\tilde H$ which includes Bethe,
Tree-reweighted (TRW) and convex entropy approximations. When $\tilde H$ is
the Bethe approximation, the settings $\epsilon=0$ and $\epsilon=1$ produce
the max-product and sum-product algorithms, respectively. When $\tilde H$ is
a convex entropy approximation and $\epsilon\rightarrow 0$, the algorithm is
a globally convergent Linear Programming (LP) relaxation of the MAP problem.
When $\tilde H$ is convex and $\epsilon=1$, norm-product is a globally
convergent algorithm for "convex free energies" for approximate marginal
probabilities, and when $\epsilon=0$ norm-product becomes a family of
convergent "max-product-like" algorithms for computing approximate MAP.

Contact:          Shai Shalev-Shwartz, TTI-C		shai at tti-c.org
834-6850



-------------- next part --------------
A non-text attachment was scrubbed...
Name: winmail.dat
Type: application/ms-tnef
Size: 7946 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090226/73862a36/attachment.bin