comparison toolboxes/FullBNT-1.0.7/bnt/inference/dynamic/@frontier_inf_engine/frontier_inf_engine.m @ 0:e9a9cd732c1e tip

first hg version after svn

+function engine = frontier_inf_engine(bnet)
+% FRONTIER_INF_ENGINE Inference engine for DBNs which which uses the frontier algorithm.
+% engine = frontier_inf_engine(bnet)
+%
+% The frontier algorithm extends the forwards-backwards algorithm to DBNs in the obvious way,
+% maintaining a joint distribution (frontier) over all the nodes in a time slice.
+% When all the hidden nodes in the DBN are persistent (have children in the next time slice),
+% its theoretical running time is often similar to that of the junction tree algorithm,
+% although in practice, this algorithm seems to very slow (at least in matlab).
+% However, it is extremely simple to describe and implement.
+%
+% Suppose there are n binary nodes per slice, so the frontier takes O(2^n) space.
+% Each time step takes between O(n 2^{n+1}) and O(n 2^{2n}) operations, depending on the graph structure.
+% The lower bound is achieved by a set of n independent chains, as in a factorial HMM.
+% The upper bound is achieved by a set of n fully interconnected chains, as in an HMM.
+%
+% The factor of n arises because we need to multiply in each CPD from slice t+1.
+% The second factor depends on the size of the frontier to which we add the new node.
+% In an FHMM, once we have added X(i,t+1), we can marginalize out X(i,t) from the frontier, since
+% no other nodes depend on it; hence the frontier never contains more than n+1 nodes.
+% In a fully coupled HMM, we must leave X(i,t) in the frontier until all X(j,t+1) have been
+% added; hence the frontier will contain 2*n nodes at its peak.
+%
+% For details, see
+%   "The Factored Frontier Algorithm for Approximate Inference in DBNs",
+%   Kevin Murphy and Yair Weiss, UAI 01.
+
+ns = bnet.node_sizes_slice;
+onodes = bnet.observed;
+ns(onodes) = 1;
+ss = length(bnet.intra);
+
+[engine.ops, engine.fdom] = best_first_frontier_seq(ns, bnet.dag);
+engine.ops1 = 1:ss;
+
+engine.fwdback = [];
+engine.fwd_frontier = [];
+engine.back_frontier = [];
+
+engine.fdom1 = cell(1,ss);
+for s=1:ss
+  engine.fdom1{s} = 1:s;
+end
+
+engine = class(engine, 'frontier_inf_engine', inf_engine(bnet));
+
+
+%%%%%%%%%
+
+function [ops, frontier_set] = best_first_frontier_seq(ns, dag)
+% BEST_FIRST_FRONTIER_SEQ Do a greedy search for the sequence of additions/removals to the frontier.
+% [ops, frontier_set] = best_first_frontier_seq(ns, dag)
+%
+% We maintain 3 sets: the frontier (F), the right set (R), and the left set (L).
+% The invariant is that the nodes in R are d-separated from L given F.
+% We start with slice 1 in F and slice 2 in R.
+% The goal is to move slice 1 from F to L, and slice 2 from R to F, so as to minimize the size
+% of the frontier at each step, where the size(F) = product of the node-sizes of nodes in F.
+% A node may be removed (from F to L) if it has no children in R.
+% A node may be added (from R to F) if its parents are in F.
+%
+% ns(i) = num. discrete values node i can take on (i=1..ss, where ss = slice size)
+% dag is the (2*ss) x (2*ss) adjacency matrix for the 2-slice DBN.
+
+% Example:
+%
+% 4    9
+% ^    ^
+% |    |
+% 2 -> 7
+% ^    ^
+% |    |
+% 1 -> 6
+% |    |
+% v    v
+% 3 -> 8
+% |    |
+% v    V
+% 5    10
+%
+% ops = -4, -5, 6, -1, 7, -2, 8, -3, 9, 10
+
+ss = length(ns);
+ns = [ns(:)' ns(:)'];
+ops = zeros(1,ss);
+L = []; F = 1:ss; R = (1:ss)+ss;
+frontier_set = cell(1,2*ss);
+for s=1:2*ss
+  remcost = inf*ones(1,2*ss);
+  %disp(['L: ' num2str(L) ', F: ' num2str(F) ', R: ' num2str(R)]);
+  maybe_removable = myintersect(F, 1:ss);
+  for n=maybe_removable(:)'
+    cs = children(dag, n);
+    if isempty(myintersect(cs, R))
+      remcost(n) = prod(ns(mysetdiff(F, n)));
+    end
+  end
+  %remcost
+  if any(remcost < inf)
+    n = argmin(remcost);
+    ops(s) = -n;
+    L = myunion(L, n);
+    F = mysetdiff(F, n);
+  else
+    addcost = inf*ones(1,2*ss);
+    for n=R(:)'
+      ps = parents(dag, n);
+      if mysubset(ps, F)
+	addcost(n) = prod(ns(myunion(F, [ps n])));
+      end
+    end
+    %addcost
+    assert(any(addcost < inf));
+    n = argmin(addcost);
+    ops(s) = n;
+    R  = mysetdiff(R, n);
+    F = myunion(F, n);
+  end
+  %fprintf('op at step %d = %d\n\n', s, ops(s));
+  frontier_set{s} = F;
+end