Database Reference
In-Depth Information
Algorithm 2
Algorithm for Computing
P ()
. The
Independent AND
and
Independent OR
rules
apply only if
Va r (
1
)
∩
holds; these rules generalize from 2 subformulas to
m
≥
2
subformulas. The
Disjoint OR
rule applies only if
1
∧
Va r (
2
)
=∅
false
. As a special case, the Shannon
expansion rule gives us a rule for atomic formulas: if
=
(X
=
a)
, then return the probability of
the atomic predicate
P(X
2
≡
=
a)
.
1:
if
≡
1
∧
2
then
P(
1
)
·
P(
2
)
/* Independent AND */
2:
if
≡
1
∨
2
then
1
−
(
1
−
P(
1
))
·
(
1
−
P(
2
))
/* Independent OR */
3:
if
≡
1
∨
2
then
P(
1
)
+
P(
2
)
/* Disjoint OR */
4:
if
≡¬
1
then
1
−
P(
1
)
/* Negation */
Va r ()
then
a
∈
Dom
X
P(
|
X
=
a
)P (X
=
a)
5:
choose
X
∈
/* Shannon expansion */
Now, we recurse into
1
and
2
.For
1
, we apply the independent-or rule and obtain
P(
1
)
=
1
−
(
1
−
P(X))
·
(
1
−
P (Y )).
For
2
, we cannot apply the independent-and or independent-or rules since the two conjuncts are
not independent. The first applicable rule is the disjoint-or rule:
P(
2
)
=
P(
3
)
+
P(
4
),
where
3
=
Z
∧
U,
and
4
=¬
Z
∧
V.
We continue with
3
and
4
: both can be decomposed into atomic formuals using the independent-
and rule.
The running time of the algorithm can vary from linear time, to exponential time in the size
of the formula
. It depends dramatically on the number and order of Shannon expansion steps; we
return to this topic in
Section 5.2
. At an extreme case, if the algorithm can be executed by applying
only the independent-and and independent-or rules, then it runs in linear time in the size of the
expression
. On the other hand, if it needs to apply Shannon's expansion
n
times, then it runs in
exponential time in
n
.
The algorithm should be implemented using dynamic programming instead of recursive calls,
in order to avoid processing the same expression repeatedly. For example, consider the simple propo-
sitional formula
n
=
X
1
Y
1
∨
X
2
Y
2
∨
...
∨
X
n
Y
n
, and suppose we decide to use only Shannon
expansion. Assume we eliminate the variables in the order
X
n
,Y
n
,X
n
−
1
,Y
n
−
1
,...
After eliminat-
ing
X
n
then
Y
n
, we obtain:
P(
n
)
=
P(X
n
)
·
P(Y
n
)
+
P(
n
−
1
)
·
P(X
n
)
·
(
1
−
P(Y
n
))
+
P(
n
−
1
)
·
(
1
−
P(X
n
))
·
P(Y
n
)
+
P(
n
−
1
)
·
(
1
−
P(X
n
))
·
(
1
−
P(Y
n
))
Here
P(
n
−
1
)
occurs three times, and a naïve recursive evaluation of the algorithm has
a running time
O(
3
n
)
. With dynamic programming, we store the values
P(
k
)
for every
k
=
1
,
2
,...,n
, and the running time is
O(n)
.
