Artificial Intelligence: A Conceptual Learner's Series

Part 4: Uncertainty

Author: Christopher DanosAI by Claude

Logic deals in certainties, but the real world rarely offers them. This part covers how AI uses probability to reason with incomplete and noisy information.

Concept 1: Probability as degree of belief

In one line: Probability is a number from 0 to 1 that says how strongly you believe something, given what you currently know, and it updates as you learn more.

Example: Your friend is usually 10 minutes late, so before they text, you'd put the chance they're on time at about 30%. Then they text: "Leaving now." They live 25 minutes away, and you're meeting in 15. Your belief that they'll be on time drops to near zero. Nothing about the world changed when the text arrived; your information did.

Formally:

A random variable is a quantity with uncertain value (Arrival = on time, late).
The prior probability P(A) is your belief before evidence. A conditional probability P(A | B) is your belief in A once you know B.
The joint distribution gives the probability of every combination of values of all variables. Every other probability can be computed from it.
Marginalization: get P(A) by summing the joint over all values of the other variables.
The product rule: P(A, B) = P(A | B) P(B).

Connections: Probability replaces the true/false of logic (Part 3) with degrees of belief, which is what a rational agent needs when its percepts are incomplete (Part 1, Concept 4).

Watch out:

P(A | B) and P(B | A) are different. Most people who are famous are on social media; most people on social media are not famous.
The full joint is usually too big to write down. With 30 yes/no variables it has over a billion entries, which motivates Concept 3.

Concept 2: Bayes' rule

In one line: Bayes' rule tells you how to flip a conditional probability around, so you can reason from observed effects back to their likely causes.

Example: A disease affects 1 in 1,000 people. A test catches 99% of real cases but also flags 5% of healthy people. You test positive. What's the chance you have the disease? Most people guess around 95%. Count it out for 100,000 people: 100 have the disease and 99 test positive. Of the 99,900 healthy people, about 4,995 also test positive. So only 99 of roughly 5,094 positives are real: under 2%. The rarity of the disease outweighs the accuracy of the test.

Formally:

P (cause ∣ effect) = \frac{P ( effect ∣ cause ) P ( cause )}{P ( effect )}

P(cause) is the prior (1 in 1,000).
P(effect | cause) is the likelihood (99% detection).
P(cause | effect) is the posterior, the updated belief (under 2%).
P(effect) normalizes the result; it's the total chance of seeing the effect from any cause.

Connections: Bayes' rule is the engine inside probabilistic diagnosis, spam filtering and the inference methods in Concept 4.

Watch out:

Base-rate neglect. Ignoring the prior is one of the most common reasoning errors, made even by trained professionals.
A second test changes things. Today's posterior becomes tomorrow's prior; a second independent positive raises the probability sharply.

Concept 3: Independence and Bayesian networks

In one line: Most variables affect only a few others directly, and a Bayesian network uses that sparsity to describe a huge probability distribution with a handful of small tables.

Example: A home security alarm can be set off by a burglary or a small earthquake. Two neighbors might call you if they hear it. Whether a neighbor calls depends directly only on the alarm. Once you know the alarm went off, learning about the earthquake tells you nothing more about whether the neighbor will call. Instead of one giant table covering all five variables at once, you need one small table per variable.

Formally:

Two variables are independent if knowing one tells you nothing about the other. They are conditionally independent given C if that holds once C is known.
A Bayesian network is a directed acyclic graph: nodes are variables, arrows point from direct causes to effects.
Each node has a conditional probability table (CPT) giving its distribution for each combination of its parents' values.
The full joint distribution factors into a product of the CPTs:

P (x_{1}, \dots, x_{n}) = i = 1 \prod n P (x_{i} ∣ Parents (X_{i}))

The local Markov property: each node is conditionally independent of its non-descendants given its parents.

Connections: The factorization is what makes probabilistic reasoning tractable, the same way structure made constraint problems tractable (Part 3, Concept 1).

Watch out:

Arrows suggest causation but don't prove it. A network can encode correct dependencies with arrows pointing the "wrong" way.
Explaining away. Two independent causes become dependent once their shared effect is observed.

Concept 4: Inference: exact and approximate

In one line: Inference means answering questions like "how likely is a burglary, given that both neighbors called?", either by exact calculation or by simulating many possible worlds and counting.

