Probabilistic Inference
4.1 Bayesian Nets: Exact Inference
4.1.1 Inference by Enumeration
Join up the whole joint distribution before you sum out the hidden variables.
4.1.2 Variable Elimination
- Interleave joining and marginalizing.
- Still NP-hard, but usually much faster than inference by enumeration.
- A polytree is a directed graph with no undirected cycles. For poly-trees you can always find an ordering that is efficient.
4.2 Bayesian Nets: Approximate Inference
4.2.1 Prior Sampling
- Ignore evidence. Sample from the joint probability.
- Do inference by counting the right samples.
4.2.2 Rejection Sampling
RejectionSample(network, evidence):
x = {}
for X_i in topological_order(network):
x[X_i] ~ P(X_i | sampled values of Parents(X_i))
if X_i in evidence and x[X_i] != evidence[X_i]:
return REJECT
return x- Repeat and estimate conditional probabilities using only accepted samples.
- Hopelessly expensive if \(P(e)\) is small.
4.2.3 Likelihood Weighting
Fix evidence values and weight each sample by the product of their conditional probabilities.
LikelihoodWeighting(X, evidence, network, N):
W = {v: 0 for v in domain(X)}
for j = 1 to N:
x, w = WeightedSample(network, evidence)
W[x[X]] += w
return normalize(W)
WeightedSample(network, evidence):
x, w = {}, 1
for X_i in topological_order(network):
parents = assigned values of Parents(X_i) in x
if X_i in evidence:
x[X_i] = evidence[X_i]
w *= P(X_i = x[X_i] | parents)
else:
x[X_i] ~ P(X_i | parents)
return x, w- Normalize the weighted counts to estimate \(P(X\mid e)\).
- Degradation in performance as the number of evidence variables increases.
4.2.4 Gibbs Sampling
Keep a complete assignment (the network state), fix evidence, and repeatedly resample one non-evidence variable at a time.
GibbsSampling(X, evidence, network, N):
counts = {v: 0 for v in domain(X)}
Z = non-evidence variables in network
x = copy(evidence)
initialize x[Z] to a valid random assignment
for j = 1 to N:
for Z_i in Z:
x[Z_i] ~ P(Z_i | current values of MB(Z_i) in x)
counts[x[X]] += 1
return normalize(counts)- Markov blanket: Parents, children, and the children’s other parents.
- Rationale: Updates use both parent and child information, allowing evidence to influence upstream and downstream variables through repeated updates.
- Monte Carlo uses random samples for estimation; MCMC generates correlated samples through a Markov chain.
- Gibbs sampling is an MCMC method. Each conditional update is a special Metropolis–Hastings step with acceptance probability 1.
4.3 Probability Reasoning over Time
4.3.1 Markov Models
- State: The value of \(X_t\) at time \(t\).
- Parameters: Initial distribution \(P(X_1)\) and transition probabilities \(P(X_t\mid X_{t-1})\).
- First-order Markov property: Past and future are conditionally independent given the present:
\[ P(X_t\mid X_1,\ldots,X_{t-1})=P(X_t\mid X_{t-1}). \]
4.3.1.1 Stationary Distribution
A distribution \(P_\infty\) unchanged by a transition. If the chain converges, its limiting distribution is stationary:
\[ P_\infty(x')=\sum_x P(x'\mid x)P_\infty(x). \]
4.3.3 Dynamic Bayes Nets (DBNs)
- We want to track multiple variables over time, using multiple sources of evidence.
- Repeat a fixed Bayes net structure at each time.
- Variables from time \(t\) can condition on those from \(t-1\).
4.3.4 Most Likely Explanation
State trellis: Graph of states and transitions over time.
4.3.4.1 Forward Algorithm (Sum)
\[ \begin{aligned} f_t[x_t] &= P(x_t,e_{1:t}) \\ &= P(e_t\mid x_t)\sum_{x_{t-1}}P(x_t\mid x_{t-1})f_{t-1}[x_{t-1}]. \end{aligned} \]
4.3.4.2 Viterbi Algorithm (Max)
\[ \begin{aligned} m_t[x_t] &= \max_{x_{1:t-1}}P(x_{1:t-1},x_t,e_{1:t}) \\ &= P(e_t\mid x_t)\max_{x_{t-1}}P(x_t\mid x_{t-1})m_{t-1}[x_{t-1}]. \end{aligned} \]