Probabilistic Inference¶

Introduction¶

A probabilistic graphical model (see Probabilistic Structures Guide) describes a joint distribution compactly, as a product of small factors. Inference answers questions about that distribution: how likely is a cause given an observed effect? How likely is an observation sequence? Which hidden sequence best explains it?

The difficulty is size. With \(n\) binary variables the joint distribution has \(2^n\) entries; summing over all of them is out of reach beyond a few dozen variables. Every algorithm on this page exploits the factorization to avoid that enumeration, and every one of them is an instance of dynamic programming (see Design Paradigms).

Algorithm	Question	Model
`variable_elimination`	\(P(Q \mid e)\) for chosen query variables	Bayesian network, Markov random field
`belief_propagation`	\(P(X \mid e)\) for every variable	Bayesian network, Markov random field
`forward`	\(P(o_{1:T})\) and \(P(S_t \mid o_{1:t})\)	hidden Markov model
`viterbi`	\(\arg\max_{s_{1:T}} P(s_{1:T}, o_{1:T})\)	hidden Markov model

Running Example: the Alarm Network¶

        graph TD
    B((Burglary<br/>0.001)) --> A((Alarm))
    E((Earthquake<br/>0.002)) --> A
    A --> J((JohnCalls))
    A --> M((MaryCalls))

Probability that the alarm rings¶
Burglary, Earthquake	\(P(A = \text{true} \mid B, E)\)
true, true	0.95
true, false	0.94
false, true	0.29
false, false	0.001

John calls with probability 0.90 when the alarm rings and 0.05 otherwise; Mary with probability 0.70 and 0.01.

Both neighbours call. How likely is a burglary?

Variable Elimination¶

Idea¶

By definition, with the hidden variables \(E\) and \(A\) summed out:

\[P(B \mid j, m) \;\propto\; \sum_{e} \sum_{a} P(B)\, P(e)\, P(a \mid B, e)\, P(j \mid a)\, P(m \mid a)\]

Enumerating the double sum repeats work: for each value of \(B\) it recomputes every product. Factors that do not mention a summed variable can be pulled out of that sum:

\[P(B \mid j, m) \;\propto\; P(B) \sum_{a} P(j \mid a)\, P(m \mid a) \underbrace{\sum_{e} P(e)\, P(a \mid B, e)}_{\tau_1(a,\,B)}\]

Summing out \(e\) first produces a new table \(\tau_1(a, B)\), computed once; summing out \(a\) then produces \(\tau_2(B)\). The normalized result is \(P(B = \text{true} \mid j, m) \approx 0.284\).

Algorithm¶

tables <- factors of the model, restricted to the evidence
for each hidden variable h (elimination order):
    combine <- tables whose scope contains h
    tables  <- (tables - combine) + { sum_h product(combine) }
return normalize(product(tables))

Each intermediate table is a stored subproblem: this is dynamic programming over the factors.

Cost and Elimination Order¶

Eliminating a variable builds a table over the union of the scopes it touches. With domains of size \(d\) and a largest intermediate scope of \(w\) variables:

\[T = O(n \cdot d^{\,w})\]

\(w\) depends on the order: eliminating the hub of a star graph first creates a table over all its neighbours, eliminating the leaves first keeps every table small. Finding the best order is NP-hard; sds uses the greedy rule “eliminate the variable that builds the smallest table”, which works well in practice. On tree-shaped models \(w\) never exceeds the largest factor, and inference is linear in the model size.

Belief Propagation¶

Messages on the Factor Graph¶

The factor graph connects each factor to the variables of its scope. Belief propagation sends two kinds of messages along its edges:

\[ \begin{align}\begin{aligned}\mu_{x \to f}(x) = \prod_{g \in N(x) \setminus \{f\}} \mu_{g \to x}(x)\\\mu_{f \to x}(x) = \sum_{\mathbf{x}_f \setminus x} f(\mathbf{x}_f) \prod_{y \in N(f) \setminus \{x\}} \mu_{y \to f}(y)\end{aligned}\end{align} \]

and every marginal is the normalized product of the messages a variable receives:

\[P(x \mid e) \;\propto\; \prod_{f \in N(x)} \mu_{f \to x}(x)\]

        graph LR
    fB[P B] --- B((B))
    fE[P E] --- E((E))
    B --- fA[P A given B,E]
    E --- fA
    fA --- A((A))
    A --- fJ[P J given A]
    A --- fM[P M given A]
    fJ --- J((J))
    fM --- M((M))

Why It Is Exact on Trees¶

