Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Pixel Club Seminar: The Norm-Product Algorithm: Convergent Message-Passing for LP-relaxation and Approximate Inference
event speaker icon
Tamir Hazan (School of Engineering and Computer Science The Hebrew University of Jerusalem)
event date icon
Tuesday, 31.03.2009, 11:30
event location icon
EE Meyer Building 1061
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.

* PhD research under the supervision of Prof. Amnon Shashua