|
wolffd@0
|
1 function [jtree, root, B, w] = cliques_to_jtree(cliques, ns)
|
|
wolffd@0
|
2 % MK_JTREE Make an optimal junction tree.
|
|
wolffd@0
|
3 % [jtree, root, B, w] = mk_jtree(cliques, ns)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % A junction tree is a tree that satisfies the jtree property, which says:
|
|
wolffd@0
|
6 % for each pair of cliques U,V with intersection S, all cliques on the path between U and V
|
|
wolffd@0
|
7 % contain S. (This ensures that local propagation leads to global consistency.)
|
|
wolffd@0
|
8 %
|
|
wolffd@0
|
9 % We can create a junction tree by computing the maximal spanning tree of the junction graph.
|
|
wolffd@0
|
10 % (The junction graph connects all cliques, and the weight of an edge (i,j) is
|
|
wolffd@0
|
11 % |C(i) intersect C(j)|, where C(i) is the i'th clique.)
|
|
wolffd@0
|
12 %
|
|
wolffd@0
|
13 % The best jtree is the maximal spanning tree which minimizes the sum of the costs on each edge,
|
|
wolffd@0
|
14 % where cost(i,j) = w(C(i)) + w(C(j)), and w(C) is the weight of clique C,
|
|
wolffd@0
|
15 % which is the total number of values C can take on.
|
|
wolffd@0
|
16 %
|
|
wolffd@0
|
17 % For details, see
|
|
wolffd@0
|
18 % - Jensen and Jensen, "Optimal Junction Trees", UAI 94.
|
|
wolffd@0
|
19 %
|
|
wolffd@0
|
20 % Input:
|
|
wolffd@0
|
21 % cliques{i} = nodes in clique i
|
|
wolffd@0
|
22 % ns(i) = number of values node i can take on
|
|
wolffd@0
|
23 % Output:
|
|
wolffd@0
|
24 % jtree(i,j) = 1 iff cliques i and j aer connected
|
|
wolffd@0
|
25 % root = the clique that should be used as root
|
|
wolffd@0
|
26 % B(i,j) = 1 iff node j occurs in clique i
|
|
wolffd@0
|
27 % w(i) = weight of clique i
|
|
wolffd@0
|
28
|
|
wolffd@0
|
29
|
|
wolffd@0
|
30
|
|
wolffd@0
|
31 num_cliques = length(cliques);
|
|
wolffd@0
|
32 w = zeros(num_cliques, 1);
|
|
wolffd@0
|
33 B = sparse(num_cliques, 1);
|
|
wolffd@0
|
34 for i=1:num_cliques
|
|
wolffd@0
|
35 B(i, cliques{i}) = 1;
|
|
wolffd@0
|
36 w(i) = prod(ns(cliques{i}));
|
|
wolffd@0
|
37 end
|
|
wolffd@0
|
38
|
|
wolffd@0
|
39
|
|
wolffd@0
|
40 % C1(i,j) = length(intersect(cliques{i}, cliques{j}));
|
|
wolffd@0
|
41 % The length of the intersection of two sets is the dot product of their bit vector representation.
|
|
wolffd@0
|
42 C1 = B*B';
|
|
wolffd@0
|
43 C1 = setdiag(C1, 0);
|
|
wolffd@0
|
44
|
|
wolffd@0
|
45 % C2(i,j) = w(i) + w(j)
|
|
wolffd@0
|
46 num_cliques = length(w);
|
|
wolffd@0
|
47 W = repmat(w, 1, num_cliques);
|
|
wolffd@0
|
48 C2 = W + W';
|
|
wolffd@0
|
49 C2 = setdiag(C2, 0);
|
|
wolffd@0
|
50
|
|
wolffd@0
|
51 jtree = sparse(minimum_spanning_tree(-C1, C2)); % Using -C1 gives *maximum* spanning tree
|
|
wolffd@0
|
52
|
|
wolffd@0
|
53 % The root is arbitrary, but since the first pass is towards the root,
|
|
wolffd@0
|
54 % we would like this to correspond to going forward in time in a DBN.
|
|
wolffd@0
|
55 root = num_cliques;
|
|
wolffd@0
|
56
|
|
wolffd@0
|
57
|
