Bayesian Networks: Inference and Relational Models

This builds on Bayesian Networks, which built the burglary network, read compactness and d-separation off the graph, and ran exact inference by variable elimination. That method is linear on polytrees but intractable in general — so we pick up where it fails, first estimating answers by sampling, then stretching the whole formalism to reason about objects it was never told exist.

Approximate inference by sampling

Sampling — Monte Carlo — algorithms trade exactness for tractability: draw many random samples from a distribution related to the network, count outcomes, and read off probabilities as frequencies. Accuracy improves with the number of samples, with the error in each estimate falling as $1/\sqrt{N}$.¹

Direct and rejection sampling

The primitive is sampling a network with no evidence. Prior sampling visits the nodes in topological order and, at each one, draws a value from its CPT conditioned on the values already fixed for its parents. One full pass yields one sample from the joint. Counting how often an event occurs across many samples estimates its probability, converging to the true joint value in the limit.

To answer a query with evidence $\mathbf{e}$, rejection sampling wraps prior sampling: generate a full sample, discard it unless it agrees with $\mathbf{e}$, and tally the query variable over the survivors. It is correct but wasteful — the fraction of samples consistent with the evidence shrinks exponentially as evidence accumulates, so most samples are thrown away, and for anything but a little evidence the method is unusable.

Likelihood weighting

Likelihood weighting removes the waste by never generating an inconsistent sample. It fixes the evidence variables to their observed values and samples only the rest, then weights each sample by the likelihood the evidence accords the network — the product, over evidence variables, of $P(e_i\mid \text{parents}(E_i))$. A sample in which the evidence looks unlikely receives a small weight; every sample counts, but not equally.²

Averaging the query counts weighted by $w$ gives a consistent estimate: combining the sampling distribution with the weight recovers exactly the true joint $P(\mathbf{z},\mathbf{e})$. Likelihood weighting uses every sample, so it beats rejection sampling — but it too degrades as evidence grows, because samples end up carrying tiny weights when the evidence sits far downstream, guiding little of the sampling.

Gibbs sampling and MCMC

Markov chain Monte Carlo works differently again: rather than build each sample from scratch, it makes a small random change to the previous one, wandering through the space of complete assignments. Gibbs sampling is the version suited to Bayesian networks. Fix the evidence, initialize the other variables arbitrarily, then repeatedly pick a nonevidence variable and resample it from its distribution given its Markov blanket — the one set of variables that isolates it. Each visited state is a sample; tallying the query variable over the whole walk estimates the posterior.³

The walk defines a Markov chain over states whose stationary distribution coincides with the posterior $P(\mathbf{x}\mid \mathbf{e})$: the long-run fraction of time spent in each state equals its probability. This holds because the transition satisfies detailed balance with that posterior, and resampling from the Markov blanket needs only the variable's own CPT and those of its children, so each step is cheap. Given enough steps, the samples are drawn from the true posterior — a correct answer built incrementally, one variable flip at a time.

Message passing, loopy BP, and variational inference

Variable elimination and the three samplers are AIMA's account, but the graphical models community organizes exact and approximate inference around a different object — message passing on a graph — and it is worth seeing where the two meet.

Exact inference as messages: the junction tree. Pearl's belief propagation (Probabilistic Reasoning in Intelligent Systems, 1988) computes exact posteriors on a polytree by passing two messages along each edge: a $\pi$ message carrying causal support down from parents and a $\lambda$ message carrying diagnostic support up from children. Each node combines its incoming messages with its CPT to get its posterior, and every message is computed once, so the whole network is solved in one forward and one backward sweep — linear time, the polytree bound this lesson already met. For a multiply connected network the trick that restores exactness is the junction tree (or clique tree) algorithm of Lauritzen and Spiegelhalter (Journal of the Royal Statistical Society B, 1988): cluster the loopy variables into cliques so the cliques form a tree, then run belief propagation between cliques. This is variable elimination in disguise — the largest clique's size is the treewidth of the graph, and inference is exponential in exactly that width, which is the precise statement of sparse enough that makes exact inference affordable. Koller and Friedman's Probabilistic Graphical Models (2009) develops this clique-tree view as the organizing frame for the whole subject.

