diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine')
12 files changed, 272 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Entries new file mode 100644 index 00000000..932cb3b4 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Entries @@ -0,0 +1,5 @@ +/enter_evidence.m/1.1.1.1/Wed May 29 15:59:56 2002// +/jtree_limid_inf_engine.m/1.1.1.1/Wed May 29 15:59:56 2002// +/marginal_family.m/1.1.1.1/Wed May 29 15:59:56 2002// +/marginal_nodes.m/1.1.1.1/Wed May 29 15:59:56 2002// +D/Old//// diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Repository new file mode 100644 index 00000000..e8bf097c --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/static/@jtree_limid_inf_engine diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Root b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Entries new file mode 100644 index 00000000..0b350b99 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Entries @@ -0,0 +1,3 @@ +/marginal_family.m/1.1.1.1/Wed May 29 15:59:56 2002// +/marginal_nodes_SS.m/1.1.1.1/Wed May 29 15:59:56 2002// +D diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Repository new file mode 100644 index 00000000..59988183 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/static/@jtree_limid_inf_engine/Old diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Root b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_family.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_family.m new file mode 100644 index 00000000..cd660ae4 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_family.m @@ -0,0 +1,59 @@ +function [m, pot] = marginal_family(engine, query) +% MARGINAL_NODES Compute the marginal on the family of the specified node (jtree_limid) +% [m, pot] = marginal_family(engine, query) +% +% query should be a single decision node, or [] (to compute global max expected utility) + +bnet = bnet_from_engine(engine); +if isempty(query) + compute_meu = 1; + d = bnet.decision_nodes(1); % pick an arbitrary root to collect to + fam = []; % marginalize root pot down to a point +else + compute_meu = 0; + d = query; + assert(myismember(d, bnet.decision_nodes)); + fam = family(bnet.dag, d); +end + +clpot = init_clpot(bnet, engine.cliques, engine.clq_ass_to_node, engine.evidence, engine.exclude); + +% collect to root (clique containing d) +C = length(engine.cliques); +seppot = cell(C, C); % separators are implicitely initialized to 1s +for n=engine.postorder{d}(1:end-1) + for p=parents(engine.rooted_jtree{d}, n) + %clpot{p} = divide_by_pot(clpot{n}, seppot{p,n}); % dividing by 1 is redundant + seppot{p,n} = marginalize_pot(clpot{n}, engine.separator{p,n}); + clpot{p} = multiply_by_pot(clpot{p}, seppot{p,n}); + end +end + +root = engine.clq_ass_to_node(d); +assert(root == engine.postorder{d}(end)); +pot = marginalize_pot(clpot{root}, fam); +m = pot_to_marginal(pot); + +%%%%%%%%%%% + + +function clpot = init_clpot(bnet, cliques, clq_ass_to_node, evidence, exclude) + +% Set the clique potentials to all 1s +C = length(cliques); +clpot = cell(1, C); +ns = bnet.node_sizes; +for i=1:C + clpot{i} = upot(cliques{i}, ns(cliques{i})); +end + +N = length(bnet.dag); +nodes = mysetdiff(1:N, exclude); + +for n=nodes(:)' + fam = family(bnet.dag, n); + e = bnet.equiv_class(n); + c = clq_ass_to_node(n); + pot = convert_to_pot(bnet.CPD{e}, 'u', ns, fam, evidence); + clpot{c} = multiply_by_pot(clpot{c}, pot); +end diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_nodes_SS.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_nodes_SS.m new file mode 100644 index 00000000..2b6ff642 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/Old/marginal_nodes_SS.m @@ -0,0 +1,52 @@ +function [pot, MEU] = marginal_nodes(engine, d) + +C = length(cliques); +%clpot = init_clpot(limid, cliques, d, clq_ass_to_node); +clpot = init_clpot(limid, cliques, [], clq_ass_to_node); + +% collect to root +if 1 + % HUGIN + seppot = cell(C, C); % separators are implicitely initialized to 1s + for n=postorder{di}(1:end-1) + for p=parents(rooted_jtree{di}, n) + %clpot{p} = divide_by_pot(clpot{n}, seppot{p,n}); % dividing by 1 is redundant + seppot{p,n} = marginalize_pot(clpot{n}, separator{p,n}); + clpot{p} = multiply_by_pot(clpot{p}, seppot{p,n}); + end + end +else + % Shafer-Shenoy + msg = cell(C,C); + for n=postorder{di}(1:end-1) + for c=children(rooted_jtree{di}, n) + clpot{n} = multiply_by_pot(clpot{n}, msg{c,n}); + end + p = parents(rooted_jtree{di}, n); + %msg{n,p} = marginalize_pot(clpot{n}, cliques{p}); + msg{n,p} = marginalize_pot(clpot{n}, separator{n,p}); + end + root = clq_ass_to_node(d); + n=postorder{di}(end); + assert(n == root); + for c=children(rooted_jtree{di}, n) + clpot{n} = multiply_by_pot(clpot{n}, msg{c,n}); + end +end + +fam = family(limid.dag, d); +pot = marginalize_pot(clpot{root}, fam); + +%%%%%%% +jpot = compute_joint_pot_limid(limid); +pot2 = marginalize_pot(jpot, fam); +assert(approxeq_pot(pot, pot2)) +%%%%%% + +[policy, score] = extract_policy(pot); + +e = limid.equiv_class(d); +limid.CPD{e} = set_params(limid.CPD{e}, 'policy', policy); + + + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/enter_evidence.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/enter_evidence.m new file mode 100644 index 00000000..5d874803 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/enter_evidence.m @@ -0,0 +1,28 @@ +function engine = enter_evidence(engine, evidence, varargin) +% ENTER_EVIDENCE Add the specified evidence to the network (jtree_limid) +% engine = enter_evidence(engine, evidence, ...) +% +% evidence{i} = [] if if X(i) is hidden, and otherwise contains its observed value. +% +% The list below gives optional arguments [default value in brackets]. +% +% exclude - list of nodes whose potential will not be included in the joint [ [] ] +% +% e.g., engine = enter_evidence(engine, ev, 'exclude', 3) + +exclude = []; + +if nargin >= 3 + args = varargin; + nargs = length(args); + for i=1:2:nargs + switch args{i}, + case 'exclude', exclude = args{i+1}; + otherwise, + error(['invalid argument name ' args{i}]); + end + end +end + +engine.exclude = exclude; +engine.evidence = evidence; diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/jtree_limid_inf_engine.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/jtree_limid_inf_engine.m new file mode 100644 index 00000000..83dd89ef --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/jtree_limid_inf_engine.m @@ -0,0 +1,52 @@ +function engine = jtree_limid_inf_engine(bnet) +% JTREE_LIMID_INF_ENGINE Make a junction tree engine for use by solve_limid +% engine = jtree_limid_inf_engine(bnet) +% +% This engine is designed to compute marginals on decision nodes + + +MG = moralize(bnet.dag); +% We do not remove the utility nodes, because that complicates the book-keeping. +% Leaving them in will not introduce any un-necessary triangulation arcs, because they are always leaves. +% Also, since utility nodes have size 1, they do not increase the size of the potentials. + +ns = bnet.node_sizes; +elim_order = best_first_elim_order(MG, ns); +[MTG, engine.cliques] = triangulate(MG, elim_order); +[engine.jtree, root, B, w] = cliques_to_jtree(engine.cliques, ns); + +% A node can be a member of many cliques, but is assigned to exactly one, to avoid +% double-counting its CPD. We assign node i to clique c if c is the "lightest" clique that +% contains i's family, so it can accomodate its CPD. +N = length(bnet.dag); +engine.clq_ass_to_node = zeros(1, N); +for i=1:N + clqs_containing_family = find(all(B(:,family(bnet.dag, i)), 2)); % all selected columns must be 1 + c = clqs_containing_family(argmin(w(clqs_containing_family))); + engine.clq_ass_to_node(i) = c; +end + + +% Compute the separators between connected cliques. +[is,js] = find(engine.jtree > 0); +num_cliques = length(engine.cliques); +engine.separator = cell(num_cliques, num_cliques); +for k=1:length(is) + i = is(k); j = js(k); + engine.separator{i,j} = find(B(i,:) & B(j,:)); % intersect(cliques{i}, cliques{j}); +end + + +% create |D| different rooted jtree's +engine.rooted_jtree = cell(1, N); +engine.preorder = cell(1, N); +engine.postorder = cell(1, N); +for d=bnet.decision_nodes(:)' + root = engine.clq_ass_to_node(d); + [engine.rooted_jtree{d}, engine.preorder{d}, engine.postorder{d}] = mk_rooted_tree(engine.jtree, root); +end + +engine.exclude = []; +engine.evidence = []; + +engine = class(engine, 'jtree_limid_inf_engine', inf_engine(bnet)); diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_family.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_family.m new file mode 100644 index 00000000..dd3bf95e --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_family.m @@ -0,0 +1,52 @@ +function [m, pot] = marginal_family(engine, query) +% MARGINAL_NODES Compute the marginal on the family of the specified node (jtree_limid) +% [m, pot] = marginal_family(engine, query) +% +% query should be a single decision node + +bnet = bnet_from_engine(engine); +d = query; +assert(myismember(d, bnet.decision_nodes)); +fam = family(bnet.dag, d); + +clpot = init_clpot(bnet, engine.cliques, engine.clq_ass_to_node, engine.evidence, engine.exclude); + +% collect to root (clique containing d) +C = length(engine.cliques); +seppot = cell(C, C); % separators are implicitely initialized to 1s +for n=engine.postorder{d}(1:end-1) + for p=parents(engine.rooted_jtree{d}, n) + %clpot{p} = divide_by_pot(clpot{n}, seppot{p,n}); % dividing by 1 is redundant + seppot{p,n} = marginalize_pot(clpot{n}, engine.separator{p,n}); + clpot{p} = multiply_by_pot(clpot{p}, seppot{p,n}); + end +end + +root = engine.clq_ass_to_node(d); +assert(root == engine.postorder{d}(end)); +pot = marginalize_pot(clpot{root}, fam); +m = pot_to_marginal(pot); + +%%%%%%%%%%% + + +function clpot = init_clpot(bnet, cliques, clq_ass_to_node, evidence, exclude) + +% Set the clique potentials to all 1s +C = length(cliques); +clpot = cell(1, C); +ns = bnet.node_sizes; +for i=1:C + clpot{i} = upot(cliques{i}, ns(cliques{i})); +end + +N = length(bnet.dag); +nodes = mysetdiff(1:N, exclude); + +for n=nodes(:)' + fam = family(bnet.dag, n); + e = bnet.equiv_class(n); + c = clq_ass_to_node(n); + pot = convert_to_pot(bnet.CPD{e}, 'u', fam(:), evidence); + clpot{c} = multiply_by_pot(clpot{c}, pot); +end diff --git a/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_nodes.m b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_nodes.m new file mode 100644 index 00000000..d3700270 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@jtree_limid_inf_engine/marginal_nodes.m @@ -0,0 +1,17 @@ +function [m, pot] = marginal_nodes(engine, query) +% MARGINAL_NODES Compute the marginal on the specified nodes (jtree_limid) +% [m, pot] = marginal_nodes(engine, query) +% +% query should be a subset of a family of a decision node + +if isempty(query) + bnet = bnet_from_engine(engine); + d = bnet.decision_nodes(1); % pick an arbitrary decision node + [dummy, big_pot] = marginal_family(engine, d); +else + [dummy, big_pot] = marginal_family(engine, query); +end +pot = marginalize_pot(big_pot, query); +m = pot_to_marginal(pot); + + |