Probability must travel through an expert system

Expert systems separate a knowledge base from the facts of a new case. The knowledge base records propositions and their relationships; an inference engine applies those relationships to a patient, machine or decision. In medicine, neither layer is complete. Symptoms are noisy, diseases are hidden, observations arrive out of order and professional knowledge contains uncertainty. Lauritzen and Spiegelhalter ask whether a coherent probability distribution can preserve the modular, graphical character that made rule-based systems attractive.

The immediate motivation is MUNIN, an expert system for diagnosing disorders of nerve and muscle from electromyographic measurements. Its knowledge network was expected to contain roughly one thousand variables, perhaps more. Many uncertainty formalisms of the period propagated non-probabilistic confidence measures because exact Bayesian updating in a multiply connected graph appeared computationally infeasible. The paper counters that claim conditionally: sparse structure can be exploited, but the graph must first be compiled into a form that supports correct local calculation.

The required operations are more demanding than one posterior query. The system should initialise a joint model from conditional assessments; absorb batches of observations independently of their order; propagate evidence globally; temporarily hypothesise a finding; retract it; decide which potential test would be informative; and identify which observed item most influenced a conclusion. A representation that answers only one query efficiently is not yet an inference engine.

Locality is therefore both a computational and organisational requirement. A clinician should not need to edit an astronomical joint table. A module should describe a limited set of variables, and a change should move through explicit interfaces. The achievement is to show when those interfaces are probabilistically sufficient. The qualification is equally important: local calculations become exact only after global graph structure has been analysed and transformed.

A tiny chest clinic contains every hard move

The paper teaches the scheme through a fictitious eight-variable “chest clinic” network, now commonly called the Asia network. A patient may have visited Asia (A), may smoke (S), and may have tuberculosis (T), lung cancer (L) or bronchitis (B). Either tuberculosis or lung cancer produces a combined state E. That state affects a positive chest X-ray (X), while E and bronchitis affect dyspnoea (D).

The graph stores a factorisation rather than a list of 256 worlds. Root priors are P(A)=.01 and P(S)=.50. Tuberculosis is more likely after travel to Asia; lung cancer and bronchitis are more likely for smokers. E is a deterministic logical OR of T and L. X and D are noisy effects. The local tables multiply into one joint law, and summing unwanted variables answers any query.

Direct evaluation is possible for eight binary variables, but its cost doubles with each new variable. More importantly, a brute-force table ignores separation. Travel affects the respiratory findings only through tuberculosis and E. Smoking reaches dyspnoea through lung cancer, bronchitis and E. The graph promises that summaries over a few boundary variables should replace enumeration of everything behind them. The rest of the paper makes that promise exact even though multiple paths create loops in the undirected structure.

First marry, then triangulate

A directed graph carries conditional tables, but the paper’s local marginal operations use an undirected Markov representation. The first transformation is moralisation. For every child with multiple parents, connect those parents if they are not already adjacent, then erase arrow directions. The new edge is called “marrying the parents”. It preserves the dependence that conditioning or marginalisation can induce between alternative causes of a common effect.

In the Asia network, T and L are married because both parent E. E and B are married because both parent D. Dropping directions then produces the moral graph. This graph can represent the joint distribution through potentials attached to complete subsets. It does not assert that newly married variables directly cause one another. The edges are computational and independence-bearing, not new causal claims.

Moralisation is not enough. A graph is triangulated, or chordal, when every cycle of length four or more has a chord connecting non-neighbouring vertices in that cycle. In a non-chordal cycle, eliminating a variable creates a dependence between its remaining neighbours that no existing clique can store. Fill-in adds edges so each elimination step leaves a complete neighbour set. In the paper’s graph, adding an edge between L and B, or choosing a different permissible chord, completes the triangulation.

The choice of fill-in changes efficiency, not the target probability. Extra edges remove conditional independences from the computational graph and enlarge cliques. They never add probability factors or scientific relationships. Finding a triangulation that minimises the largest state space is difficult; practical algorithms rely on ordering heuristics. The paper uses maximum-cardinality search to recognise and order chordal structure after fill-in.

Overlapping cliques form a tree with a memory rule

The maximal complete subsets of the triangulated graph become computational units. For Asia, one useful collection is {A,T}, {T,L,E}, {L,E,B}, {L,B,S}, {E,B,D} and {E,X}. These cliques can be arranged as a tree. Every edge is labelled by the intersection of its endpoint cliques, called a separator.

Not every tree over the cliques is valid. It must satisfy the running-intersection property: if a variable appears in two cliques, it must appear in every clique along the path between them. Equivalently, all cliques containing a variable form one connected subtree. This is the memory rule that prevents a variable’s information from disappearing and reappearing as if unrelated.

A set-chain ordering expresses the same property. Number cliques C₁,…,Cₖ so that each residual Rᵢ, the variables first introduced at clique i, is paired with a separator Sᵢ contained in one earlier parent clique. The joint law then factors into local conditionals P(Rᵢ|Sᵢ). A forward pass initialises clique marginals; a reverse pass completes them. The paper shows that this representation can be converted to potentials or calibrated marginals as the requested operation demands.

