Examples of Eliminating Variables

## Examples of Eliminating Variables

The four operations above are all that is needed to eliminate a variable. A variable is eliminated when it is summed out of all contexts.

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:

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
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,
 E Z Value true true 0.4925 true false 0.3425 false true 0.5075 false false 0.6575

The other nontrivial confactors produced when summing out B are:
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

See Example * below for some trivial confactors produced and how to avoid them.

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.

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 <`~`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.

In order to be able to multiply confactors, we can split confactor (*) on Z producing:

 <`~`a &`~`c &d &z ,t3[B,E]> <`~`a &`~`c &d &`~`z ,t3[B,E]>

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

 <`~`a &z,t7[D]>

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

 <`~`a &c &z,t7[D]> <`~`a &`~`c &z,t7[D]>
We can sum out D from confactor (*), producing <`~`a &c &z,1>, as in the previous case.

We can split confactor (*) on D producing:

 <`~`a &`~`c &d &z,0.29> <`~`a &`~`c &`~`d &z,0.71>
where 0.29 and 0.71 are the corresponding values from t7[D]. These are functions of no variables, and so are just numbers.

We can now multiply confactor (*) and (*), producing:

 <`~`a &`~`c &d &z ,0.29 t3[B,E]>
where 0.29 t3[B,E] is the table obtained by multiplying each element of t3[B,E] by 0.29.

We can also split confactor (*) on Z, producing:

 <`~`a &`~`c &`~`d &z ,t4[E]> <`~`a &`~`c &`~`d &`~`z ,t4[E]>
We can multiply confactors (*) and (*), producing:
 <`~`a &`~`c &`~`d &z ,0.71 t4[E]>

We now have only complementary confactors for D in the context `~`a &`~`c &z, namely confactors (*) and (*) so we can sum-out D in this context resulting in

 <`~`a &`~`c &z ,t9[B,E]>
where t9[B,E] is 0.29 t3[B,E]+t0.71 t4[E]. In full form this is:
`~`a&`~`c&z,
 B E Value true true 0.36225 true false 0.63775 false true 0.6015 false false 0.3985

The other confactor produced when summing out D is:

`~`a&`~`c&`~`z,
 B E Y Value true true true 0.12475 true true false 0.21975 true false true 0.87525 true false false 0.78025 false true true 0.7765 false true false 0.7065 false false true 0.2235 false false false 0.2935

David Poole and Nevin Lianwen Zhang,Exploiting Contextual Independence In Probabilistic Inference, Journal of Artificial Intelligence Research, 18, 2003, 263-313.

 Examples of Eliminating Variables