Bayesian networks: Uncertainty gets a calculus

The event and the narrow claim

In 1988 Morgan Kaufmann published Judea Pearl's Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, a 552-page book that the ACM Digital Library catalog record dates to that year. Its publisher describes it as an account of probability as a language for reasoning with partial belief, offering techniques based on belief networks that make such reasoning operational, with applications ranging from diagnosis and forecasting to image interpretation and speech recognition ( the publisher's description of the book). Pearl, a UCLA computer scientist who had founded the university's Cognitive Systems Laboratory in 1978, had developed the ideas across six years of papers. The book gathered them into one argument: an intelligent system can reason under uncertainty with ordinary probability theory, provided its knowledge is organized as a graph of local dependencies.

The narrow claim is technical. A directed acyclic graph, annotated with small conditional probability tables, defines a complete and consistent joint distribution; the arrows it leaves out state independence assumptions that can be read directly off the picture; and evidence can be propagated through it by local message passing, exactly so when the graph has no loops. The broad claim, made by others in retrospect, is that this changed the field. When ACM gave Pearl the 2011 A.M. Turing Award, its citation honored "a calculus for probabilistic and causal reasoning", and the laureate essay by Stuart Russell credits him with inventing Bayesian networks and the principal algorithms for inference in them ( ACM's laureate profile and essay). This report dates the event to the book because it was the synthesis most researchers read, while treating the 1982, 1985 and 1986 papers as the places where its individual ideas first appeared.

Uncertainty in the expert-system era

The problem the book answered had been sharpened by the success of expert systems. Programs in the line of DENDRAL and XCON encoded expertise as rules, and rules are crisp: if the premise holds, the conclusion follows. Medicine and geology do not work that way, so designers attached numbers to their rules. Shortliffe and Buchanan built the certainty-factor model in the mid-1970s for MYCIN, a program for diagnosing meningitis and blood infections, and it became the standard way to manage uncertainty in rule-based systems ( Heckerman's encyclopedia article on the certainty-factor model). At SRI, Duda, Hart and Nilsson took a "subjective Bayesian" route for the PROSPECTOR mineral-exploration system, modifying Bayes' rule to cope with the inconsistencies typical of experts' subjective statements ( their 1976 conference paper).

Both schemes were compromises with a perceived impossibility. As Russell's essay recounts, probabilistic methods had been tried in the 1960s and judged wanting, because estimating the probability of a disease from n symptoms seemed to require a number of parameters exponential in n ( ACM's laureate essay). Certainty factors avoided that cost by treating each rule as a self-contained module. David Heckerman showed in 1985 what the modularity bought and what it hid: any consistent probabilistic reading of MYCIN's combination functions requires evidence to be conditionally independent given both a hypothesis and its negation, and requires the inference network to be a tree, assumptions he judged rarely true in practice ( Heckerman's analysis of MYCIN's certainty factors).

The failures were concrete. In Heckerman's later illustration, a burglar alarm can be set off by a burglary or by an earthquake. A rule that raises belief in a burglary whenever belief in the alarm rises cannot lower that belief when a radio report of an earthquake arrives, even though the earthquake now accounts for the alarm. Nor can such a system tell that three news reports of a disaster, all traced to one original source, are weaker evidence than three independent ones ( Heckerman's certainty-factor article). The same article notes a practical cost: rules had to run from effect to cause, while physicians find it more natural to judge how likely a symptom is given a disease than the reverse. Reasoning under uncertainty, unlike logic, is not modular. The right update depends on where a belief came from and what else is known.

Replacing the giant table with local judgments

Pearl's way out started from a claim about human knowledge. In his 1985 paper for the Cognitive Science Society, the one with "Bayesian networks" in its title, he argued that people decide whether two propositions are dependent given a third far more readily than they produce numerical probabilities, and that the building blocks of knowledge are low-order relations among small clusters of related propositions rather than entries in one enormous joint table ( Pearl's 1985 paper). UCLA's account of the Turing Award credits Pearl with coining the term that year, after the eighteenth-century English mathematician Thomas Bayes ( UCLA Samueli's announcement).

The representation follows directly. Each variable is a node; arrows run from direct causes to their effects; each node carries a table giving its probabilities for every combination of its parents' values. The product of these local tables is the joint distribution. A network over six binary variables thereby fixes a unique distribution over all 64 combinations of their values, and Adnan Darwiche notes that networks with thousands of variables have been built and queried in the same way ( Darwiche's review of Bayesian networks).

