diff options
Diffstat (limited to 'sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine')
9 files changed, 316 insertions, 0 deletions
diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Entries b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Entries new file mode 100644 index 00000000..a2b559af --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Entries @@ -0,0 +1,7 @@ +/belprop_mrf2_inf_engine.m/1.1.1.1/Fri Jan 3 22:01:56 2003// +/bp_mrf2.m/1.1.1.1/Mon Jan 5 01:23:34 2004// +/enter_soft_evidence.m/1.1.1.1/Thu Jan 2 17:29:54 2003// +/find_mpe.m/1.1.1.1/Thu Jan 2 17:49:18 2003// +/marginal_nodes.m/1.1.1.1/Tue Dec 31 21:24:30 2002// +/set_params.m/1.1.1.1/Thu Jan 2 17:28:56 2003// +D diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Repository b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Repository new file mode 100644 index 00000000..fe4612c3 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Repository @@ -0,0 +1 @@ +FullBNT/BNT/inference/static/@belprop_mrf2_inf_engine diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Root b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_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_mrf2_inf_engine/belprop_mrf2_inf_engine.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/belprop_mrf2_inf_engine.m new file mode 100644 index 00000000..f7e9d695 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/belprop_mrf2_inf_engine.m @@ -0,0 +1,46 @@ +function engine = belprop_mrf2_inf_engine(mrf2, varargin) +% BELPROP_MRF2_INF_ENGINE Belief propagation for MRFs with discrete pairwise potentials +% engine = belprop_mrf2_inf_engine(mrf2, ...) +% +% This is like belprop_inf_engine, except it is designed for mrf2, so is much faster. +% +% [ ... ] = belprop_mrf2_inf_engine(..., 'param1',val1, 'param2',val2, ...) +% allows you to specify optional parameters as name/value pairs. +% Parameters modifying behavior of enter_evidence are below [default value in brackets] +% +% max_iter - max. num. iterations [ 5*nnodes] +% momentum - weight assigned to old message in convex combination +% (useful for damping oscillations) [0] +% tol - tolerance used to assess convergence [1e-3] +% verbose - 1 means print error at every iteration [0] +% +% Parameters can be changed later using set_params + + +% The advantages of pairwise potentials are +% (1) we can compute messages using vector-matrix multiplication +% (2) we can easily specify the parameters: one potential per edge +% In contrast, potentials on larger cliques are more complicated to deal with. + + +nnodes = length(mrf2.adj_mat); + +[engine.max_iter, engine.momentum, engine.tol, engine.verbose] = ... + process_options(varargin, 'max_iter', [], 'momentum', 0, 'tol', 1e-3, ... + 'verbose', 0); + +if isempty(engine.max_iter) % no user supplied value, so compute default + engine.max_iter = 5*nnodes; + %if acyclic(mrf2.adj_mat, 0) --- can be very slow! + % engine.max_iter = nnodes; + %else + % engine.max_iter = 5*nnodes; + %end +end + +engine.bel = cell(1, nnodes); % store results of enter_evidence here +engine.mrf2 = mrf2; + +engine = class(engine, 'belprop_mrf2_inf_engine'); + + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/bp_mrf2.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/bp_mrf2.m new file mode 100644 index 00000000..90baaba1 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/bp_mrf2.m @@ -0,0 +1,209 @@ +function [new_bel, niter, new_msg, edge_id, nstates] = bp_mrf2_general(adj_mat, pot, local_evidence, varargin) +% BP_MRF2_GENERAL Belief propagation on an MRF with pairwise potentials +% function [bel, niter] = bp_mrf2_general(adj_mat, pot, local_evidence, varargin) +% +% Input: +% adj_mat(i,j) = 1 iff there is an edge between nodes i and j +% pot(ki,kj,i,j) or pot{i,j}(ki,kj) = potential on edge between nodes i,j +% If the potentials on all edges are the same, +% you can just pass in 1 array, pot(ki,kj) +% local_evidence(state, node) or local_evidence{i}(k) = Pr(observation at node i | Xi=k) +% +% Use cell arrays if the hidden nodes do not all have the same number of values. +% +% Output: +% bel(k,i) or bel{i}(k) = P(Xi=k|evidence) +% niter contains the number of iterations used +% +% [ ... ] = bp_mrf2(..., 'param1',val1, 'param2',val2, ...) +% allows you to specify optional parameters as name/value pairs. +% Parameters names are below [default value in brackets] +% +% max_iter - max. num. iterations [ 5*nnodes] +% momentum - weight assigned to old message in convex combination +% (useful for damping oscillations) - currently ignored i[0] +% tol - tolerance used to assess convergence [1e-3] +% maximize - 1 means use max-product, 0 means use sum-product [0] +% verbose - 1 means print error at every iteration [0] +% +% fn - name of function to call at end of every iteration [ [] ] +% fnargs - we call feval(fn, bel, iter, fnargs{:}) [ [] ] + +nnodes = length(adj_mat); + +[max_iter, momentum, tol, maximize, verbose, fn, fnargs] = ... + process_options(varargin, 'max_iter', 5*nnodes, 'momentum', 0, ... + 'tol', 1e-3, 'maximize', 0, 'verbose', 0, ... + 'fn', [], 'fnargs', []); + +if iscell(local_evidence) + use_cell = 1; +else + use_cell = 0; + [nstates nnodes] = size(local_evidence); +end + +if iscell(pot) + tied_pot = 0; +else + tied_pot = (ndims(pot)==2); +end + + +% give each edge a unique number +ndx = find(adj_mat); +nedges = length(ndx); +edge_id = zeros(1, nnodes*nnodes); +edge_id(ndx) = 1:nedges; +edge_id = reshape(edge_id, nnodes, nnodes); + +% initialise messages +if use_cell + prod_of_msgs = cell(1, nnodes); + old_bel = cell(1, nnodes); + nstates = zeros(1, nnodes); + old_msg = cell(1, nedges); + for i=1:nnodes + nstates(i) = length(local_evidence{i}); + prod_of_msgs{i} = local_evidence{i}; + old_bel{i} = local_evidence{i}; + end + for i=1:nnodes + nbrs = find(adj_mat(:,i)); + for j=nbrs(:)' + old_msg{edge_id(i,j)} = normalise(ones(nstates(j),1)); + end + end +else + prod_of_msgs = local_evidence; + old_bel = local_evidence; + %old_msg = zeros(nstates, nnodes, nnodes); + old_msg = zeros(nstates, nedges); + m = normalise(ones(nstates,1)); + for i=1:nnodes + nbrs = find(adj_mat(:,i)); + for j=nbrs(:)' + old_msg(:, edge_id(i,j)) = m; + %old_msg(:,i,j) = m; + end + end +end + + +converged = 0; +iter = 1; + +while ~converged & (iter <= max_iter) + + % each node sends a msg to each of its neighbors + for i=1:nnodes + nbrs = find(adj_mat(i,:)); + for j=nbrs(:)' + if tied_pot + pot_ij = pot; + else + if iscell(pot) + pot_ij = pot{i,j}; + else + pot_ij = pot(:,:,i,j); + end + end + pot_ij = pot_ij'; % now pot_ij(xj, xi) + % so pot_ij * msg(xi) = sum_xi pot(xj,xi) msg(xi) = f(xj) + + if 1 + % Compute temp = product of all incoming msgs except from j + % by dividing out old msg from j from the product of all msgs sent to i + if use_cell + temp = prod_of_msgs{i}; + m = old_msg{edge_id(j,i)}; + else + temp = prod_of_msgs(:,i); + m = old_msg(:, edge_id(j,i)); + end + if any(m==0) + fprintf('iter=%d, send from i=%d to j=%d\n', iter, i, j); + keyboard + end + m = m + (m==0); % valid since m(k)=0 => temp(k)=0, so can replace 0's with anything + temp = temp ./ m; + temp_div = temp; + end + + if 1 + % Compute temp = product of all incoming msgs except from j in obvious way + if use_cell + %temp = ones(nstates(i),1); + temp = local_evidence{i}; + for k=nbrs(:)' + if k==j, continue, end; + temp = temp .* old_msg{edge_id(k,i)}; + end + else + %temp = ones(nstates,1); + temp = local_evidence(:,i); + for k=nbrs(:)' + if k==j, continue, end; + temp = temp .* old_msg(:, edge_id(k,i)); + end + end + end + %assert(approxeq(temp, temp_div)) + assert(approxeq(normalise(pot_ij * temp), normalise(pot_ij * temp_div))) + + if maximize + newm = max_mult(pot_ij, temp); % bottleneck + else + newm = pot_ij * temp; + end + newm = normalise(newm); + if use_cell + new_msg{edge_id(i,j)} = newm; + else + new_msg(:, edge_id(i,j)) = newm; + end + end % for j + end % for i + old_prod_of_msgs = prod_of_msgs; + + % each node multiplies all its incoming msgs and computes its local belief + if use_cell + for i=1:nnodes + nbrs = find(adj_mat(:,i)); + prod_of_msgs{i} = local_evidence{i}; + for j=nbrs(:)' + prod_of_msgs{i} = prod_of_msgs{i} .* new_msg{edge_id(j,i)}; + end + new_bel{i} = normalise(prod_of_msgs{i}); + end + err = abs(cat(1,new_bel{:}) - cat(1, old_bel{:})); + else + for i=1:nnodes + nbrs = find(adj_mat(:,i)); + prod_of_msgs(:,i) = local_evidence(:,i); + for j=nbrs(:)' + prod_of_msgs(:,i) = prod_of_msgs(:,i) .* new_msg(:,edge_id(j,i)); + end + new_bel(:,i) = normalise(prod_of_msgs(:,i)); + end + err = abs(new_bel(:) - old_bel(:)); + end + converged = all(err < tol); + if verbose, fprintf('error at iter %d = %f\n', iter, sum(err)); end + if ~isempty(fn) + if isempty(fnargs) + feval(fn, new_bel); + else + feval(fn, new_bel, iter, fnargs{:}); + end + end + + iter = iter + 1; + old_msg = new_msg; + old_bel = new_bel; +end % while + +niter = iter-1; + +fprintf('converged in %d iterations\n', niter); + diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/enter_soft_evidence.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/enter_soft_evidence.m new file mode 100644 index 00000000..032ca064 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/enter_soft_evidence.m @@ -0,0 +1,15 @@ +function [engine, ll, niter] = enter_soft_evidence(engine, local_evidence) +% ENTER_SOFT_EVIDENCE Propagate evidence using belief propagation +% [engine, ll, niter] = enter_soft_evidence(engine, local_evidence) +% +% local_evidence{i}(j) = Pr(observation at node i | S(i)=j) +% +% The log-likelihood is not computed; ll = 0. +% niter contains the number of iterations used + +ll = 0; +mrf2 = engine.mrf2; +[bel, niter] = bp_mrf2(mrf2.adj_mat, mrf2.pot, local_evidence, ... + 'max_iter', engine.max_iter, 'momentum', engine.momentum, ... + 'tol', engine.tol, 'maximize', 0, 'verbose', engine.verbose); +engine.bel = bel; diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/find_mpe.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/find_mpe.m new file mode 100644 index 00000000..fbd91265 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/find_mpe.m @@ -0,0 +1,12 @@ +function mpe = find_mpe(engine, local_evidence) +% FIND_MPE Find the most probable explanation of the data +% function mpe = find_mpe(engine, local_evidence +% +% local_evidence{i}(j) = Pr(observation at node i | S(i)=j) +% +% This finds the marginally most likely value for each hidden node. +% It may give inconsistent results if there are ties. + +[mpe, niter] = bp_mpe_mrf2(engine.mrf2.adj_mat, engine.mrf2.pot, local_evidence, ... + 'max_iter', engine.max_iter, 'momentum', engine.momentum, ... + 'tol', engine.tol); diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/marginal_nodes.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/marginal_nodes.m new file mode 100644 index 00000000..c51ed666 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/marginal_nodes.m @@ -0,0 +1,10 @@ +function marginal = marginal_nodes(engine, query) +% MARGINAL_NODES Compute the marginal on the specified query nodes (belprop) +% marginal = marginal_nodes(engine, query) +% +% query must be a single node + +if length(query)>1 + error('can only handle single node marginals') +end +marginal = engine.bel{query}; diff --git a/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/set_params.m b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/set_params.m new file mode 100644 index 00000000..f5328006 --- /dev/null +++ b/sourcecodes/bnt-master/BNT/inference/static/@belprop_mrf2_inf_engine/set_params.m @@ -0,0 +1,15 @@ +function engine = set_params(engine, varargin) +% SET_PARAMS Modify parameters of the inference engine +% engine = set_params(engine, 'param1',val1, 'param2',val2, ...) +% +% Parameter names are listed below. +% +% max_iter - max. num. iterations +% momentum - weight assigned to old message in convex combination +% (useful for damping oscillations) +% tol - tolerance used to assess convergence +% verbose - 1 means print error at every iteration [0] + +[engine.max_iter, engine.momentum, engine.tol, engine.verbose] = ... + process_options('max_iter', engine.max_iter, 'momentum', engine.momentum, ... + 'tol', engine.tol, 'verbose', engine.verbose); |