(Sometimes called ‘The Sum Product Algorithm’)

The basic ‘inference problem’ in graphical models is – given a joint distribution, you want to compute the marginal distribution for a given variable.

One option – multiply out all factors and marginalise on that factor as previously explained. Problem: Table could be massive if you had 1000 variables or something.

Better to interleave multiplication and addition to keep it small.

This is easier than it sounds.

Sometimes the order that you eliminate variables makes a difference to the time it takes, as sometimes you’ll end up with massive amounts of data as you multiply out factors. Wont have much of an effect on small amounts of data, but if you have 1000s of variables it would.

Cluster Forest

Way of visualising this variable elimination at work. Each vertex is a list of variables in a factor. Arrow drawn from one to the other as they are reduced by variable elimination. Root (graph is a tree) is the result. Easier to understand if you look at one.