Four representations trade storage for operations

The paper distinguishes four ways to hold one distribution. Conditional probability tables align with the original directed families and are natural for elicitation. Evidence potentials attach non-negative functions to complete subsets of the moral graph and multiply to the joint law up to a normalising constant. A set-chain representation expresses residual variables conditional on separators. A clique-marginal representation stores marginal tables whose overlaps agree.

No representation dominates. Conditional tables are compact and interpretable before evidence arrives but awkward after arbitrary observations. Potentials absorb evidence by zeroing or selecting entries without immediately renormalising. Set chains support recursive initialisation and marginalisation. Calibrated clique marginals make any variable or subset contained in a clique immediately available. Fast transfer between forms is therefore part of the algorithm, not administrative overhead.

The second identity exposes why consistent overlaps matter. Multiplying clique marginals counts separator variables more than once; dividing by separator marginals corrects the duplication. If neighbouring clique tables disagree on their shared separator, there is no single global distribution with both as marginals. Calibration is the act of restoring that agreement by local messages.

Evidence enters once and travels as separator ratios

Hard evidence restricts a variable to an observed state. In a potential representation, select the matching slice in one clique containing that variable, or multiply by an indicator potential. Unobserved states receive zero. Logical zeros are therefore ordinary and useful; the scheme need not divide by them if messages are scheduled carefully. Several findings can be absorbed before propagation, and commutativity ensures that their order does not change the final posterior.

To propagate, choose a root clique. In a collect pass, every leaf sends a message towards the root after receiving messages from its other neighbours. A message is the sender’s current potential marginalised onto the separator. In the Lauritzen–Spiegelhalter architecture, a receiving clique updates by multiplying by the ratio of new separator marginal to the old stored separator marginal, with conventions for zeros. A distribute pass reverses direction. When both passes finish, adjacent cliques agree on every separator and all clique tables are proportional to their exact posterior marginals.

Branch information is summarised once. The separator variables shield the receiving side from every eliminated detail behind the sending clique. This is the same locality principle Pearl exploited on polytrees, lifted to groups of variables after triangulation. The cost is that a group may be much larger than a single node.

Temporary hypotheses use the same machinery. Clamp a state, propagate, inspect consequences, then restore the saved potentials and recalibrate. Planning can compare candidate tests by the expected change they would induce. Influential findings can be studied by retracting one item and measuring the shift. The paper recognises that these are computational primitives, not complete decision theory: a test’s value also depends on costs, actions and utilities.

Exactness ends at the clique-size cliff

The paper analyses operations in terms of clique state spaces. A clique with variables of cardinalities r₁,…,rₖ needs their product number of cells. For binary nodes the cost is exponential in k. Sparse graphs often yield small cliques, but a modest number of strategically placed edges can create a large treewidth. The visual size of the original graph is therefore a poor runtime predictor.

Triangulation quality matters because fill-in selects the cliques that will be materialised. The paper gives upper bounds based on total clique state space and the largest clique, and it discusses further savings from collapsibility, specialised queries and object-oriented precomputation. Later complexity results sharpen the boundary: exact inference in general Bayesian networks is NP-hard, and finding optimal triangulations is itself difficult.

For MUNIN-like systems, domain structure can still make exact work possible. Many nodes may have small state spaces and narrow separators. Repeated queries repay compilation because the clique tree can be retained while evidence changes. Yet discussants point to medical networks with high-cardinality disease nodes and large families whose tables alone are enormous. Approximation, model decomposition or hybrid sampling may then be necessary.

Conditioning and marginalisation are the primitive instructions

Underneath the graph terminology, the engine repeatedly performs two probability operations. Conditioning fixes selected states and removes inconsistent configurations. Marginalisation sums over variables that do not belong in the outgoing result. Multiplication combines factors that share variables. Division corrects a contribution already present in a receiving clique. The graph compiler determines an order in which these elementary instructions never require the full joint table.

The potential representation is deliberately tolerant of incomplete normalisation. If local functions multiply to ZP(V), the constant Z can be postponed while evidence is absorbed and messages are moved. This is valuable because most intermediate operations need only proportional values. The constant becomes an evidence likelihood when all remaining variables are summed out. It also provides a diagnostic: zero means the observations are incompatible with the model’s structural zeros, not that a floating-point routine should quietly invent a posterior.

Marginalising a collection of potentials requires first gathering every factor that mentions an eliminated variable, multiplying them, summing that variable away, and placing the resulting factor back on its remaining scope. This is variable elimination written without modern terminology. Different elimination orders give the same exact marginal but create different intermediate scopes. Triangulation records those scopes in advance, while the junction tree caches them for repeated queries.

Collapsibility can sometimes avoid full propagation. If a requested subset lies inside one clique, its marginal follows immediately from that calibrated table. More generally, portions of the graph whose variables separate cleanly can be collapsed without changing the query. The paper treats this as an extension rather than a magical shortcut: one must prove that the discarded interactions cannot affect the target. Query-specific calculation may be much cheaper than preparing every marginal, especially when only one decision variable matters.

