Lecture 11.1: Probabilistic Reasoning and Bayesian Networks

In real-world settings, agents must act under uncertainty. Since classical logic cannot easily handle noisy or incomplete information, we rely on probability theory to model belief.

Bayesian reasoning provides a mathematically rigorous way to update an agent's beliefs (represented as probabilities) when new evidence or observations arrive, moving from initial intuition to disciplined reasoning.

---

Foundations of Conditional Probability

To understand Bayes' rule, we first build from basic probability concepts.

Mutually Exclusive Events

Two events $A$ and $B$ are mutually exclusive if they cannot occur at the same time (e.g., throwing a single die and getting both a $1$ and a $6$ simultaneously). The probability of either event occurring is the sum of their individual probabilities: $P(A \lor B) = P(A) + P(B)$

Dependent Events & Joint Probability

When events are not independent, the occurrence of one event alters the likelihood of another. The joint probability $P(A \land B)$ represents the probability that both $A$ and $B$ occur: $P(A \land B) = P(A | B) P(B) = P(B | A) P(A)$

Because joint probability is commutative ($P(A \land B) = P(B \land A)$), we can derive Conditional Probability (the probability of $A$ occurring given that $B$ has already occurred): $P(A | B) = \frac{P(A \land B)}{P(B)} = \frac{P(B | A) P(A)}{P(B)}$

---

Bayes' Theorem (Bayes' Rule)

Named after Reverend Thomas Bayes, this fundamental theorem describes how to update the probability of a hypothesis ($H$) based on observing new evidence ($E$):

$P(H | E) = \frac{P(E | H) \times P(H)}{P(E)}$

Where:

• $P(H | E)$ (Posterior Probability): The updated probability of hypothesis $H$ after observing evidence $E$.
• $P(E | H)$ (Likelihood): The probability of observing evidence $E$ given that hypothesis $H$ is true.
• $P(H)$ (Prior Probability): The initial probability of the hypothesis before seeing the evidence.
• $P(E)$ (Marginal Likelihood / Evidence): The total probability of the evidence under all possible hypotheses. If we only have two mutually exclusive outcomes ($H$ and $\neg H$), it is calculated as: $P(E) = P(E | H)P(H) + P(E | \neg H)P(\neg H)$

Thus, the full expanded form is: $P(H | E) = \frac{P(E | H) \times P(H)}{P(E | H)P(H) + P(E | \neg H)P(\neg H)}$

---

Generalizing Bayes' Rule: Multiple Hypotheses & Evidence

In complex diagnostic settings, we often choose among multiple mutually exclusive and exhaustive hypotheses $H_1, H_2, \dots, H_m$ given multiple independent evidences $E_1, E_2, \dots, E_n$.

Assuming the evidences are conditionally independent given each hypothesis, the generalized posterior probability is:

$P(H_i | E_1 E_2 \dots E_n) = \frac{P(E_1|H_i) \times P(E_2|H_i) \times \dots \times P(E_n|H_i) \times P(H_i)}{\sum_{k=1}^m \left[ P(E_1|H_k) \times P(E_2|H_k) \times \dots \times P(E_n|H_k) \times P(H_k) \right]}$

Step-by-Step Simulation: Updating Beliefs with Incoming Evidence

Let's walk through a concrete numerical example. Suppose a system has three possible hypotheses ($H_1, H_2, H_3$) and can observe three pieces of evidence ($E_1, E_2, E_3$).

Prior and Conditional Probabilities Table:

We will observe evidences one by one and update our beliefs dynamically.

Step 1: Observing Evidence $E_3$

When $E_3$ is observed, we compute the updated probability for each hypothesis.

• Denominator (Marginal Likelihood $P(E_3)$): $P(E_3) = \sum_{k=1}^3 P(E_3 | H_k) P(H_k) = (0.6 \times 0.40) + (0.7 \times 0.35) + (0.9 \times 0.25)$ $P(E_3) = 0.240 + 0.245 + 0.225 = 0.710$

• Updated Posteriors $P(H_i | E_3)$:

  • $P(H_1 | E_3) = \frac{0.6 \times 0.40}{0.710} \approx \mathbf{0.34}$
  • $P(H_2 | E_3) = \frac{0.7 \times 0.35}{0.710} \approx \mathbf{0.34}$
  • $P(H_3 | E_3) = \frac{0.9 \times 0.25}{0.710} \approx \mathbf{0.32}$

Belief Shift: After observing $E_3$, the belief in $H_1$ decreases slightly (from $0.40$ to $0.34$), while the belief in $H_3$ increases (from $0.25$ to $0.32$). $H_1$ and $H_2$ are now tied.

Step 2: Observing Evidence $E_1$ (in addition to $E_3$)

Now we receive $E_1$ and update the beliefs using joint evidence $E_1 E_3$:

