Sum Product Algorithm

COMP4670/8600 - Introduction to Statistical Machine Learning - Tutorial 9

Setting up the environment

In [ ]:
import numpy as np

%install_ext https://sml.forge.nicta.com.au/isml15/data/tikzmagic.py
In [ ]:
%load_ext tikzmagic

The aim of this exercise is to implement the sum product algorithm on a chain graph.

Distributive law

The distributive property can be used to save computation, and is the basis of message passing and dynamic programming. See an anecdote about camels.

Consider the following equation: $$ 2*3 + 2*5 = 2 * (3+5) $$

  • How many mathematical operations (multiplications and additions) are on the left hand side?
  • How many mathematical operations are on the right hand side?

Construct a larger example where there is even more computational savings.

Solution description

Message passing

Consider the following factor graph.

In [ ]:
%%tikz --scale 2 --size 700,100 -f jpg
\tikzstyle{rv}=[circle, draw=black, fill=white, line width=0.5mm, minimum size=25pt, inner sep=0pt]
\tikzstyle{factor}=[rectangle, draw=black, fill=white, line width=0.5mm, minimum size=15pt, inner sep=0pt]
\tikzstyle{edge} = [draw, line width=1mm]

\node[rv,label=above:{A}] (a) at (0,0) {};
\node[rv,label=above:{B}] (b) at (2,0) {};
\node[rv,label=above:{C}] (c) at (4,0) {};

\node[factor,label=below:{f(A,B)}] (f) at (1,0) {};
\node[factor,label=below:{g(B,C)}] (g) at (3,0) {};
\node[factor,label=below:{h(C)}] (h) at (5,0) {};

\foreach \source/ \dest in {a/f, f/b, b/g, g/c, c/h}
        \path[edge] (\source) -- (\dest);

The factors are given by the following tables:

f(A,B) A=$\square$ A=$\bigcirc$ A = $\clubsuit$ A = $\heartsuit$ A = $\triangle$
B=$p$ 0.01 0.01 0.12 0.01 0.14
B=$q$ 0.03 0.15 0.01 0.01 0.01
B=$r$ 0.13 0.11 0.07 0.18 0.01
g(B,C) B=$p$ B=$q$ B=$r$
C=$w$ 0.05 0.06 0.07
C=$x$ 0.1 0.3 0.2
C=$y$ 0.03 0.02 0.1
C=$z$ 0.11 0.15 0.08
h(C)
C=$w$ 1.2
C=$x$ 3.2
C=$y$ 1.8
C=$z$ 2.3

Using the sum product algorithm, compute the marginal distribution of the random variable $B$.

Hint: Note that the factors are not normalised.

Solution description

In [ ]:
# Solution goes here