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:

$\text{Prior belief} + \text{New evidence} \longrightarrow \text{Updated belief}$

In rule-based expert systems, this relationship is expressed as: $\text{IF } E \text{ is true THEN } H \text{ is true } \{\text{with probability } p\}$

---

Foundations of Conditional & Joint Probability

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

Classical Probability & Dice Roll Model

Consider a single throw of a standard 6-sided die where obtaining a $6$ is defined as the only successful event.

• Let $s = 1$ be the number of successful outcomes ($6$).
• Let $f = 5$ be the number of failure outcomes ($\{1, 2, 3, 4, 5\}$).

The probability of success $p$ and probability of failure $q$ are: $P(\text{success}) = p = \frac{s}{s + f} = \frac{1}{1 + 5} = \frac{1}{6} \approx 0.1666$ $P(\text{failure}) = q = \frac{f}{s + f} = \frac{5}{1 + 5} = \frac{5}{6} \approx 0.8333$

Since success and failure partition the outcome space, their sum equals unity: $p + q = 1$

Mutually Exclusive vs. Dependent Events

• Mutually Exclusive Events: Two events $A$ and $B$ are mutually exclusive if they cannot occur simultaneously in a single trial (e.g., obtaining both a $1$ and a $6$ on a single die throw). The probability of either event occurring is: $P(A \cup B) = P(A) + P(B)$
• Dependent Events: When events are not independent, the occurrence of one event alters the likelihood of another occurring.

Conditional & Joint Probability Derivation

From a counting perspective, the conditional probability of event $A$ occurring given that event $B$ has already occurred is defined as: $P(A | B) = \frac{\text{Number of outcomes where both } A \text{ and } B \text{ occur}}{\text{Number of outcomes where } B \text{ occurs}}$

In standard set and logic notation, the joint probability $P(A \cap B)$ (or $P(A \land B)$) represents the probability that both $A$ and $B$ occur: $P(A \cap B) = P(A | B) P(B) \quad \text{for } P(B) > 0$ $P(B \cap A) = P(B | A) P(A) \quad \text{for } P(A) > 0$

Because joint probability is commutative ($P(A \cap B) = P(B \cap A)$), we can equate both expressions: $P(A | B) P(B) = P(B | A) P(A)$

Rearranging yields the core definition of Conditional Probability: $P(A | B) = \frac{P(A \cap B)}{P(B)} = \frac{P(B | A) P(A)}{P(B)}$

---

Law of Total Probability & Sample Space Partitioning

When an event $A$ depends on a set of $n$ mutually exclusive and exhaustive events $B_1, B_2, \dots, B_n$, the joint probability for each partition is: $P(A \cap B_1) = P(A | B_1) P(B_1)$ $P(A \cap B_2) = P(A | B_2) P(B_2)$ $\vdots$ $P(A \cap B_n) = P(A | B_n) P(B_n)$

Summing across all partitions yields the Law of Total Probability: $P(A) = \sum_{i=1}^n P(A \cap B_i) = \sum_{i=1}^n P(A | B_i) P(B_i)$

Binary Sample Space Partition ($B$ and $\neg B$)

If event $A$ depends on only two mutually exclusive events ($B$ and its complement $\neg B$), the total probabilities of $A$ and $B$ expand as: $P(A) = P(A | B) P(B) + P(A | \neg B) P(\neg B)$ $P(B) = P(B | A) P(A) + P(B | \neg A) P(\neg A)$

---

Bayes' Theorem (Bayes' Rule)

Named after Reverend Thomas Bayes, Bayes' Theorem describes how to update the probability of a hypothesis ($H$) given observed evidence ($E$):

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

By substituting the binary Law of Total Probability for $P(E)$, we obtain the expanded form:

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

Terminology Breakdown:

• $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 hypothesis $H$ before observing evidence.
• $P(\neg H)$ (Complementary Prior): The prior probability of hypothesis $H$ being false ($P(\neg H) = 1 - P(H)$).
• $P(E | \neg H)$ (Likelihood under Complement): The probability of finding evidence $E$ even when hypothesis $H$ is false (false positive rate).
• $P(E)$ (Marginal Likelihood / Evidence): The total probability of observing evidence $E$ across all possible states of the hypothesis.

---

Generalizing Bayes' Rule: Multiple Hypotheses & Evidence

In diagnostic reasoning, an expert often evaluates multiple hypotheses ($H_1, H_2, \dots, H_m$) given one or more pieces of evidence ($E_1, E_2, \dots, E_n$).

Critical Assumption: For these formulations to hold, the set of hypotheses $H_1, H_2, \dots, H_m$ as well as the set of evidences $E_1, E_2, \dots, E_n$ must be mutually exclusive and exhaustive.

Case 1: Single Evidence $E$ and Multiple Hypotheses $H_1, \dots, H_m$

When a single piece of evidence $E$ is observed, the posterior probability for hypothesis $H_i$ is:

$P(H_i | E) = \frac{P(E | H_i) \times P(H_i)}{\sum_{k=1}^m P(E | H_k) \times P(H_k)}$

Case 2: Multiple Evidences $E_1, \dots, E_n$ and Multiple Hypotheses $H_1, \dots, H_m$

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.