Example: To estimate the burglary probability exactly, you'd sum over every combination of the variables you didn't observe. For five variables that's quick. For a medical network with hundreds of variables, it can be hopeless. Alternative: simulate the network a million times, rolling dice according to each CPT, keep only the runs where both neighbors called, and count how often a burglary happened in those runs. The answer is approximate but improves the more you simulate.

Formally:

Exact inference by enumeration sums the joint over hidden variables. Variable elimination does the same sums more cleverly, reusing intermediate results.
Exact inference is intractable in the worst case, so large networks use approximate inference.
Rejection sampling generates samples and discards those inconsistent with the evidence. It wastes samples when evidence is rare.
Likelihood weighting fixes the evidence and weights each sample by how likely the evidence was.
Markov chain Monte Carlo (MCMC), such as Gibbs sampling, wanders through possible worlds so that time spent in each is proportional to its probability.

Connections: Approximate inference is bounded rationality (Part 1, Concept 5) applied to probability: a good-enough answer in reasonable time.

Watch out:

Sampling error shrinks slowly. Halving the error takes about four times as many samples.
Rare evidence breaks naive sampling. If the evidence occurs once in a million runs, rejection sampling throws away almost everything.

Concept 5: Reasoning over time

In one line: When the world keeps changing and you only see noisy clues, you can track what's probably happening by repeatedly predicting forward and then correcting with each new observation.

Example: You're in a windowless office trying to guess the weather outside. You can't see it, but you can see whether coworkers arrive carrying umbrellas. Rain tends to follow rain. Each morning you predict today's weather from yesterday's belief, then update when you see the umbrellas. One umbrella-free day after a rainy week doesn't flip your belief completely, but three in a row will.

Formally:

A Markov chain models a state that changes over time, where the next state depends only on the current one.
A hidden Markov model (HMM) adds observations: the true state is hidden, and each observation depends only on the current state.
Filtering: estimate the current state from all evidence so far. Prediction: estimate future states. Smoothing: re-estimate past states using later evidence. Most likely explanation: find the single most probable sequence of states (the Viterbi algorithm).
Kalman filters do the same predict-then-correct cycle for continuous quantities like position and velocity, and are used in GPS and spacecraft navigation.
Particle filters approximate the belief with many weighted samples, handling messier, nonlinear problems.

Connections: An HMM is a Bayesian network (Concept 3) unrolled over time, and filtering is repeated application of Bayes' rule (Concept 2).

Watch out:

The Markov assumption is a choice. If the real process has longer memory, enrich the state rather than ignore it.
Errors compound when observations stop. Predictions without new evidence grow more uncertain with every step.

Retention kit

Answer from memory, then check. Review at about 1 day, 3 days, 1 week, 2 weeks and 1 month.

What's the difference between a prior and a conditional probability? Give an example.
Work through the rare-disease test example. Why is the answer so much lower than the test's accuracy?
How does a Bayesian network avoid writing down the full joint distribution?
How does rejection sampling estimate a probability, and when does it fail?
In a hidden Markov model, what is hidden, what is observed, and what does filtering compute?

Build exercise (1–2 hours): Code the burglary-alarm network with made-up CPTs. Compute P(Burglary | both neighbors call) exactly by enumeration. Then estimate it with rejection sampling at 1,000, 10,000 and 100,000 samples and watch the estimate converge.

Python algorithms

Bayes' rule on the rare-disease test (Concept 2), the burglary-alarm network solved exactly by enumeration and approximately by rejection sampling (Concepts 3–4), and the umbrella hidden Markov model with filtering and Viterbi (Concept 5). The network's probabilities are illustrative. Runs with plain Python 3.

import random
from itertools import product

# 1. Bayes' rule: the rare-disease test
def posterior(prior, sensitivity, false_positive_rate):
    p_pos = sensitivity * prior + false_positive_rate * (1 - prior)   # P(effect)
    return sensitivity * prior / p_pos

# 2. Burglary-alarm Bayesian network (illustrative numbers)
P_B, P_E = 0.001, 0.002
P_A = {(True, True): 0.95, (True, False): 0.94, (False, True): 0.29, (False, False): 0.001}
P_N1 = {True: 0.90, False: 0.05}      # neighbor 1 calls given alarm
P_N2 = {True: 0.70, False: 0.01}      # neighbor 2 calls given alarm