• Denominator $P(E_1 E_3)$: $P(E_1 E_3) = \sum_{k=1}^3 P(E_1 | H_k) P(E_3 | H_k) P(H_k) = (0.3 \times 0.6 \times 0.40) + (0.8 \times 0.7 \times 0.35) + (0.5 \times 0.9 \times 0.25)$ $P(E_1 E_3) = 0.072 + 0.196 + 0.1125 = 0.3805$

• Updated Posteriors $P(H_i | E_1 E_3)$:

  • $P(H_1 | E_1 E_3) = \frac{0.072}{0.3805} \approx \mathbf{0.19}$
  • $P(H_2 | E_1 E_3) = \frac{0.196}{0.3805} \approx \mathbf{0.52}$
  • $P(H_3 | E_1 E_3) = \frac{0.1125}{0.3805} \approx \mathbf{0.29}$

Belief Shift: $H_2$ is now considered the most likely hypothesis by far ($0.52$), and belief in $H_1$ has dropped dramatically down to $0.19$.

Step 3: Observing Evidence $E_2$ (in addition to $E_1, E_3$)

Finally, we observe $E_2$ and update to $E_1 E_2 E_3$:

• Denominator $P(E_1 E_2 E_3)$:

  • Note that $P(E_2 | H_2) = 0.0$. Thus, $H_2$ cannot produce evidence $E_2$. $P(E_1 E_2 E_3) = (0.3 \times 0.9 \times 0.6 \times 0.40) + (0.8 \times 0.0 \times 0.7 \times 0.35) + (0.5 \times 0.7 \times 0.9 \times 0.25)$ $P(E_1 E_2 E_3) = 0.0648 + 0.0 + 0.07875 = 0.14355$

• Updated Posteriors $P(H_i | E_1 E_2 E_3)$:

  • $P(H_1 | E_1 E_2 E_3) = \frac{0.0648}{0.14355} \approx \mathbf{0.45}$
  • $P(H_2 | E_1 E_2 E_3) = \frac{0.0}{0.14355} = \mathbf{0.0}$
  • $P(H_3 | E_1 E_2 E_3) = \frac{0.07875}{0.14355} \approx \mathbf{0.55}$

Belief Shift: Because $P(E_2 | H_2) = 0$, hypothesis $H_2$ is completely abandoned ($P=0$). $H_3$ emerges as the most likely hypothesis ($0.55$), followed closely by $H_1$ ($0.45$).

---

Bayesian Networks

A Bayesian Network is a graphical model that represents probabilistic dependencies among a set of random variables. It consists of:

1. Structure (DAG): A Directed Acyclic Graph where:
   • Nodes: Represent random variables (discrete or continuous).
   • Edges: Directed arrows pointing from parent to child, representing direct influence or causal dependency. Cycles are forbidden to avoid infinite probability calculation loops.
2. Parameters (CPTs): Each node has an associated Conditional Probability Table (CPT) that quantifies the effects of its parent nodes. If a node has no parents (root node), its CPT reduces to its prior probability distribution.

Reasoning and Inference in Bayesian Networks

Once the network structure and CPTs are defined, we can perform inference—calculating posterior probabilities of target query variables given some observed variables (evidence).

1. Exact Inference Algorithms

Calculate the exact mathematical posterior distribution:

• Variable Elimination: Evaluates the joint distribution sum by distributing sums over products, avoiding redundant computations.
• Junction Tree Algorithm: Transforms the DAG into a tree of cliques (clique tree) and uses belief propagation messaging to calculate exact margins.

2. Approximate Inference Algorithms

For highly complex networks with hundreds of variables, exact inference is NP-hard. We use randomized sampling:

• Direct Sampling: Generates samples starting from root nodes down using prior distributions.
• Rejection Sampling: Generates direct samples but discards (rejects) any sample that does not match the observed evidence.
• Likelihood Weighting: Keeps all samples but weights each one by the likelihood of the observed evidence, avoiding the sample waste of rejection sampling.
• Markov Chain Monte Carlo (MCMC) & Gibbs Sampling: Generates samples by making state transitions in a Markov chain whose stationary distribution matches the network's joint probability distribution.

3. Deterministic Approximations

• Mean Field Variational Methods: Formulates inference as an optimization problem, approximating the true posterior with a simpler, factorized distribution.
• Expectation Propagation: Iteratively updates local approximations of factorized distributions.

---

Influence Diagrams: Extending Bayes Networks for Decision Making

While Bayesian networks model probabilistic dependencies (diagnosis and prediction), Influence Diagrams extend them to model choice and value. They introduce two new types of nodes:

1. Decision Nodes (Rectangles): Represent actions or choices that the agent can actively choose to perform.
2. Utility Nodes (Diamonds): Quantify the desirability, reward, or value associated with different outcomes.

By combining probability, choice, and utility, influence diagrams serve as a complete framework for making optimal decisions under uncertainty.