Artificial Intelligence - Bayesian Networks and Probability Basics

Course Overview & Schedule

• Course Name: COSE361 Artificial Intelligence
• Primary Module: Bayesian Networks & Probabilistic Reasoning

Uncertainty and Utility

• Nature of the Real World:

  • Real-world environments are inherently uncertain.
  • Example scenario: Leaving for Incheon International Airport (ICN) $60\,\text{minutes}$ before a flight.

• Sources of Uncertainty:

  • Partial Observability: Incomplete knowledge about external states (e.g., road conditions, other drivers' decisions).
  • Noisy Sensors: Unreliable inputs (e.g., traffic radio reports, GPS routing estimates).
  • Immense Complexity: Extreme difficulty in modeling complex systems fully (e.g., traffic jams, airport security lines).
  • Ignorance of World Dynamics: Unpredictable physical events (e.g., flat tire, vehicle accidents).

• Role of Probabilistic Assertions:

  • Probabilistic assertions summarize the combined effects of ignorance (incomplete knowledge) and laziness (inability or unwillingness to compute exact states).

• Decision Making Under Uncertainty:

  • Rational decision-making combines probability and utility theory.
  • Maximum Expected Utility (MEU) Principle: An optimal agent chooses an action $a^*$ that maximizes its expected utility across all possible states $s$:

$a^* = \arg\max_a \sum_s P(s \mid a) U(s)$

Discrete Probability Fundamentals

• Outcome Space (Sample Space):

  • Defined as a set $\Omega$ containing all possible world outcomes $\omega$.
  • Example: Rolling a single standard six-sided die gives $\Omega = \{1, 2, 3, 4, 5, 6\}$.

• Probability Model:

  • Assigns a numeric probability $P(\omega)$ to every individual outcome $\omega \in \Omega$.
  • For a fair die: $P(1) = P(2) = P(3) = P(4) = P(5) = P(6) = \frac{1}{6}$.

• Probability Axioms / Constraints:

  1. Non-negativity: $0 \le P(\omega)$ for all $\omega \in \Omega$
  2. Normalization: $\sum_{\omega \in \Omega} P(\omega) = 1$

• Events:

  • An event $A$ is any subset of outcomes: $A \subseteq \Omega$
  • The probability of event $A$ is the sum of probabilities of its constituent outcomes:

$P(A) = \sum_{\omega \in A} P(\omega)$

• Examples:
  • Event "roll $< 4$": $A = \{1, 2, 3\} \implies P(\text{roll} < 4) = P(1) + P(2) + P(3) = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{1}{2}$
  • Event "roll is odd": $A = \{1, 3, 5\} \implies P(\text{roll is odd}) = P(1) + P(3) + P(5) = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{1}{2}$

Random Variables

• Definition:

  • A random variable $X$ represents a specific feature or aspect of the world whose value is uncertain.
  • Formally, a random variable is a deterministic function mapping an outcome $\omega \in \Omega$ to a specific domain value.
  • Denoted using uppercase letters (e.g., $X, T, D, W, G$).

• Domains / Ranges of Random Variables:

  • Boolean / Discrete Domain:
  • $\text{Odd} \in \{\text{true}, \text{false}\}$ where $\text{Odd}(1) = \text{true}$, $\text{Odd}(6) = \text{false}$
  • $T \in \{\text{hot}, \text{cold}\}$
  • Continuous Domain:
  • $D \in [0, \infty)$ (e.g., time to travel to the airport)
  • Spatial / Coordinate Domain:
  • $L_{\text{Ghost}} \in \{(0,0), (0,1), (1,0), \dots\}$

• Probability Distribution of a Random Variable:

  • Assigns a probability to every value $x$ in the domain range of $X$
  • Notation: $P(X = x) = \sum_{\{\omega : X(\omega) = x\}} P(\omega)$, abbreviated as $P(x)$
  • $P(X)$ refers to the complete distribution (represented as a table or vector).

Joint Distributions

• Definition:

  • A joint probability distribution over multiple variables $X_1, X_2, \dots, X_n$ specifies the probability of every possible combination of variable assignments $P(X_1 = x_1, X_2 = x_2, \dots, X_n = x_n)$.
  • The sum of all entries across the entire joint table equals $1.0$

• Necessity of Joint Distributions:

  • Individual (marginal) distributions do not provide information about how variables interact or depend on each other.
  • Joint distributions capture all variable interactions and dependencies.

• Fundamental Relationship:

  • Joint distributions cannot be deduced from individual marginal distributions alone (unless variables are known to be independent).
  • Marginal distributions can always be calculated directly from a joint distribution.

• Canonical Example Table: $P(T, W)$

Marginalization (Summing Out)

• Definition:

  • The marginal distribution of a subset of variables is derived by eliminating (summing out) the unmentioned variables from a joint distribution.

• Mathematical Formulas:

$P(X = x) = \sum_{y} P(X = x, Y = y)$

$P(Y = y) = \sum_{x} P(X = x, Y = y)$

• Derivations from the $P(T, W)$ Joint Table:
  • Marginal distribution of Weather $P(W)$:
  • $P(W = \text{sun}) = 0.45 + 0.15 = 0.60$
  • $P(W = \text{rain}) = 0.02 + 0.08 = 0.10$
  • $P(W = \text{fog}) = 0.03 + 0.27 = 0.30$
  • $P(W = \text{meteor}) = 0.00 + 0.00 = 0.00$
  • Marginal distribution of Temperature $P(T)$:
  • $P(T = \text{hot}) = 0.45 + 0.02 + 0.03 + 0.00 = 0.50$
  • $P(T = \text{cold}) = 0.15 + 0.08 + 0.27 + 0.00 = 0.50$

Dimensionality and Space Complexity

• Possible Worlds:

  • A possible world represents a full assignment of values to every random variable in a model.

• Distribution Size Complexity:

  • For $n$ random variables, each having a domain size of $d$:
  • Number of entries in full joint distribution: $d^n$
  • Example: For two dice rolls ($n=2, d=6$), joint size = $6^2 = 36$.
  • Exponential size growth ($O(d^n)$) makes manual entry or direct table storage unfeasible for large systems.

Probability of General Events

• Using the joint distribution $P(T, W)$, event probabilities are computed by summing matching table cells:
  • $P(\text{hot AND sun}) = P(T = \text{hot}, W = \text{sun}) = 0.45$
  • $P(\text{hot}) = 0.45 + 0.02 + 0.03 + 0.00 = 0.50$
  • $P(\text{hot OR not fog}) = P(\text{hot}) + P(\text{cold, sun}) + P(\text{cold, rain}) + P(\text{cold, meteor})$
  • $= 0.50 + 0.15 + 0.08 + 0.00 = 0.73$

Practice Problems & Solutions

Practice Problem Set I

Using the original joint distribution table $P(T, W)$:

• Question 1: Compare $P(\text{sun})$ vs. $P(\text{rain})$

  • $P(\text{sun}) = 0.45 + 0.15 = 0.60$
  • $P(\text{rain}) = 0.02 + 0.08 = 0.10$
  • Higher: Option 1 ($P(\text{sun}) = 0.60$

• Question 2: Compare $P(\text{fog})$ vs. $P(\text{hot})$

  • $P(\text{fog}) = 0.03 + 0.27 = 0.30$
  • $P(\text{hot}) = 0.45 + 0.02 + 0.03 + 0.00 = 0.50$
  • Higher: Option 2 ($P(\text{hot}) = 0.50$

• Question 3: Compare $P(\text{cold}, \text{fog})$ vs. $P(\text{rain})$

  • $P(\text{cold}, \text{fog}) = 0.27$
  • $P(\text{rain}) = 0.10$
  • Higher: Option 1 ($P(\text{cold}, \text{fog}) = 0.27$

• Question 4: Compare $P(\text{cold} \mid \text{rain})$ vs. $P(\text{sun})$

  • $P(\text{cold} \mid \text{rain}) = \frac{P(\text{cold}, \text{rain})}{P(\text{rain})} = \frac{0.08}{0.10} = 0.80$
  • $P(\text{sun}) = 0.60$
  • Higher: Option 1 ($P(\text{cold} \mid \text{rain}) = 0.80$

Practice Problem Set II

Given modified marginals and conditional probability tables:

• Marginal $P(T)$: $P(\text{hot}) = 0.25$, $P(\text{cold}) = 0.75$

• Conditional $P(W \mid T)$:

  • $P(\text{sun} \mid \text{hot}) = 0.90$, $P(\text{rain} \mid \text{hot}) = 0.04$, $P(\text{fog} \mid \text{hot}) = 0.06$, $P(\text{meteor} \mid \text{hot}) = 0.00$
  • $P(\text{sun} \mid \text{cold}) = 0.30$, $P(\text{rain} \mid \text{cold}) = 0.16$, $P(\text{fog} \mid \text{cold}) = 0.54$, $P(\text{meteor} \mid \text{cold}) = 0.00$

• Question 1: Compare $P(\text{sun}, \text{hot})$ vs. $P(\text{sun}, \text{cold})$

  • $P(\text{sun}, \text{hot}) = P(\text{hot}) P(\text{sun} \mid \text{hot}) = 0.25 \times 0.90 = 0.225$
  • $P(\text{sun}, \text{cold}) = P(\text{cold}) P(\text{sun} \mid \text{cold}) = 0.75 \times 0.30 = 0.225$
  • Result: Neither is higher (Both equal $0.225$

• Question 2: Compare $P(\text{sun})$ vs. $P(\text{fog})$

  • $P(\text{sun}) = 0.225 + 0.225 = 0.45$
  • $P(\text{fog}) = P(\text{hot}) P(\text{fog} \mid \text{hot}) + P(\text{cold}) P(\text{fog} \mid \text{cold}) = (0.25 \times 0.06) + (0.75 \times 0.54) = 0.015 + 0.405 = 0.420$
  • Higher: Option 1 ($P(\text{sun}) = 0.45$

• Question 3: Compare $P(\text{hot} \mid \text{sun})$ vs. $P(\text{cold} \mid \text{sun})$

  • $P(\text{hot} \mid \text{sun}) = \frac{P(\text{sun}, \text{hot})}{P(\text{sun})} = \frac{0.225}{0.45} = 0.50$
  • $P(\text{cold} \mid \text{sun}) = \frac{P(\text{sun}, \text{cold})}{P(\text{sun})} = \frac{0.225}{0.45} = 0.50$
  • Result: Equal probability ($0.50$

• Question 4: Compare $P(\text{hot} \mid \text{not fog})$ vs. $P(\text{cold} \mid \text{not fog})$

  • $P(\text{not fog}) = 1 - P(\text{fog}) = 1 - 0.42 = 0.58$
  • $P(\text{not fog} \mid \text{hot}) = 0.90 + 0.04 = 0.94$
  • $P(\text{hot}, \text{not fog}) = P(\text{hot}) P(\text{not fog} \mid \text{hot}) = 0.25 \times 0.94 = 0.235$
  • $P(\text{hot} \mid \text{not fog}) = \frac{0.235}{0.58} \approx 0.405$
  • $P(\text{cold} \mid \text{not fog}) = 1 - 0.405 = 0.595$
  • Higher: Option 2 ($P(\text{cold} \mid \text{not fog}) \approx 0.595$

Conditional Probability and Normalization

• Conditional Probability Formula:
  • Defines probability of event $a$ occurring given event $b$ has occurred:

$P(a \mid b) = \frac{P(a, b)}{P(b)}$

• Calculation Example:

  • Calculate $P(W = \text{sun} \mid T = \text{cold})$:
  • $P(T = \text{cold}) = 0.15 + 0.08 + 0.27 + 0.00 = 0.50$
  • $P(W = \text{sun}, T = \text{cold}) = 0.15$
  • $P(W = \text{sun} \mid T = \text{cold}) = \frac{0.15}{0.50} = 0.30$

• Normalization Procedure:

  • Normalization scales a set of non-negative values so that their sum equals $1.0$
  • Normalization constant $\alpha$:

$\alpha = \frac{1}{P(b)} = \frac{1}{\sum_{a} P(a, b)}$

• Expressing conditional distribution via normalization:

$P(A \mid b) = \alpha P(A, b)$

• Example for $P(W \mid T = \text{cold})$:

  • Unnormalized vector $P(W, T = \text{cold}) = \begin{pmatrix} 0.15 \\ 0.08 \\ 0.27 \\ 0.00 \end{pmatrix}$

  • Sum $= 0.50 \implies \alpha = \frac{1}{0.50} = 2.0$

  • Normalized distribution $P(W \mid T = \text{cold}) = 2.0 \times \begin{pmatrix} 0.15 \\ 0.08 \\ 0.27 \\ 0.00 \end{pmatrix} = \begin{pmatrix} 0.30 \\ 0.16 \\ 0.54 \\ 0.00 \end{pmatrix}$

  • Conditional Distribution Tables:

• Table $P(W \mid T)$ contains two distinct, disjoint probability distributions:

Product Rule and Chain Rule

• Product Rule:
  • Reconstructs joint probabilities from marginal and conditional probabilities:

$P(a, b) = P(a \mid b) P(b) = P(b \mid a) P(a)$

• Chain Rule:
  • Generalized product rule for $n$ variables by sequential decomposition:

$P(x_1, x_2, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_1, \dots, x_{i-1})$

• Expansions:
  • For 2 variables: $P(x_1, x_2) = P(x_2 \mid x_1) P(x_1)$
  • For 3 variables: $P(x_1, x_2, x_3) = P(x_3 \mid x_1, x_2) P(x_2 \mid x_1) P(x_1)$
  • For 4 variables: $P(x_1, x_2, x_3, x_4) = P(x_4 \mid x_1, x_2, x_3) P(x_3 \mid x_1, x_2) P(x_2 \mid x_1) P(x_1)$

Probabilistic Inference & Enumeration

• Probabilistic Inference:

  • Process of computing a target probability distribution from a probabilistic model given observed evidence.
  • Beliefs update dynamically upon receiving new evidence:
  • Prior belief: $P(\text{class on time} \mid \text{no holidays}) = 0.90$
  • Updated belief: $P(\text{class on time} \mid \text{no holidays}, 10\,\text{a.m.}) = 0.95$
  • Further updated belief: $P(\text{class on time} \mid \text{no holidays}, 10\,\text{a.m.}, \text{raining}) = 0.80$

• Variable Partitioning:

  • All variables in model $X_1, \dots, X_n$ partitioned into:
  • Evidence Variables $E$: Observed variables with known values $E = e$
  • Query Variables $Q$: Target unobserved variables to infer
  • Hidden Variables $H$: Unobserved, non-target variables

• Inference by Enumeration Algorithm:

  1. Select: Filter full joint distribution table for entries matching evidence $E = e$
  2. Sum Out: Marginalize out all hidden variables $H$:

$P(Q, e) = \sum_{h} P(Q, h, e)$

3. Normalize: Multiply by $\alpha = \frac{1}{\sum_q P(q, e)}$ to obtain final distribution:

$P(Q \mid e) = \alpha P(Q, e)$

• Worked Example: $P(\text{Season} \mid W = \text{sun})$:

  • Query ($Q$): Season
  • Evidence ($E$): $Weather = sun$
  • Hidden ($H$): Temp
  • Step 1 & 2: Sum over hidden variable Temp:
  • $P(\text{summer}, \text{sun}) = P(\text{summer, hot, sun}) + P(\text{summer, cold, sun}) = 0.35 + 0.10 = 0.45$
  • $P(\text{winter}, \text{sun}) = P(\text{winter, hot, sun}) + P(\text{winter, cold, sun}) = 0.10 + 0.15 = 0.25$
  • Step 3: Normalize:
  • Total sum $= 0.45 + 0.25 = 0.70 \implies \alpha = \frac{1}{0.70}$
  • $P(\text{summer} \mid \text{sun}) = \frac{0.45}{0.70} \approx 0.64$
  • $P(\text{winter} \mid \text{sun}) = \frac{0.25}{0.70} \approx 0.36$
  • Distribution: $\{\text{summer}: 0.64, \text{winter}: 0.36\}$

• Complexity Issues with Enumeration:

  • Time Complexity: $O(d^n)$ (exponential in variable count $n$)
  • Space Complexity: $O(d^n)$ (must store complete joint table)

Bayes' Rule and Applications

• Mathematical Derivation:
  • From product rule: $P(a, b) = P(a \mid b) P(b) = P(b \mid a) P(a)$
  • Dividing by $P(b)$ yields Bayes' Rule:

$P(a \mid b) = \frac{P(b \mid a) P(a)}{P(b)}$

• Terminology:

  • $P(a)$: Prior probability (unconditional belief of $a$)
  • $P(b \mid a)$: Likelihood (probability of evidence $b$ given $a$)
  • $P(b)$: Total Evidence probability
  • $P(a \mid b)$: Posterior probability (updated belief of $a$ given evidence $b$)

• Medical Diagnostic Application:

  • Given:
  • Likelihood $P(\text{positive} \mid \text{covid}) = 0.80$
  • Prior $P(\text{covid}) = 0.0001$
  • Evidence $P(\text{positive}) = 0.01$
  • Posterior Calculation:

$P(\text{covid} \mid \text{positive}) = \frac{P(\text{positive} \mid \text{covid}) P(\text{covid})}{P(\text{positive})} = \frac{0.80 \times 0.0001}{0.01} = 0.008$

• Interpretation: The posterior is low ($0.8\%$

  • Dog Breed Probability Examples:

• Scenario A: Two dogs (Hodu and Maru). Each is equally likely Maltese ($M$) or Poodle ($P$).

  • Outcomes: $\{(P,P), (P,M), (M,P), (M,M)\}$
  • $P(\text{both poodles}) = \frac{1}{4} = 25\%$

• Scenario B: Given that at least one dog is a poodle, what is $P(\text{both poodles})$?

  • Event $a$ (at least one poodle): $\{(P,P), (P,M), (M,P)\} \implies P(a) = \frac{3}{4}$
  • Event $b$ (both poodles): $\{(P,P)\} \implies P(b) = \frac{1}{4}$
  • $P(a \mid b) = 1.0$
  • Applying Bayes' Rule:

$P(b \mid a) = \frac{P(a \mid b) P(b)}{P(a)} = \frac{1.0 \times \frac{1}{4}}{\frac{3}{4}} = \frac{1}{3} \approx 33.33\%$

Conditional Independence

• Independence Definition:
  • $X$ and $Y$ are independent ($X \perp \! \! \perp Y$) if:

$\forall x, y \quad P(x, y) = P(x) P(y) \iff P(x \mid y) = P(x)$

• Conditional Independence Definition:
  • $X$ and $Y$ are conditionally independent given $Z$ ($X \perp \! \! \perp Y \mid Z$) if:

$\forall x, y, z \quad P(x \mid y, z) = P(x \mid z) \quad \text{and} \quad P(y \mid x, z) = P(y \mid z)$

• Equivalent joint factorization given $Z$:

$\forall x, y, z \quad P(x, y \mid z) = P(x \mid z) P(y \mid z)$

• Ghostbusters Grid Example:

• Setup: Ghost location $G \in \{(1,1), \dots, (3,3)\}$ (9 possible locations). Sensors at grid locations $C_{x,y} \in \{\text{red}, \text{orange}, \text{yellow}, \text{green}\}$.
• Sensor Model: $P(C_{x,y} \mid G)$ depends strictly on distance to ghost $G$
• Full Joint Size without Independence:
  • $9 \times 4^9 = 2,359,296$ parameters.
• Applying Conditional Independence:
  • Sensor reading $C_{1,1}$ is conditionally independent of $C_{1,2}$ given ghost location $G$:

$P(C_{1,1} \mid G, C_{1,2}) = P(C_{1,1} \mid G)$

• Decomposed Joint Formula:

$P(G, C_{1,1}, \dots, C_{3,3}) = P(G) \prod_{x,y} P(C_{x,y} \mid G)$

• Reduced Parameter Count: $9 + (9 \times 4 \times 9) = 324$ parameters (quadratic reduction vs exponential).
• Naïve Bayes Structure: Model containing one discrete query variable $G$ influencing multiple conditionally independent evidence variables $C_{x,y}$.

Bayesian Networks

• Definition:

  • A Bayesian Network is a directed acyclic graph (DAG) structure combined with local conditional probability tables (CPTs) that compactly represents a full joint probability distribution.

• Representation Components:

  • Nodes: Represent random variables $X_i$ with specified domains.
  • Directed Arcs: Represent direct causal or statistical influences ($X \rightarrow Y$).
  • Absence of Arcs: Encodes explicit conditional independence relationships.
  • Conditional Probability Tables (CPTs): Quantify relationships; each node has a table specifying $P(X_i \mid \text{Parents}(X_i))$.

• Dental Diagnostic Example:

• Node Cavity directly points to Toothache and Catch.
• Absence of direct arc between Toothache and Catch means Toothache and Catch are conditionally independent given Cavity:

$P(\text{Toothache}, \text{Catch} \mid \text{Cavity}) = P(\text{Toothache} \mid \text{Cavity}) P(\text{Catch} \mid \text{Cavity})$

• Bayes Net Syntax & Semantics:
  • A Bayes Net is defined by:

$\text{Bayes Net} = \text{Topology (DAG Graph)} + \text{Local Conditional Probabilities (CPTs)}$

• Full joint distribution encoded by a Bayes Net is constructed via the chain rule for Bayes nets:

$P(X_1, X_2, \dots, X_n) = \prod_{i=1}^{n} P(X_i \mid \text{Parents}(X_i))$