---
title: "Bayesian Networks: Inference and Relational Models"
module: Uncertainty
moduleNumber: 4
lessonNumber: 4
order: 404
summary: >
  When exact inference is intractable, sampling estimates the posterior instead:
  prior and rejection sampling, likelihood weighting, and Gibbs/MCMC, whose error
  shrinks as one over the square root of the sample count. The same graphical idea
  then lifts from a fixed set of variables to whole populations — relational and
  open-universe probability models write dependencies once and unroll them over
  objects — and we close by placing probability against the rule-based, Dempster–Shafer,
  and fuzzy alternatives it displaced.
topics: [Uncertainty]
sources:
  - book: AIMA
    ref: "Ch. 14 — Probabilistic Reasoning; §14.5 Approximate Inference in Bayesian Networks"
  - book: AIMA
    ref: "§14.6 Relational and First-Order Probability Models; §14.7 Other Approaches to Uncertain Reasoning"
---

This builds on [Bayesian Networks](/artificial-intelligence/uncertainty/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}$.[^aima-mc]

### 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.[^aima-lw]

```algorithm
caption: $\textsc{Weighted-Sample}(bn, \mathbf{e})$ — one likelihood-weighted sample and its weight
input: $bn$, a Bayesian network; $\mathbf{e}$, the fixed evidence
$w \gets 1$
$\mathbf{x} \gets$ an event with the evidence variables set from $\mathbf{e}$
for each variable $X_i$ in $X_1, \ldots, X_n$ do
  if $X_i$ is an evidence variable with value $x_i$ in $\mathbf{e}$ then
    $w \gets w \cdot P(x_i \mid \text{parents}(X_i))$
  else
    $\mathbf{x}[i] \gets$ a random sample from $\mathbf{P}(X_i \mid \text{parents}(X_i))$
return $\mathbf{x}$, $w$
```

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.[^aima-gibbs]

$$
% caption: Gibbs sampling as a walk over complete states. Evidence variables
% (shaded) stay fixed; at each step one nonevidence variable is resampled given
% its Markov blanket, moving to a neighboring state. The long-run fraction of time
% the walk spends in each state converges to that state's posterior probability.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={draw, minimum width=17mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (s1) at (0,0)    {C=t, R=f\\ (f\/ixed: S,W)};
  \node[st] (s2) at (3.2,0.9){C=f, R=f};
  \node[st] (s3) at (6.4,0)  {C=f, R=t};
  \node[st, draw=acc, text=acc] (s4) at (9.4,0.9) {C=t, R=t};
  \draw[->, acc, thick] (s1) to[bend left=18] node[midway, above, font=\scriptsize] {f\/lip C} (s2);
  \draw[->, acc, thick] (s2) to[bend left=18] node[midway, above, font=\scriptsize] {f\/lip R} (s3);
  \draw[->, acc, thick] (s3) to[bend left=18] node[midway, above, font=\scriptsize] {f\/lip C} (s4);
  \node[anchor=north, text=black, font=\scriptsize] at (4.7,-1.0) {each step resamples one variable given its Markov-blanket};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Gibbs-Ask}(X, \mathbf{e}, bn, N)$ — approximate inference by Gibbs sampling
input: $X$, the query variable; $\mathbf{e}$, the evidence; $bn$; $N$, sample count
$\mathbf{N} \gets$ a vector of zero counts, one per value of $X$
$\mathbf{Z} \gets$ the nonevidence variables of $bn$
$\mathbf{x} \gets$ the current state, evidence set from $\mathbf{e}$, rest random
for $j = 1$ to $N$ do
  for each $Z_i$ in $\mathbf{Z}$ do
    set $Z_i$ in $\mathbf{x}$ by sampling from $\mathbf{P}(Z_i \mid mb(Z_i))$
    $\mathbf{N}[x] \gets \mathbf{N}[x] + 1$ // $x$ is the value of $X$ in $\mathbf{x}$
