|
wolffd@0
|
1 function engine = jtree_limid_inf_engine(bnet)
|
|
wolffd@0
|
2 % JTREE_LIMID_INF_ENGINE Make a junction tree engine for use by solve_limid
|
|
wolffd@0
|
3 % engine = jtree_limid_inf_engine(bnet)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % This engine is designed to compute marginals on decision nodes
|
|
wolffd@0
|
6
|
|
wolffd@0
|
7
|
|
wolffd@0
|
8 MG = moralize(bnet.dag);
|
|
wolffd@0
|
9 % We do not remove the utility nodes, because that complicates the book-keeping.
|
|
wolffd@0
|
10 % Leaving them in will not introduce any un-necessary triangulation arcs, because they are always leaves.
|
|
wolffd@0
|
11 % Also, since utility nodes have size 1, they do not increase the size of the potentials.
|
|
wolffd@0
|
12
|
|
wolffd@0
|
13 ns = bnet.node_sizes;
|
|
wolffd@0
|
14 elim_order = best_first_elim_order(MG, ns);
|
|
wolffd@0
|
15 [MTG, engine.cliques] = triangulate(MG, elim_order);
|
|
wolffd@0
|
16 [engine.jtree, root, B, w] = cliques_to_jtree(engine.cliques, ns);
|
|
wolffd@0
|
17
|
|
wolffd@0
|
18 % A node can be a member of many cliques, but is assigned to exactly one, to avoid
|
|
wolffd@0
|
19 % double-counting its CPD. We assign node i to clique c if c is the "lightest" clique that
|
|
wolffd@0
|
20 % contains i's family, so it can accomodate its CPD.
|
|
wolffd@0
|
21 N = length(bnet.dag);
|
|
wolffd@0
|
22 engine.clq_ass_to_node = zeros(1, N);
|
|
wolffd@0
|
23 for i=1:N
|
|
wolffd@0
|
24 clqs_containing_family = find(all(B(:,family(bnet.dag, i)), 2)); % all selected columns must be 1
|
|
wolffd@0
|
25 c = clqs_containing_family(argmin(w(clqs_containing_family)));
|
|
wolffd@0
|
26 engine.clq_ass_to_node(i) = c;
|
|
wolffd@0
|
27 end
|
|
wolffd@0
|
28
|
|
wolffd@0
|
29
|
|
wolffd@0
|
30 % Compute the separators between connected cliques.
|
|
wolffd@0
|
31 [is,js] = find(engine.jtree > 0);
|
|
wolffd@0
|
32 num_cliques = length(engine.cliques);
|
|
wolffd@0
|
33 engine.separator = cell(num_cliques, num_cliques);
|
|
wolffd@0
|
34 for k=1:length(is)
|
|
wolffd@0
|
35 i = is(k); j = js(k);
|
|
wolffd@0
|
36 engine.separator{i,j} = find(B(i,:) & B(j,:)); % intersect(cliques{i}, cliques{j});
|
|
wolffd@0
|
37 end
|
|
wolffd@0
|
38
|
|
wolffd@0
|
39
|
|
wolffd@0
|
40 % create |D| different rooted jtree's
|
|
wolffd@0
|
41 engine.rooted_jtree = cell(1, N);
|
|
wolffd@0
|
42 engine.preorder = cell(1, N);
|
|
wolffd@0
|
43 engine.postorder = cell(1, N);
|
|
wolffd@0
|
44 for d=bnet.decision_nodes(:)'
|
|
wolffd@0
|
45 root = engine.clq_ass_to_node(d);
|
|
wolffd@0
|
46 [engine.rooted_jtree{d}, engine.preorder{d}, engine.postorder{d}] = mk_rooted_tree(engine.jtree, root);
|
|
wolffd@0
|
47 end
|
|
wolffd@0
|
48
|
|
wolffd@0
|
49 engine.exclude = [];
|
|
wolffd@0
|
50 engine.evidence = [];
|
|
wolffd@0
|
51
|
|
wolffd@0
|
52 engine = class(engine, 'jtree_limid_inf_engine', inf_engine(bnet));
|