The graph also carries meaning without any numbers. Pearl's 1985 paper stated the separation criterion now called d-separation: if every path between two variables is blocked by a set of observed variables, the two are independent given that set, with the special rule that a path on which two arrows meet head to head is blocked unless the meeting node or one of its descendants is observed ( Pearl's 1985 paper). That exception is explaining away. Fire and tampering are independent causes of an alarm, but once the alarm is known to have sounded, evidence of fire lowers the probability of tampering, precisely the behavior that certainty factors could not express ( Darwiche's review). Geiger, Verma and Pearl later proved the criterion sound and complete with respect to probability theory, and gave an algorithm that finds every independence implied by a network's topology in time linear in its number of edges ( their 1989 paper on d-separation).

Belief propagation: evidence as messages

A representation is useful only if conclusions can be computed from it, and Pearl's first contribution here predates the name. His paper at the AAAI-82 conference, "Reverend Bayes on Inference Engines", restricted attention to trees and gave each variable its own processor ( the AAAI-82 paper). Each processor holds two kinds of support for its variable: anticipatory support passed down from its parent and evidential support passed up from its children. When evidence arrives, processors exchange messages only with their neighbors and without central supervision, a design the paper likens to the cooperating knowledge sources of the HEARSAY speech-understanding system. Pearl later wrote that Rumelhart's 1976 account of reading, as a mix of top-down and bottom-up inference, had pushed him toward a distributed and purely Bayesian scheme ( ACM's laureate essay).

The difficulty the paper solved was instability. If belief in a hypothesis raises the expectation of its evidence, and that evidence in turn raises belief in the hypothesis, two communicating processors could amplify each other indefinitely. By keeping the two kinds of support separate, and removing from each message the contribution that came from its recipient, the updates settle in a single pass, in parallel time equal to the diameter of the network, at values that match exact Bayesian conditioning ( the AAAI-82 paper). The paper concluded that Bayes' formula still served as the basic rule for revising belief in large inference systems, against the common view that practical inexact reasoning had to bend probability theory. ACM's annotated bibliography calls it the paper that began the probabilistic revolution in AI ( ACM's annotated bibliography of Pearl's work).

Extensions followed quickly. Kim and Pearl generalized the scheme in 1983 to variables with several parents; Pearl's 1986 paper "Fusion, propagation and structuring in belief networks" covered representation and exact inference in general networks and had become, by 1991, the most cited paper in the history of the journal Artificial Intelligence; and a 1987 paper derived an approximation by stochastic simulation that the bibliography describes as the first significant use of Markov chain Monte Carlo in mainstream AI ( ACM's annotated bibliography). Graphs with loops remained the hard case. The 1985 paper listed the options: collapse the variables in a loop into one compound node, which works only for small loops; sample states stochastically, which converges slowly; or condition on a few variables so that the rest becomes singly connected and reason case by case ( Pearl's 1985 paper). In 1988 Lauritzen and Spiegelhalter published an exact method that first transforms a network into a tree whose nodes are sets of variables ( Heckerman's tutorial on learning with Bayesian networks).

What the 1988 book consolidated

The book drew these threads into a single treatment. Its publisher presents it as a coherent account of probability as a language for partial belief, setting network propagation against the alternatives then competing in AI, including the Dempster-Shafer formalism, truth maintenance systems and nonmonotonic logic, and addressing readers in decision theory, statistics, philosophy and cognitive psychology as well as AI ( the publisher's description). Russell's essay calls it a work that combined Pearl's philosophy, his theories of human cognition and his technical results into a persuasive whole, and reports that within a few years prominent researchers from AI's logic-based and neural-network communities alike had taken up the probabilistic approach. His comparison is to George Boole: Bayesian networks gave multivariate probability models a syntax and a calculus, as Boole had done for logical models ( ACM's laureate essay).

The shift is visible inside the expert-systems literature itself. Heckerman's 1985 critique of certainty factors had appeared in the proceedings of the first Conference on Uncertainty in Artificial Intelligence ( its arXiv record). In 1992 Heckerman and Edward Shortliffe, the MYCIN designer whose certainty factors had become the standard, published a review that set out the theoretical and practical limits of the certainty-factor model and argued that the belief network, grounded firmly in probability, overcame many of them ( Heckerman and Shortliffe's paper). ACM's bibliography credits the 1988 book with converting many researchers who had worked on logic or neural networks, and Russell's essay counts some 50,000 publications with Bayesian networks as a primary focus by 2012 ( ACM's laureate essay).

Where the networks went to work

Applications followed the book's list. Medical networks became standard test beds for inference algorithms: the ALARM network, built by medical experts to monitor patients in intensive care, and the QMR-DT network, a two-layer model linking roughly 600 diseases to roughly 4000 findings ( Murphy, Weiss and Jordan's study of loopy belief propagation). At Microsoft Research, the Lumiere project, begun in 1993, built Bayesian user models that inferred what a person working in a spreadsheet was trying to do from their actions and queries. A derivative shipped in January 1997 as the Office Assistant in Microsoft Office 97 ( the Lumiere paper). In 1998 Sahami, Dumais, Heckerman and Horvitz framed junk e-mail filtering as inference in a Bayesian network of the simplest kind, naive Bayes, and labeled a message as junk only when its probability exceeded 99.9 percent, because discarding a legitimate message costs more than admitting spam ( their AAAI workshop paper).

The most surprising application came from communications engineering. Turbo codes, introduced by Berrou and colleagues in 1993, performed close to the Shannon limit, but their iterative decoder lacked a theoretical explanation ( Murphy, Weiss and Jordan). In 1998 McEliece, MacKay and Cheng showed that turbo decoding is Pearl's belief propagation applied to the belief network of a concatenated code, and that the same procedure yields decoders for Gallager's low-density parity-check codes and other schemes ( the Caltech record of their paper). They stated the catch plainly: these networks contain loops, while Pearl had proved his algorithm correct only for graphs without them. Darwiche's review describes the wider pattern. Hidden Markov models in speech recognition, pedigrees in genetic linkage analysis and pixel models in stereo vision can all be cast as Bayesian networks, and casting linkage analysis that way produced the most efficient exact algorithms for general pedigrees ( Darwiche's review).

The causal turn

While building this machinery, Pearl concluded that it could not answer the questions he cared most about. A Bayesian network encodes dependence, and dependence is symmetric: as Russell's essay explains, a network with an arrow from smoking to cancer is mathematically equivalent to one with the arrow reversed. What distinguishes a causal network is its response to intervention. Forcing a variable to a value should cut the arrows into it while leaving beliefs about its causes unchanged, so making someone smoke changes the expectation of cancer, but inducing cancer says nothing about whether the person smokes ( ACM's laureate essay).

