Exploiting Contextual Independence In Probabilistic Inference -- Ones

Ones

Ones

In a Bayesian network we can remove a non-observed, non-query node with no children without changing the conditional probability of the query variable. This can be carried out recursively. In VE, if we were to eliminate such variables, we create factors that are all ones (as SUM_X P(X|Y) = 1).

In contextual VE, we can have a more subtle version when a variable may have no children in some contexts, even if it has children in another context.

Example. Consider eliminating B as in Example * where the belief network is given in Figure * and the structured conditional probabilities are given in Figure *). In the context ~a&c, the only confactors that are applicable are those that define P(B|YZ). As stated, the contextual VE algorithm, the following three confactors are created:

<~a&c&y,1[Z]>

<~a&c&~y,1>

where 1[Z] is a function of Z that has value 1 everywhere and 1 is the function of no variables that has value 1.

Confactors that have contribution 1 can be removed without affecting the correctness of the algorithms (as long as these confactors aren't the only confactors that contain a variable in some context). It is easy to show that the first part of the program invariant is maintained as multiplying by 1 doesn't affect any number. The second part of the invariant is also maintained, as there are always the confactors for the child (E in this case) that don't depend on the variable being eliminated, as well as the confactors for the parents of the variable being eliminated.

It is however probably better to never construct such confactors rather than to construct them and then throw them away. We show how this can be done in Section *.

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

Ones