Loopy belief propagation. The cheap idea is to run Pearl's message-passing rules on a multiply connected graph anyway, ignoring that they are only exact on trees, and iterate until the messages stop changing. Loopy belief propagation has no guarantee of converging or of giving the right answer when it does, yet Murphy, Weiss, and Jordan (UAI, 1999) showed empirically that it often converges to useful approximate posteriors — and it became the decoding algorithm behind turbo codes and low-density parity-check codes, whose near-Shannon-limit performance is loopy BP running on a code's factor graph. Yedidia, Freeman, and Weiss (2005) later connected its fixed points to the stationary points of the Bethe free energy, explaining when the approximation is good.

Variational inference. The other large family replaces sampling with optimization. Rather than draw from the true posterior $P(\mathbf{x}\mid \mathbf{e})$, variational inference picks a tractable family of distributions $q$ — often a fully factored mean field $q(\mathbf{x})={\prod }_i{q}_i(x_i)$ — and finds the member closest to the posterior by minimizing the KL divergence $\mathrm{KL}(q\Vert P)$, equivalently maximizing a lower bound on the evidence (the ELBO). The result is a deterministic estimate rather than a noisy one, and it scales where MCMC mixes too slowly. Jordan, Ghahramani, Jaakkola, and Saul's 1999 introduction (Machine Learning 37) framed the mean-field approach for graphical models, and Blei, Kucukelbir, and McAuliffe's review (Journal of the American Statistical Association, 2017) traces its growth into the default inference method for large Bayesian models. The connection back to deep learning is direct: the variational autoencoder (Kingma and Welling, 2014) is variational inference with the approximating $q$ and the generative model both parameterized by neural networks, trained by maximizing the same ELBO — the sampling-versus-optimization choice this lesson draws in miniature, scaled to models with millions of latent variables.

Relational and first-order probability models

Everything so far assumed a fixed cast of variables drawn in advance. Real problems are not so tidy: an online store has thousands of customers and books, and you cannot draw a node for each by hand. The move here mirrors the leap from propositional to first-order logic — write the dependencies once, with logical variables ranging over objects, and let the model expand itself to however many customers and books actually exist.

A Bayesian network is essentially propositional: its set of random variables is fixed and finite, and each has a fixed domain. That is a real limit. First-order logic gained its power over propositional logic by committing to objects and relations and quantifying over them, and we would like probability to gain the same. A model that could speak of all customers, or every book, without naming each in advance, would multiply the range of problems probability can handle.⁴

Take an online retailer aggregating customer recommendations into an overall quality estimate for each book. The crude answer — average the recommendations — ignores that some customers are kinder than others (they rate mediocre books highly) and some are less honest (they rate for reasons unrelated to quality, say because they work for a publisher). A Bayesian network for one customer $C_1$ recommending one book $B_1$ has $Recommendation(C_1,B_1)$ depending on $Honest(C_1)$, $Kindness(C_1)$, and $Quality(B_1)$. With two customers and two books the network already needs four recommendation nodes, and for realistic numbers of customers and books it is hopeless to draw by hand.

Relational probability models

The network has enormous repeated structure: every $Recommendation(c,b)$ node has the same three kinds of parent, and its CPT is identical across all pairs, as are all the $Honest(c)$ priors, and so on. This is tailor-made for a first-order language. A relational probability model (RPM) has constant, function, and predicate symbols, and a type signature fixing the type of each argument and value:⁴

The random variables are obtained by instantiating each function on every combination of objects — $Honest(C_1)$, $Quality(B_2)$, $Recommendation(C_1,B_2)$, and so on. Because each type has finitely many instances, the set of variables is finite. The dependencies are written once, with logical variables ranging over objects:

where $RecCPT$ is one shared table with $2\times 5\times 5=50$ rows. The RPM's semantics is defined by unrolling: instantiate the dependencies for all known constants to produce an ordinary Bayesian network over the RPM's variables. A template written once thus unfolds into arbitrarily many objects.

