Setting up the environment
import numpy as np
%install_ext https://sml.forge.nicta.com.au/isml15/data/tikzmagic.py
%load_ext tikzmagic
The aim of this exercise is to implement the sum product algorithm on a chain graph.
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) $$
Construct a larger example where there is even more computational savings.
Consider the following factor graph.
%%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 goes here