The Taub Faculty of Computer Science Events and Talks

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