Daniel@0: % Find out how big the cliques are in an HHMM as a function of depth
Daniel@0: % (This is how we get the complexity bound of O(D K^{1.5D}).)
Daniel@0: 
Daniel@0: if 0
Daniel@0: Qsize = [];
Daniel@0: Fsize = [];
Daniel@0: Nclqs = [];
Daniel@0: end
Daniel@0: 
Daniel@0: ds = 1:15;
Daniel@0: 
Daniel@0: for d = ds
Daniel@0:   allQ = 1;
Daniel@0:   [intra, inter, Qnodes, Fnodes, Onode] = mk_hhmm_topo(d, allQ);
Daniel@0:   
Daniel@0:   N = length(intra);
Daniel@0:   ns = 2*ones(1,N);
Daniel@0:   
Daniel@0:   bnet = mk_dbn(intra, inter, ns);
Daniel@0:   for i=1:N
Daniel@0:     bnet.CPD{i} = tabular_CPD(bnet, i);
Daniel@0:   end
Daniel@0:   
Daniel@0:   if 0
Daniel@0:     T = 5;
Daniel@0:     dag = unroll_dbn_topology(intra, inter, T);
Daniel@0:     engine = jtree_unrolled_dbn_inf_engine(bnet, T, 'constrained', 1);
Daniel@0:     S = struct(engine);
Daniel@0:     S1 = struct(S.sub_engine);
Daniel@0:   end
Daniel@0:   
Daniel@0:   engine = jtree_dbn_inf_engine(bnet);
Daniel@0:   S = struct(engine);
Daniel@0:   J = S.jtree_struct;
Daniel@0:   
Daniel@0:   ss = 2*d+1;
Daniel@0:   Qnodes2 = Qnodes + ss;
Daniel@0:   QQnodes = [Qnodes Qnodes2];
Daniel@0:   
Daniel@0:   % find out how many Q nodes in each clique, and how many F nodes
Daniel@0:   C = length(J.cliques);
Daniel@0:   Nclqs(d) = 0;
Daniel@0:   for c=1:C
Daniel@0:     Qsize(c,d) = length(myintersect(J.cliques{c}, QQnodes));
Daniel@0:     Fsize(c,d) = length(myintersect(J.cliques{c}, Fnodes));
Daniel@0:     if length(J.cliques{c}) > 1 % exclude observed leaves
Daniel@0:       Nclqs(d) = Nclqs(d) + 1;
Daniel@0:     end
Daniel@0:   end
Daniel@0:   %pred_max_Qsize(d) = ceil(d+(d+1)/2);
Daniel@0:   pred_max_Qsize(d) = ceil(1.5*d);
Daniel@0:   
Daniel@0:   fprintf('d=%d\n', d);
Daniel@0:   %fprintf('D=%d, max F = %d. max Q = %d, pred max Q = %d\n', ...
Daniel@0: 	%  D, max(Fsize), max(Qsize), ceil(D+(D+1)/2));
Daniel@0: 	     
Daniel@0:   %histc(Qsize,1:max(Qsize)) % how many of each size?
Daniel@0: end % next d
Daniel@0: 
Daniel@0: 
Daniel@0: Q = 2;
Daniel@0: pred_mass = ds.*(Q.^ds) + Q.^(ceil(1.5 * ds))
Daniel@0: pred_mass2 = Q.^(ceil(1.5 * ds))
Daniel@0: 
Daniel@0: for d=ds
Daniel@0:   mass(d) = 0;
Daniel@0:   for c=1:C
Daniel@0:     mass(d) = mass(d) + Q^Qsize(c,d);
Daniel@0:   end
Daniel@0: end
Daniel@0:     
Daniel@0: 
Daniel@0: if 0
Daniel@0: %plot(ds, max(Qsize), 'o-',  ds, pred_max_Qsize, '*--');
Daniel@0: %plot(ds, max(Qsize), 'o-',  ds, 1.5*ds, '*--');
Daniel@0: %plot(ds, mass, 'o-',  ds, pred_mass, '*--');
Daniel@0: D = 15;
Daniel@0: %plot(ds(1:D), mass(1:D), 'bo-',  ds(1:D), pred_mass(1:D), 'g*--', ds(1:D), pred_mass2(1:D), 'k+-.');
Daniel@0: 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+-.');
Daniel@0: 
Daniel@0: grid on
Daniel@0: xlabel('depth of hierarchy')
Daniel@0: title('max num Q nodes in any clique vs. depth')
Daniel@0: legend('actual', 'predicted')
Daniel@0: 
Daniel@0: %previewfig(gcf, 'width', 3, 'height', 1.5, 'color', 'bw');
Daniel@0: %exportfig(gcf, '/home/cs/murphyk/WP/ConferencePapers/HHMM/clqsize2.eps', ...
Daniel@0: %          'width', 3, 'height', 1.5, 'color', 'bw');   
Daniel@0: 
Daniel@0: end
Daniel@0: 
Daniel@0: 
Daniel@0: if 0
Daniel@0: for d=ds
Daniel@0:   effnumclqs(d) = length(find(Qsize(:,d)>0));
Daniel@0: end
Daniel@0: ds = 1:10;
Daniel@0: Qs = 2:10;
Daniel@0: maxC = size(Qsize, 1);
Daniel@0: cost = [];
Daniel@0: cost_bound = [];
Daniel@0: for qi=1:length(Qs)
Daniel@0:   Q = Qs(qi);
Daniel@0:   for d=ds
Daniel@0:     cost(d,qi) = 0;
Daniel@0:     for c=1:maxC
Daniel@0:       if length(Qsize(c,d) > 0) % this clique contains Q nodes
Daniel@0: 	cost(d,qi) = cost(d,qi) + Q^Qsize(c,d)*2^Fsize(c,d);
Daniel@0:       end
Daniel@0:     end
Daniel@0:     %cost_bound(d,qi) = effnumclqs(d) * 8 * Q^(max(Qsize(:,d)));
Daniel@0:     cost_bound(d,qi) = (effnumclqs(d)*8) + Q^(max(Qsize(:,d)));
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: qi=2; plot(ds, cost(:,qi), 'o-',  ds, cost_bound(:,qi), '*--');
Daniel@0: end
Daniel@0: 
Daniel@0: 
Daniel@0: if 0
Daniel@0: % convert numbers in cliques into names
Daniel@0: for d=1:D
Daniel@0:   Fdecode(Fnodes(d)) = d;
Daniel@0: end
Daniel@0: for c=8:15
Daniel@0:   clqs = J.cliques{c};
Daniel@0:   fprintf('clique %d: ', c);
Daniel@0:   for k=clqs
Daniel@0:     if myismember(k, Qnodes)
Daniel@0:       fprintf('Q%d ', k)
Daniel@0:     elseif myismember(k, Fnodes)
Daniel@0:       fprintf('F%d ', Fdecode(k))
Daniel@0:     elseif isequal(k, Onode)
Daniel@0:       fprintf('O ')
Daniel@0:     elseif myismember(k, Qnodes2)
Daniel@0:       fprintf('Q%d* ', k-ss)
Daniel@0:     else
Daniel@0:       error(['unrecognized node ' k])
Daniel@0:     end
Daniel@0:   end
Daniel@0:   fprintf('\n');
Daniel@0: end
Daniel@0: end