# 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.

## 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