44 Bayesian Network Inference

Inference is Bayesian networks answers 2 types of questions :

• Diagnosis : $P(Cause|Effect)$, e.g. $P(R|W)$.
• Prediction: $P(Effect|Cause)$, e.g. $P(W|C)$. Applications of inference in Bayesian networks :
• Classification : $ma{x}_{class}P(class|data)$.
• Decision making : ${\sum }_{i}P({\text{Effect}}_i\mid \text{Cause})\times \text{Utility}({\text{Effect}}_i\mid \text{Cause})$

Three categories of variables

For inference purposes, we distinguish 3 categories of variables (nodes) in a Bayes net :

• Evidence variables $E=\{E_1,\dots ,E_m\}$ (known)
• Query variables $X=\{X_1,\dots ,X_m\}$ (wanted)
• Non-evidence variables $Y=\{Y_1,\dots ,Y_k\}$ (neither known nor wanted, but must deal with) The complete set of variables (nodes) of a Bayesian network is the union of these: $E\cup X\cup Y$ .

Inference in Bayesian Networks

Inference (aka. Query): Answering questions about the underlying probability distribution.

• Unconditional or conditional probability inference :
  • What is the probability of a given value assignment for a subset of variables in $X$? Example: $P(W=1)$
  • What is the probability of different value assignments for query variables $X$ given evidence about variables $E$: Compute $P(X|E=e)$. Example: $P(W|C=1)$
• Maximum a posteriori (MAP) inference :
  • Given evidence $E=e$, find the most likely assignment of values to the query variables $X$: $$\text{MAP}(X\mid E=e)=\arg \underset{x}{\max }P(X=x\mid E=e)$$

Exact Inference in Bayesian Networks

Exact inference computes the posterior probability distribution :

$$\begin{array}{rl}P(X\mid E)& =\frac{P(X,E)}{P(E)}\\ & =\alpha \cdot P(X,E)\\ & =\alpha \cdot \sum _{Y}P(X,E,Y)\end{array}$$

where $\alpha =\frac{1}{P(E)}$

Bayesian inference algorithms that calculate the exact value of probability $P(X\mid E)$.

Inference by Enumeration :

• We infer a posterior probability by marginalization of the joint distribution.
• That is, we compute the exact value of probability $P(X\mid E)$.

Computation Complexity :

• The number of terms in the sum is exponential in the number of non-evidence random variables: The complexity is $O(n{m}^n)$, where:
  • $n$ is the number of non-evidence variables.
  • $m$ is the number of values each variable can take.

Example

In the ”Wet Grass” problem, if we do not cancel $P(C=1)$, the full calculation requires summing 4 terms, each involving 4 multiplications.