Exploiting Contextual Independence In Probabilistic Inference -- Summing Out A Variable That Appears In The Table

Summing Out A Variable That Appears In The Table

Summing Out A Variable That Appears In The Table

Suppose we are eliminating Y, and have a confactor:

<b ,t>

such that table t involves Y, and no other confactor that is compatible with b contains Y, we can replace this confactor with

<b ,SUM_Y t>

Note that after this operation Y is summed out in context b.

Correctness:

To see why this is correct, consider a context c on the remaining variables (c doesn't give a value for Y). If c isn't compatible with b, it isn't affected by this operation. If it is compatible with b, by elementary probability theory:

P(c) = SUM_i P(c &Y=v_i)

By the program invariant, and because there are no other confactors containing Y that are compatible with c, P(c &Y=v_i) = p_i p, for some product p of contributions of confactors that don't involve Y. Exactly the same confactors will be used for the different values of Y. Thus we have P(c) = p (SUM_i p_i ), and so we have maintained the first part of the program invariant. The second part of the program invariant is trivially maintained.

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

Summing Out A Variable That Appears In The Table