|
wolffd@0
|
1 function order = best_first_elim_order(G, node_sizes, stage)
|
|
wolffd@0
|
2 % BEST_FIRST_ELIM_ORDER Greedily search for an optimal elimination order.
|
|
wolffd@0
|
3 % order = best_first_elim_order(moral_graph, node_sizes)
|
|
wolffd@0
|
4 %
|
|
wolffd@0
|
5 % Find an order in which to eliminate nodes from the graph in such a way as to try and minimize the
|
|
wolffd@0
|
6 % weight of the resulting triangulated graph. The weight of a graph is the sum of the weights of each
|
|
wolffd@0
|
7 % of its cliques; the weight of a clique is the product of the weights of each of its members; the
|
|
wolffd@0
|
8 % weight of a node is the number of values it can take on.
|
|
wolffd@0
|
9 %
|
|
wolffd@0
|
10 % Since this is an NP-hard problem, we use the following greedy heuristic:
|
|
wolffd@0
|
11 % at each step, eliminate that node which will result in the addition of the least
|
|
wolffd@0
|
12 % number of fill-in edges, breaking ties by choosing the node that induces the lighest clique.
|
|
wolffd@0
|
13 % For details, see
|
|
wolffd@0
|
14 % - Kjaerulff, "Triangulation of graphs -- algorithms giving small total state space",
|
|
wolffd@0
|
15 % Univ. Aalborg tech report, 1990 (www.cs.auc.dk/~uk)
|
|
wolffd@0
|
16 % - C. Huang and A. Darwiche, "Inference in Belief Networks: A procedural guide",
|
|
wolffd@0
|
17 % Intl. J. Approx. Reasoning, 11, 1994
|
|
wolffd@0
|
18 %
|
|
wolffd@0
|
19
|
|
wolffd@0
|
20 % Warning: This code is pretty old and could probably be made faster.
|
|
wolffd@0
|
21
|
|
wolffd@0
|
22 n = length(G);
|
|
wolffd@0
|
23 if nargin < 3, stage = { 1:n }; end % no constraints
|
|
wolffd@0
|
24
|
|
wolffd@0
|
25 % For long DBNs, it may be useful to eliminate all the nodes in slice t before slice t+1.
|
|
wolffd@0
|
26 % This will ensure that the jtree has a repeating structure (at least away from both edges).
|
|
wolffd@0
|
27 % This is why we have stages.
|
|
wolffd@0
|
28 % See the discussion of splicing jtrees on p68 of
|
|
wolffd@0
|
29 % Geoff Zweig's PhD thesis, Dept. Comp. Sci., UC Berkeley, 1998.
|
|
wolffd@0
|
30 % This constraint can increase the clique size significantly.
|
|
wolffd@0
|
31
|
|
wolffd@0
|
32 MG = G; % copy the original graph
|
|
wolffd@0
|
33 uneliminated = ones(1,n);
|
|
wolffd@0
|
34 order = zeros(1,n);
|
|
wolffd@0
|
35 t = 1; % Counts which time slice we are on
|
|
wolffd@0
|
36 for i=1:n
|
|
wolffd@0
|
37 U = find(uneliminated);
|
|
wolffd@0
|
38 valid = myintersect(U, stage{t});
|
|
wolffd@0
|
39 % Choose the best node from the set of valid candidates
|
|
wolffd@0
|
40 min_fill = zeros(1,length(valid));
|
|
wolffd@0
|
41 min_weight = zeros(1,length(valid));
|
|
wolffd@0
|
42 for j=1:length(valid)
|
|
wolffd@0
|
43 k = valid(j);
|
|
wolffd@0
|
44 nbrs = myintersect(neighbors(G, k), U);
|
|
wolffd@0
|
45 l = length(nbrs);
|
|
wolffd@0
|
46 M = MG(nbrs,nbrs);
|
|
wolffd@0
|
47 min_fill(j) = l^2 - sum(M(:)); % num. added edges
|
|
wolffd@0
|
48 min_weight(j) = prod(node_sizes([k nbrs])); % weight of clique
|
|
wolffd@0
|
49 end
|
|
wolffd@0
|
50 lightest_nbrs = find(min_weight==min(min_weight));
|
|
wolffd@0
|
51 % break ties using min-fill heuristic
|
|
wolffd@0
|
52 best_nbr_ndx = argmin(min_fill(lightest_nbrs));
|
|
wolffd@0
|
53 j = lightest_nbrs(best_nbr_ndx); % we will eliminate the j'th element of valid
|
|
wolffd@0
|
54 %j1s = find(score1==min(score1));
|
|
wolffd@0
|
55 %j = j1s(argmin(score2(j1s)));
|
|
wolffd@0
|
56 k = valid(j);
|
|
wolffd@0
|
57 uneliminated(k) = 0;
|
|
wolffd@0
|
58 order(i) = k;
|
|
wolffd@0
|
59 ns = myintersect(neighbors(G, k), U);
|
|
wolffd@0
|
60 if ~isempty(ns)
|
|
wolffd@0
|
61 G(ns,ns) = 1;
|
|
wolffd@0
|
62 G = setdiag(G,0);
|
|
wolffd@0
|
63 end
|
|
wolffd@0
|
64 if ~any(logical(uneliminated(stage{t}))) % are we allowed to the next slice?
|
|
wolffd@0
|
65 t = t + 1;
|
|
wolffd@0
|
66 end
|
|
wolffd@0
|
67 end
|
|
wolffd@0
|
68
|
