diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine')
7 files changed, 276 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Entries new file mode 100644 index 00000000..0cfdeafe --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Entries @@ -0,0 +1,5 @@ +/enter_evidence.m/1.1.1.1/Wed Jun 19 22:05:04 2002// +/find_mpe.m/1.1.1.1/Wed Jun 19 22:11:42 2002// +/marginal_nodes.m/1.1.1.1/Thu Sep 30 03:09:00 2004// +/var_elim_inf_engine.m/1.1.1.1/Wed Jun 19 22:04:50 2002// +D diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Repository new file mode 100644 index 00000000..8595410d --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/static/@var_elim_inf_engine diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Root b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/enter_evidence.m b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/enter_evidence.m new file mode 100644 index 00000000..ed3fbe19 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/enter_evidence.m @@ -0,0 +1,12 @@ +function [engine, loglik] = enter_evidence(engine, evidence, varargin) +% ENTER_EVIDENCE Add the specified evidence to the network (var_elim) +% [engine, loglik] = enter_evidence(engine, evidence, ...) +% +% evidence{i} = [] if if X(i) is hidden, and otherwise contains its observed value (scalar or column vector) + +% we could pre-process the evidence here, to prevent repeated work, but we don't. +engine.evidence = evidence; + +if nargout == 2 + [m, loglik] = marginal_nodes(engine, [1]); +end diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/find_mpe.m b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/find_mpe.m new file mode 100644 index 00000000..63be5625 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/find_mpe.m @@ -0,0 +1,163 @@ +function mpe = find_mpe(engine, new_evidence, max_over) +% FIND_MPE Find the most probable explanation of the data (assignment to the hidden nodes) +% function mpe = find_mpe(engine, evidence, order) +% +% PURPOSE: +% CALC_MPE Computes the most probable explanation to the network nodes +% given the evidence. +% +% [mpe, ll] = calc_mpe(engine, new_evidence, max_over) +% +% INPUT: +% bnet - the bayesian network +% new_evidence - optional, if specified - evidence to be incorporated [cell(1,n)] +% max_over - optional, if specified determines the variable elimination order [1:n] +% +% OUTPUT: +% mpe - the MPE assignmet for the net variables (or [] if no satisfying assignment) +% ll - log assignment probability. +% +% Notes: +% 1. Adapted from '@var_elim_inf_engine\marginal_nodes' for MPE by Ron Zohar, 8/7/01 +% 2. Only discrete potentials are supported at this time. +% 3. Complexity: O(nw*) where n is the number of nodes and w* is the induced tree width. +% 4. Implementation based on: +% - R. Dechter, "Bucket Elimination: A Unifying Framework for Probabilistic Inference", +% UA1 96, pp. 211-219. + +bnet = bnet_from_engine(engine); +ns = bnet.node_sizes; +n = length(bnet.dag); +evidence = cell(1,n); +if (nargin<2) + new_evidence = evidence; +end + +onodes = find(~isemptycell(new_evidence)); % observed nodes +hnodes = find(isemptycell(new_evidence)); % hidden nodes +pot_type = determine_pot_type(bnet, onodes); + +if pot_type ~= 'd' + error('only disrete potentials supported at this time') +end + +for i=1:n + fam = family(bnet.dag, i); + CPT{i} = convert_to_pot(bnet.CPD{bnet.equiv_class(i)}, pot_type, fam(:), evidence); +end + +% handle observed nodes: set impossible cases' probability to zero +% rather than prun matrix (this makes backtracking easier) + +for ii=onodes + lIdx = 1:ns(ii); + lIdx = setdiff(lIdx, new_evidence{ii}); + + sCPT=struct(CPT{ii}); % violate object privacy + + sargs = ''; + for jj=1:(length(sCPT.domain)-1) + sargs = [sargs, ':,']; + end + for jj=lIdx + eval(['sCPT.T(', sargs, num2str(jj), ')=0;']); + end + CPT{ii}=dpot(sCPT.domain, sCPT.sizes, sCPT.T); +end + +B = cell(1,n); +for b=1:n + B{b} = mk_initial_pot(pot_type, [], [], [], []); +end + +if (nargin<3) + max_over = (1:n); +end +order = max_over; % no attempt to optimize this + + +% Initialize the buckets with the CPDs assigned to them +for i=1:n + b = bucket_num(domain_pot(CPT{i}), order); + B{b} = multiply_pots(B{b}, CPT{i}); +end + +% Do backward phase +max_over = max_over(length(max_over):-1:1); % reverse +maximize = 1; +for i=max_over(1:end-1) + % max-ing over variable i which occurs in bucket j + j = bucket_num(i, order); + rest = mysetdiff(domain_pot(B{j}), i); + %temp = marginalize_pot_max(B{j}, rest); + temp = marginalize_pot(B{j}, rest, maximize); + b = bucket_num(domain_pot(temp), order); + % fprintf('maxing over bucket %d (var %d), putting result into bucket %d\n', j, i, b); + sB=struct(B{b}); % violate object privacy + if ~isempty(sB.domain) + B{b} = multiply_pots(B{b}, temp); + else + B{b} = temp; + end +end +result = B{1}; +marginal = pot_to_marginal(result); +[prob, mpe] = max(marginal.T); + +% handle impossible cases +if ~(prob>0) + mpe = []; + ll = -inf; + %warning('evidence has zero probability') + return +end + +ll = log(prob); + +% Do forward phase +for ii=2:n + marginal = pot_to_marginal(B{ii}); + mpeidx = []; + for jj=order(1:length(mpe)) + %assert(ismember(jj, marginal.domain)) %%% bug + temp = find_equiv_posns(jj, marginal.domain); + mpeidx = [mpeidx, temp] ; + if isempty(temp) + mpeidx = [mpeidx, Inf] ; + end + end + [mpeidxsorted sortedtompe] = sort(mpeidx) ; + + % maximize the matrix obtained from assigning values from previous buckets. + % this is done by building a string and using eval. + + kk=1; + sargs = '('; + for jj=1:length(marginal.domain) + if (jj~=1) + sargs = [sargs, ',']; + end + if (mpeidxsorted(kk)==jj) + sargs = [sargs, num2str(mpe(sortedtompe(kk)))]; + if (kk<length(mpe)) + kk = kk+1 ; + end + else + sargs = [sargs, ':']; + end + end + sargs = [sargs, ')'] ; + eval(['[val, loc] = max(marginal.T', sargs, ');']) + mpe = [mpe loc]; +end +[I,J] = sort(order); +mpe = mpe(J); + +mpe = num2cell(mpe); + +%%%%%%%%% + +function b = bucket_num(domain, order) + +b = max(find_equiv_posns(domain, order)); + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/marginal_nodes.m b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/marginal_nodes.m new file mode 100644 index 00000000..98551cb0 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/marginal_nodes.m @@ -0,0 +1,79 @@ +function [marginal, loglik] = marginal_nodes(engine, query, add_ev) +% MARGINAL_NODES Compute the marginal on the specified query nodes (var_elim) +% [marginal, loglik] = marginal_nodes(engine, query) + +if nargin < 3, add_ev = 0; end + +assert(length(query)>=1); + +evidence = engine.evidence; + +bnet = bnet_from_engine(engine); +ns = bnet.node_sizes; +n = length(bnet.dag); + +onodes = find(~isemptycell(evidence)); +hnodes = find(isemptycell(evidence)); +pot_type = determine_pot_type(bnet, onodes); + +% Fold the evidence into the CPTs - this could be done in 'enter_evidence' +CPT = cell(1,n); +for i=1:n + fam = family(bnet.dag, i); + CPT{i} = convert_to_pot(bnet.CPD{bnet.equiv_class(i)}, pot_type, fam(:), evidence); +end + + + +sum_over = mysetdiff(1:n, query); +order = [query sum_over]; % no attempt to optimize this + +% Initialize the buckets with the product of the CPTs assigned to them +B = cell(1,n+1); +for b=1:n+1 + B{b} = mk_initial_pot(pot_type, [], [], [], []); +end +for i=1:n + b = bucket_num(domain_pot(CPT{i}), order); + B{b} = multiply_pots(B{b}, CPT{i}); +end + +% Do the marginalization +sum_over = sum_over(length(sum_over):-1:1); % reverse +for i=sum_over(:)' + % summing over variable i which occurs in bucket j + j = bucket_num(i, order); + rest = mysetdiff(domain_pot(B{j}), i); + % minka + if ~isempty(rest) + temp = marginalize_pot(B{j}, rest); + b = bucket_num(domain_pot(temp), order); + %fprintf('summing over bucket %d (var %d), putting result into bucket %d\n', j, i, b); + B{b} = multiply_pots(B{b}, temp); + end +end + +% Combine all the remaining buckets into one +result = B{1}; +for i=2:length(query) + if ~isempty(domain_pot(B{i})) + result = multiply_pots(result, B{i}); + end +end +[result, loglik] = normalize_pot(result); + + +marginal = pot_to_marginal(result); +% minka: from jtree_inf_engine +if add_ev + bnet = bnet_from_engine(engine); + %marginal = add_ev_to_dmarginal(marginal, engine.evidence, bnet.node_sizes); + marginal = add_evidence_to_gmarginal(marginal, engine.evidence, bnet.node_sizes, bnet.cnodes); +end + +%%%%%%%%% + +function b = bucket_num(domain, order) + +b = max(find_equiv_posns(domain, order)); + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/var_elim_inf_engine.m b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/var_elim_inf_engine.m new file mode 100644 index 00000000..dd3c940a --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@var_elim_inf_engine/var_elim_inf_engine.m @@ -0,0 +1,15 @@ +function engine = var_elim_inf_engine(bnet, varargin) +% VAR_ELIM_INF_ENGINE Variable elimination inference engine +% engine = var_elim_inf_engine(bnet) +% +% For details on variable elimination, see +% - R. Dechter, "Bucket Elimination: A Unifying Framework for Probabilistic Inference", UA1 96, pp. 211-219. +% - Z. Li and B. D'Ambrosio, "Efficient inference in Bayes networks as a combinatorial +% optimization problem", Intl. J. Approximate Reasoning, 11(1):55-81, 1994 +% - R. McEliece and S. M. Aji, "The Generalized Distributive Law", IEEE Trans. Inform. Theory, 46(2), 2000 + + +% This is where we will store the results between enter_evidence and marginal_nodes +engine.evidence = []; + +engine = class(engine, 'var_elim_inf_engine', inf_engine(bnet)); |