Uncertainty in AI

Classical logic-based AI assumes complete, certain knowledge - a statement is True or False, never "probably true." Real agents almost never have this luxury. Module 3 begins by cataloging why uncertainty arises and why probability theory, not logic alone, is the right mathematical tool.

Sources of Uncertainty

Why Not Just Use Logic with "Maybe" Rules?

A natural first instinct is to write logical rules like "Toothache → Cavity." But this fails because the rule is neither always true (a toothache can have other causes) nor will adding more and more exception clauses (qualifications) ever produce a complete, manageable rule set - this is known as the qualification problem. Probability theory solves this elegantly by allowing degrees of belief rather than requiring exhaustive logical certainty.

Probability as a Summary of Ignorance

A probability statement like P(Cavity | Toothache) = 0.6 doesn't claim cavities cause toothaches 60% of the time in some deep causal sense - it summarizes the agent's degree of belief given everything else it doesn't know, observe, or have bothered to model. This is the foundation for the rest of Module 3.

Key Points

• Uncertainty arises from sensor noise, partial observability, stochastic effects, incomplete data, and computational limits.
• Pure logic fails due to the qualification problem - too many exceptions to enumerate.
• Probability theory provides a principled, compact way to reason under uncertainty.

Interview Questions

Storing a full joint probability distribution over n binary variables requires 2ⁿ−1 numbers - utterly intractable for even modest n. Bayesian Networks exploit the fact that most variables are only directly influenced by a few others, compactly encoding this structure.

Core Components

• Nodes - random variables (discrete or continuous), e.g., Burglary, Earthquake, Alarm.
• Directed Edges - represent direct influence/dependency (parent → child); absence of an edge implies conditional independence given the parents.
• CPT (Conditional Probability Table) - for each node X with parents Parents(X), specifies P(X | Parents(X)) for every combination of parent values.

Classic Worked Example - Burglary Alarm Network

Sample CPT for node Alarm - P(B)=0.001, P(E)=0.002 are the prior (root) probabilities; this entire network needs only 10 numbers total vs. 31 for the full joint distribution over 5 binary variables.

The Chain Rule for Bayesian Networks

This single formula is the entire payoff of the BN structure: the full joint distribution factors into a product of small, local CPTs, each depending only on a node's direct parents - exploiting conditional independence to avoid the exponential blowup of a naive joint table.

Conditional Independence & D-Separation

A Bayesian network encodes that each node is conditionally independent of its non-descendants, given its parents. More generally, d-separation is the graphical criterion for reading off conditional independence statements directly from the graph structure, without needing to inspect the actual probability numbers.

Three Canonical Connection Patterns

Advantages & Disadvantages

Applications

• Medical diagnosis systems (e.g., disease-symptom networks)
• Spam filtering and fraud detection
• Genetic/pedigree analysis
• Fault diagnosis in industrial/engineering systems

Interview & Exam Questions

Once a BN's structure is fixed, two remaining problems must be solved: learning the CPT numbers from data, and inference - answering probability queries given evidence.

Part A: Learning Parameters

When some variables are hidden/unobserved in the training data, simple counting doesn't work directly - the Expectation-Maximization (EM) algorithm is used instead, alternating between estimating expected values for hidden variables and re-estimating CPTs, until convergence.

Part B: Inference in Bayesian Networks

Types of Reasoning Patterns

Exact Inference: Enumeration & Variable Elimination

The simplest exact method, Inference by Enumeration, directly sums out all non-query, non-evidence variables from the full joint (reconstructed via the chain rule). It's correct but computationally wasteful since it repeats the same sub-computations.

Variable Elimination improves on this by eliminating (summing out) hidden variables one at a time, caching intermediate "factors" to avoid redundant computation - significantly faster in practice, though still NP-hard in the worst case for general graphs.

function ENUMERATION-ASK(X, e, bn):
    Q(X) ← distribution over X, initially empty
    for each value x of X:
        Q(x) ← ENUMERATE-ALL(bn.VARS, e ∪ {X=x})
    return NORMALIZE(Q)

function ENUMERATE-ALL(vars, e):
    if vars is empty: return 1.0
    Y ← FIRST(vars)
    if Y has a value y in e:
        return P(y | parents(Y)) × ENUMERATE-ALL(REST(vars), e)
    else:
        return Σ_y P(y | parents(Y)) × ENUMERATE-ALL(REST(vars), e ∪ {Y=y})

Approximate Inference: Sampling Methods

For large networks, exact inference is often infeasible. Approximate inference via sampling trades exactness for speed:

• Direct (Prior) Sampling - generate samples by sampling each variable in topological order according to its CPT; estimate probabilities from sample frequencies.
• Rejection Sampling - generate full samples, discard ("reject") any inconsistent with the observed evidence, estimate from the rest. Wasteful if evidence is rare.
• Likelihood Weighting - fix evidence variables to their observed values, sample only the remaining variables, and weight each sample by how likely the evidence was given the sampled values - avoids rejection waste.
• Markov Chain Monte Carlo (MCMC) / Gibbs Sampling - generate a sequence of samples, each obtained by resampling one variable conditioned on all others, converging to the true posterior distribution over many iterations.

Applications

• Medical diagnostic expert systems
• Spam/fraud detection (Naive Bayes - a simplified BN)
• Speech recognition (Hidden Markov Models are a special BN structure)
• Sensor fusion in robotics

Interview & Exam Questions

