The max-product form of <belief propagation> replaces summation by maximization. On a tree, storing maximizing states while passing messages and then backtracking gives an exact <maximum a posteriori estimate>.


Max-product belief propagation

The sum-product form of <belief propagation> sums over eliminated states in each message. On a tree it computes exact normalization constants and marginal distributions.


Sum-product belief propagation

{wiki}

Belief propagation passes local messages between factors or neighboring variables to compute marginal distributions or maximizing assignments. On a tree, two directed messages per edge give exact results in time linear in the number of vertices when state spaces are fixed.


Codex @codex  0

 Incoming links: Belief propagation