This paper extends VE to exploit this finer-grain factorization. We will compute the answer to a query by summing out variables one by one from the factorization just as we did in VE .
The correctness of VE is guaranteed by the fact that factors in a homogeneous factorization can be combined (by multiplication) in any order and by the distributivity of multiplication over summations (see the proof of Theorem 1).
According to Proposition 3, the operator is
distributive over summations. However, factors in a heterogeneous factorization
cannot be combined in arbitrary order. For example, consider the
heterogeneous factorization (6). While it is correct
to combine
and
using
, and
to combine
and
using
,
it is not correct to combine
and
with
. We want to combine these latter two by multiplication,
but only after each has been combined with its sibling heterogeneous
factors.
To overcome this difficulty, a transformation called deputation will be performed on our BN. The transformation does not change the answers to queries. And the heterogeneous factorization represented by the transformed BN is flexible in the following sense:
A heterogeneous factorization of a joint probability is flexible if:
This property allows us to carry out multiplication of homogeneous
factors in arbitrary order, and since is associative and commutative,
combination of heterogeneous factors in arbitrary order.
If the conditions of Proposition 4 are satisfied, we can also
exchange a multiplication with a combination by
.
To guarantee the conditions of Proposition 4, the elimination ordering
needs to be constrained (Sections 7 and 8).
The heterogeneous factorization of
given at the end of the previous section is
not flexible. Consider combining all the heterogeneous factors.
Since the operator
is commutative and associative, one can first
combine, for each i, all the
's, obtaining
the conditional probability of
, and then combine the resulting
conditional probabilities. The combination
is not the same as the multiplication
because the
convergent variables and
appear in more than one factor.
Consequently, equation (7) does not hold and
the factorization is not flexible.
This problem arises when a convergent variable
is shared between two factors that are not siblings. For example, we
do not want to combine
and
using
. In order to tackle this problem we introduce a new
`deputation' variable so that each heterogeneous factor contains a
single convergent variable.
Deputation is a transformation that one can apply to a BN to make
the heterogeneous factorization represented by the BN flexible.
Let e be a convergent variable.
To depute e is to
make a copy of e, make
the parents of e be parents of
,
replace e with
in the contributing factors of e,
make
the only parent of
e, and set the conditional probability
as follows:
We shall call the deputy of e.
The deputy variable
is a
convergent variable by definition. The variable e, which is convergent
before deputation,
becomes a regular variable after deputation.
We shall refer to it as a new regular variable.
In contrast, we shall refer to the variables that are regular
before deputation as old regular variables.
The conditional probability
is
a homogeneous factor by definition.
It will sometimes be called the deputing function and written
as
since it ensures that
and e always take the same value.
Figure 2: The BN in Figure 1 after the deputation of convergent variables.
A deputation BN is obtained from a BN by deputing all the convergent variables. In a deputation BN, deputy variables are convergent variables and only deputy variables are convergent variables.
Figure 2 shows the deputation of the BN in Figure 1. It factorizes the joint probability
into homogeneous factors
and heterogeneous factors
This factorization has three important properties.
Proof: Consider the
combination, by , of all the heterogeneous
factors in the deputation BN.
Since the combination operator
is commutative
and associative, we can carry out the combination in
following two steps. First for each convergent (deputy) variable
,
combine all the heterogeneous factors that contain
,
yielding the conditional probability
of
.
Then combine
those resulting conditional probabilities.
It follows from the first property mentioned above that
for different convergent variables
and
,
and
do not share convergent variables. Hence the combination
of the
's is just the multiplication of them.
Consequently, the combination, by
,
of all heterogeneous factors in a deputation BN
is just the multiplication of the conditional probabilities of
all convergent variables. Therefore, we have
The proposition is hence proved.
Deputation does not change the answer to a query. More precisely, we have
Proof: Let R, E, and be the lists
of old regular, new regular, and deputy variables in the
deputation BN respectively. It suffices to show that
is the same in the original BN as in the deputation
BN. For any new regular variable e, let
be its deputy.
It is easy to see that the quantity
in the deputation BN is the
same as
in the original BN. Hence,
The proposition is proved.