Probability theory tells us how likely outcomes are. But a rational agent (recall Module 1's definition) needs to combine likelihood with preference to actually choose an action. Decision theory = Probability Theory + Utility Theory.

Maximum Expected Utility (MEU) Principle

Worked Example

Since EU(Buy umbrella) = 5.0 > EU(Don't buy) = 4.0, the MEU-rational choice is to buy the umbrella - even though "don't buy" has a better best-case outcome, MEU correctly accounts for the probability-weighted full picture.

Axioms of Utility Theory (von Neumann–Morgenstern)

Utility theory is not arbitrary - it can be derived from a small set of rationality axioms about preferences over lotteries (probabilistic combinations of outcomes):

The key theorem: if an agent's preferences obey these axioms, then there exists a utility function such that the agent's preferences are exactly equivalent to maximizing expected utility - this is precisely why MEU is considered the formally correct standard of rational decision-making.

Risk Attitudes & Utility Curve Shape

Multi-Attribute Utility & Decision Networks (brief mention)

Real decisions often involve multiple competing objectives (cost, safety, time). Multi-attribute utility theory combines several attributes into one scalar utility, often via a weighted sum (under independence assumptions). Decision networks (influence diagrams) extend Bayesian networks with decision nodes and utility nodes, allowing MEU computation directly over a graphical model.

Interview & Exam Questions

Decision theory (previous topic) handles a single one-shot decision. Most real agents must make a sequence of decisions over time, in a stochastic environment, where each action affects future states and rewards. Markov Decision Processes formalize exactly this setting - and form the mathematical bedrock of reinforcement learning.

The Markov Property

Policy - The Output of MDP Solving

Discounting and the Value of a Policy

The discount factor γ (0 ≤ γ < 1) makes future rewards worth less than immediate ones - this (a) reflects realistic preference for sooner rewards, (b) ensures the infinite sum converges to a finite value, and (c) handles the possibility of indefinitely long or infinite-horizon tasks.

Classic Grid-World Example

MDP vs. Standard Search Problem - Key Distinctions

Applications

• Robot navigation under actuator/sensor uncertainty
• Reinforcement learning (MDPs are RL's foundational mathematical model)
• Inventory management and supply chain optimization
• Healthcare treatment planning under uncertain patient response

Value Iteration is the most direct algorithm for solving an MDP - it computes the optimal value of every state by repeatedly applying the Bellman equation as an update rule until the values converge.

Step-by-Step Algorithm

1. Initialize V₀(s) = 0 for all states s (arbitrary starting point).
2. For each state s, compute V_k+1(s) using the Bellman update above, considering every action.
3. Repeat step 2 for all states simultaneously (one "sweep" = one iteration).
4. Stop when the maximum change in V between iterations falls below a small threshold ε (convergence).
5. Extract the optimal policy: π*(s) = argmax_a Σ_s′ P(s′|s,a)[R(s,a,s′) + γV*(s′)].

def value_iteration(states, actions, P, R, gamma=0.9, theta=1e-4):
    V = {s: 0.0 for s in states}
    while True:
        delta = 0
        new_V = {}
        for s in states:
            if is_terminal(s):
                new_V[s] = R(s); continue
            new_V[s] = max(
                sum(P(s, a, s2) * (R(s, a, s2) + gamma * V[s2]) for s2 in states)
                for a in actions(s)
            )
            delta = max(delta, abs(new_V[s] - V[s]))
        V = new_V
        if delta < theta:
            break
    # extract greedy policy
    policy = {}
    for s in states:
        policy[s] = max(actions(s), key=lambda a:
            sum(P(s, a, s2) * (R(s, a, s2) + gamma * V[s2]) for s2 in states))
    return V, policy

Convergence Properties

Interview Questions

Policy Iteration is an alternative MDP-solving algorithm that often converges in far fewer iterations than Value Iteration, by working directly with policies rather than values.

Step-by-Step Algorithm

1. Initialize an arbitrary policy π₀(s) for all states.
2. Policy Evaluation: solve for V^π(s) = Σ_s′ P(s′|s,π(s)) [R(s,π(s),s′) + γV^π(s′)] - either by solving the linear system exactly, or by iterating it to convergence (a fixed policy, unlike Value Iteration's max).
3. Policy Improvement: for each state, compute π′(s) = argmax_a Σ_s′ P(s′|s,a)[R(s,a,s′) + γV^π(s′)].
4. If π′ = π for every state (no change), stop - π is optimal.
5. Otherwise set π ← π′ and repeat from step 2.

def policy_iteration(states, actions, P, R, gamma=0.9):
    policy = {s: actions(s)[0] for s in states}     # arbitrary initial policy
    while True:
        # --- Policy Evaluation (iterative version) ---
        V = {s: 0.0 for s in states}
        while True:
            delta = 0
            for s in states:
                v = V[s]
                a = policy[s]
                V[s] = sum(P(s, a, s2) * (R(s, a, s2) + gamma * V[s2]) for s2 in states)
                delta = max(delta, abs(v - V[s]))
            if delta < 1e-6:
                break

        # --- Policy Improvement ---
        stable = True
        for s in states:
            old_action = policy[s]
            policy[s] = max(actions(s), key=lambda a:
                sum(P(s, a, s2) * (R(s, a, s2) + gamma * V[s2]) for s2 in states))
            if old_action != policy[s]:
                stable = False
        if stable:
            return policy, V

Value Iteration vs. Policy Iteration - The Most-Asked Comparison

Interview & Exam Questions