wolffd@0
|
1 % Find out how big the cliques are in an HHMM as a function of depth
|
wolffd@0
|
2 % (This is how we get the complexity bound of O(D K^{1.5D}).)
|
wolffd@0
|
3
|
wolffd@0
|
4 if 0
|
wolffd@0
|
5 Qsize = [];
|
wolffd@0
|
6 Fsize = [];
|
wolffd@0
|
7 Nclqs = [];
|
wolffd@0
|
8 end
|
wolffd@0
|
9
|
wolffd@0
|
10 ds = 1:15;
|
wolffd@0
|
11
|
wolffd@0
|
12 for d = ds
|
wolffd@0
|
13 allQ = 1;
|
wolffd@0
|
14 [intra, inter, Qnodes, Fnodes, Onode] = mk_hhmm_topo(d, allQ);
|
wolffd@0
|
15
|
wolffd@0
|
16 N = length(intra);
|
wolffd@0
|
17 ns = 2*ones(1,N);
|
wolffd@0
|
18
|
wolffd@0
|
19 bnet = mk_dbn(intra, inter, ns);
|
wolffd@0
|
20 for i=1:N
|
wolffd@0
|
21 bnet.CPD{i} = tabular_CPD(bnet, i);
|
wolffd@0
|
22 end
|
wolffd@0
|
23
|
wolffd@0
|
24 if 0
|
wolffd@0
|
25 T = 5;
|
wolffd@0
|
26 dag = unroll_dbn_topology(intra, inter, T);
|
wolffd@0
|
27 engine = jtree_unrolled_dbn_inf_engine(bnet, T, 'constrained', 1);
|
wolffd@0
|
28 S = struct(engine);
|
wolffd@0
|
29 S1 = struct(S.sub_engine);
|
wolffd@0
|
30 end
|
wolffd@0
|
31
|
wolffd@0
|
32 engine = jtree_dbn_inf_engine(bnet);
|
wolffd@0
|
33 S = struct(engine);
|
wolffd@0
|
34 J = S.jtree_struct;
|
wolffd@0
|
35
|
wolffd@0
|
36 ss = 2*d+1;
|
wolffd@0
|
37 Qnodes2 = Qnodes + ss;
|
wolffd@0
|
38 QQnodes = [Qnodes Qnodes2];
|
wolffd@0
|
39
|
wolffd@0
|
40 % find out how many Q nodes in each clique, and how many F nodes
|
wolffd@0
|
41 C = length(J.cliques);
|
wolffd@0
|
42 Nclqs(d) = 0;
|
wolffd@0
|
43 for c=1:C
|
wolffd@0
|
44 Qsize(c,d) = length(myintersect(J.cliques{c}, QQnodes));
|
wolffd@0
|
45 Fsize(c,d) = length(myintersect(J.cliques{c}, Fnodes));
|
wolffd@0
|
46 if length(J.cliques{c}) > 1 % exclude observed leaves
|
wolffd@0
|
47 Nclqs(d) = Nclqs(d) + 1;
|
wolffd@0
|
48 end
|
wolffd@0
|
49 end
|
wolffd@0
|
50 %pred_max_Qsize(d) = ceil(d+(d+1)/2);
|
wolffd@0
|
51 pred_max_Qsize(d) = ceil(1.5*d);
|
wolffd@0
|
52
|
wolffd@0
|
53 fprintf('d=%d\n', d);
|
wolffd@0
|
54 %fprintf('D=%d, max F = %d. max Q = %d, pred max Q = %d\n', ...
|
wolffd@0
|
55 % D, max(Fsize), max(Qsize), ceil(D+(D+1)/2));
|
wolffd@0
|
56
|
wolffd@0
|
57 %histc(Qsize,1:max(Qsize)) % how many of each size?
|
wolffd@0
|
58 end % next d
|
wolffd@0
|
59
|
wolffd@0
|
60
|
wolffd@0
|
61 Q = 2;
|
wolffd@0
|
62 pred_mass = ds.*(Q.^ds) + Q.^(ceil(1.5 * ds))
|
wolffd@0
|
63 pred_mass2 = Q.^(ceil(1.5 * ds))
|
wolffd@0
|
64
|
wolffd@0
|
65 for d=ds
|
wolffd@0
|
66 mass(d) = 0;
|
wolffd@0
|
67 for c=1:C
|
wolffd@0
|
68 mass(d) = mass(d) + Q^Qsize(c,d);
|
wolffd@0
|
69 end
|
wolffd@0
|
70 end
|
wolffd@0
|
71
|
wolffd@0
|
72
|
wolffd@0
|
73 if 0
|
wolffd@0
|
74 %plot(ds, max(Qsize), 'o-', ds, pred_max_Qsize, '*--');
|
wolffd@0
|
75 %plot(ds, max(Qsize), 'o-', ds, 1.5*ds, '*--');
|
wolffd@0
|
76 %plot(ds, mass, 'o-', ds, pred_mass, '*--');
|
wolffd@0
|
77 D = 15;
|
wolffd@0
|
78 %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
|
79 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
|
80
|
wolffd@0
|
81 grid on
|
wolffd@0
|
82 xlabel('depth of hierarchy')
|
wolffd@0
|
83 title('max num Q nodes in any clique vs. depth')
|
wolffd@0
|
84 legend('actual', 'predicted')
|
wolffd@0
|
85
|
wolffd@0
|
86 %previewfig(gcf, 'width', 3, 'height', 1.5, 'color', 'bw');
|
wolffd@0
|
87 %exportfig(gcf, '/home/cs/murphyk/WP/ConferencePapers/HHMM/clqsize2.eps', ...
|
wolffd@0
|
88 % 'width', 3, 'height', 1.5, 'color', 'bw');
|
wolffd@0
|
89
|
wolffd@0
|
90 end
|
wolffd@0
|
91
|
wolffd@0
|
92
|
wolffd@0
|
93 if 0
|
wolffd@0
|
94 for d=ds
|
wolffd@0
|
95 effnumclqs(d) = length(find(Qsize(:,d)>0));
|
wolffd@0
|
96 end
|
wolffd@0
|
97 ds = 1:10;
|
wolffd@0
|
98 Qs = 2:10;
|
wolffd@0
|
99 maxC = size(Qsize, 1);
|
wolffd@0
|
100 cost = [];
|
wolffd@0
|
101 cost_bound = [];
|
wolffd@0
|
102 for qi=1:length(Qs)
|
wolffd@0
|
103 Q = Qs(qi);
|
wolffd@0
|
104 for d=ds
|
wolffd@0
|
105 cost(d,qi) = 0;
|
wolffd@0
|
106 for c=1:maxC
|
wolffd@0
|
107 if length(Qsize(c,d) > 0) % this clique contains Q nodes
|
wolffd@0
|
108 cost(d,qi) = cost(d,qi) + Q^Qsize(c,d)*2^Fsize(c,d);
|
wolffd@0
|
109 end
|
wolffd@0
|
110 end
|
wolffd@0
|
111 %cost_bound(d,qi) = effnumclqs(d) * 8 * Q^(max(Qsize(:,d)));
|
wolffd@0
|
112 cost_bound(d,qi) = (effnumclqs(d)*8) + Q^(max(Qsize(:,d)));
|
wolffd@0
|
113 end
|
wolffd@0
|
114 end
|
wolffd@0
|
115
|
wolffd@0
|
116 qi=2; plot(ds, cost(:,qi), 'o-', ds, cost_bound(:,qi), '*--');
|
wolffd@0
|
117 end
|
wolffd@0
|
118
|
wolffd@0
|
119
|
wolffd@0
|
120 if 0
|
wolffd@0
|
121 % convert numbers in cliques into names
|
wolffd@0
|
122 for d=1:D
|
wolffd@0
|
123 Fdecode(Fnodes(d)) = d;
|
wolffd@0
|
124 end
|
wolffd@0
|
125 for c=8:15
|
wolffd@0
|
126 clqs = J.cliques{c};
|
wolffd@0
|
127 fprintf('clique %d: ', c);
|
wolffd@0
|
128 for k=clqs
|
wolffd@0
|
129 if myismember(k, Qnodes)
|
wolffd@0
|
130 fprintf('Q%d ', k)
|
wolffd@0
|
131 elseif myismember(k, Fnodes)
|
wolffd@0
|
132 fprintf('F%d ', Fdecode(k))
|
wolffd@0
|
133 elseif isequal(k, Onode)
|
wolffd@0
|
134 fprintf('O ')
|
wolffd@0
|
135 elseif myismember(k, Qnodes2)
|
wolffd@0
|
136 fprintf('Q%d* ', k-ss)
|
wolffd@0
|
137 else
|
wolffd@0
|
138 error(['unrecognized node ' k])
|
wolffd@0
|
139 end
|
wolffd@0
|
140 end
|
wolffd@0
|
141 fprintf('\n');
|
wolffd@0
|
142 end
|
wolffd@0
|
143 end
|