Calculating the probability of a specific configuration is another special case. If the requested variables sit in a clique, read and sum the relevant cells. If they span several cliques, combine calibrated clique and separator marginals along the minimal connecting subtree. The running-intersection property again supplies the guarantee. Without it, multiplying local answers can count shared variables incorrectly or assume independence that the joint model does not contain.

The authors also describe drawing a complete configuration from calibrated marginals. Sample the residual variables of a root clique, then traverse the set chain and sample each new residual conditional on its separator. The result is a draw from the represented joint distribution, assembled locally. This anticipates later uses of junction trees for simulation, decoding and hybrid inference. Exact sampling here depends on already calibrated finite tables; it does not rescue a clique whose state space cannot be stored.

Explanation is harder than calculation. A posterior can be recomputed after retracting one finding, producing an influence measure for that item. Several findings can be removed in turn, and hypothetical tests can be inserted. Yet an influence score depends on the chosen contrast and can miss interactions among findings. A clinician may need the causal and temporal story, not only a numerical sensitivity. The paper is unusually candid that a fast inference engine does not automatically become a satisfactory explanation engine.

These primitives define a useful verification strategy. Test every local table for normalisation and declared structural zeros. Confirm that moralisation connects every co-parent pair. Verify chordality after fill-in and the running-intersection property after tree construction. Compare calibrated marginals with exhaustive enumeration on small subnetworks. Then test evidence order, retraction, impossible evidence and repeated propagation. The algorithm’s mathematical modularity becomes an engineering advantage only when each interface has an executable invariant.

The discussion separates calculation from knowledge

The unusually long published discussion tests the method from statistics, medicine, artificial intelligence and computer science. A. Thatcher lists assumptions behind success: an appropriate causal network exists and is known, experts can provide all required probabilities, those probabilities apply conditionally to the patient, and the clinic can observe the evidence. Exact propagation does not validate any of these premises.

J. Q. Smith praises evidence potentials but warns that probability elicitation needs a structural discipline. The graph should be elicited before numerical probabilities, and model criticism should follow. Max Henrion highlights the complexity bound and notes that clique size depends on connectivity and state cardinality. Gregory Cooper invokes hardness results: there are network families for which any exact general method must require exponential effort unless major complexity assumptions fail.

Jensen, Olesen and Andersen propose a junction-tree implementation that keeps the clique tree explicitly and simplifies propagation. This line became the HUGIN architecture. Later comparisons distinguish Lauritzen–Spiegelhalter, HUGIN and Shenoy–Shafer message stores and schedules. They share the junction-tree invariant while trading divisions, storage and reusability.

Ross Shachter observes that directed graphs can be transformed through arc reversal and node reduction, and warns against casual causal language when a graph only encodes conditional independence. Anthony O’Hagan and others question whether assessed probabilities are stable, precise or transportable. Medical symptoms and disease prevalence change across populations; a coherent posterior can be precisely conditional on the wrong clinic.

In reply, Lauritzen and Spiegelhalter welcome the explicit clique tree, recognise modelling and sensitivity analysis as central, and defend graph transformations as a way to reveal where calculation is possible. They stress that fill-in should not be read as scientific dependence and that irrelevance and causal ordering still matter for elicitation and explanation. They also acknowledge loops, imprecision and dynamic restructuring as open areas.

Exact Asia junction-tree laboratory

The laboratory instantiates the paper’s eight binary variables and six-clique tree. Local factors are assigned to cliques, hard evidence is absorbed, and recursive sum-product messages calibrate the tree. An independent exhaustive oracle scores all 256 joint states. Five evidence profiles and every displayed variable must agree to machine precision. A structural test verifies the running-intersection property.

The “visited Asia and dyspnoea” profile reconstructs the paper’s worked numbers to rounding. The hypothesis profile illustrates a temporary clamp rather than a causal intervention: conditioning T=false changes beliefs through the observational model. Retraction means restoring the unclamped potential and recalibrating, not applying an inverse probability.

Memory studio

What remains after every separator agrees

Lauritzen and Spiegelhalter transform exact inference from an undifferentiated exponential sum into a compilation and calibration problem. Directed families capture expert assessments. Moralisation exposes collider dependencies. Triangulation makes elimination stable. Cliques retain interactions, separators transmit sufficient summaries, and two tree sweeps make local marginals globally coherent.

The transformation clarifies rather than abolishes complexity. If triangulation creates a large clique, the exact method faithfully reveals the cost hidden in the model’s dependence structure. State cardinality can matter more than node count. Repeated evidence makes compilation worthwhile, but no scheduling trick defeats treewidth in general.

The paper’s multiple representations remain a valuable engineering lesson. Store knowledge in the form suited to elicitation; convert it to the form suited to evidence; calibrate it into the form suited to queries. Treat conversions as verified contracts. A conditional table, a potential and a marginal may carry the same distribution while supporting very different safe operations.

Finally, distinguish probabilistic coherence from epistemic warrant. A calibrated junction tree guarantees that its clique marginals belong to one conditioned joint model. It does not guarantee that the states are well defined, the graph transports to a new clinic, the probabilities are calibrated, or the recommendation serves the patient. Exact local computation solves the inference problem after the knowledge problem has been stated.