Make a probability language usable before hiding its price
By 1991 Bayesian networks had several names: belief networks, knowledge maps and probabilistic causal networks among them: and an expanding research community. They had been applied to diagnosis, navigation, language, vision and search. Yet Charniak judged that their ideas had not travelled far beyond specialists. His title states the editorial ambition: explain the machinery to an artificial-intelligence researcher whose probability background is limited, while retaining the points at which intuition can mislead.
This is not a paper that introduces one new propagation theorem. It is a tutorial reconstruction of a field in motion. Pearl’s 1988 book supplies its central synthesis; many researchers supply algorithms and applications. Charniak contributes a teaching order. Begin with an ordinary domestic uncertainty, attach numbers locally, explain which missing arrows are independence assertions, prove that the local pieces determine one joint distribution, then survey exact and approximate evaluation. Only after the formal machine is visible does he ask where its probabilities come from.
The paper therefore matters as infrastructure for thought. A directed diagram is tempting because it resembles the causal sketches people already draw. The tutorial shows exactly what additional commitments make that sketch a probabilistic model. Each node must name a random variable with a state space. Every root needs a prior distribution. Every other node needs a conditional distribution for every configuration of its parents. The absence of edges must be defended as conditional independence. Evaluation then means conditioning the resulting joint distribution on evidence.
That disciplined translation is still urgent. Contemporary systems often display a graph and speak of “belief flowing” as though animation were semantics. Charniak repeatedly brings the reader back to conditional probabilities. When evidence arrives, the unconditional distribution has not changed. What changes is the question: the system now reports probabilities conditional on a larger evidence set. “Belief” is safe shorthand only if this conditioning operation remains explicit.
Probe 1 · Add an arrow because it feels plausible
Suppose the family’s location directly changes how readily the dog barks, even after the dog’s location is known. The original network says that influence is absent. Adding family-out → hear-bark is not decorative: it removes a conditional-independence claim, expands the hear-bark table and changes every posterior involving those variables. Test the new mechanism and elicit its conditional probabilities before calling the revision an improvement.
The family-out problem turns a sketch into a model
Imagine arriving home and wanting to know whether the family is out before trying a door that might be double locked. An outdoor light is often switched on when the family leaves, but it can also be on because a guest is expected. The dog is often placed outside when nobody is home, but bowel trouble can also put it there. A bark is more likely when the dog is outside, though another dog can create a false impression. The story contains noisy causes, indirect effects and conflicting clues without requiring specialised medicine or engineering.
The variables are Boolean: family-out, bowel-problem, light-on, dog-out and hear-bark. Family-out and bowel-problem are roots, so Charniak supplies P(family-out)=0.15 and P(bowel-problem)=0.01. Light-on has one parent and needs two probabilities: 0.60 if the family is out and 0.05 otherwise. Hear-bark similarly needs 0.70 if the dog is out and 0.01 otherwise. Dog-out has two parents, so its table needs four entries: 0.99 when both causes are present, 0.90 for family-out alone, 0.97 for bowel-problem alone and 0.30 when neither is present.
Ten independent assessments specify this five-node model. A naked joint table over five Boolean variables has 32 cells and therefore 31 free numbers after normalisation. The reduction is not magic and is not merely graphical neatness. It is purchased by statements such as light-on being independent of bowel-problem once family-out is fixed, and hear-bark being independent of family-out and bowel-problem once dog-out is fixed. If those statements are false, the small model is misspecified.
Worked example 1 · Light on, but no bark
Set light-on=true and hear-bark=false, then sum the joint product over bowel-problem and dog-out. The evidence probability is 0.0662351325. The portion in which family-out=true is 0.03315411, so P(family-out | light-on, ¬hear-bark)=0.5005517. This rounds to Charniak’s stated 0.5. The light raises suspicion; the missing bark pulls the other way; the network makes the compromise explicit.
Notice what the result does not say. It does not establish that the family caused the light state, that a 50 per cent threshold should trigger one door rather than another, or that the table transfers to another household. It answers one conditional question inside one supplied model. The modest domestic setting helps the reader keep epistemic scale aligned with numerical precision.
Chains block, forks screen off, colliders awaken
Charniak introduces dependence through paths. Along a path, an interior node can be linear, diverging or converging. A linear node lies on a chain such as family-out → dog-out → hear-bark. A diverging node is a common cause, such as family-out → light-on and family-out → dog-out. A converging node is a common effect, such as family-out → dog-out ← bowel-problem. These three motifs respond differently when evidence is observed.
In a chain, learning the middle node blocks information between the endpoints. Once dog-out is known, family-out supplies no further information about hear-bark under this model. In a fork, learning the common cause similarly blocks association between its effects. Once family-out is fixed, light-on does not tell us about dog-out through that fork. These are screening-off relations: the middle state renders a more remote state irrelevant along that path.
A collider reverses the rule. Without evidence about dog-out or its descendants, family-out and bowel-problem are independent root causes. Observing dog-out opens the path. If the family is known to be home while the dog is known to be outside, bowel trouble becomes more plausible. Conversely, strong evidence that the family is out reduces the need for the alternative explanation. Observing a descendant such as hear-bark can also open the collider because it supplies information about dog-out.
Charniak states this using d-connection. A path is active given evidence when every linear or diverging interior node is unobserved, and every converging interior node is observed or has an observed descendant. Two variables are d-separated when no active path connects them. The definition is graphical, but its purpose is probabilistic: it identifies conditional independences entailed by the network for all distributions that factorise according to it.
Worked example 2 · Explaining away bowel trouble
Before observing anything, P(bowel-problem)=0.01 and it remains 0.01 after learning family-out because the roots are independent. After observing dog-out, the two causes become dependent. If family-out is false, the model must account for an outside dog mainly through the bowel route or the 0.30 background probability; if family-out is true, the 0.90 baseline already explains most of the observation. The executable laboratory reports both conditional values so the collider’s effect can be inspected numerically.
Probe 2 · Condition on selection
A dataset containing only households where the dog was outside conditions on the collider. Family absence and bowel trouble can then appear associated even though they were independent in the source population. Before interpreting a correlation as a mechanism, ask whether entry into the dataset is a shared effect of the variables being compared.
Local consistency buys global consistency
A loose collection of conditional numbers can contradict itself. Charniak gives a compact warning: values for P(a|b), P(b|a) and P(b) may look individually reasonable yet imply P(a)>1 when Bayes’s rule is applied. Earlier rule-based systems such as PROSPECTOR required special handling for inconsistency. A Bayesian network imposes a stronger construction contract. Each node’s conditional table must normalise for every parent configuration; the product of those tables then defines one normalised joint distribution.
The proof begins with the chain rule, which holds for any ordered variables: P(v₁,…,vₙ)=P(v₁)P(v₂|v₁)…P(vₙ|v₁,…,vₙ₋₁). Choose a topological order in which every parent precedes its descendants. For each variable, d-separation lets us delete earlier non-parents from its conditioning set. What remains is precisely P(vᵢ|parents(vᵢ)). Multiplying these local terms yields the network factorisation.
The result establishes existence, uniqueness and consistency together. There is exactly one joint distribution determined by the tables; all its cells are non-negative; and their sum is one if every local table is normalised. It also establishes the operational meaning of the graph: it is a recipe for forming joint cells without storing them all.
The parameter saving can be dramatic. A full table for n Boolean variables has 2ⁿ cells and 2ⁿ−1 free values. A bounded-parent network needs a number of entries proportional to the number of nodes times the parent-state combinations. Charniak illustrates the contrast by grafting a whimsical second five-node copy onto the first. The ten-node joint would require 1,023 free values, while the structured model needs only 21 assessments. The saving grows because the graph asserts that most contextual distinctions do not matter locally.
Worked example 3 · Score one complete world
Take family-out=true, bowel-problem=false, light-on=true, dog-out=true and hear-bark=false. The joint cell is 0.15 × 0.99 × 0.60 × 0.90 × 0.30 = 0.024057. No separate five-way probability needs to be elicited. Change dog-out to false and the dog factor becomes 0.10 while the no-bark factor becomes 0.99. Every complete world is scored by the same five-factor instruction.
Probe 3 · Delete an inconvenient parent
Removing a parent shrinks a conditional table, but it also asserts invariance across that parent’s states. If guest expectation changes light use independently of family location and is systematically related to the evidence, omitting it may produce confident but transportedly wrong posteriors. Parameter economy is evidence about modelling assumptions, not a free compression ratio.
Exactness is easy on one path and costly around loops
The fundamental query is a node’s conditional distribution given all evidence observed so far. In general this evaluation problem is NP-hard. Charniak emphasises that worst-case language is not merely ceremonial: depending on topology, numbers, algorithm and implementation, a network with tens of nodes can be troublesome while a network with thousands can be manageable. Node count alone is not a performance specification.
Polytrees form the favourable exact class. Ignore arrow direction; if there is at most one undirected path between every pair of nodes, evidence from different branches can be summarised independently at their meeting point. A node can combine information arriving from above with information arriving from below, normalise, and send branch-excluding messages onwards. Pearl’s propagation algorithm exploits that separation and runs linearly in the number of nodes for bounded state spaces.
Multiply connected networks break this clean decomposition. A change can reach the same node by more than one route, so naïvely combining messages counts dependent information as though it were independent. Charniak sketches clustering: combine variables until the transformed network is singly connected, evaluate the cluster tree, then recover original marginals. The cure creates larger state spaces. A cluster of ten Boolean variables has 1,024 configurations, and dense networks can create much larger tables.
At the time, Charniak identifies the Lauritzen–Spiegelhalter method, improved by Jensen, as the fastest exact approach for many applications. That historical sentence links Paper 0025 directly to Paper 0024: the earlier paper in this collection gave the full clique-tree compilation; Charniak turns it into a reader’s map. The general lesson survives implementation changes. Exact inference replaces an implicit global sum by a structured elimination schedule, but its cost remains exponential in the largest intermediate cluster.
Worked example 4 · One diamond, one cluster
Let a point to b and c, and let both b and c point to d. Ignoring directions yields two routes from a to d. Evidence at d affects c directly and also through b’s effect on a; the routes do not separate. Cluster b and c into a four-state node. The transformed a → {b,c} → d chain is singly connected, but its middle table is larger. Exactness is restored by storing the interaction the loop made unavoidable.
Approximate methods trade a deterministic exact answer for samples. Logic sampling chooses root values from their priors, walks downward in topological order, samples each child from its conditional table, and estimates probabilities from frequencies. Straight logic sampling does not handle evidence efficiently: if the evidence is rare, most generated worlds are irrelevant. Likelihood weighting and other variants retain or weight samples differently. Bounded conditioning and related methods offer still other compromises.
Charniak’s distinction is unusually sharp. Exact-algorithm performance is governed mainly by topology because topology determines cluster size. Approximation performance is often governed by quantities because small likelihoods and concentrated probabilities determine sample variance and rejection. There may be no single method that wins everywhere. A library of algorithms plus an explicit selection policy may be more honest than a universal-inference label.
Probe 4 · Observe a rare event
Run forward logic sampling for light-on=true and hear-bark=false. Only about 6.6 per cent of samples match. Make the evidence one hundred times rarer and the effective sample collapses. The graph is unchanged, yet approximation quality deteriorates because the probability values changed. Report effective sample size and uncertainty, not only the number of draws.
Diagnosis is one pattern; maps and stories reuse it
PATHFINDER is Charniak’s principal diagnostic example. Its model covered 60 lymph-node diseases and more than 130 observable features, many with more than two states. A pathologist could enter microscopic findings and obtain disease probabilities conditional on the accumulated evidence. The system also used decision theory to choose a next test when current evidence was insufficient. Treatment decisions were technically representable but withheld because results were sensitive to disputed utilities: a boundary as important as the successful diagnosis.
Charniak reports that PATHFINDER’s Bayesian-network and decision-theoretic versions outperformed MYCIN-style certainty factors, Dempster–Shafer belief functions and simpler Bayesian models with less realistic independence assumptions. The application demonstrates why representation matters: a probabilistic method is not one monolith. Changing the independence structure can matter as much as choosing a family of uncertainty calculus.
Map learning reuses the same architecture. A robot travelling west detects features suggesting a north–south corridor. That sensor reading raises the probability that the corridor intersects a known east–west route farther north. Corridor layouts play the role of diseases, junctions the role of latent abnormalities, and sensor readings the role of tests. Reasoning backwards from measurements to layout enables a later decision about whether exploration is worth the detour.
Story understanding makes the analogy more surprising. High-level plans generate events; an author observes some events and writes words; the reader must infer the plan through noisy, ambiguous linguistic evidence. In “Sue ordered a milkshake. She picked up the straw,” an eating-out context supports a drinking event, which supports the drinking-straw sense over animal bedding. A knowledge base constructs a story-specific Bayesian network on the fly, so word-sense disambiguation becomes probabilistic abduction.
These applications share a direction of generation and a reverse direction of diagnosis. Diseases generate findings, maps generate sensor readings, and plans generate words. The arrows encode a generative account, while inference can travel against them. That distinction prevents a common mistake: arrows do not restrict the direction in which evidence may revise belief. They specify factorisation; Bayes’s rule permits prediction, diagnosis and intercausal reasoning on the same joint model.
Worked example 5 · Straw is evidence, not merely a token
The word “straw” alone may support multiple senses. Add “ordered” and “milkshake”; those observations raise the eating-out and straw-drinking hypotheses, which in turn raise the drinking-straw sense. The network combines lexical ambiguity with event structure instead of selecting a dictionary sense in isolation. The worked point is architectural: remote context affects a word through an explicit chain of uncertain hypotheses.
Probe 5 · Reverse an arrow to match query direction
A diagnosis query asks disease given symptom, but the natural model points disease → symptom. Reversing the arrow solely because the query runs backwards can multiply parents and obscure causal assumptions. Keep the generative direction when it supports modular assessment; let conditioning perform the reverse inference.
The graph reduces elicitation; it does not abolish it
Charniak closes with the awkward practical question: where do the numbers come from? A multi-parent conditional table can still be too large for an expert to assess. For fever caused by cold, pneumonia and chicken pox, three Boolean causes nominally require eight probabilities. A noisy-OR assumption can combine individual causal strengths and reduce the burden to roughly one parameter per cause. That is a further independence claim: causal contributions act independently unless an explicit interaction is added.
Even reduced tables need values. In many early applications they were elicited from experts, or, in Charniak’s deliberately plain language, “made up” by informed practitioners. He argues that there is nothing automatically disreputable about subjective assessment. Experts can be useful, and a cited medical study found assessments fairly close to subsequently collected frequencies, except that doctors were too ready to assign exact zero. The warning about zero remains operationally severe: a zero likelihood can make later contrary evidence impossible to absorb.
Data are preferable when the relevant cases can be collected, defined and transported. Yet data do not automatically deliver a network. Variables must be operationalised, missingness modelled, selection understood and causal directions defended. Estimates from one clinic may fail in another. A network learned for prediction may not support interventions. The tutorial’s constructive discipline still applies: distinguish structural assumptions, numerical assessment and evidence collection rather than collapsing them into one score.
Charniak also answers a familiar objection that flexible probabilities can explain any example after the fact. A sparse network has relatively few parameters. A sufficiently varied test set therefore overconstrains them: the same local numbers must account for many joint observations and queries. This is precisely why validation should be organised by mechanisms and contexts, not by one aggregate accuracy measure. A compact model gains testability along with compression.
Assessment should therefore preserve uncertainty about the assessments themselves. A table entry such as 0.60 can be a convenient best judgement without being known to two decimal places. Sensitivity analysis can vary influential entries, compare plausible experts and identify conclusions that reverse under small changes. Posterior precision should never silently exceed input warrant. When several models fit current observations, disagreement among their answers is useful evidence about structural uncertainty rather than an inconvenience to average away.
Maintenance matters as much as initial elicitation. The meaning of a test, the population entering a clinic and the behaviour of a sensor can change while the graph remains syntactically valid. Teams need dated probability versions, calibration reports, alert thresholds and a path for revising structure. The same local modularity that made the network assessable makes such governance practical: an audit can locate which conditional mechanism drifted, determine which downstream queries depend on it and decide whether recalibration is enough or a parent set must change.
Historical boundary
The 1991 tutorial sometimes speaks causally where the formal guarantee is factorisation and d-separation. A DAG can encode observational independences without identifying intervention effects. Learning, calibration, fairness, dataset shift and causal identification now have richer literatures. This companion preserves the tutorial’s causal intuition while marking the additional assumptions required to treat an arrow as an intervention-ready mechanism.
Structure audit
Are variables and states stable? Does every missing edge assert a defensible conditional independence? Is selection represented?
Number audit
Who supplied each table, from which population, at what date, with what uncertainty and calibration evidence?
Decision audit
Which posterior changes an action? Whose utilities and costs define that threshold? What happens under disagreement?
Place in the canon
Paper 0025 follows Lauritzen and Spiegelhalter because it changes altitude. Paper 0024 gave the technical architecture for exact local computation in multiply connected graphs. Charniak’s tutorial explains why anyone should want that architecture, starting from a five-node domestic model and moving through d-separation, factorisation, polytrees, clustering, sampling and applications. It is a work of conceptual translation whose sequence became part of the field’s standard pedagogy.
It also gathers earlier canon threads. Bayes supplies inverse probability; Chow and Liu show that a tree can approximate a distribution through selected dependence; Pearl makes local propagation explicit; Cooper marks worst-case hardness; sampling papers provide approximate alternatives. The Bayesian network joins these ideas into a representation where a graph, local tables and an inference procedure have distinct responsibilities.
For intelligence and agency, the important achievement is disciplined revisability. A system can represent uncertain hypotheses, receive partial evidence, propagate consequences in either direction and preserve global coherence. But it does not thereby understand a household, a patient or a story. People choose the ontology, causal story, priors, likelihoods, observation process, loss function and deployment boundary. The network performs conditional bookkeeping over those choices. Agency begins only when actions, utilities, authority and feedback are specified, and consciousness is not supplied by posterior computation.
Family-out exact-inference laboratory
The laboratory implements Charniak’s five binary variables and published local probabilities. It enumerates all 32 complete worlds, conditions on six evidence profiles, and reports every posterior. Its tests check joint normalisation, reproduce the paper’s light-on-without-bark result, and verify both screening off and collider activation. The diagram shows the selected marginal rather than implying that probability is a fluid moving through arrows.
The evidence profile is observational. “Dog out, family home” is especially useful for seeing explaining away: once the main family-out explanation is excluded, bowel trouble becomes more plausible. It is not an intervention that forces the dog outside while severing its causes. Such a do-operation would require a different graph transformation and a different question.
Memory studio
One sentence
A Bayesian network is a directed factorisation whose missing arrows encode conditional independences and whose evidence queries condition one coherent joint distribution.
Five verbs
name variables and states.
draw direct dependencies.
assess local tables.
condition on evidence.
audit assumptions and cost.
Three path rules
chain middle evidence blocks.
fork common-cause evidence blocks.
collider common-effect evidence opens.
Three costs
Tables grow with parent combinations. Exact inference grows with cluster state space. Sampling degrades with hostile probabilities and rare evidence.
The invariant
Every complete world receives the product of one local entry per node; all world probabilities are non-negative and sum to one.
Recall ladder
30 seconds graph, tables, separation, condition.
5 minutes explain the family network and collider.
1 hour derive the factorisation and benchmark exact versus sampled inference.
What remains after the tears are removed
Charniak’s tutorial succeeds because it never treats accessibility as the deletion of structure. The family example gives every abstract move a physical interpretation. The three path motifs reveal why conditioning can both destroy and create association. The topological proof turns a graph into a unique joint distribution. The inference survey distinguishes easy topologies, clustered exact computation and sample-based approximation. The applications show that the same generative pattern can organise medicine, navigation and language.
Its most durable engineering principle is modular assessment. State a probability for a variable given its direct parents, not an unstructured opinion about every possible world. The graph documents which distinctions matter locally. That modularity makes models buildable, reviewable and revisable. It also makes errors traceable: a surprising posterior can be decomposed into structure, tables, evidence and algorithm.
The same modularity creates specific obligations. Missing arrows are assertions, not empty space. Local tables need provenance and calibration. Exact algorithms need a disclosed complexity measure. Approximate algorithms need convergence diagnostics. Observational evidence must not be confused with intervention. Posterior probability must not be confused with utility, policy or moral authority.
“Without tears” is therefore best read as a promise of conceptual control, not effortless deployment. A Bayesian network makes uncertainty calculable after the modeller has done the hard work of representation. Its arrows provide a compact argument about how a world might generate observations. Its mathematics ensures that local commitments compose coherently. Its limits remind us that coherence is necessary for intelligent reasoning but never sufficient for truth, judgement or responsible agency.