The Abstract Contextual Variable Elimination Algorithm |

To compute P(X|E _{1}=o_{1} &...&E_{s}=o_{s}) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Given multiset R of confactors | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

1. | Incorporate evidence as in Section *. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

2. | while there is a non-query variable to be eliminated | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Select non-query variable Y to eliminate; | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Call R := eliminate(Y,R); | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

3. | Compute posterior probability for X as in Section * |

Procedure eliminate(Y,R): | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

partition R into: | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rthose confactors in ^{-} = R that don't involve Y; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

R;^{*} = {r in R : r involves Y } | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

while there is { where <b_{1} ,T_{1}>,
<b_{2} ,T_{2}>} subset R^{*}b and _{1}b are
compatible,_{2} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

remove and
<b_{1} ,T_{1}> from <b_{2} ,T_{2}> R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

split on <b_{1} ,T_{1}>b putting residual confactors in _{2}R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

split
on <b_{2} ,T_{2}>b, putting residual confactors in
_{1}R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

add to <b_{1}&b_{2} ,T_{1}×_{t}T_{2}>R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

for every such that <b,t> in R^{*}Y appears in t | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

remove from <b,t> R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

add to <b,SUM_{Y}
t>R;^{-} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

while R is not empty^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

if { <b &Y=v_{1},T_{1}> ,...,
<b &Y=v_{k},T_{k}>} subset R^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

remove from <b &Y=v_{1},T_{1}> ,...,
<b &Y=v_{k},T_{k}>R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

add to <b ,T_{1}+_{t}...+_{t}T_{k}>R;^{-} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

else if { where <b_{1} &Y=v_{i} ,T_{1}>,
<b_{2} &Y=v_{j} ,T_{2}>} subset R^{*}b and _{1}b are
compatible and _{2}b_{1} != b_{2} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

{ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

remove and
<b_{1} &Y=v_{i} ,T_{1}> from <b_{2} &Y=v_{j} ,T_{2}>R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

split on
<b_{1} &Y=v_{i} ,T_{1}>b, putting all created confactors in _{2}R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

split
on <b_{2} &Y=v_{j} ,T_{2}>b, putting all created confactors in _{1}R;^{*} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

} | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return R.
^{-} |

× is defined in Section *._{t} | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

+ is defined in Section *._{t} | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

All set operations are assumed to be on multisets. |

Contextual Variable Elimination

The elimination procedure is called once for
each non-query, non-observed variable. The order in which the
variables are selected is called the **elimination ordering**.
This algorithm does not imply that the elimination ordering
has to be given a priori. The
other choice points are the order in which to do multiplication, and
the splitting ordering.

Note that in the *eliminate* algorithm, all set operations are assumed
to be on multisets. It is possible, and not uncommon, to get multiple
copies of the same confactor. One example where this happens is when
there is a naive Bayes model with variable *C* with no parents, and
variables *Y _{1},...,Y_{n}* each with only

To see the correctness of the procedure, note that all of the local
operations preserve the program invariants; we still need to check
that the algorithm halts. After the first
while-loop of eliminate, the contexts of the confactors in *R ^{*}* are mutually
exclusive and covering by the second part of the loop invariant. For
all complete contexts on the variables that remain after

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

The Abstract Contextual Variable Elimination Algorithm |