The model refines easily. A context-specific independence lets a variable ignore some parents given certain values of others: a dishonest customer ignores a book's quality, so $Recommendation(c,b)$ is independent of $Kindness(c)$ and $Quality(b)$ when $Honest(c)=false$, and the dependency becomes an if–then–else whose test the inference engine may not know the value of. Layer on more structure — an honest customer who is a fan of a book's author always gives a $5$ — and if the author $Author(b)$ is itself unknown, the system must reason over all possible authors, with $Author(b)$ acting as a multiplexer selecting which $Fan$ variable influences the recommendation. Uncertainty about $Author(b)$, which changes the dependency structure itself, is relational uncertainty. From a model of a few lines, the posterior can infer things like who wrote a book — if three customers who are fans only of author $A_1$ all rate $B_2$ a $5$ while others find it dismal, $A_1$ is very likely its author.

Inference by unrolling then running variable elimination is correct but can produce a huge network, and unknown relations give some variables many parents. Three economies help: the repeated substructure makes many elimination factors identical, so caching yields speedups of orders of magnitude; context-specific independence prunes work; and MCMC samples complete possible worlds, in each of which the relational structure is fully known, so relational uncertainty costs no extra network complexity — the sampler simply includes moves that change which author $B_2$ has. A lifted inference, analogous to resolution over propositionalization, would instantiate logical variables only as needed, letting one lifted factor stand for many ground ones.

Open-universe probability models

Database semantics assumes we know exactly which objects exist and can name them unambiguously. That assumption is often false. A book may carry several ISBNs, so aggregating recommendations across the same book is uncertain; a dishonest customer may hold thousands of login IDs (a sibyl attack). More broadly: a vision system does not know what is around the corner or whether it is the same object seen a minute ago; a text system does not know in advance which entities a document mentions or whether Mary, she, and his mother corefer; an analyst hunting spies never knows how many spies there are. These are existence uncertainty (what objects underlie the data) and identity uncertainty (which symbols name the same object), and much of human cognition seems to require exactly this — learning what objects exist and connecting observations, which almost never arrive with unique IDs, to hypothesized objects.

For these we need open-universe probability models (OUPMs) built on the standard semantics of first-order logic, where possible worlds vary in the objects they contain. The trick is to see how a Bayes net defines a unique distribution — it generates a world event by event, in topological order, each event assigning a value to a variable — and to extend that generative view. An RPM extends it to sets of events (the instantiations of a predicate); an OUPM goes further, allowing generative steps that add objects to the world under construction, where the number and type of new objects may depend on those already present. The generated event is now the very existence of an object.

One way to write an OUPM is to give conditional distributions over the numbers of objects. To separate customers (real people) from their login IDs, expecting between $100$ and $10,000$ customers, use a prior $\#Customer\sim LogNormal[6.9,2.3^2]()$; honest customers own one ID, dishonest ones between $10$ and $1000$:

Here $Owner$ is an origin function recording where each generated object came from. Under acyclicity and well-foundedness conditions, such a model defines a unique distribution over possible worlds, and there exist inference algorithms whose answer to any first-order query approaches the true posterior in the limit — though they are delicate: an MCMC sampler cannot enumerate unbounded worlds, so it samples finite partial worlds and includes moves that merge two objects into one or split one into two. The result is that the probability of any first-order sentence $\phi$ is still well defined as a sum over the worlds where it holds,

so open-universe first-order probability lets one small model reason about an unbounded, unknown population of objects — the increase in expressive power that makes vision, text understanding, and intelligence analysis tractable as probabilistic inference.

Other approaches to uncertain reasoning

Probability is the dominant calculus of uncertainty, but AI tried many alternatives, especially during the years (roughly 1975 to 1988) when efficient Bayesian-network algorithms were unknown and the full joint's exponential size seemed to doom the probabilistic approach.⁵ Three families are worth knowing, if only to see what they trade away.

