wolffd@0
|
1 function engine = jtree_inf_engine(bnet, varargin)
|
wolffd@0
|
2 % JTREE_INF_ENGINE Junction tree inference engine
|
wolffd@0
|
3 % engine = jtree_inf_engine(bnet, ...)
|
wolffd@0
|
4 %
|
wolffd@0
|
5 % The following optional arguments can be specified in the form of name/value pairs:
|
wolffd@0
|
6 % [default value in brackets]
|
wolffd@0
|
7 %
|
wolffd@0
|
8 % clusters - a cell array of sets of nodes we want to ensure are in the same clique (in addition to families) [ {} ]
|
wolffd@0
|
9 % root - the root of the junction tree will be a clique that contains this set of nodes [N]
|
wolffd@0
|
10 % stages - stages{t} is a set of nodes we want to eliminate before stages{t+1}, ... [ {1:N} ]
|
wolffd@0
|
11 %
|
wolffd@0
|
12 % e.g., engine = jtree_inf_engine(bnet, 'maximize', 1);
|
wolffd@0
|
13 %
|
wolffd@0
|
14 % For more details on the junction tree algorithm, see
|
wolffd@0
|
15 % - "Probabilistic networks and expert systems", Cowell, Dawid, Lauritzen and Spiegelhalter, Springer, 1999
|
wolffd@0
|
16 % - "Inference in Belief Networks: A procedural guide", C. Huang and A. Darwiche,
|
wolffd@0
|
17 % Intl. J. Approximate Reasoning, 15(3):225-263, 1996.
|
wolffd@0
|
18
|
wolffd@0
|
19
|
wolffd@0
|
20 % set default params
|
wolffd@0
|
21 N = length(bnet.dag);
|
wolffd@0
|
22 clusters = {};
|
wolffd@0
|
23 root = N;
|
wolffd@0
|
24 stages = { 1:N };
|
wolffd@0
|
25 maximize = 0;
|
wolffd@0
|
26
|
wolffd@0
|
27 if nargin >= 2
|
wolffd@0
|
28 args = varargin;
|
wolffd@0
|
29 nargs = length(args);
|
wolffd@0
|
30 if ~isstr(args{1})
|
wolffd@0
|
31 error('the interface to jtree has changed; now, onodes is not allowed and all optional params must be passed by name')
|
wolffd@0
|
32 end
|
wolffd@0
|
33 for i=1:2:nargs
|
wolffd@0
|
34 switch args{i},
|
wolffd@0
|
35 case 'clusters', clusters = args{i+1};
|
wolffd@0
|
36 case 'root', root = args{i+1};
|
wolffd@0
|
37 case 'stages', stages = args{i+1};
|
wolffd@0
|
38 case 'maximize', maximize = args{i+1};
|
wolffd@0
|
39 otherwise,
|
wolffd@0
|
40 error(['invalid argument name ' args{i}]);
|
wolffd@0
|
41 end
|
wolffd@0
|
42 end
|
wolffd@0
|
43 end
|
wolffd@0
|
44
|
wolffd@0
|
45 engine = init_fields;
|
wolffd@0
|
46 engine = class(engine, 'jtree_inf_engine', inf_engine(bnet));
|
wolffd@0
|
47
|
wolffd@0
|
48 engine.maximize = maximize;
|
wolffd@0
|
49
|
wolffd@0
|
50 onodes = bnet.observed;
|
wolffd@0
|
51
|
wolffd@0
|
52 %[engine.jtree, dummy, engine.cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ...
|
wolffd@0
|
53 % dag_to_jtree(bnet, onodes, stages, clusters);
|
wolffd@0
|
54
|
wolffd@0
|
55 porder = determine_elim_constraints(bnet, onodes);
|
wolffd@0
|
56 strong = ~isempty(porder);
|
wolffd@0
|
57 ns = bnet.node_sizes(:);
|
wolffd@0
|
58 ns(onodes) = 1; % observed nodes have only 1 possible value
|
wolffd@0
|
59 [engine.jtree, root2, engine.cliques, B, w] = ...
|
wolffd@0
|
60 graph_to_jtree(moralize(bnet.dag), ns, porder, stages, clusters);
|
wolffd@0
|
61
|
wolffd@0
|
62
|
wolffd@0
|
63 engine.cliques_bitv = B;
|
wolffd@0
|
64 engine.clique_weight = w;
|
wolffd@0
|
65 C = length(engine.cliques);
|
wolffd@0
|
66 engine.clpot = cell(1,C);
|
wolffd@0
|
67
|
wolffd@0
|
68 % Compute the separators between connected cliques.
|
wolffd@0
|
69 [is,js] = find(engine.jtree > 0);
|
wolffd@0
|
70 engine.separator = cell(C,C);
|
wolffd@0
|
71 for k=1:length(is)
|
wolffd@0
|
72 i = is(k); j = js(k);
|
wolffd@0
|
73 engine.separator{i,j} = find(B(i,:) & B(j,:)); % intersect(cliques{i}, cliques{j});
|
wolffd@0
|
74 end
|
wolffd@0
|
75
|
wolffd@0
|
76 % A node can be a member of many cliques, but is assigned to exactly one, to avoid
|
wolffd@0
|
77 % double-counting its CPD. We assign node i to clique c if c is the "lightest" clique that
|
wolffd@0
|
78 % contains i's family, so it can accomodate its CPD.
|
wolffd@0
|
79
|
wolffd@0
|
80 engine.clq_ass_to_node = zeros(1, N);
|
wolffd@0
|
81 for i=1:N
|
wolffd@0
|
82 %c = clq_containing_nodes(engine, family(bnet.dag, i));
|
wolffd@0
|
83 clqs_containing_family = find(all(B(:,family(bnet.dag, i)), 2)); % all selected columns must be 1
|
wolffd@0
|
84 c = clqs_containing_family(argmin(w(clqs_containing_family)));
|
wolffd@0
|
85 engine.clq_ass_to_node(i) = c;
|
wolffd@0
|
86 end
|
wolffd@0
|
87
|
wolffd@0
|
88 % Make the jtree rooted, so there is a fixed message passing order.
|
wolffd@0
|
89 if strong
|
wolffd@0
|
90 % the last clique is guaranteed to be a strong root
|
wolffd@0
|
91 % engine.root_clq = length(engine.cliques);
|
wolffd@0
|
92
|
wolffd@0
|
93 % --- 4/17/2010, by Wei Sun (George Mason University):
|
wolffd@0
|
94 % It has been proved that the last clique is not necessary to be the
|
wolffd@0
|
95 % strong root, instead, a clique called interface clique, that contains
|
wolffd@0
|
96 % all discrete parents and at least one continuous node from a connected
|
wolffd@0
|
97 % continuous component in a CLG, is guaranteed to be a strong root.
|
wolffd@0
|
98 engine.root_clq = findroot(bnet, engine.cliques) ;
|
wolffd@0
|
99 else
|
wolffd@0
|
100 % jtree_dbn_inf_engine requires the root to contain the interface.
|
wolffd@0
|
101 % This may conflict with the strong root requirement! *********** BUG *************
|
wolffd@0
|
102 engine.root_clq = clq_containing_nodes(engine, root);
|
wolffd@0
|
103 if engine.root_clq <= 0
|
wolffd@0
|
104 error(['no clique contains ' num2str(root)]);
|
wolffd@0
|
105 end
|
wolffd@0
|
106 end
|
wolffd@0
|
107
|
wolffd@0
|
108 [engine.jtree, engine.preorder, engine.postorder] = mk_rooted_tree(engine.jtree, engine.root_clq);
|
wolffd@0
|
109
|
wolffd@0
|
110 % collect
|
wolffd@0
|
111 engine.postorder_parents = cell(1,length(engine.postorder));
|
wolffd@0
|
112 for n=engine.postorder(:)'
|
wolffd@0
|
113 engine.postorder_parents{n} = parents(engine.jtree, n);
|
wolffd@0
|
114 end
|
wolffd@0
|
115 % distribute
|
wolffd@0
|
116 engine.preorder_children = cell(1,length(engine.preorder));
|
wolffd@0
|
117 for n=engine.preorder(:)'
|
wolffd@0
|
118 engine.preorder_children{n} = children(engine.jtree, n);
|
wolffd@0
|
119 end
|
wolffd@0
|
120
|
wolffd@0
|
121
|
wolffd@0
|
122
|
wolffd@0
|
123 %%%%%%%%
|
wolffd@0
|
124
|
wolffd@0
|
125 function engine = init_fields()
|
wolffd@0
|
126
|
wolffd@0
|
127 engine.jtree = [];
|
wolffd@0
|
128 engine.cliques = [];
|
wolffd@0
|
129 engine.separator = [];
|
wolffd@0
|
130 engine.cliques_bitv = [];
|
wolffd@0
|
131 engine.clique_weight = [];
|
wolffd@0
|
132 engine.clpot = [];
|
wolffd@0
|
133 engine.clq_ass_to_node = [];
|
wolffd@0
|
134 engine.root_clq = [];
|
wolffd@0
|
135 engine.preorder = [];
|
wolffd@0
|
136 engine.postorder = [];
|
wolffd@0
|
137 engine.preorder_children = [];
|
wolffd@0
|
138 engine.postorder_parents = [];
|
wolffd@0
|
139 engine.maximize = [];
|
wolffd@0
|
140 engine.evidence = [];
|
wolffd@0
|
141
|