return $\textsc{Normalize}(\mathbf{N})$
```

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 \,\|\, 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.

$$
% caption: Three routes to a posterior. Exact inference (variable elimination /
% junction tree) is exponential in the treewidth. Sampling (MCMC, likelihood
% weighting) trades exactness for noisy estimates that improve with more samples.
% Variational inference optimizes a tractable $q$ to approximate the posterior
% deterministically. Loopy BP sits between exact and approximate: exact rules run on
% a loopy graph.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  m/.style={draw, minimum width=30mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{accent}{HTML}{2348F2}
  \node[m, draw=accent, text=accent] (post) at (0,0) {posterior\\P(X given e)};
  \node[m] (exact) at (-4.6,-2.4) {exact:\\elimination,\\junction tree};
  \node[m] (samp) at (0,-2.4) {sampling:\\MCMC,\\lik. weighting};
  \node[m] (vi) at (4.6,-2.4) {variational:\\optimize q,\\max ELBO};
  \draw[->, thick] (exact) -- (post);
  \draw[->, thick] (samp) -- (post);
  \draw[->, accent, thick] (vi) -- (post);
  \node[font=\scriptsize, text=black, anchor=north] at (-4.6,-3.15) {cost: exp(treewidth)};
  \node[font=\scriptsize, text=black, anchor=north] at (0,-3.15) {error: 1 / sqrt(N)};
  \node[font=\scriptsize, text=black, anchor=north] at (4.6,-3.15) {biased, deterministic};
\end{tikzpicture}
$$

## 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.[^aima-rpm]

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.

$$
% caption: The book-recommendation Bayes net for two customers and two books. Each
% $Rec(c, b)$ node depends on that customer's honesty and kindness and that book's
% quality; the structure repeats identically for every customer-book pair, which is
% what a first-order language captures in one line.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  v/.style={draw, ellipse, minimum width=16mm, minimum height=6.5mm, inner sep=1pt, font=\scriptsize},
  r/.style={draw, ellipse, minimum width=18mm, minimum height=6.5mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[v] (h1) at (0,3.0) {Honest(C1)};
  \node[v] (k1) at (0,1.8) {Kind(C1)};
  \node[v] (h2) at (0,0.4) {Honest(C2)};
  \node[v] (k2) at (0,-0.8) {Kind(C2)};
  \node[v] (q1) at (8.6,3.0) {Qual(B1)};
  \node[v] (q2) at (8.6,-0.8) {Qual(B2)};
  \node[r, draw=acc, text=acc] (r11) at (4.3,2.7) {Rec(C1,B1)};
  \node[r, draw=acc, text=acc] (r21) at (4.3,1.3) {Rec(C2,B1)};
  \node[r, draw=acc, text=acc] (r12) at (4.3,-0.1) {Rec(C1,B2)};
  \node[r, draw=acc, text=acc] (r22) at (4.3,-1.5) {Rec(C2,B2)};
  \draw[->] (h1) -- (r11); \draw[->] (k1) -- (r11); \draw[->] (q1) -- (r11);
  \draw[->] (h2) -- (r21); \draw[->] (k2) -- (r21); \draw[->] (q1) -- (r21);
  \draw[->] (h1) -- (r12); \draw[->] (k1) -- (r12); \draw[->] (q2) -- (r12);
  \draw[->] (h2) -- (r22); \draw[->] (k2) -- (r22); \draw[->] (q2) -- (r22);
\end{tikzpicture}
$$

### 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:[^aima-rpm]

$$
\begin{aligned}
Honest &: Customer \to \{true, false\} \\
Kindness &: Customer \to \{1,2,3,4,5\} \\
Quality &: Book \to \{1,2,3,4,5\} \\
Recommendation &: Customer \times Book \to \{1,2,3,4,5\}.
\end{aligned}
$$

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:

$$
\begin{aligned}
Honest(c) &\sim \langle 0.99, 0.01 \rangle \\
Kindness(c) &\sim \langle 0.1, 0.1, 0.2, 0.3, 0.3 \rangle \\
Quality(b) &\sim \langle 0.05, 0.2, 0.4, 0.2, 0.15 \rangle \\
Recommendation(c, b) &\sim RecCPT\big(Honest(c), Kindness(c), Quality(b)\big),
\end{aligned}
$$

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.

> **Definition (Relational probability model).** A probability model with typed
> constant, function, and predicate symbols and a dependency statement per
> function, its arguments logical variables over objects. Instantiating the
> functions over the constants yields the random variables; unrolling the
> dependencies over the constants yields an equivalent Bayesian network defining
> the joint distribution. RPMs adopt database semantics (unique names, domain
> closure) but _not_ the closed-world assumption — treating every unknown fact as
> false makes no sense under probability.

$$
% caption: An RPM template (top) unrolled over concrete objects (bottom). The
% single dependency $Rec(c, b) \sim RecCPT(Honest(c), Kind(c), Qual(b))$ generates
% one Bayes-net fragment per customer-book pair, all sharing the same CPT; adding
% objects grows the network but never the specification.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  tmpl/.style={draw, minimum width=70mm, minimum height=9mm, align=center, font=\scriptsize},
  v/.style={draw, ellipse, minimum width=14mm, minimum height=6mm, inner sep=1pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % template box
  \node[tmpl, draw=acc, text=acc] (t) at (3.4,3.4)
    {template: Rec(c, b) depends on Honest(c), Kind(c), Qual(b)};
  \node[font=\scriptsize, text=black, anchor=west] at (-1.9,2.55) {unroll over C1, C2, B1};
  \draw[->, acc, thick] (3.4,2.95) -- (3.4,2.35);
  % two instances
  \node[v] (h1) at (0.4,1.5) {Hon(C1)};
  \node[v] (k1) at (0.4,0.4) {Kind(C1)};
  \node[v] (q1) at (3.4,0.95) {Qual(B1)};
  \node[v, draw=acc, text=acc] (rc1) at (1.9,-0.7) {Rec(C1,B1)};
  \draw[->] (h1) -- (rc1); \draw[->] (k1) -- (rc1); \draw[->] (q1) -- (rc1);
  \node[v] (h2) at (6.4,1.5) {Hon(C2)};
  \node[v] (k2) at (6.4,0.4) {Kind(C2)};
  \node[v, draw=acc, text=acc] (rc2) at (5.0,-0.7) {Rec(C2,B1)};
  \draw[->] (h2) -- (rc2); \draw[->] (k2) -- (rc2); \draw[->] (q1) -- (rc2);
\end{tikzpicture}
$$

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.

$$
% caption: The generative hierarchy. A Bayesian network generates a world by
% assigning a value to one variable at a time; an RPM assigns values to whole sets
% of variables (all instantiations of a function); an OUPM additionally generates
% the existence of objects, so the number of objects is itself uncertain.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=42mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (bn) at (0,0) {Bayes net\\generates: one variable value};
  \node[box] (rpm) at (0,-1.7) {RPM\\generates: sets of variable values};
  \node[box, draw=acc, text=acc] (oupm) at (0,-3.4) {OUPM\\generates: existence of objects};
  \draw[->, thick] (bn) -- (rpm);
  \draw[->, acc, thick] (rpm) -- (oupm);
  \node[font=\scriptsize, text=black, anchor=west] at (2.5,0) {f\/inite, f\/ixed variables};
  \node[font=\scriptsize, text=black, anchor=west] at (2.5,-1.7) {f\/inite, known objects};
  \node[acc, font=\scriptsize, anchor=west] at (2.5,-3.4) {unbounded, unknown objects};
\end{tikzpicture}
$$

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$:

$$
\#LoginID(Owner = c) \sim
\begin{cases}
Exactly(1) & \text{if } Honest(c) \\
LogNormal[6.9, 2.3^2]() & \text{otherwise.}
\end{cases}
$$

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 $\varphi$ is still well defined as a sum over the worlds
where it holds,

$$
P(\varphi) = \sum_{\omega : \varphi \text{ true in } \omega} P(\omega),
$$

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.[^aima-other] 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 \lor 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 \lor B)$ depends on the events, not just their probabilities: with a fair coin,
$P(H_1 \lor H_1) = 0.5$ but $P(H_1 \lor T_1) = 1.0$ and $P(H_1 \lor 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(\lnot 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(\lnot 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.

$$
% caption: Dempster-Shafer belief for the coin from a magician's pocket, an expert
% 90 percent sure it is fair. Bel(Heads) = 0.45 and Bel(not Heads) = 0.45 leave a
% 0.10 gap of uncommitted belief; the interval [Bel(A), 1 - Bel(not A)] = [0.45,
% 0.55] bounds the probability of heads, rather than fixing it at a single number.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % the [0,1] belief line
  \draw[black, thick] (0,0) -- (10,0);
  \foreach \x/\l in {0/0, 5/0.5, 10/1} {
    \draw[black] (\x,0.12) -- (\x,-0.12);
    \node[font=\scriptsize, anchor=north, text=black] at (\x,-0.15) {\l};
  }
  % Bel(Heads) segment 0 to 4.5
  \draw[acc, line width=3pt] (0,0.35) -- (4.5,0.35);
  \node[acc, anchor=south, font=\scriptsize] at (2.25,0.4) {Bel(Heads) = 0.45};
  % gap 4.5 to 5.5
  \draw[red, line width=3pt] (4.5,0.35) -- (5.5,0.35);
  \node[red, anchor=south, font=\scriptsize] at (5.0,0.9) {gap 0.10};
  \draw[red, ->] (5.0,0.85) -- (5.0,0.5);
  % Bel(not Heads) segment 5.5 to 10
  \draw[black, line width=3pt] (5.5,0.35) -- (10,0.35);
  \node[anchor=south, font=\scriptsize] at (7.75,0.4) {Bel(not Heads) = 0.45};
  \node[font=\scriptsize, text=black, anchor=north] at (5.0,-0.7) {probability of heads bounded in [0.45, 0.55]};
\end{tikzpicture}
$$

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'10''$ 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 \land B) = \min(T(A), T(B))$, $T(A \lor B) = \max(T(A),
T(B))$, $T(\lnot A) = 1 - T(A)$. Being truth-functional, it stumbles the same way
rule-based systems do — $T(Tall \land Heavy) = 0.4$ looks reasonable, but $T(Tall
\land \lnot Tall) = 0.4$ does not, because a truth-functional rule cannot see the
anticorrelation between $Tall$ and $\lnot 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.

$$
% caption: The two axes these formalisms address. Probability and Dempster-Shafer
% handle uncertainty (is the proposition true?); fuzzy logic handles vagueness (is
% the predicate sharply defined?). The axes are orthogonal — a proposition can be
% certainly-known yet vague, or sharply-defined yet uncertain.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (7.2,0) node[right, black, font=\scriptsize] {uncertainty};
  \draw[->, black] (0,0) -- (0,4.6) node[above, black, font=\scriptsize] {vagueness};
  % probability: high uncertainty, low vagueness
  \node[acc, anchor=center, align=center, font=\scriptsize] at (5.0,0.9)
    {probability,\\Dempster-Shafer};
  \fill[acc] (5.0,0.35) circle (1.8pt);
  % fuzzy: low uncertainty, high vagueness
  \node[red, anchor=center, align=center, font=\scriptsize] at (1.7,3.6)
    {fuzzy logic\\(vague predicates)};
  \fill[red] (1.7,3.05) circle (1.8pt);
  % logic: low both
  \node[black, anchor=center, font=\scriptsize] at (1.4,0.55) {logic};
  \fill[black] (0.6,0.3) circle (1.8pt);
  \node[font=\scriptsize, text=black, anchor=north] at (3.6,-0.35) {the two are orthogonal issues};
\end{tikzpicture}
$$

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](/deep-learning/probabilistic-methods/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](/artificial-intelligence/uncertainty/reasoning-over-time), unrolling the
same factorization across a sequence of steps; after that, we attach payoffs and
choose actions in
[making decisions](/artificial-intelligence/uncertainty/making-decisions).

[^aima-mc]: **Russell & Norvig**, _AIMA_, §14.5, §14.5.1, Figures 14.13–14.14 — Monte Carlo / randomized sampling, prior sampling ($\textsc{Prior-Sample}$) generating events in topological order, and rejection sampling for evidence with its exponential rejection rate; error falling as $1/\sqrt{n}$.
[^aima-lw]: **Russell & Norvig**, _AIMA_, §14.5.1, Figure 14.15 — likelihood weighting as importance sampling: fixing evidence, sampling nonevidence variables, weighting by the product of evidence likelihoods $\prod_i P(e_i \mid parents(E_i))$, consistency of the weighted estimate, and degradation when evidence occurs late in the ordering.
[^aima-gibbs]: **Russell & Norvig**, _AIMA_, §14.5.2, Figure 14.16 — Markov chain Monte Carlo and Gibbs sampling: resampling each nonevidence variable from its Markov blanket $\mathbf{P}(X_i \mid mb(X_i))$, the Markov chain whose stationary distribution is the posterior, ergodicity, and detailed balance.
[^aima-rpm]: **Russell & Norvig**, _AIMA_, §14.6 — Relational and First-Order Probability Models: the propositional limit of Bayesian networks, the book-recommendation example (Figure 14.17), possible worlds and Equation (14.13) $P(\varphi) = \sum_{\omega : \varphi} P(\omega)$, RPMs with type signatures and shared dependencies (§14.6.2), unrolling, context-specific independence, relational uncertainty (the $Author(b)$ multiplexer, Figure 14.19), lifted inference, and open-universe models (§14.6.3) with number statements, origin functions, existence/identity uncertainty, sibyl attacks, and merge/split MCMC.
[^aima-other]: **Russell & Norvig**, _AIMA_, §14.7 — Other Approaches to Uncertain Reasoning: rule-based methods and the failure of locality, detachment, and truth-functionality (certainty factors and MYCIN, §14.7.1); Dempster–Shafer theory with belief functions, masses, and the belief gap (§14.7.2); and fuzzy set theory / fuzzy logic / fuzzy control as a treatment of vagueness rather than uncertainty (§14.7.3).