Database Reference
In-Depth Information
Algorithm 3
Approximation Algorithm for
P ()
. It improves
Algorithm 2
by updating continu-
ously the bounds
[
L, U
]
for
P ()
: therefore, one can stop the algorithm at any time and use the
bounds
instead of the exact probability. As in
Algorithm 2
, the rules for independent AND,
independent OR, and disjoint OR generalize from 2 subformulas to
m
≥
2 subformulas.
1:
Choose a non-atomic leaf node, expand it using one of the five rules in
Algorithm 2
.
2:
For each child
i
of
, compute
[
L, U
]
by applying repeatedly
Eq. (5.7)
and
Eq. (5.6)
.
3:
for all
non-leaf nodes
in the circuit, update its bounds
[
L
i
,U
i
]
[
L, U
]
:
do
/* Independent-AND */
if
≡
1
∧
2
then
4:
[
L, U
]=[
L
1
·
L
2
,U
1
·
U
2
]
/* Independent-OR */
if
5:
≡
1
∨
2
then
[
L, U
]=[
1
−
(
1
−
L
1
)
·
(
1
−
L
2
),
1
−
(
1
−
U
1
)
·
(
1
−
U
2
)
]
/* Disjoint-OR */
if
6:
≡
1
∨
2
then
[
L, U
]=[
L
1
+
L
2
,
min
(U
1
+
U
2
,
1
)
]
/* Negation */
if
7:
≡¬
1
then
[
L, U
]=[
1
−
U
1
,
1
−
L
1
]
/* Shannon expansion */
if
=
i
∧
(X
=
a
i
)
then
8:
[
L, U
]=[
L
i
·
P(X
=
a
i
),
U
i
·
P(X
=
a
i
)
]
9:
end for
modifying it such that it computes a circuit for
, rather than returning
P ()
directly, as we
described in
Section 5.2
. That is, each node of the circuit corresponds to some subformula, and each
non-leaf node is labeled with an an independent-AND, independent-OR, disjoint-OR, negation,
or Shannon-expansion. The algorithm starts with a circuit consisting of a single node, labeled
,
and no children. At each step, it chooses (using some heuristics) a leaf node that is not an atomic
formula; if
is the formula labeling the node, then the algorithm expands it by using one of the
five rules in
Subsection 5.1.1
. The algorithm terminates when all leaves in the circuit are labeled
with atomic formulas: the probabilities
P ()
can now be computed in linear time, by traversing the
circuit in topological order, from the leaves to the root node
.
Algorithm 3
shows the modified algorithm that can stop at any time an return some bound
[
L, U
]
for the probability
P ()
of a circuit node
. Whenever it expands a formula by applying
some rule, the bounds for the new leaf nodes are computed by applying repeatedly the rules
Eq. (5.6)
and
Eq. (5.7)
: after that, the algorithm updates the lower/upper bounds for all nodes in the circuit,
as shown in
Algorithm 3
. This update step can be optimized since only the nodes that are ancestors
of the node
need to be updated. Thus, at each moment, the algorithm has a pair of bounds
]
for the root node
, which improve over time. If the algorithm needs to be stopped early, one can
use the current bound. If the algorithm reaches atomic formulas for all leaf nodes in the circuit, then
L
=
U
=
P ()
and the algorithm returns the exact probability.
Absolute or relative approximations can be obtained for any given error
ε
: a value
[
L, U
p
is an ab-
solute
ε
-approximation of a probability
p
if
p
−
ε
≤
p
≤
p
+
ε
, and it is a relative
ε
-approximation
