6.3.3. Inference in Bayes Nets

Inference in Bayes Nets

Inference in a Bayesian Network is the process of reasoning under uncertainty - computing how beliefs about some variables should change when others are observed. The objective is to determine the posterior probability of one or more query variables $Q$ given evidence variables $e$, such that
$P(Q\mid e)=\alpha P(Q,e)=\alpha {\sum }_h{\prod }_{i}P(X_i\mid \text{Parents}(X_i)),$
where $h$ are hidden variables, and $\alpha =\frac{1}{P(e)}$ is a normalization constant.

Exact inference computes this posterior without approximation and can be performed using several methods that differ mainly in efficiency.

1. Inference by enumeration computes $P(Q\mid e)$ directly by expanding the full joint distribution defined by the network. We begin with the standard factorization formula for Bayes nets over all variables $\{Q,h,e\}$. We then marginalize out the hidden variables $h$ to keep only the query $Q$ and the evidence $e$:
   $P(Q,e)={\sum }_{h}P(Q,h,e)={\sum }_h{\prod }_{i}P(X_i\mid \text{Parents}(X_i)),$
   after which we normalize to turn this joint into a conditional over $Q$:
   $P(Q\mid e)=\frac{P(Q,e)}{P(e)}=\alpha {\sum }_h{\prod }_{i}P(X_i\mid \text{Parents}(X_i)),\alpha =\frac{1}{P(e)}.$
   Although conceptually straightforward, the number of terms grows exponentially with the number of hidden nodes.
2. Variable elimination produces the same $P(Q\mid e)$, but it does not form ${\sum }_h$ in one giant step. Instead, it eliminates hidden variables one at a time. Let $Z$ be a hidden variable to eliminate. Collect all current factors that mention $Z$; call them $f_1,f_2,\dots ,f_k$. Form their product into a single joint factor over $Z$ and its neighboring variables $Y$: