Mercurial > hg > camir-aes2014
diff toolboxes/FullBNT-1.0.7/bnt/examples/dynamic/HHMM/hhmm_jtree_clqs.m @ 0:e9a9cd732c1e tip
first hg version after svn
author | wolffd |
---|---|
date | Tue, 10 Feb 2015 15:05:51 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/toolboxes/FullBNT-1.0.7/bnt/examples/dynamic/HHMM/hhmm_jtree_clqs.m Tue Feb 10 15:05:51 2015 +0000 @@ -0,0 +1,143 @@ +% Find out how big the cliques are in an HHMM as a function of depth +% (This is how we get the complexity bound of O(D K^{1.5D}).) + +if 0 +Qsize = []; +Fsize = []; +Nclqs = []; +end + +ds = 1:15; + +for d = ds + allQ = 1; + [intra, inter, Qnodes, Fnodes, Onode] = mk_hhmm_topo(d, allQ); + + N = length(intra); + ns = 2*ones(1,N); + + bnet = mk_dbn(intra, inter, ns); + for i=1:N + bnet.CPD{i} = tabular_CPD(bnet, i); + end + + if 0 + T = 5; + dag = unroll_dbn_topology(intra, inter, T); + engine = jtree_unrolled_dbn_inf_engine(bnet, T, 'constrained', 1); + S = struct(engine); + S1 = struct(S.sub_engine); + end + + engine = jtree_dbn_inf_engine(bnet); + S = struct(engine); + J = S.jtree_struct; + + ss = 2*d+1; + Qnodes2 = Qnodes + ss; + QQnodes = [Qnodes Qnodes2]; + + % find out how many Q nodes in each clique, and how many F nodes + C = length(J.cliques); + Nclqs(d) = 0; + for c=1:C + Qsize(c,d) = length(myintersect(J.cliques{c}, QQnodes)); + Fsize(c,d) = length(myintersect(J.cliques{c}, Fnodes)); + if length(J.cliques{c}) > 1 % exclude observed leaves + Nclqs(d) = Nclqs(d) + 1; + end + end + %pred_max_Qsize(d) = ceil(d+(d+1)/2); + pred_max_Qsize(d) = ceil(1.5*d); + + fprintf('d=%d\n', d); + %fprintf('D=%d, max F = %d. max Q = %d, pred max Q = %d\n', ... + % D, max(Fsize), max(Qsize), ceil(D+(D+1)/2)); + + %histc(Qsize,1:max(Qsize)) % how many of each size? +end % next d + + +Q = 2; +pred_mass = ds.*(Q.^ds) + Q.^(ceil(1.5 * ds)) +pred_mass2 = Q.^(ceil(1.5 * ds)) + +for d=ds + mass(d) = 0; + for c=1:C + mass(d) = mass(d) + Q^Qsize(c,d); + end +end + + +if 0 +%plot(ds, max(Qsize), 'o-', ds, pred_max_Qsize, '*--'); +%plot(ds, max(Qsize), 'o-', ds, 1.5*ds, '*--'); +%plot(ds, mass, 'o-', ds, pred_mass, '*--'); +D = 15; +%plot(ds(1:D), mass(1:D), 'bo-', ds(1:D), pred_mass(1:D), 'g*--', ds(1:D), pred_mass2(1:D), 'k+-.'); +plot(ds(1:D), log(mass(1:D)), 'bo-', ds(1:D), log(pred_mass(1:D)), 'g*--', ds(1:D), log(pred_mass2(1:D)), 'k+-.'); + +grid on +xlabel('depth of hierarchy') +title('max num Q nodes in any clique vs. depth') +legend('actual', 'predicted') + +%previewfig(gcf, 'width', 3, 'height', 1.5, 'color', 'bw'); +%exportfig(gcf, '/home/cs/murphyk/WP/ConferencePapers/HHMM/clqsize2.eps', ... +% 'width', 3, 'height', 1.5, 'color', 'bw'); + +end + + +if 0 +for d=ds + effnumclqs(d) = length(find(Qsize(:,d)>0)); +end +ds = 1:10; +Qs = 2:10; +maxC = size(Qsize, 1); +cost = []; +cost_bound = []; +for qi=1:length(Qs) + Q = Qs(qi); + for d=ds + cost(d,qi) = 0; + for c=1:maxC + if length(Qsize(c,d) > 0) % this clique contains Q nodes + cost(d,qi) = cost(d,qi) + Q^Qsize(c,d)*2^Fsize(c,d); + end + end + %cost_bound(d,qi) = effnumclqs(d) * 8 * Q^(max(Qsize(:,d))); + cost_bound(d,qi) = (effnumclqs(d)*8) + Q^(max(Qsize(:,d))); + end +end + +qi=2; plot(ds, cost(:,qi), 'o-', ds, cost_bound(:,qi), '*--'); +end + + +if 0 +% convert numbers in cliques into names +for d=1:D + Fdecode(Fnodes(d)) = d; +end +for c=8:15 + clqs = J.cliques{c}; + fprintf('clique %d: ', c); + for k=clqs + if myismember(k, Qnodes) + fprintf('Q%d ', k) + elseif myismember(k, Fnodes) + fprintf('F%d ', Fdecode(k)) + elseif isequal(k, Onode) + fprintf('O ') + elseif myismember(k, Qnodes2) + fprintf('Q%d* ', k-ss) + else + error(['unrecognized node ' k]) + end + end + fprintf('\n'); +end +end