| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference | Tamir Hazan
; Amnon Shashua
; | Date: |
18 Mar 2009 | Abstract: | In this paper we treat both forms of probabilistic inference, estimating
marginal probabilities of the joint distribution and finding the most probable
assignment, through a unified message-passing algorithm architecture. We
generalize the Belief Propagation (BP) algorithms of sum-product and
max-product and tree-rewaighted (TRW) sum and max product algorithms (TRBP) and
introduce a new set of convergent algorithms based on "convex-free-energy" and
Linear-Programming (LP) relaxation as a zero-temprature of a
convex-free-energy. The main idea of this work arises from taking a general
perspective on the existing BP and TRBP algorithms while observing that they
all are reductions from the basic optimization formula of $f + sum_i h_i$
where the function $f$ is an extended-valued, strictly convex but non-smooth
and the functions $h_i$ are extended-valued functions (not necessarily convex).
We use tools from convex duality to present the "primal-dual ascent" algorithm
which is an extension of the Bregman successive projection scheme and is
designed to handle optimization of the general type $f + sum_i h_i$. Mapping
the fractional-free-energy variational principle to this framework introduces
the "norm-product" message-passing. Special cases include sum-product and
max-product (BP algorithms) and the TRBP algorithms. When the
fractional-free-energy is set to be convex (convex-free-energy) the
norm-product is globally convergent for estimating of marginal probabilities
and for approximating the LP-relaxation. We also introduce another branch of
the norm-product, the "convex-max-product". The convex-max-product is
convergent (unlike max-product) and aims at solving the LP-relaxation. | Source: | arXiv, 0903.3127 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |