CVE Compared To VEContextual Variable EliminationMulti-Valued VariablesWhy CVE Does More Than Representing Factors As Trees

Why CVE Does More Than Representing Factors As Trees

It may seem that CVE is a confactor based representation for factors, in much the same way as the trees in the structured policy iteration [4] for solving MDPs. In this section we present a detailed example that explains why CVE can be much more efficient than a tree-based representation of the VE factors.

Example. Figure * shows a fragment of a belief network.

A fragment of a belief network: OT to eliminate.
 

This is an elaboration of Example *, where what affects the inside temperature depends on whether the air conditioning is broken or is working. All the variables are Boolean. We use the following interpretation:

FB
Fred's air conditioning is broken
FT
Fred's thermostat setting is high
OT
Outside temperature is hot
FH
Fred's house is hot
MB
Mary's air conditioning is broken
MT
Mary's thermostat setting is high
MH
Mary's house is hot
S
Season, that is true if it is Summer

The ancestors of FT, FB, S, MB, and MT are not shown. They can be multiply connected. Similarly, the descendants of FH and MH are not shown. They can be multiply connected.

The outside temperature (OT) is only relevant to Fred's house being hot (FH) when Fred's air conditioner is broken (FB is true) in which case Fred's thermostat setting (FT) is not relevant. Fred's thermostat setting (FT) is only relevant to Fred's house being hot (FH) when Fred's air conditioner is working (FB is false), in which case the outside (OT) is not relevant. And similarly for Mary's house. See Figure *. What is important to note is that FH and MH are dependent, but only if both air conditioners are broken, in which case the thermostat settings are irrelevant.

Tree-structured conditional probability tables for A and for B. Left branches correspond to true and right branches to false. Thus p1 = P(a|d &e), p2 = P(a|d &~e), etc.
 

Suppose we were to sum out OT in VE. Once OT is eliminated, FH and MH become dependent. In VE and bucket elimination we form a factor f(FH,MH,FT,FB,MB,MT,S) containing all the remaining variables. This factor represents P(FH,MH|FT,FB,MB,MT,S) (unless there is a pathological case such as if MT or MB is a descendent of FH, or if FT or FB is a descendent of MH). One could imagine a version of VE that builds a tree-based representation for this factor. We show here how the confactor-based version is exploiting more structure than this.

If we are to take the contextual independence into account, we need to consider the dependence between FH and MH when both FB and MB are true (in which case FT and MT are irrelevant). For all of the other contexts, we can treat FH and MH as independent. The algorithm CVE does this automatically.

The conditional probabilities of Figures * and * can be represented as the following confactors:

fb,
FH OT Value
true true p1
true false p2
false true 1-p1
false false 1-p2
 
~fb,
FH FT Value
true true p3
true false p4
false true 1-p3
false false 1-p4
 
mb,
MH OT Value
true true p5
true false p6
false true 1-p5
false false 1-p6
 
~mb,
MH MT Value
true true p7
true false p8
false true 1-p7
false false 1-p8
 
OT S Value
true true p9
true false p10
false true 1-p9
false false 1-p10
 

Eliminating OT from these confactors results in six confactors:

fb&mb,
FH MH S Value
true true true p9*(p5*p1)+(1-p9)*(p6*p2)
true true false p10*(p5*p1)+(1-p10)*(p6*p2)
true mbalse true p9*((1-p5)*p1)+(1-p9)*((1-p6)*p2)
true mbalse false p10*((1-p5)*p1)+(1-p10)*((1-p6)*p2)
false true true p9*(p5*(1-p1))+(1-p9)*(p6*(1-p2))
false true false p10*(p5*(1-p1))+(1-p10)*(p6*(1-p2))
false false true p9*((1-p5)*(1-p1))+(1-p9)*((1-p6)*(1-p2))
false false false p10*((1-p5)*(1-p1))+(1-p10)*((1-p6)*(1-p2))
 
fb&~mb,
FH S Value
true true p9*p1+(1-p9)*p2
true false p10*p1+(1-p10)*p2
false true p9*(1-p1)+(1-p9)*(1-p2)
false false p10*(1-p1)+(1-p10)*(1-p2)
 
~fb,
FH FT Value
true true p3
true false p4
false true 1-p3
false false 1-p4
 
~fb&mb,
MH S Value
true true p9*p5+(1-p9)*p6
true false p10*p5+(1-p10)*p6
false true p9*(1-p5)+(1-p9)*(1-p6)
false false p10*(1-p5)+(1-p10)*(1-p6)
 
~fb&~mb,
S Value
true p9+(1-p9)
false p10+(1-p10)
 
~mb,
MH MT Value
true true p7
true false p8
false true 1-p7
false false 1-p8
 

Note that the third and the sixth confactors were there originally and were not affected by eliminating OT. The resultant confactors encode the probabilities of {FH,MH} in the context fb&mb. For all other contexts, CVE considers FH and MH separately. The total table size of the confactors after OT is eliminated is 24.

Unlike VE or BEBA, we need the combined effect on FH and MH only for the contexts where OT is relevant to both FH and MH. For all other contexts, we don't need to combine the confactors for FH and MH. This is important, as combining the confactors is the primary source of combinatorial explosion. By avoiding combining confactors, we can have a potentially huge saving when the variable to be summed out appears in few contexts.


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

CVE Compared To VEContextual Variable EliminationMulti-Valued VariablesWhy CVE Does More Than Representing Factors As Trees