Pearl formalized this in "Causal diagrams for empirical research", published in Biometrika in 1995 ( the UCLA copy of the Biometrika paper). It gave directed graphs a causal reading based on nonparametric structural equations, gave graphical conditions (the back-door and front-door criteria) under which a causal effect can be estimated from observational data, and introduced three rules for inserting, deleting and exchanging observations and interventions, the calculus now known as the do-calculus. One example asked whether the effect of smoking on lung cancer could be identified through tar deposits even if an unobserved genotype influenced both smoking and cancer. Pearl left open in 1995 whether the three rules sufficed to derive every identifiable effect; his 2019 article describes the calculus as an engine that predicts an intervention's effect whenever feasible and exits with failure when the stated assumptions do not allow it ( Pearl's 2019 article in Communications of the ACM). The book Causality followed in 2000 and won the 2001 Lakatos Award ( ACM's annotated bibliography); its second edition presents causation as a mathematical theory that unifies probabilistic, manipulative, counterfactual and structural approaches ( Cambridge's page for the second edition).

The causal turn matters to this event because it marks the boundary of the 1988 achievement. The book gave AI a calculus of belief. It did not give a calculus of action, and its author spent the following decade building one.

The honest limits

The first limit is computational. Belief propagation is exact and fast on trees and singly connected graphs, but realistic models have loops. In 1990 Gregory Cooper proved that probabilistic inference in general belief networks is NP-hard and advised researchers to pursue special-case, average-case and approximation algorithms instead of a general efficient method ( Cooper's research note in Artificial Intelligence). Dagum and Luby then showed that approximate inference is NP-hard as well ( Heckerman's tutorial). Exact algorithms based on elimination and conditioning cost time exponential in a graph measure called treewidth, which for an image model of n by n pixels equals n, far too high for exact methods ( Darwiche's review). Loopy belief propagation became the practical substitute, without guarantees: Murphy, Weiss and Jordan found that it often converged to good approximations, yet on the QMR-DT network its beliefs oscillated with no obvious relation to the correct posteriors ( their 1999 study).

The second limit is knowledge. A network has to come from somewhere. Hand-built networks need experts to supply both structure and many conditional probabilities, and learning networks from data is hard in its own right. Chickering proved that finding a high-scoring network under the Bayesian BDe metric is NP-complete when each node may have up to K parents ( Chickering's 1996 chapter), and Heckerman noted that the number of candidate structures grows faster than exponentially with the number of variables, which forces greedy and other heuristic searches ( Heckerman's tutorial). Simplified structures trade fidelity for tractability: the spam filter's authors cautioned that naive Bayes, because of its independence assumption, does not produce very accurate probability estimates, even when its classifications are usable ( the spam-filtering paper).

The third limit is priority. Directed probabilistic graphs predate Pearl. Heckerman's survey traces the representation to Sewall Wright's 1921 work on correlation and causation, to I. J. Good in 1961 and to a 1968 Stanford report, and notes that Howard and Matheson's influence diagrams of 1981 had already extended it to decisions ( Heckerman's certainty-factor article). Cooper's note points out that PROSPECTOR and CASNET had used directed graphs of probabilistic relationships ( Cooper's research note), and Lauritzen and Spiegelhalter's exact method appeared the same year as Pearl's book. Pearl's distinctive contributions were the distributed propagation algorithm, the independence semantics that d-separation makes precise, and the synthesis that persuaded AI.

