max-product on trees

(55 minutes to learn)


Max-product is an algorithm for MAP estimation in graphical models, based on dynamic programming. It is a generalization of the Viterbi algorithm for hidden Markov models.


This concept has the prerequisites:

Core resources (read/watch one of the following)


Supplemental resources (the following are optional, but you may find them useful)


Information Theory, Inference, and Learning Algorithms
A graudate-level textbook on machine learning and information theory.
Author: David MacKay
Coursera: Probabilistic Graphical Models (2013)
An online course on probabilistic graphical models.
Author: Daphne Koller
Other notes:
  • These lectures describe the junction tree (or clique tree) algorithm, a way of applying BP to general graphs. The notation differs significantly from the more traditional formulation of BP on factor graphs.
  • Click on "Preview" to see the videos.


See also