Exact & Approximate Inference in Bayesian Networks

The fundamental inference query in a Bayesian Network consists of:

• Query Variable X: The target variable whose posterior distribution we wish to compute.

• Evidence Variables E = {E_1, ..., E_k}: Variables observed to have specific instantiated values e = {e_1, ..., e_k}.

• Hidden Variables Y = {Y_1, ..., ..., Y_m}: All remaining unobserved non-query variables in the network (Y = Variables \setminus ({X} \cup E)).

We compute P(X \mid E = e) by marginalizing out all hidden variables:

$P(X \mid E = e) = \alpha P(X, E = e) = \alpha \sum_{y_1} \sum_{y_2} ... \sum_{y_m} P(X, e, y_1, y_2, ..., y_m)$

Where \alpha = \frac{1}{P(E = e)} = \frac{1}{\sum_x P(X = x, E = e)} is the normalization constant.

Enumeration repeats identical sub-calculations exponentially many times. Variable Elimination computes the sum efficiently by moving summations inside products (algebraic distributive law ab + ac = a(b + c)).

Core Operations on Factors:

1. Pointwise Factor Product: Multiplying two factors \phi_1(A, B) and \phi_2(B, C) yields a new factor \phi_3(A, B, C) = \phi_1(A, B) \cdot \phi_2(B, C).

2. Summing Out (Marginalization): Summing out variable B from factor \phi_3(A, B) yields a reduced factor \phi_4(A) = \sum_b \phi_3(A, B = b).

Variable Elimination Protocol:

1. Collect all initial CPTs as factors \Phi.

2. Set instantiated evidence values E = e across all factors.

3. Choose an elimination ordering for hidden variables Y_1, Y_2, ..., Y_m.

4. For each hidden variable Y_j:

• Remove from \Phi all factors mentioning Y_j.

• Multiply these factors together into a single composite factor.

• Sum out Y_j from this factor.

• Insert the resulting factor back into \Phi.

5. Multiply remaining factors containing query X and normalize by \alpha.