Instance based learning

In a nutshell, the variable elimination procedure repeats the following steps.

1. Pick a variable Xi

2. Multiply all expressions involving that variable, resulting in an expression f over a

number of variables (including Xi)

3. Sum out Xi, i.e. compute and store

For the multiplication, we must compute a number for each joint instantiation of all variables in f, so complexity is exponential in the largest number of variables participating in one of these multiplicative subexpressions.

If we wish to compute several marginals at the same time, we can use Dynamic Programming to avoid the redundant computation that would be involved if we used variable elimination repeatedly.

Exact inferencing in a general Bayes net is a hard problem. However, for networks with

some special topologies efficient solutions inferencing techniques. We discuss one such technque for a class of networks called Poly-trees.