On a tree, the message \(\mu_{f \to x}\) summarizes exactly the part of the model on \(f\)’s side of the edge \(f - x\): removing that edge splits the tree in two, and the recursion above is variable elimination performed along that split. Each message is therefore computed once per edge and direction, and all marginals come out exact for the price of two passes.

When the Graph Has Cycles¶

On a factor graph with cycles the same updates can still be iterated, but information comes back around each cycle and is counted more than once. This loopy belief propagation often converges to good approximations, but not to exact marginals. On the sprinkler network, whose four variables form a cycle (Cloudy → Sprinkler → WetGrass ← Rain ← Cloudy), it estimates \(P(\text{Rain} \mid \text{WetGrass}) \approx 0.78\) where the exact answer is about 0.71. belief_propagation() emits a RuntimeWarning if the messages do not settle; use variable_elimination when an exact answer matters.

Hidden Markov Models¶

        graph LR
    S1((Rain₁)) --> S2((Rain₂)) --> S3((Rain₃))
    S1 --> O1[Umbrella₁]
    S2 --> O2[Umbrella₂]
    S3 --> O3[Umbrella₃]

The umbrella world: each day it rains or not (hidden), and the director arrives with an umbrella or not (observed). Rain persists with probability 0.7; an umbrella is seen on 90 % of rainy days and 20 % of dry ones.

Forward: Evaluation and Filtering¶

Summing \(P(s_{1:T}, o_{1:T})\) over the \(|S|^T\) state sequences is exponential. The forward variable \(\alpha_t(s) = P(o_{1:t}, S_t = s)\) satisfies a recurrence on \(t\):

\[ \begin{align}\begin{aligned}\alpha_1(s) = \pi(s)\, e(o_1 \mid s), \qquad \alpha_t(s) = e(o_t \mid s) \sum_{r} \alpha_{t-1}(r)\, T(s \mid r)\\P(o_{1:T}) = \sum_{s} \alpha_T(s)\end{aligned}\end{align} \]

There are \(T \cdot |S|\) values, each costing \(O(|S|)\):

\[T_{\text{forward}} = O(T\, |S|^2)\]

The \(\alpha_t\) shrink exponentially with \(t\). forward() divides them by their sum \(c_t\) at every step; the rescaled values are the filtered distributions \(P(S_t \mid o_{1:t})\), and

\[\log P(o_{1:T}) = \sum_{t=1}^{T} \log c_t\]

stays finite for any length. After two umbrella days, \(P(\text{Rain}_2 \mid u_1, u_2) = 0.883\).

Viterbi: Decoding¶

Replacing the sum by a maximum gives the probability of the best path ending in each state, plus a pointer to its best predecessor:

\[\delta_t(s) = e(o_t \mid s)\, \max_{r}\; \delta_{t-1}(r)\, T(s \mid r), \qquad \psi_t(s) = \arg\max_{r}\; \delta_{t-1}(r)\, T(s \mid r)\]

The best final state is \(\arg\max_s \delta_T(s)\); following \(\psi\) backwards rebuilds the path. Optimal substructure makes this correct: the best path to \(s\) at time \(t\) extends the best path to some \(r\) at time \(t - 1\). viterbi() works on logarithms, so products become sums and long sequences do not underflow.

        graph LR
    R1((rain)) --> R2((rain)) --> D3((sun)) --> R4((rain)) --> R5((rain))

%% Umbrella observed: yes, yes, no, yes, yes

Warning

The most likely path is not the sequence of individually most likely states. Picking the best state at each step separately can yield a sequence whose transitions are improbable, or impossible, as a whole.

Summary¶

Algorithm	Recurrence over	Time	Exact
`variable_elimination`	factors, one hidden variable at a time	\(O(n\, d^{\,w})\)	yes
`belief_propagation`	messages on the factor graph	\(O(I \sum_f \|f\|)\) per run	on trees
`forward`	time steps, sum	\(O(T\, \|S\|^2)\)	yes
`viterbi`	time steps, max	\(O(T\, \|S\|^2)\)	yes

References¶

D. Koller and N. Friedman, Probabilistic Graphical Models, chapters 9 (variable elimination) and 10–11 (belief propagation); the open Stanford CS228 notes follow the same path — https://ermongroup.github.io/cs228-notes/
S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, chapters 13–14 (the alarm network, the umbrella world).
D. Jurafsky and J. H. Martin, Speech and Language Processing (3rd ed. draft, free online), appendix Hidden Markov Models — https://web.stanford.edu/~jurafsky/slp3/
CLRS, chapter 15 (dynamic programming).