Bayesian Networks

Directed graphical models, conditional independence, factorization, exact inference, sampling, parameter learning, and model validation.

A full joint distribution over n Boolean variables requires up to 2^n entries. Most domains contain structure: a sensor depends directly on machine condition, not on every unrelated variable. A Bayesian network represents those local dependencies with a directed acyclic graph (DAG).

Network Structure

Each node is a random variable. An arrow from X to Y means X is a parent in Y’s conditional model. Every node has:

P(X | Parents(X))

The joint distribution factorizes as:

P(X₁,...,Xₙ) = ∏ᵢ P(Xᵢ | Parents(Xᵢ))

The graph must be acyclic so variables can be ordered from causes or predecessors toward consequences.

An arrow encodes direct probabilistic dependence in the model. It does not prove real-world causation.

Alarm Example

Consider variables:

Burglary;
Earthquake;
Alarm;
NeighborCalls.

Edges:

Burglary  → Alarm ← Earthquake
                 ↓
          NeighborCalls

The joint factorizes:

P(B,E,A,C)
= P(B)P(E)P(A|B,E)P(C|A)

This is much smaller than storing every combination independently.

Independence

A network states that each variable is conditionally independent of its non-descendants given its parents.

In the example, NeighborCalls is independent of Burglary once Alarm is known. Evidence about the call still informs burglary when alarm state is unknown.

Explaining away

Before evidence, burglary and earthquake may be independent. After learning the alarm sounded, they become dependent: evidence for an earthquake reduces the need to explain the alarm with a burglary.

This pattern—two causes converging on one effect—is called a collider. Conditioning can create dependence as well as remove it.

D-Separation

D-separation reads conditional independence from graph structure. Consider any path between two variables:

a chain X → M → Y is blocked when M is observed;
a fork X ← M → Y is blocked when M is observed;
a collider X → M ← Y is blocked when neither M nor one of its descendants is observed.

The collider rule is deliberately reversed: observing a shared effect opens a path between its possible causes. If every path between two variable sets is blocked by evidence Z, the sets are conditionally independent given Z.

D-separation is a property of the model structure. It tells us which independencies the network asserts for every compatible parameter setting; it does not show that the chosen structure is correct for the real domain.

Inference Queries

Common tasks include:

posterior: P(Burglary | NeighborCalls=true);
prediction: P(NeighborCalls | Burglary=true);
diagnosis: infer likely causes from effects;
most probable explanation;
expected utility for a decision.

Inference sums over unobserved variables:

P(query | evidence) ∝ Σ_hidden P(all variables)

Enumeration is simple but repeats work.

For the alarm network, diagnostic inference expands as:

P(B | C)
∝ P(B) Σ_e Σ_a P(e)P(a | B,e)P(C | a)

The sums account for earthquake and alarm states that were not observed. Normalization is performed after computing the unscaled value for both B=true and B=false. Writing the expression before calculating helps prevent omitted cases and reversed conditionals.

Exact Inference Example

The following Boolean network implementation makes every probability operation visible. A conditional table stores P(node=true | parent values). Nodes must appear after their parents, which is a topological order.

from itertools import product

def parent_key(node, assignment):
    key = ""
    for parent in node["parents"]:
        if assignment[parent]:
            key += "T"
        else:
            key += "F"
    return key

def node_probability(node, value, assignment):
    key = parent_key(node, assignment)
    probability_true = node["table"][key]
    return probability_true if value else 1 - probability_true

def joint_probability(network, assignment):
    probability = 1.0
    for node in network:
        probability *= node_probability(
            node, assignment[node["name"]], assignment
        )
    return probability

def posterior(network, query, evidence):
    names = []
    for node in network:
        names.append(node["name"])

    if query in evidence:
        value = evidence[query]
        return {False: float(not value), True: float(value)}
    if query not in names:
        raise KeyError(query)
    if not set(evidence) <= set(names):
        raise KeyError("unknown evidence variable")

    hidden = []
    for name in names:
        if name != query and name not in evidence:
            hidden.append(name)

    totals = {False: 0.0, True: 0.0}

    for query_value in (False, True):
        for hidden_values in product(
            (False, True), repeat=len(hidden)
        ):
            assignment = evidence.copy()
            assignment[query] = query_value

            for index in range(len(hidden)):
                name = hidden[index]
                assignment[name] = hidden_values[index]

            totals[query_value] += joint_probability(
                network, assignment
            )

    normalizer = totals[False] + totals[True]
    if normalizer == 0:
        raise ValueError("evidence has zero probability")
    totals[False] = totals[False] / normalizer
    totals[True] = totals[True] / normalizer
    return totals

Now define the burglary network. Parent tuple order and table-key order must match exactly.

BURGLARY = [
    {"name": "B", "parents": [], "table": {"": 0.001}},
    {"name": "E", "parents": [], "table": {"": 0.002}},
    {
        "name": "A",
        "parents": ["B", "E"],
        "table": {
            "TT": 0.95,
            "TF": 0.94,
            "FT": 0.29,
            "FF": 0.001,
        },
    },
    {
        "name": "J",
        "parents": ["A"],
        "table": {"T": 0.90, "F": 0.05},
    },
    {
        "name": "M",
        "parents": ["A"],
        "table": {"T": 0.70, "F": 0.01},
    },
]

