Bayesian Networks

You wake up and the grass is wet. Did it rain — or did someone leave the sprinkler on? Both causes make the grass wet, but they are not equally likely given everything else you know. A Bayesian network is a tool for thinking through exactly this kind of uncertainty systematically.

The idea, developed by Judea Pearl in the 1980s (earning him the 2011 Turing Award), is to represent every variable as a node in a directed acyclic graph. An arrow from Rain to Wet grass means "rain influences whether the grass is wet." Each node stores a small conditional probability table — numbers like "if it rained, the grass is wet with probability 0.99." That is all you need. Once the graph is built, observing any variable instantly constrains every other one through the structure.

The magic is that you can do inference without enumerating every combination. Instead of multiplying out a joint probability table that would grow exponentially with the number of variables, the graph lets you pass messages along edges. Add one new fact, run message-passing, and every node in the network has an updated belief. It is Bayes' theorem, scaled up and made efficient by a graph.

Below is the classic Sprinkler network — four variables connected by causal arrows. Each node shows its current probability of being True. Click any node to cycle it through unknown → observed True → observed False, then watch how every other belief updates.

<p class="hint">{{hint}}</p>
<div id="network"></div>
<div id="legend">
  <span class="leg-item"><span class="leg-dot unknown"></span>{{leg_unknown}}</span>
  <span class="leg-item"><span class="leg-dot true"></span>{{leg_obs_true}}</span>
  <span class="leg-item"><span class="leg-dot false"></span>{{leg_obs_false}}</span>
</div>
<button id="reset" type="button">{{btn_reset}}</button>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
#network { position: relative; width: 100%; height: 320px; }
svg.edges { position: absolute; inset: 0; width: 100%; height: 100%; pointer-events: none; overflow: visible; }
svg.edges path { fill: none; stroke: #8fa3b2; stroke-width: 2; marker-end: url(#arr); }
.node { position: absolute; width: 110px; text-align: center; cursor: pointer; user-select: none; transform: translate(-50%, -50%); }
.node-box { border-radius: 12px; padding: .5rem .4rem .4rem; border: 2px solid #8fa3b2; background: #eef2f5; transition: background .2s, border-color .2s; }
.node.obs-true  .node-box { background: #d4edda; border-color: #28a745; }
.node.obs-false .node-box { background: #f8d7da; border-color: #dc3545; }
.node-box:hover { filter: brightness(0.96); }
.node-name { font-size: .78rem; font-weight: 700; color: #1d3557; margin-bottom: .25rem; }
.node-prob { font-size: 1.05rem; font-weight: 800; color: #1d3557; }
.node-state { font-size: .7rem; color: #555; margin-top: .15rem; min-height: .85rem; }
#legend { display: flex; gap: 1rem; font-size: .8rem; color: #555; margin: .6rem 0 .5rem; flex-wrap: wrap; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.leg-dot { width: 12px; height: 12px; border-radius: 50%; border: 2px solid; }
.leg-dot.unknown { background: #eef2f5; border-color: #8fa3b2; }
.leg-dot.true    { background: #d4edda; border-color: #28a745; }
.leg-dot.false   { background: #f8d7da; border-color: #dc3545; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Code not found

Notice what happens when you set Wet Grass = True: both Rain and Sprinkler become more likely — the evidence "explains" either cause. Now also set Rain = True: Sprinkler drops back down. This is explaining away — once rain accounts for the wet grass, the sprinkler becomes less necessary as an explanation. It emerges automatically from the math, no special logic required.

Bayesian networks look like they should be easy — after all, it's just a graph and some probability tables. But the hardness hides in the structure.

• Exact inference is #P-hard. In 1990 Gregory Cooper proved that computing the exact posterior probability of any node in a general Bayesian network is #P-hard — at least as hard as counting solutions to a SAT formula, which is believed to be exponentially harder than P vs NP already.
• The culprit is loops. On a tree (no cycles), the message-passing algorithm called belief propagation is exact and runs in linear time. Once the graph has cycles — undirected cycles, even if the directed edges have no directed cycle — inference can require exponential work in the worst case.
• Treewidth is the key. The graph parameter called treewidth measures how "tree-like" the network is. Variable elimination runs in time exponential in treewidth. Networks with low treewidth (like trees, polytrees, or sparse graphs) are tractable; dense, highly connected networks are not.
• Approximate inference rescues practice. Algorithms like Markov chain Monte Carlo (MCMC), loopy belief propagation, and variational methods trade exactness for speed and work well enough on most real networks even when exact inference is intractable.

So Bayesian networks sit at a junction: they make probabilistic reasoning possible where a flat joint probability table would be impossible, yet exact reasoning remains hard in general, requiring approximations or special graph structure.

Any time you have multiple uncertain variables that influence each other, a Bayesian network can help:

• Medical diagnosis: the famous CPCS and QMR-DT networks connected hundreds of diseases to thousands of symptoms, letting doctors update diagnoses as test results arrived — each new result propagated automatically through the graph.
• Spam filtering: early Bayesian spam filters modeled words as evidence nodes and "spam/ham" as the hidden variable. Naïve Bayes (a degenerate Bayesian network) still runs inside most email clients today.
• Autonomous vehicles: perception uncertainty — is that a pedestrian or a shadow? — is exactly what Bayesian networks handle. The car's belief about the world is a probability distribution that updates as sensors fire.
• Fault detection: in aircraft and industrial plants, a network over sensor readings lets engineers reason backwards: given these alarms, which component is most likely failing?
• Genomics and epidemiology: gene regulatory networks and disease-spread models both encode who influences whom, making Bayesian networks a natural fit.

Learn how a Bayesian network works and you've also understood the probabilistic core of modern AI — the same ideas live inside hidden Markov models, Kalman filters, and deep generative models like variational autoencoders. See also Bayes' theorem for the single-variable foundation everything else builds on.

A Bayesian network is, at its core, a compact way to write down a large joint probability distribution — compact because the graph encodes exactly which variables are independent of which others. That compactness is what makes inference tractable on graphs with low treewidth and what makes it hard in general.

Judea Pearl's insight was that structure matters. Random variables do not influence each other randomly; causality has a shape. Capture that shape in a graph, attach small probability tables, and you can reason about complicated uncertain worlds with arithmetic alone — no enumeration required, as long as the graph stays sparse enough.

Next time you update your beliefs after new evidence, you are running a mental version of belief propagation. The question is just how tangled your internal graph of assumptions really is — and whether it has low enough treewidth for an exact answer to be within reach.