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