Bayesian network

• 1. Introduction

  ›

  A Bayesian network is a tool that does something deceptively simple: it maps what we know, and what we do not know, onto a picture of causes and effects. Judea Pearl coined the term in 1985, deliberately choosing the name to honor Thomas Bayes and to signal three commitments. First, that the inputs are often subjective. Second, that updating beliefs follows Bayes' rule. Third, that the model distinguishes between reasoning forward from causes and reasoning backward from evidence. Those three commitments sit at the heart of everything that makes Bayesian networks both powerful and genuinely strange. How can a diagram of arrows and boxes tell a doctor which disease most likely explains a patient's symptoms? How can the same mathematical structure be used to decide whether it is worth turning on a garden sprinkler? And what happens when the problem is so large that finding the exact answer is provably impossible? Those are the questions this documentary explores.

• 2. A Picture of Causes

  ›

  At its core, a Bayesian network is a directed acyclic graph, which means a diagram of arrows that never loop back on themselves. Each node in the graph stands for a variable: something that can take different values, whether it is observable, unknown, or a pure hypothesis. Each arrow stands for a direct conditional dependency. Two nodes with no connecting path are conditionally independent of each other. That word "acyclic" is load-free in the technical sense but carries a practical meaning: there is no circularity, no variable is ever its own cause, even indirectly. A simple classroom example makes this concrete. Imagine three variables: whether it is raining, whether a garden sprinkler is active, and whether the grass is wet. Rain affects whether the sprinkler runs, because people tend to turn off sprinklers when it rains. Both rain and the sprinkler can wet the grass independently. That three-variable situation already captures something that pure probability tables struggle with: the direction of influence matters as much as the strength of association. Rather than storing every possible combination of all variables, the network stores only the local relationships. For ten two-valued variables, a full probability table requires storage for a number of values that grows exponentially. A Bayesian network, where no variable depends on more than three parents, stores at most a fraction of that. The savings are not cosmetic.

• 3. Reading Evidence Backward

  ›

  Pearl designed Bayesian networks partly to handle what he called inverse probability: the problem of reasoning from effects back to causes. Given that the grass is wet, what is the probability it is raining? The network can answer that question by applying conditional probability formulas and summing over the variables that are not directly observed. Formally, computing the posterior distribution of hidden variables given observed evidence is called probabilistic inference. The network acts as an automatic application of Bayes' theorem to problems that would be too tangled to solve by hand. There is also a sharper kind of question the network can handle: interventional questions, not just observational ones. Asking "what is the probability of rain, given that I observe wet grass?" is different from asking "what would happen if I deliberately wetted the grass myself?" Pearl captured this distinction with a do-operator. Forcing a variable to a value, written as do(G = true), removes the arrow pointing into that variable from the rest of the network. After that removal, the action of wetting the grass has no effect on the probability of rain, because rain is not caused by wet grass. This may sound obvious, but making it mathematically precise was a significant step. It separated correlation from causation in a way that data alone cannot. When intervening on a variable is not straightforward because other variables are unobserved, the back-door criterion provides a test. If a set of observed nodes can block all indirect paths from a cause to an effect, those nodes are called admissible, and causal effects can still be estimated from non-experimental data. When no such set exists, the effect is said to be unidentified, and passive observation cannot resolve the question. The three rules of do-calculus provide a systematic way to test whether any causal quantity is identifiable from a given network.

