diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine')
13 files changed, 452 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Entries new file mode 100644 index 00000000..b071e13e --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Entries @@ -0,0 +1,11 @@ +/bk_inf_engine.m/1.1.1.1/Wed May 29 15:59:56 2002// +/dbn_init_bel.m/1.1.1.1/Wed May 29 15:59:56 2002// +/dbn_marginal_from_bel.m/1.1.1.1/Wed May 29 15:59:56 2002// +/dbn_update_bel.m/1.1.1.1/Wed May 29 15:59:56 2002// +/dbn_update_bel1.m/1.1.1.1/Wed May 29 15:59:56 2002// +/enter_evidence.m/1.1.1.1/Wed May 29 15:59:56 2002// +/enter_soft_evidence.m/1.1.1.1/Sat Jan 11 18:13:50 2003// +/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// +/update_engine.m/1.1.1.1/Wed May 29 15:59:56 2002// +D diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Repository new file mode 100644 index 00000000..5e810837 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/dynamic/@bk_inf_engine diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Root b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/bk_inf_engine.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/bk_inf_engine.m new file mode 100644 index 00000000..2ca0350f --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/bk_inf_engine.m @@ -0,0 +1,107 @@ +function engine = bk_inf_engine(bnet, varargin) +% BK_INF_ENGINE Boyen-Koller approximate inference algorithm for DBNs. +% +% In the BK algorithm, the belief state is represented as a product of marginals, +% even though the factors may not be independent. +% +% engine = bk_inf_engine(bnet, ...) +% +% The following optional arguments can be specified in the form of name/value pairs: +% [default value in brackets] +% +% clusters - if a cell array, clusters{i} specifies the terms in the i'th factor. +% - 'exact' means create one cluster that contains all the nodes in a slice [exact] +% - 'ff' means create one cluster per node (ff = fully factorised). +% +% +% For details, see +% - "Tractable Inference for Complex Stochastic Processes", X. Boyen and D. Koller, UAI 98. +% - "Approximate learning of dynamic models", X. Boyen and D. Koller, NIPS 98. +% (The UAI98 paper discusses filtering and theory, and the NIPS98 paper discusses smoothing.) + +ss = length(bnet.intra); +% set default params +clusters = 'exact'; + + +if nargin >= 2 + args = varargin; + nargs = length(args); + for i=1:2:nargs + switch args{i}, + case 'clusters', clusters = args{i+1}; + otherwise, error(['unrecognized argument ' args{i}]) + end + end +end + +if strcmp(clusters, 'exact') + %clusters = { compute_interface_nodes(bnet.intra, bnet.inter) }; + clusters = { 1:ss }; +elseif strcmp(clusters, 'ff') + clusters = num2cell(1:ss); +end + + +% We need to insert the prior on the clusters in slice 1, +% and extract the posterior on the clusters in slice 2. +C = length(clusters); +clusters2 = cell(1,2*C); +clusters2(1:C) = clusters; +for c=1:C + clusters2{c+C} = clusters{c} + ss; +end + +onodes = bnet.observed; +obs_nodes = [onodes(:) onodes(:)+ss]; +engine.sub_engine = jtree_inf_engine(bnet, 'clusters', clusters2); + +engine.clq_ass_to_cluster = zeros(C, 2); +for c=1:C + engine.clq_ass_to_cluster(c,1) = clq_containing_nodes(engine.sub_engine, clusters{c}); + engine.clq_ass_to_cluster(c,2) = clq_containing_nodes(engine.sub_engine, clusters{c}+ss); +end +engine.clusters = clusters; + +engine.clq_ass_to_node = zeros(ss, 2); +for i=1:ss + engine.clq_ass_to_node(i, 1) = clq_containing_nodes(engine.sub_engine, i); + engine.clq_ass_to_node(i, 2) = clq_containing_nodes(engine.sub_engine, i+ss); +end + + + +% Also create an engine just for slice 1 +bnet1 = mk_bnet(bnet.intra1, bnet.node_sizes_slice, 'discrete', myintersect(bnet.dnodes, 1:ss), ... + 'equiv_class', bnet.equiv_class(:,1), 'observed', onodes); +for i=1:max(bnet1.equiv_class) + bnet1.CPD{i} = bnet.CPD{i}; +end + +engine.sub_engine1 = jtree_inf_engine(bnet1, 'clusters', clusters); + +engine.clq_ass_to_cluster1 = zeros(1,C); +for c=1:C + engine.clq_ass_to_cluster1(c) = clq_containing_nodes(engine.sub_engine1, clusters{c}); +end + +engine.clq_ass_to_node1 = zeros(1, ss); +for i=1:ss + engine.clq_ass_to_node1(i) = clq_containing_nodes(engine.sub_engine1, i); +end + +engine.clpot = []; % this is where we store the results between enter_evidence and marginal_nodes +engine.filter = []; +engine.maximize = []; +engine.T = []; + +engine.bel = []; +engine.bel_clpot = []; +engine.slice1 = []; +%engine.pot_type = 'cg'; +% hack for online inference so we can cope with hidden Gaussians and discrete +% it will not affect the pot type used in enter_evidence +engine.pot_type = determine_pot_type(bnet, onodes); + +engine = class(engine, 'bk_inf_engine', inf_engine(bnet)); + diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_init_bel.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_init_bel.m new file mode 100644 index 00000000..fa6a27de --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_init_bel.m @@ -0,0 +1,8 @@ +function engine = dbn_init_bel(engine) +% DBN_INIT_BEL Compute the initial belief state (bk) +% engine = dbn_init_bel(engine)) + +bnet = bnet_from_engine(engine); +ss = length(bnet.intra); +evidence = cell(1,ss); +engine = dbn_update_bel1(engine, evidence); diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_marginal_from_bel.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_marginal_from_bel.m new file mode 100644 index 00000000..7e5a968d --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_marginal_from_bel.m @@ -0,0 +1,18 @@ +function marginal = dbn_marginal_from_bel(engine, i) +% DBN_MARGINAL_FROM_BEL Compute the marginal on a node given the current belief state (bk) +% marginal = dbn_marginal_from_bel(engine, i) + +if engine.slice1 + j = i; + c = clq_containing_nodes(engine.sub_engine1, j); +else + bnet = bnet_from_engine(engine); + ss = length(bnet.intra); + j = i+ss; + c = clq_containing_nodes(engine.sub_engine, j); +end +assert(c >= 1); +bigpot = engine.bel_clpot{c}; + +pot = marginalize_pot(bigpot, j); +marginal = pot_to_marginal(pot); diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel.m new file mode 100644 index 00000000..0c8e02b5 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel.m @@ -0,0 +1,37 @@ +function [engine, loglik] = dbn_update_bel(engine, evidence) +% DBN_UPDATE_BEL Update the belief state (bk) +% [engine, loglik] = dbn_update_bel(engine, evidence) +% +% evidence{i,1} contains the evidence on node i in slice t-1 +% evidence{i,2} contains the evidence on node i in slice t + +oldbel = engine.bel; + +ss = size(evidence, 1); +bnet = bnet_from_engine(engine); +CPDpot = cell(1, ss); +for n=1:ss + fam = family(bnet.dag, n, 2); + e = bnet.equiv_class(n, 2); + CPDpot{n} = convert_to_pot(bnet.CPD{e}, engine.pot_type, fam(:), evidence); +end + +observed = ~isemptycell(evidence); +onodes2 = find(observed(:)); +clqs = [engine.clq_ass_to_cluster(:,1); engine.clq_ass_to_node(:,2)]; +pots = [oldbel(:); CPDpot(:)]; + +[clpot, loglik] = enter_soft_evidence(engine.sub_engine, clqs, pots, onodes2(:), engine.pot_type); + +C = length(engine.clusters); +newbel = cell(1,C); +for c=1:C + k = engine.clq_ass_to_cluster(c,2); + cl = engine.clusters{c}; + newbel{c} = marginalize_pot(clpot{k}, cl+ss); % extract slice 2 posterior + newbel{c} = set_domain_pot(newbel{c}, cl); % shift back to slice 1 for re-use as prior +end + +engine.bel = newbel; +engine.bel_clpot = clpot; +engine.slice1 = 0; diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel1.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel1.m new file mode 100644 index 00000000..a3b6cc79 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/dbn_update_bel1.m @@ -0,0 +1,30 @@ +function [engine, loglik] = dbn_update_bel1(engine, evidence) +% DBN_UPDATE_BEL1 Update the initial belief state (bk) +% engine = dbn_update_bel1(engine, evidence) +% +% evidence{i} has the evidence on node i for slice 1 + +bnet = bnet_from_engine(engine); +ss = length(bnet.intra); +CPDpot = cell(1,ss); +t = 1; +for n=1:ss + fam = family(bnet.dag, n); + e = bnet.equiv_class(n, 1); + CPDpot{n} = convert_to_pot(bnet.CPD{e}, engine.pot_type, fam(:), evidence); +end + +onodes = find(~isemptycell(evidence)); + +[clpot, loglik] = enter_soft_evidence(engine.sub_engine1, engine.clq_ass_to_node1, CPDpot, onodes, engine.pot_type); + +C = length(engine.clusters); +newbel = cell(1,C); +for c=1:C + k = engine.clq_ass_to_cluster1(c); + newbel{c} = marginalize_pot(clpot{k}, engine.clusters{c}); +end + +engine.bel = newbel; +engine.bel_clpot = clpot; +engine.slice1 = 1; diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_evidence.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_evidence.m new file mode 100644 index 00000000..7008137b --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_evidence.m @@ -0,0 +1,48 @@ +function [engine, loglik] = enter_evidence(engine, evidence, varargin) +% ENTER_EVIDENCE Add the specified evidence to the network (bk) +% [engine, loglik] = enter_evidence(engine, evidence, ...) +% +% evidence{i,t} = [] if if X(i,t) is hidden, and otherwise contains its observed value (scalar or column vector) +% +% The following optional arguments can be specified in the form of name/value pairs: +% [default value in brackets] +% +% maximize - if 1, does max-product instead of sum-product [0] +% filter - if 1, do filtering, else smoothing [0] +% +% e.g., engine = enter_evidence(engine, ev, 'maximize', 1) + +maximize = 0; +filter = 0; + +% parse optional params +args = varargin; +nargs = length(args); +if nargs > 0 + for i=1:2:nargs + switch args{i}, + case 'maximize', maximize = args{i+1}; + case 'filter', filter = args{i+1}; + otherwise, + error(['invalid argument name ' args{i}]); + end + end +end + +[ss T] = size(evidence); +engine.filter = filter; +engine.maximize = maximize; +engine.T = T; + +if maximize + error('BK does not yet support max propagation') + % because it calls enter_soft_evidence, not enter_evidence +end + +observed_bitv = ~isemptycell(evidence); +onodes = find(observed_bitv); +bnet = bnet_from_engine(engine); +pot_type = determine_pot_type(bnet, onodes); +CPDpot = convert_dbn_CPDs_to_pots(bnet, evidence, pot_type); +[engine.clpot, loglik] = enter_soft_evidence(engine, CPDpot, observed_bitv, pot_type, filter); + diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_soft_evidence.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_soft_evidence.m new file mode 100644 index 00000000..1cbc634e --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/enter_soft_evidence.m @@ -0,0 +1,88 @@ +function [clpot, loglik] = enter_soft_evidence(engine, CPDpot, observed, pot_type, filter) +% ENTER_SOFT_EVIDENCE Add the specified soft evidence to the network (bk) +% [clpot, loglik] = enter_soft_evidence(engine, CPDpot, observed, pot_type, filter) + +[ss T] = size(CPDpot); +C = length(engine.clusters); +Q = length(cliques_from_engine(engine.sub_engine)); +Q1 = length(cliques_from_engine(engine.sub_engine1)); +clpot = cell(Q,T); +alpha = cell(C,T); + +% Forwards +% The method is a generalization of the following HMM equation: +% alpha(j,t) = normalise( (sum_i alpha(i,t-1) * transmat(i,j)) * obsmat(j,t) ) +% where alpha(j,t) = Pr(Q(t)=j | y(1:t)) +t = 1; +[clpot(1:Q1,t), logscale(t)] = enter_soft_evidence(engine.sub_engine1, engine.clq_ass_to_node1(:), ... + CPDpot(:,1), find(observed(:,1)), pot_type); +for c=1:C + k = engine.clq_ass_to_cluster1(c); + alpha{c,t} = marginalize_pot(clpot{k,t}, engine.clusters{c}); +end +% For filtering, clpot{1} contains evidence on slice 1 only + +%fprintf('alphas t=%d\n', t); +%for c=1:8 +% temp = pot_to_marginal(alpha{c,t}); +% temp.T +%end + +% clpot{t} contains evidence from slices t-1, t for t > 1 +clqs = [engine.clq_ass_to_cluster(:,1); engine.clq_ass_to_node(:,2)]; +for t=2:T + pots = [alpha(:,t-1); CPDpot(:,t)]; + [clpot(:,t), logscale(t)] = enter_soft_evidence(engine.sub_engine, clqs, pots, find(observed(:,t-1:t)), pot_type); + for c=1:C + k = engine.clq_ass_to_cluster(c,2); + cl = engine.clusters{c}; + alpha{c,t} = marginalize_pot(clpot{k,t}, cl+ss); % extract slice 2 posterior + alpha{c,t} = set_domain_pot(alpha{c,t}, cl); % shift back to slice 1 for re-use as prior + end + +end + +loglik = sum(logscale); + +if filter + return; +end + +% Backwards +% The method is a generalization of the following HMM equation: +% beta(i,t) = (sum_j transmat(i,j) * obsmat(j,t+1) * beta(j,t+1)) +% where beta(i,t) = Pr(y(t+1:T) | Q(t)=i) +t = T; +bnet = bnet_from_engine(engine); +beta = cell(C,T); +for c=1:C + beta{c,t} = mk_initial_pot(pot_type, engine.clusters{c} + ss, bnet.node_sizes(:), bnet.cnodes(:), ... + find(observed(:,t-1:t))); +end +for t=T-1:-1:1 + clqs = [engine.clq_ass_to_cluster(:,2); engine.clq_ass_to_node(:,2)]; + pots = [beta(:,t+1); CPDpot(:,t+1)]; + temp = enter_soft_evidence(engine.sub_engine, clqs, pots, find(observed(:,t:t+1)), pot_type); + for c=1:C + k = engine.clq_ass_to_cluster(c,1); + cl = engine.clusters{c}; + beta{c,t} = marginalize_pot(temp{k}, cl); % extract slice 1 + beta{c,t} = set_domain_pot(beta{c,t}, cl + ss); % shift fwd to slice 2 + end +end + +% Combine +% The method is a generalization of the following HMM equation: +% xi(i,j,t) = normalise( alpha(i,t) * transmat(i,j) * obsmat(j,t+1) * beta(j,t+1) ) +% where xi(i,j,t) = Pr(Q(t)=i, Q(t+1)=j | y(1:T)) +for t=1:T-1 + clqs = [engine.clq_ass_to_cluster(:); engine.clq_ass_to_node(:,2)]; + pots = [alpha(:,t); beta(:,t+1); CPDpot(:,t+1)]; + clpot(:,t+1) = enter_soft_evidence(engine.sub_engine, clqs, pots, find(observed(:,t:t+1)), pot_type); +end +% for smoothing, clpot{1} is undefined +for k=1:Q1 + clpot{k,1} = []; +end + + diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_family.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_family.m new file mode 100644 index 00000000..e948b836 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_family.m @@ -0,0 +1,25 @@ +function m = marginal_family(engine, i, t) +% MARGINAL_FAMILY Compute the marginal on the specified family (bk) +% marginal = marginal_family(engine, i, t) + +% This is just like inf_engine/marginal_family, except when we call +% marginal_nodes, we provide a 4th argument, to tell it's a family. + +if nargin < 3, t = 1; end + +bnet = bnet_from_engine(engine); +if t==1 + m = marginal_nodes(engine, family(bnet.dag, i), t, 1); +else + ss = length(bnet.intra); + fam = family(bnet.dag, i+ss); + if any(fam<=ss) + % i has a parent in the preceeding slice + % Hence the lowest numbered slice containing the family is t-1 + m = marginal_nodes(engine, fam, t-1, 1); + else + % The family all fits inside slice t + % Hence shift the indexes back to slice 1 + m = marginal_nodes(engine, fam-ss, t, 1); + end +end diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_nodes.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_nodes.m new file mode 100644 index 00000000..30bf9a9d --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/marginal_nodes.m @@ -0,0 +1,67 @@ +function marginal = marginal_nodes(engine, nodes, t, fam) +% MARGINAL_NODES Compute the marginal on the specified query nodes (bk) +% +% marginal = marginal_nodes(engine, i, t) +% returns Pr(X(i,t) | Y(1:T)), where X(i,t) is the i'th node in the t'th slice. +% If enter_evidence used filtering instead of smoothing, this will return Pr(X(i,t) | Y(1:t)). +% +% marginal = marginal_nodes(engine, query, t) +% returns Pr(X(query(1),t), ... X(query(end),t) | Y(1:T)), +% where X(q,t) is the q'th node in the t'th slice. If q > ss (slice size), this is equal +% to X(q mod ss, t+1). That is, 't' specifies the time slice of the earliest node. +% 'query' cannot span more than 2 time slices. +% Example: +% Consider a DBN with 2 nodes per slice. +% Then t=2, nodes=[1 3] refers to node 1 in slice 2 and node 1 in slice 3. + +if nargin < 3, t = 1; end +if nargin < 4, fam = 0; else fam = 1; end + + +% clpot{t} contains slice t-1 and t +% Example +% clpot #: 1 2 3 +% slices: 1 1,2 2,3 +% For filtering, we must take care not to take future evidence into account. +% For smoothing, clpot{1} does not exist. + +bnet = bnet_from_engine(engine); +ss = length(bnet.intra); + +nodes2 = nodes; +if ~engine.filter + if t < engine.T + slice = t+1; + else % earliest t is T, so all nodes fit in one slice + slice = engine.T; + nodes2 = nodes + ss; + end +else + if t == 1 + slice = 1; + else + if all(nodes<=ss) + slice = t; + nodes2 = nodes + ss; + elseif t == engine.T + slice = t; + else + slice = t + 1; + end + end +end + +if engine.filter & t==1 + c = clq_containing_nodes(engine.sub_engine1, nodes2, fam); +else + c = clq_containing_nodes(engine.sub_engine, nodes2, fam); +end +assert(c >= 1); +bigpot = engine.clpot{c, slice}; + +pot = marginalize_pot(bigpot, nodes2); +marginal = pot_to_marginal(pot); + +% we convert the domain to the unrolled numbering system +% so that update_ess extracts the right evidence. +marginal.domain = nodes+(t-1)*ss; diff --git a/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/update_engine.m b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/update_engine.m new file mode 100644 index 00000000..b36833a1 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/dynamic/@bk_inf_engine/update_engine.m @@ -0,0 +1,11 @@ +function engine = update_engine(engine, newCPDs) +% UPDATE_ENGINE Update the engine to take into account the new parameters (bk) +% engine = update_engine(engine, newCPDs) + +engine.inf_engine = update_engine(engine.inf_engine, newCPDs); +engine.sub_engine = update_engine(engine.sub_engine, newCPDs); + +bnet = bnet_from_engine(engine); +eclass1 = bnet.equiv_class(:,1); +engine.sub_engine1 = update_engine(engine.sub_engine1, newCPDs(1:max(eclass1))); + |