Rule-based methods attach a fudge factor to each logical rule and combine them by purely local, truth-functional operations — the belief in $A\vee B$ a function of the beliefs in $A$ and $B$ alone. Logical rule systems enjoy three properties: locality (rule $A\Rightarrow B$ fires on $A$ alone), detachment (a proved $B$ is usable regardless of how it was proved), and truth-functionality. None survives contact with uncertainty. Truth-functionality fails because $P(A\vee B)$ depends on the events, not just their probabilities: with a fair coin, $P(H_1\vee H_1)=0.5$ but $P(H_1\vee T_1)=1.0$ and $P(H_1\vee H_2)=0.75$, all from operands of probability $0.5$. Locality and detachment fail because chaining causal and diagnostic rules ($Rain\Rightarrow WetGrass$ and $WetGrass\Rightarrow Rain$) forms a feedback loop that double-counts evidence, and a truth-functional system cannot explain away — seeing the sprinkler on should lower belief in rain, but forward chaining only raises it. The certainty-factors model of the MYCIN medical system worked only by restricting rule sets to be purely diagnostic or purely causal, singly connected, with evidence entered at the roots; outside those bounds it over-counted, and Bayesian networks displaced it.

Dempster–Shafer theory targets the distinction between uncertainty and ignorance. A fair coin and a coin of unknown bias both give $P(heads)=0.5$, yet the two states of knowledge differ. Rather than a probability, Dempster–Shafer computes a belief function $Bel(X)$: the probability that the evidence supports$X$. It assigns masses to sets of possible worlds (events), summing to $1$, and $Bel(A)$ is the total mass of events that entail $A$. With no evidence about the coin, $Bel(Heads)=0$ and $Bel(\neg Heads)=0$ — a skeptical stance. An expert $90\%$ sure the coin is fair gives $Bel(Heads)=0.9\times 0.5=0.45$ and likewise for tails, leaving a $10$-point gap: the interval between $Bel(A)$ and $1-Bel(\neg A)$ bounds the probability of $A$. The gap is also the theory's difficulty — with belief uncommitted over an interval, a decision problem can be posed that the system cannot resolve, since the meaning of masses and their link to utility remains unsettled.

A Bayesian would say no new formalism is needed: model the coin's $Bias$ (a number in $[0,1]$) with a prior reflecting its magician's-pocket provenance and a conditional $P(Flip\mid Bias)$. If the prior is symmetric about $0.5$ the predicted $P(heads)=0.5$, the same number as for a coin believed fair — but the two are not treated identically, because the difference shows up in how the posterior over $Bias$ moves after evidence. Three heads barely budge a strong belief in fairness, but shift a magician's-pocket coin sharply toward biased. Ignorance, in the Bayesian view, is expressed by how beliefs would change under future evidence, not by a gap.

Fuzzy logic addresses a different thing entirely: vagueness, not uncertainty. Nate is tall at $5^{\prime }10^{\prime \prime }$ is not something we are uncertain about — we know his height — the predicate $Tall$ simply has no sharp boundary. Fuzzy set theory gives $Tall(Nate)$ a truth value in $[0,1]$, and fuzzy logic combines them truth-functionally: $T(A\wedge B)=\min (T(A),T(B))$, $T(A\vee B)=\max (T(A),T(B))$, $T(\neg A)=1-T(A)$. Being truth-functional, it stumbles the same way rule-based systems do — $T(Tall\wedge Heavy)=0.4$ looks reasonable, but $T(Tall\wedge \neg Tall)=0.4$ does not, because a truth-functional rule cannot see the anticorrelation between $Tall$ and $\neg Tall$. Fuzzy control, which maps real-valued inputs to outputs by fuzzy rules, succeeds commercially (transmissions, cameras, shavers), but critics argue the success owes to small rule bases and tunable parameters, the fuzzy operators being incidental to providing a concise smoothly interpolated function.

The common point is probability's discipline — carrying dependences and the provenance of evidence rather than collapsing everything into one local number. The truth-functional shortcuts throw that away, and keeping it is what lets a Bayesian model do the work Dempster–Shafer and fuzzy logic each aim at from one side.

Structure is the whole story

One idea recurs throughout. Writing down the direct dependences of a domain as a graph fixes its conditional independences; those independences factor the joint into small local tables, which is what makes the model both compact to store and fast to reason over. Exact inference stays linear precisely when the graph is sparse enough to be a polytree; when it is not, the same structure guides the sampling that approximates the answer. The identical assumption — that the world's dependences are local, so a graph of them stands in for a full joint — reappears in deep learning's structured probabilistic models, where the graph organizes a distribution over thousands of variables that no table could hold. The next lesson lets the network run in time, unrolling the same factorization across a sequence of steps; after that, we attach payoffs and choose actions in making decisions.