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