| | | Examples of Eliminating Variables |
Example.
When we eliminate B from the confactors of Figure
*, we only need to consider the four confactors
that contain B. The preconditions for summing out B or for
multiplying are not satisfied, so we need to split. If we split the
first confactor for P(E|A,B,C,D) on Y (as in Example
*) and split the first confactor for P(B|Y,Z) on
A (as in Example *), we produce two confactors,
(*) and (*), that can be multiplied
producing:
These confactors should be contrasted with the factor on A,C,D,E,Y,Z (of
size 32) that is produced by eliminating B in VE.
This is the only confactor that contains B and is applicable
in the context a&y, so we can sum out B from the table,
producing the confactor:
a&y,
B E Z Value
true true true 0.4235
true true false 0.0935
true false true 0.3465
true false false 0.0765
false true true 0.069
false true false 0.249
false false true 0.161
false false false 0.581
The other nontrivial confactors produced when summing out B are:
a&y,
E Z Value
true true 0.4925
true false 0.3425
false true 0.5075
false false 0.6575
See Example * below for some trivial confactors produced and
how to avoid them.
a& ~y,
E Value
true 0.3675
false 0.6325
~a&~c&d&y,
E Z Value
true true 0.21475
true false 0.70975
false true 0.78525
false false 0.29025
~a&~c&d&~y,
E Value
true 0.62725
false 0.37275
Example.
Suppose that instead we were to eliminate D from the
confactors of Figure
*. This example differs from the previous example as
D appear in the bodies as well as in the tables.
The two confactors for P(E|A,B,C,D) that contain D, namely
< In order to be able to multiply
confactors, we can split confactor
(*) on Z producing:
The confactors for P(D|Y,Z) are <z,t7[D]> and
<z,t8[D,Y]>. We can split the first of these on A
producing
There are no other confactors containing D with context compatible with
confactor (*). The prerequisite required to sum
out D in the context a&z is satisfied. This results in the
confactor <a &z,1> where 1 is the factor of no variables
that has value 1. This can be removed as the product of 1 doesn't
change anything. Intuitively this can be justified because in the
context when A is true D has no children. We can detect this
case to improve efficiency (see Section *).
The confactor (*) can be split on C, producing
We can split confactor (*) on D producing:
We can now multiply confactor (*) and
(*), producing:
We can also split confactor (*) on Z,
producing:
We now have only complementary confactors for D in the context The other confactor produced when summing out D is:
~a &~c &d ,t3[B,E]> (confactor
(*)), and <~a &~c &~d
,t4[E]> (confactor (*)) are both compatible with both
confactors for P(D|Y,Z). So we cannot sum out the variable or
multiply any confactors.
< ~a &~c &d &z ,t3[B,E]>
< ~a &~c &d &~z ,t3[B,E]>
<a &z,t7[D]>
< ~a &z,t7[D]>
We can sum out D from confactor (*), producing <
< ~a &c &z,t7[D]>
< ~a &~c &z,t7[D]>
~a &c &z,1>, as in the previous case.
where 0.29 and 0.71 are the corresponding values from
t7[D]. These are functions of no variables, and so are just numbers.
< ~a &~c &d &z,0.29>
< ~a &~c &~d &z,0.71>
where 0.29 t3[B,E] is the table obtained by multiplying each element
of t3[B,E] by 0.29.
< ~a &~c &d &z ,0.29 t3[B,E]>
We can multiply confactors (*) and
(*), producing:
< ~a &~c &~d &z
,t4[E]>
< ~a &~c &~d &~z
,t4[E]>
< ~a &~c &~d &z
,0.71 t4[E]>
~a
&~c &z, namely confactors (*) and
(*) so we can sum-out D in this context resulting
in
where t9[B,E] is 0.29 t3[B,E]+t0.71 t4[E]. In full form
this is:
< ~a &~c &z
,t9[B,E]>
~a&~c&z,
B E Value
true true 0.36225
true false 0.63775
false true 0.6015
false false 0.3985
| | | Examples of Eliminating Variables |