answer = posterior(
    BURGLARY,
    query="B",
    evidence={"J": True, "M": True},
)

assert abs(sum(answer.values()) - 1.0) < 1e-12
assert round(answer[True], 3) == 0.284
print(f"P(B | J, M) = {answer[True]:.6f}")

Enumeration is exponential in the number of hidden variables, but it is an excellent correctness oracle for a small network. A variable-elimination or sampling implementation can be tested against it before scaling up.

Variable Elimination

Variable elimination treats conditional tables as factors:

restrict factors using evidence;
choose a hidden variable;
multiply factors containing it;
sum it out;
repeat;
multiply remaining factors and normalize.

Elimination order affects intermediate factor size. A poor order may create a factor over many variables even when the original tables were small. Graph connectivity, especially treewidth, controls practical complexity.

Sampling

When exact inference is too expensive:

prior sampling generates variables in topological order;
rejection sampling discards samples inconsistent with evidence;
likelihood weighting fixes evidence and weights samples;
Gibbs sampling repeatedly resamples one non-evidence variable from its local conditional.

Rare evidence makes rejection sampling wasteful. Sampling methods provide estimates, so they need error analysis, convergence checks, and enough effective samples.

Sampling Example

Likelihood weighting fixes evidence variables instead of waiting for them to occur. Each sample receives the likelihood of the fixed evidence under its sampled parents.

from random import Random

def weighted_sample(network, evidence, rng):
    assignment = {}
    weight = 1.0

    for node in network:
        name = node["name"]

        if name in evidence:
            value = evidence[name]
            assignment[name] = value
            weight *= node_probability(
                node, value, assignment
            )
        else:
            key = parent_key(node, assignment)
            probability_true = node["table"][key]
            assignment[name] = rng.random() < probability_true

    return assignment, weight

def likelihood_weighting(
    network, query, evidence, samples, seed=0
):
    if samples < 1:
        raise ValueError("samples must be positive")

    rng = Random(seed)
    totals = {False: 0.0, True: 0.0}

    for _ in range(samples):
        assignment, weight = weighted_sample(
            network, evidence, rng
        )
        totals[assignment[query]] += weight

    normalizer = totals[False] + totals[True]
    totals[False] = totals[False] / normalizer
    totals[True] = totals[True] / normalizer
    return totals

estimate = likelihood_weighting(
    BURGLARY,
    "B",
    {"J": True, "M": True},
    samples=100_000,
    seed=12,
)
exact = posterior(BURGLARY, "B", {"J": True, "M": True})
assert abs(estimate[True] - exact[True]) < 0.02

The tolerance is statistical, not a promise that every sample size or seed produces the same error. Repeat the experiment across seeds and plot absolute error against sample count. The curve should trend downward, though individual runs will fluctuate.

Parameter Learning

If structure is known, conditional probabilities can be estimated from data. Maximum likelihood uses observed frequencies. Bayesian estimation adds priors, reducing extreme probabilities when data is sparse.

Missing variables complicate learning. Expectation-maximization can alternate between estimating hidden values and updating parameters, but may converge to local optima.

Structure learning is harder: many DAGs can represent the same independencies, and observational data alone may not identify causal direction.

Decision Networks

A Bayesian network describes beliefs. A decision network adds:

decision nodes for controllable choices;
utility nodes for preferences over outcomes;
informational arcs showing what is known when a decision is made.

The best decision maximizes expected utility after probabilistic inference. For maintenance, a model may compare repair now, inspect, and continue operation. Inspection has value only if its possible findings can change the preferred action enough to offset cost and delay.

Decision networks keep facts and preferences separate. A high failure probability does not by itself determine an action; consequences, costs, risk limits, and alternatives also matter.

Model Validation

Validate:

every conditional row sums to one;
graph is acyclic;
independencies are defensible;
calibration matches observed frequencies;
predictions generalize;
results remain stable under plausible parameter changes;
sensitive decisions are audited across groups.

Sensitivity analysis asks how much a conclusion changes when uncertain parameters vary. A confident answer resting on a fragile probability deserves caution.

Applications

medical diagnosis;
fault detection;
risk analysis;
sensor fusion;
decision support;
reliability;
student modelling;
causal hypothesis design.

Common Mistakes

Reading every arrow as causation.
Reversing conditional probabilities.
Ignoring explaining away.
Choosing a costly elimination order.
Using rejection sampling with rare evidence.
Treating approximate inference as exact.
Learning zero probabilities from tiny datasets.
Conditioning on a collider without noticing the induced dependence.
Confusing a probable outcome with the best decision.

Exercises

Factorize the alarm network joint distribution.
Compute one posterior by enumeration.
Identify conditional independencies using the graph.
Demonstrate explaining away numerically.
Perform one variable-elimination step with explicit factors.
Compare rejection sampling and likelihood weighting for rare evidence.
Design and validate a small diagnostic network.
Use d-separation to analyze a chain, fork, and collider.
Extend a diagnostic network with inspection and repair decisions.
Add CPT validation for missing rows, invalid probabilities, and parent order.
Compare enumeration and likelihood weighting over increasing sample counts.
Build the medical-diagnosis network and compute a symptom-and-test posterior.