Databases Reference
In-Depth Information
f
B3
(x
Prop1
)
f
B2
(x
Prop1
,x
Cleanse
)
f
B3
(x
Prop2
)
f
B2
(x
Prop2
,x
Cleanse
)
f
B3
(x
Cleanse
)
x
ReadData1
x
ReadData2
x
Prop1
x
Prop2
x
Cleanse
x
WriteData
f
B1
(x
ReadData1
,x
Prop1
, x
WriteData
)
f
B1
(x
ReadData1
,x
Prop1
, x
WriteData
)
f
B1
(x
ReadData2
,x
Prop2
, x
WriteData
)
f
B1
(x
ReadData1
,x
Prop1
, x
WriteData
)
FIGURE 11.8: Factor graph for the propagation graph in Example 2.
line 14 (in our implementation, we picked this initial value to be 0.5), and we
set B
total
in to 1 in line 15.
Since the graph G
0
is a DAG, F(n) and F
total
(n) can be computed by
traversing potential sanitizers in topological sorted order, and B(n) and
B
total
in can be computed by traversing potential sanitizers in reverse topo-
logical order. The computation of F(n) and F
total
(n) in forward topological
order is done in lines 5{12 and the computation of B(n) and B
total
in in
reverse topological order is done in lines 17{24. Once F(n) and B(n) are
computed, W(n) is set to F(n) B(n) and s(n) is set to
W(n)
F
total
(n) B
total
(n)
W(n)
W
total
(n)
=
as shown in line 26.
Parameter tuning. The parameters low
1
, low
2
, high
1
, high
2
, high
3
, and
high
4
all need to be instantiated with any values between 0.0 and 1.0. In
Section 11.5 we show how to compute parameter values for low
1
associated
with the constraints B1 from the parameter values for the constraints A1. We
have experimented with varying the values of high
1
, high
2
, high
3
and high
4
from 0.8 to 0.95, and the low
1
, low
2
, values from 0.05 to 0.2 in increments
as small as .01. Fortunately, our inference is quite robust: these parameter
variations do not significantly affect the quality of results produced by the
inference in the applications we have tried.
Example 4 Figure 11.8 shows the factor graph obtained by applying al-
gorithm FactorGraph to the propagation graph in Figure 11.2. The marginal
probabilities for all variable nodes are computed by probabilistic inference on
the factor graph and these are used to classify sources, sanitizers, and sinks
in the propagation graph.
2
Search WWH ::
Custom Search