Max-Product Algorithm

Table of contents

  1. Algorithm

What is the most probable joint configuration \((a^*, b^*, c^*, d^*) = \arg \max_{a,b,c,d} p(a,b,c,d)\)?

  1. Calculate \(max p(a,b,c,d)\)
  2. Backtrack to find \((a^*, b^*, c^*, d^*) = \arg \max_{a,b,c,d}\)

max-product

Algorithm

In a tree argmaxes can be done by two passes of the max-product algorithm

  1. Pick one node as the root node
  2. Initialize:
    1. Messages from leaf factor nodes initialized to factors
    2. Messages from leaf variable nodes set to unity
  3. Step 1: Propagate messages from leaves to root
  4. Step 2: Propagate messages from root to leaves