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.

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.

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

In [ ]:

```
# Solution goes here
```