Algorithms for Graphical Models (AGM)

Practical 05: Join trees and sampling

1. Some maths
2. Forming join trees
3. Manual triangulation
4. Graham's algorithm
5. Basic sampling

Some maths

Acknowledgement: This question comes from Introduction to Bayesian Networks by Finn Jensen. The solution is from a web resource for that book.

Let G be a triangulated graph with vertices U, and let a1, a2, ...an be a zero fill-in for G. Assume that eliminated variables (and lines to them) are actually deleted. Let Ci be the set of variables containing ai and all its neighbours at the time of elimination.

1. Show that each clique of G is a Ci for some i.
2. Show that for all i < n, there is a j>i such that Ci \ {ai} is a subset of Cj

NB. If Ci and Cj are cliques (i<j) such that Ci \ {ai} is a subset of Cj, then there exists a junction tree for G with the link (Ci,Cj).

Solution: Look at i) and ii) of Exercise 8

Forming join trees (or not as the case may be)

Show that it is not possible to create a join tree from the following graph. Identify what the problem is and how the graph can be altered to overcome the problems.

Manual triangulation

Find optimal triangulations for the following graphs.

Graham's algorithm

Write a program which uses Graham's algorithm to check whether a hypergraph is decomposable. Use gPy's Hypergraph class to represent your hypergraph. Feel free to use any methods of that class (except of course those that check for decomposability!) Use the following hypergraphs as test cases.

1. {{A,B},{B,C},{C,D},{A,D}}
2. {{A,B,C},{A,C,D} }
3. { {TbOrCa, XRay}, {Bronchitis, Smoking}, {Tuberculosis, VisitAsia}, {Bronchitis, Dyspnea, TbOrCa}, {Cancer, Smoking}, {Cancer, TbOrCa, Tuberculosis} }
4. { {TbOrCa, XRay}, {Bronchitis, Smoking}, {Tuberculosis, VisitAsia}, {Bronchitis, Dyspnea, TbOrCa}, {Cancer, TbOrCa, Tuberculosis} }

Classification of test hypergraphs

If you're feeling ambitious you can adapt your program to construct a join forest en passant.

A complicated solution Simpler, but perhaps slower ones are fine.

Basic sampling

Design a class for a basic sampler. Only two public methods are needed. A constructor __init__ which takes a probability distribution as a sequence of n floats as its only argument, and a method sample which spits out an integer in the list range(n) according to the probability distribution. This is not hard to get working, but your job is to ensure that the sampling is efficient (in the long run) whatever the input distribution.

ANSWERS

Last modified: Fri Nov 25 09:25:37 GMT 2011