• 4. The Hardness of Exact Answers

  ›

  In 1990, at Stanford University, Cooper proved that exact inference in Bayesian networks is NP-hard. That result reoriented the field. NP-hard means, roughly, that no known algorithm can solve every instance in a time that grows polynomially with the problem size. It was a mathematical ceiling on ambition. Then, in 1993, Paul Dagum and Michael Luby sharpened the picture further. They proved two results that surprised researchers. No tractable deterministic algorithm can approximate probabilistic inference to within an absolute error smaller than one-half. No tractable randomized algorithm can match that bound either, as long as the confidence requirement exceeds one-half. Roth added another layer: exact inference in Bayesian networks is not just NP-hard but #P-complete, as hard as counting the number of satisfying assignments of a logical formula in conjunctive normal form. Even approximate inference, within a factor of two raised to a power that grows with the network size, is NP-hard for networks with restricted architecture. These results did not make Bayesian networks less useful. They forced researchers to be specific about which problems they were solving. Exact methods, including variable elimination, clique tree propagation, and recursive conditioning, all have complexity exponential in the network's treewidth. For sparse, well-structured networks, treewidth stays low and exact methods remain feasible. For large, dense networks, approximate algorithms took center stage: importance sampling, stochastic Markov chain Monte Carlo simulation, loopy belief propagation, and variational methods each trade some precision for tractability. Dagum and Luby also developed the bounded variance algorithm, the first provable fast approximation algorithm for probabilistic inference that came with guarantees on the approximation error.

• 5. Learning From Data

  ›

  When a human expert cannot specify a Bayesian network by hand, the structure and its parameters must be learned from data, and that turns out to be its own set of hard problems. Parameter learning addresses the simpler case: given a fixed graph, estimate the probability distributions at each node. When those distributions are unknown, they can be estimated by maximum likelihood. A classical tool for this is the expectation-maximization algorithm, which alternates between estimating unobserved variable values and maximizing the likelihood of the observed data, repeating until the estimates converge. When only constraints on the distributions are known, the principle of maximum entropy selects the distribution with the greatest entropy consistent with those constraints. Structure learning is harder. Automatically recovering the graph topology from data is, in general, NP-hard, because the number of possible directed acyclic graphs grows superexponentially with the number of variables. Two broad strategies exist. The first is constraint-based: algorithms developed from a recovery method by Rebane and Pearl identify which variable pairs are conditionally independent, reconstruct the skeleton of the graph, and then determine the direction of arrows wherever the conditional independences allow. A key insight from that approach is that three-node patterns come in three varieties: a chain, a fork, and a collider. The first two impose the same conditional independence structure and cannot be told apart from data alone. The collider can, because in a collider the two parents are marginally independent but become dependent once the child is observed. The second strategy uses optimization: score a candidate structure using something like the Bayesian Information Criterion, then search the space of structures to maximize that score. Local search makes incremental changes; global methods like Markov chain Monte Carlo avoid local minima. For very large problems with thousands of variables, sampling orderings of variables and finding the best network consistent with each ordering has been shown to perform better than other available methods. For problems with up to 100 variables, casting the learning task as an integer program and adding acyclicity constraints as cutting planes during solving offers an exact and fast alternative.

• 6. Roots and Extensions

  ›

  By the late 1980s, two books had turned Bayesian networks from a set of techniques into a recognized field. Pearl's Probabilistic Reasoning in Intelligent Systems and Neapolitan's Probabilistic Reasoning in Expert Systems together documented the properties of these models and established their mathematical foundations. Pearl's 1985 coinage of the term was deliberate: he wanted the name to carry three things at once, the subjectivity of the inputs, the role of Bayes' conditioning, and the separation of causal from evidential reasoning. Before that, related ideas existed under names that did not signal those commitments. The framework extends in several directions. When variables unfold over time, such as speech signals or protein sequences, the model becomes a dynamic Bayesian network. When the goal is not just to reason about probabilities but to make decisions under uncertainty, the framework expands into an influence diagram. For hierarchical problems, where parameters themselves have prior distributions that depend on yet further parameters, Bayesian networks provide the natural structure for what is called a hierarchical Bayes model. The Markov blanket concept captures a useful locality property: for any node in a network, the set of its parents, its children, and the other parents of its children contains all the information needed to determine that node's distribution, rendering the rest of the network irrelevant. Software implementations now include several open and commercial options. WinBUGS was one of the first computational implementations of Markov chain Monte Carlo samplers for Bayesian inference, and OpenBUGS continues that line as an open-source development. Stan implements a different sampler, the No-U-Turn variant of Hamiltonian Monte Carlo. The marginal independence structure of a Bayesian network, a simpler undirected graph with special intersection and independence properties, can be learned from data in polynomial time, even when full structure recovery is out of reach.