Interactive demo · Probabilistic Machine Learning: Advanced Topics · Chapter 9

Variable elimination: choosing the order

The student network has eight binary variables. Pick the order in which to sum them out (click the letters; the last one is the query). Each step multiplies the factors that mention the variable and sums it out; the new factor couples all its neighbours, adding fill-in edges. The cost is the sum of 2|c| over the maximal cliques of the induced graph. A good order keeps the cliques small; the junction tree (below) reuses the same cliques to get all marginals.

Elimination order (last = query)

Try these

The variables: C coherence, D difficulty, I intelligence, G grade, S SAT, L letter, J job, H happy. Arrows of the Bayes net: C→D, D→G, I→G, I→S, G→L, L→J, S→J, G→H, J→H; the graph shown is the moral graph. The probability tables are illustrative numbers of our own. Cost and width follow (9.91)–(9.92); the exact value is checked against summing all 28 terms.

In the lecture notes