1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
function CPD = boolean_CPD(bnet, self, ftype, fname, pfail)
% BOOLEAN_CPD Make a tabular CPD representing a (noisy) boolean function
%
% CPD = boolean_cpd(bnet, self, 'inline', f) uses the inline function f
% to specify the CPT.
% e.g., suppose X4 = X2 AND (NOT X3). Then we can write
% bnet.CPD{4} = boolean_CPD(bnet, 4, 'inline', inline('(x(1) & ~x(2)'));
% Note that x(1) refers pvals(1) = X2, and x(2) refers to pvals(2)=X3.
%
% CPD = boolean_cpd(bnet, self, 'named', f) assumes f is a function name.
% f can be built-in to matlab, or a file.
% e.g., If X4 = X2 AND X3, we can write
% bnet.CPD{4} = boolean_CPD(bnet, 4, 'named', 'and');
% e.g., If X4 = X2 OR X3, we can write
% bnet.CPD{4} = boolean_CPD(bnet, 4, 'named', 'any');
%
% CPD = boolean_cpd(bnet, self, 'rnd') makes a random non-redundant bool fn.
%
% CPD = boolean_CPD(bnet, self, 'inline'/'named', f, pfail)
% will put probability mass 1-pfail on f(parents), and put pfail on the other value.
% This is useful for simulating noisy boolean functions.
% If pfail is omitted, it is set to 0.
% (Note that adding noise to a random (non-redundant) boolean function just creates a different
% (potentially redundant) random boolean function.)
%
% Note: This cannot be used to simulate a noisy-OR gate.
% Example: suppose C has parents A and B, and the
% link of A->C fails with prob pA and the link B->C fails with pB.
% Then the noisy-OR gate defines the following distribution
%
% A B P(C=0)
% 0 0 1.0
% 1 0 pA
% 0 1 pB
% 1 1 pA * PB
%
% By contrast, boolean_CPD(bnet, C, 'any', p) would define
%
% A B P(C=0)
% 0 0 1-p
% 1 0 p
% 0 1 p
% 1 1 p
if nargin==0
% This occurs if we are trying to load an object from a file.
CPD = tabular_CPD(bnet, self);
return;
elseif isa(bnet, 'boolean_CPD')
% This might occur if we are copying an object.
CPD = bnet;
return;
end
if nargin < 5, pfail = 0; end
ps = parents(bnet.dag, self);
ns = bnet.node_sizes;
psizes = ns(ps);
self_size = ns(self);
psucc = 1-pfail;
k = length(ps);
switch ftype
case 'inline', f = eval_bool_fn(fname, k);
case 'named', f = eval_bool_fn(fname, k);
case 'rnd', f = mk_rnd_bool_fn(k);
otherwise, error(['unknown function type ' ftype]);
end
CPT = zeros(prod(psizes), self_size);
ndx = find(f==0);
CPT(ndx, 1) = psucc;
CPT(ndx, 2) = pfail;
ndx = find(f==1);
CPT(ndx, 2) = psucc;
CPT(ndx, 1) = pfail;
if k > 0
CPT = reshape(CPT, [psizes self_size]);
end
clamp = 1;
CPD = tabular_CPD(bnet, self, CPT, [], clamp);
%%%%%%%%%%%%
function f = eval_bool_fn(fname, n)
% EVAL_BOOL_FN Evaluate a boolean function on all bit vectors of length n
% f = eval_bool_fn(fname, n)
%
% e.g. f = eval_bool_fn(inline('x(1) & x(3)'), 3)
% returns 0 0 0 0 0 1 0 1
ns = 2*ones(1, n);
f = zeros(1, 2^n);
bits = ind2subv(ns, 1:2^n);
for i=1:2^n
f(i) = feval(fname, bits(i,:)-1);
end
%%%%%%%%%%%%%%%
function f = mk_rnd_bool_fn(n)
% MK_RND_BOOL_FN Make a random bit vector of length n that encodes a non-redundant boolean function
% f = mk_rnd_bool_fn(n)
red = 1;
while red
f = sample_discrete([0.5 0.5], 2^n, 1)-1;
red = redundant_bool_fn(f);
end
%%%%%%%%
function red = redundant_bool_fn(f)
% REDUNDANT_BOOL_FN Does a boolean function depend on all its input values?
% r = redundant_bool_fn(f)
%
% f is a vector of length 2^n, representing the output for each bit vector.
% An input is redundant if there is no assignment to the other bits
% which changes the output e.g., input 1 is redundant if u(2:n) s.t.,
% f([0 u(2:n)]) <> f([1 u(2:n)]).
% A function is redundant it it has any redundant inputs.
n = log2(length(f));
ns = 2*ones(1,n);
red = 0;
for i=1:n
ens = ns;
ens(i) = 1;
U = ind2subv(ens, 1:2^(n-1));
U(:,i) = 1;
f1 = f(subv2ind(ns, U));
U(:,i) = 2;
f2 = f(subv2ind(ns, U));
if isequal(f1, f2)
red = 1;
return;
end
end
%%%%%%%%%%
function [b, iter] = rnd_truth_table(N)
% RND_TRUTH_TABLE Construct the output of a random truth table s.t. each input is non-redundant
% b = rnd_truth_table(N)
%
% N is the number of inputs.
% b is a random bit string of length N, representing the output of the truth table.
% Non-redundant means that, for each input position k,
% there are at least two bit patterns, u and v, that differ only in the k'th position,
% s.t., f(u) ~= f(v), where f is the function represented by b.
% We use rejection sampling to ensure non-redundancy.
%
% Example: b = [0 0 0 1 0 0 0 1] is indep of 3rd input (AND of inputs 1 and 2)
bits = ind2subv(2*ones(1,N), 1:2^N)-1;
redundant = 1;
iter = 0;
while redundant && (iter < 4)
iter = iter + 1;
b = sample_discrete([0.5 0.5], 1, 2^N)-1;
redundant = 0;
for i=1:N
on = find(bits(:,i)==1);
off = find(bits(:,i)==0);
if isequal(b(on), b(off))
redundant = 1;
break;
end
end
end
|