def p(prob, value):
    return prob if value else 1 - prob

def joint(b, e, a, n1, n2):
    """Product of the five small tables (the network's factorization)."""
    return (p(P_B, b) * p(P_E, e) * p(P_A[(b, e)], a)
            * p(P_N1[a], n1) * p(P_N2[a], n2))

def enumerate_burglary(n1=True, n2=True):
    """Exact P(Burglary | n1, n2) by summing out the hidden variables."""
    score = {b: sum(joint(b, e, a, n1, n2) for e, a in product([True, False], repeat=2))
             for b in (True, False)}
    return score[True] / (score[True] + score[False])

def rejection_sample(n_samples, seed=0):
    """Approximate P(Burglary | both call): simulate, keep matching runs, count."""
    rng, kept, hits = random.Random(seed), 0, 0
    for _ in range(n_samples):
        b = rng.random() < P_B
        e = rng.random() < P_E
        a = rng.random() < P_A[(b, e)]
        n1 = rng.random() < P_N1[a]
        n2 = rng.random() < P_N2[a]
        if n1 and n2:
            kept += 1
            hits += b
    return hits / kept if kept else float("nan"), kept

# 3. Hidden Markov model: weather (hidden) and umbrellas (observed)
STATES = ["rain", "dry"]
START = {"rain": 0.5, "dry": 0.5}
TRANS = {"rain": {"rain": 0.7, "dry": 0.3}, "dry": {"rain": 0.3, "dry": 0.7}}
EMIT = {"rain": {True: 0.9, False: 0.1}, "dry": {True: 0.2, False: 0.8}}

def filter_hmm(observations):
    """Forward algorithm: predict with TRANS, correct with EMIT, normalize."""
    belief, history = dict(START), []
    for i, obs in enumerate(observations):
        if i > 0:
            belief = {s: sum(belief[r] * TRANS[r][s] for r in STATES) for s in STATES}
        belief = {s: belief[s] * EMIT[s][obs] for s in STATES}
        total = sum(belief.values())
        belief = {s: v / total for s, v in belief.items()}
        history.append(round(belief["rain"], 3))
    return history

def viterbi(observations):
    """Most likely sequence of hidden states."""
    best = {s: (START[s] * EMIT[s][observations[0]], [s]) for s in STATES}
    for obs in observations[1:]:
        best = {s: max(((pr * TRANS[r][s] * EMIT[s][obs], path + [s])
                        for r, (pr, path) in best.items()), key=lambda t: t[0])
                for s in STATES}
    return max(best.values(), key=lambda t: t[0])[1]

if __name__ == "__main__":
    print(f"P(disease | positive) = {posterior(0.001, 0.99, 0.05):.4f}")
    print(f"Exact P(burglary | both call) = {enumerate_burglary():.4f}")
    for n in (10_000, 100_000, 1_000_000):
        est, kept = rejection_sample(n)
        print(f"Rejection sampling n={n:>9,}: {est:.4f} (kept {kept} samples)")
    umbrellas = [True, True, False, True, True]
    print("Filtered P(rain) by day:", filter_hmm(umbrellas))
    print("Most likely weather:", viterbi(umbrellas))

Output when run:

P(disease | positive) = 0.0194
Exact P(burglary | both call) = 0.2842
Rejection sampling n=   10,000: 0.2353 (kept 17 samples)
Rejection sampling n=  100,000: 0.3532 (kept 201 samples)
Rejection sampling n=1,000,000: 0.2899 (kept 2187 samples)
Filtered P(rain) by day: [0.818, 0.883, 0.191, 0.731, 0.867]
Most likely weather: ['rain', 'rain', 'dry', 'rain', 'rain']

Notice the sampling results: because both neighbors calling is rare, a million simulations keep only about 2,000 runs, which is why the estimate wobbles. That's the "rare evidence breaks naive sampling" caution from Concept 4.

Try it:

Change the disease prior to 1 in 100 and see how much the posterior jumps.
Add likelihood weighting: fix n1 and n2 to True, and weight each run by P(n1) × P(n2) instead of discarding it. Compare how fast it converges.