diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine')
9 files changed, 273 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Entries new file mode 100644 index 00000000..a4fbc6ee --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Entries @@ -0,0 +1,7 @@ +/belprop_fg_inf_engine.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// +/find_mpe.m/1.1.1.1/Thu Jun 20 00:02:12 2002// +/loopy_converged.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// +/set_params.m/1.1.1.1/Wed May 29 15:59:56 2002// +D diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Repository new file mode 100644 index 00000000..7e75998c --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/static/@belprop_fg_inf_engine diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Root b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/belprop_fg_inf_engine.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/belprop_fg_inf_engine.m new file mode 100644 index 00000000..1945c3f2 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/belprop_fg_inf_engine.m @@ -0,0 +1,47 @@ +function engine = belprop_fg_inf_engine(fg, varargin) +% BELPROP_FG_INF_ENGINE Make a belief propagation inference engine for factor graphs +% engine = belprop_fg_inf_engine(factor_graph, ...) +% +% The following optional arguments can be specified in the form of name/value pairs: +% [default in brackets] +% e.g., engine = belprop_inf_engine(fg, 'tol', 1e-2, 'max_iter', 10) +% +% max_iter - max. num. iterations [ 2*num_nodes ] +% momentum - weight assigned to old message in convex combination (useful for damping oscillations) [0] +% tol - tolerance used to assess convergence [1e-3] +% maximize - 1 means use max-product, 0 means use sum-product [0] +% +% This uses potential objects, like belprop_inf_engine, and hence is quite slow. + +engine = init_fields; +engine = class(engine, 'belprop_fg_inf_engine'); + +% set params to default values +N = length(fg.G); +engine.max_iter = 2*N; +engine.momentum = 0; +engine.tol = 1e-3; +engine.maximize = 0; + +% parse optional arguments +engine = set_params(engine, varargin); + +engine.fgraph = fg; + +% store results computed by enter_evidence here +engine.marginal_nodes = cell(1, fg.nvars); +engine.evidence = []; + + +%%%%%%%%%%%% + +function engine = init_fields() + +engine.fgraph = []; +engine.max_iter = []; +engine.momentum = []; +engine.tol = []; +engine.maximize = []; +engine.marginal_nodes = []; +engine.evidence = []; +engine.niter = []; diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/enter_evidence.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/enter_evidence.m new file mode 100644 index 00000000..e275e298 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/enter_evidence.m @@ -0,0 +1,126 @@ +function [engine, ll, niter] = enter_evidence(engine, evidence, varargin) +% ENTER_EVIDENCE Propagate evidence using belief propagation +% [engine, ll, niter] = enter_evidence(engine, evidence, ...) +% +% The log-likelihood is not computed; ll = 0. +% niter contains the number of iterations used +% +% The following optional arguments can be specified in the form of name/value pairs: +% [default value in brackets] +% +% maximize - 1 means use max-product, 0 means use sum-product [0] +% +% e.g., engine = enter_evidence(engine, ev, 'maximize', 1) + +ll = 0; +maximize = 0; + +if nargin >= 3 + args = varargin; + nargs = length(args); + for i=1:2:nargs + switch args{i}, + case 'maximize', maximize = args{i+1}; + otherwise, + error(['invalid argument name ' args{i}]); + end + end +end + +verbose = 0; + +ns = engine.fgraph.node_sizes; +onodes = find(~isemptycell(evidence)); +hnodes = find(isemptycell(evidence)); +cnodes = engine.fgraph.cnodes; +pot_type = determine_pot_type(engine.fgraph, onodes); + +% prime each local kernel with evidence (if any) +nfactors = engine.fgraph.nfactors; +nvars = engine.fgraph.nvars; +factors = cell(1,nfactors); +for f=1:nfactors + K = engine.fgraph.factors{engine.fgraph.equiv_class(f)}; + factors{f} = convert_to_pot(K, pot_type, engine.fgraph.dom{f}(:), evidence); +end + +% initialise msgs +msg_var_to_fac = cell(nvars, nfactors); +for x=1:nvars + for f=engine.fgraph.dep{x} + msg_var_to_fac{x,f} = mk_initial_pot(pot_type, x, ns, cnodes, onodes); + end +end +msg_fac_to_var = cell(nfactors, nvars); +dom = cell(1, nfactors); +for f=1:nfactors + %hdom{f} = myintersect(engine.fgraph.dom{f}, hnodes); + dom{f} = engine.fgraph.dom{f}(:)'; + for x=dom{f} + msg_fac_to_var{f,x} = mk_initial_pot(pot_type, x, ns, cnodes, onodes); + %msg_fac_to_var{f,x} = marginalize_pot(factors{f}, x); + end +end + + + +converged = 0; +iter = 1; +var_prod = cell(1, nvars); +fac_prod = cell(1, nfactors); + +while ~converged && (iter <= engine.max_iter) + if verbose, fprintf('iter %d\n', iter); end + + % absorb + old_var_prod = var_prod; + for x=1:nvars + var_prod{x} = mk_initial_pot(pot_type, x, ns, cnodes, onodes); + for f=engine.fgraph.dep{x} + var_prod{x} = multiply_by_pot(var_prod{x}, msg_fac_to_var{f,x}); + end + end + for f=1:nfactors + fac_prod{f} = mk_initial_pot(pot_type, dom{f}, ns, cnodes, onodes); + for x=dom{f} + fac_prod{f} = multiply_by_pot(fac_prod{f}, msg_var_to_fac{x,f}); + end + end + + % send msgs to neighbors + old_msg_var_to_fac = msg_var_to_fac; + old_msg_fac_to_var = msg_fac_to_var; + converged = 1; + for x=1:nvars + %if verbose, disp(['var ' num2str(x) ' sending to fac ' num2str(engine.fgraph.dep{x})]); end + for f=engine.fgraph.dep{x} + temp = divide_by_pot(var_prod{x}, old_msg_fac_to_var{f,x}); + msg_var_to_fac{x,f} = normalize_pot(temp); + if ~approxeq_pot(msg_var_to_fac{x,f}, old_msg_var_to_fac{x,f}, engine.tol), converged = 0; end + end + end + for f=1:nfactors + %if verbose, disp(['fac ' num2str(f) ' sending to var ' num2str(dom{f})]); end + for x=dom{f} + temp = divide_by_pot(fac_prod{f}, old_msg_var_to_fac{x,f}); + temp2 = multiply_by_pot(factors{f}, temp); + temp3 = marginalize_pot(temp2, x, maximize); + msg_fac_to_var{f,x} = normalize_pot(temp3); + if ~approxeq_pot(msg_fac_to_var{f,x}, old_msg_fac_to_var{f,x}, engine.tol), converged = 0; end + end + end + + if iter==1 + converged = 0; + end + iter = iter + 1; +end + +niter = iter - 1; +engine.niter = niter; + +for x=1:nvars + engine.marginal_nodes{x} = normalize_pot(var_prod{x}); +end + + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/find_mpe.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/find_mpe.m new file mode 100644 index 00000000..439936d5 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/find_mpe.m @@ -0,0 +1,49 @@ +function mpe = find_mpe(engine, evidence, varargin) +% FIND_MPE Find the most probable explanation of the data (belprop_fg) +% function mpe = find_mpe(engine, evidence,...) +% +% evidence{i} = [] if X(i) is hidden, and otherwise contains its observed value (scalar or column vector). +% +% This finds the marginally most likely value for each hidden node, +% and may give the wrong results even if the graph is acyclic, +% unless you set break_ties = 1. +% +% The following optional arguments can be specified in the form of name/value pairs: +% [default value in brackets] +% +% break_ties is optional. If 1, we will force ties to be broken consistently +% by calling enter_evidence N times. (see Jensen96, p106) Default = 1. + +break_ties = 1; + +% parse optional params +args = varargin; +nargs = length(args); +for i=1:2:nargs + switch args{i}, + case 'break_ties', break_ties = args{i+1}; + otherwise, + error(['invalid argument name ' args{i}]); + end +end + +engine = enter_evidence(engine, evidence, 'maximize', 1); + +observed = ~isemptycell(evidence); +evidence = evidence(:); % hack to handle unrolled DBNs +N = length(evidence); +mpe = cell(1,N); +for i=1:N + m = marginal_nodes(engine, i); + % observed nodes are all set to 1 inside the inference engine, so we must undo this + if observed(i) + mpe{i} = evidence{i}; + else + mpe{i} = argmax(m.T); + if break_ties + evidence{i} = mpe{i}; + [engine, ll] = enter_evidence(engine, evidence, 'maximize', 1); + end + end +end + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/loopy_converged.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/loopy_converged.m new file mode 100644 index 00000000..b9015e85 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/loopy_converged.m @@ -0,0 +1,12 @@ +function niter = loopy_converged(engine) +% LOOPY_CONVERGED Did loopy belief propagation converge? 0 means no, eles we return the num. iterations. +% function niter = loopy_converged(engine) +% +% We use a simple heuristic: we say convergence occurred if the number of iterations +% used was less than the maximum allowed. + +if engine.niter == engine.max_iter + niter = 0; +else + niter = engine.niter; +end diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/marginal_nodes.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/marginal_nodes.m new file mode 100644 index 00000000..0c85aed6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/marginal_nodes.m @@ -0,0 +1,6 @@ +function marginal = marginal_nodes(engine, query) +% MARGINAL_NODES Compute the marginal on the specified query nodes (belprop) +% marginal = marginal_nodes(engine, query) + +assert(length(query)==1); +marginal = pot_to_marginal(engine.marginal_nodes{query}); diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/set_params.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/set_params.m new file mode 100644 index 00000000..a495b3bb --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_fg_inf_engine/set_params.m @@ -0,0 +1,24 @@ +function engine = set_params(engine, varargin) +% SET_PARAMS Set the parameters (fields) for a belprop_inf_engine object +% engine = set_params(engine, name/value pairs) +% +% The following optional arguments can be specified in the form of name/value pairs: +% e.g., engine = set_params(engine, 'tol', 1e-2, 'max_iter', 10) +% +% max_iter - max. num. loopy iterations +% momentum - weight assigned to old message in convex combination +% tol - tolerance used to assess convergence +% maximize - 1 means use max-product, 0 means use sum-product + +args = varargin{1}; +nargs = length(args); +for i=1:2:nargs + switch args{i}, + case 'max_iter', engine.max_iter = args{i+1}; + case 'momentum', engine.momentum = args{i+1}; + case 'tol', engine.tol = args{i+1}; + case 'maximize', engine.maximize = args{i+1}; + otherwise, + error(['invalid argument name ' args{i}]); + end +end |