How to place Bayesian networks in AI history

Bayesian networks mark the point at which AI's handling of uncertainty moved from logic with numbers attached to probability with structure attached. The move did not abandon the expert-system ambition, since networks were still built from expert knowledge; it corrected its mathematics. The book's publication falls in the period this record covers as the second AI winter, and Russell's essay notes that the probabilistic approach his work set off came to be called, simply, the modern approach to AI ( ACM's laureate essay).

The line into machine learning is direct and documented. When Hinton, Osindero and Teh revived deep networks in 2006, their model was a deep belief net, a directed network topped by an undirected associative memory, and they named explaining away as the effect that makes inference difficult in densely connected belief nets, citing Pearl's book ( their paper on deep belief nets; see the deep learning revival). Kingma and Welling's variational autoencoder opened by asking how to perform efficient inference and learning in directed probabilistic models with continuous latent variables and intractable posteriors ( their 2013 paper; see learning a generative latent space). Those are Pearl's questions, answered with neural networks and gradient-based approximation instead of exact message passing.

That inheritance should be stated with care. The largest current neural models are not hand-specified Bayesian networks, and Pearl himself argues that systems which only fit observed data remain on the associational rung of his three-level hierarchy, below intervention and counterfactuals ( Pearl's 2019 article). The durable legacy of 1988 is a vocabulary and a set of tests: conditional independence as the organizing principle of uncertain knowledge, graphs as a way to state and check it, and inference as computation over local structure. How much of present-day AI rests on that legacy, as opposed to echoing it, remains a judgment in progress.

References

• Pearl (1982). Reverend Bayes on Inference Engines: A Distributed Hierarchical Approach.
• Pearl (1985). Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning.
• Pearl (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference.
• ACM Digital Library (1988). Probabilistic reasoning in intelligent systems: networks of plausible inference, catalog record.
• ACM (2012). Judea Pearl, A.M. Turing Award laureate profile and essay by Stuart Russell.
• ACM (2012). Judea Pearl: short annotated bibliography.
• UCLA Samueli School of Engineering (2012). Judea Pearl Wins ACM Turing Award for Contributions that Transformed Artificial Intelligence.
• Duda, Hart and Nilsson (1976). Subjective Bayesian methods for rule-based inference systems.
• Heckerman (1985). Probabilistic Interpretations for MYCIN's Certainty Factors.
• Heckerman (1992). The Certainty-Factor Model.
• Heckerman and Shortliffe (1992). From Certainty Factors to Belief Networks.
• Geiger, Verma and Pearl (1989). d-Separation: From Theorems to Algorithms.
• Darwiche (2010). Bayesian Networks.
• Heckerman (2020). A Tutorial on Learning With Bayesian Networks.
• Cooper (1990). The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks.
• Chickering (1996). Learning Bayesian Networks is NP-Complete.
• Murphy, Weiss and Jordan (1999). Loopy Belief Propagation for Approximate Inference: An Empirical Study.
• Horvitz et al. (1998). The Lumiere Project: Bayesian User Modeling for Inferring the Goals and Needs of Software Users.
• Sahami et al. (1998). A Bayesian Approach to Filtering Junk E-Mail.
• McEliece, MacKay and Cheng (1998). Turbo decoding as an instance of Pearl's belief propagation algorithm.
• Pearl (1995). Causal diagrams for empirical research.
• Cambridge University Press (2009). Causality: Models, Reasoning, and Inference, second edition.
• Pearl (2019). The Seven Tools of Causal Inference, with Reflections on Machine Learning.
• Hinton, Osindero and Teh (2006). A fast learning algorithm for deep belief nets.
• Kingma and Welling (2013). Auto-Encoding Variational Bayes.