When to SplitContextual Variable EliminationConfactor SplittingExamples 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:

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:
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:
E Value
true 0.3675
false 0.6325
E Z Value
true true 0.21475
true false 0.70975
false true 0.78525
false false 0.29025
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]>  
<~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:
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:

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.

When to SplitContextual Variable EliminationConfactor SplittingExamples of Eliminating Variables