Intelligent Systems Lecture Notes

26 October 2011 • Probabilistic Inference

---

Outline

• Factors
• Evidence
• Variable elimination.
• Stochastic simulation.
• Sampling
  • Forward, rejection, and importance.
• Particle Filtering

Belief Network Inference

• Conditional independence is not stronger than exponential growth.
  • Computing belief-net values is NP hard.
• Alternative computing methods include:
  1. Eliminate non-observed, non-query variables.
  2. Generate random cases to simulate behavior to generate statistics.
• These are approximate methods.

Variable Elimination

• The query Pr(H | E₁, \(\ldots\), E_n) may not include all the random variables in a belief net.

Factors

• A factor is a function from random variables to reals.
  • f(X₁, \(\ldots\), X_j)
• In essence, the factor

  f(X₁, X₂, \(\ldots\), X_j)

• represents the conditional probability

  Pr(X₁ | X₂, \(\ldots\), X_j)

Partial Evaluation

• Some of the variables in a factor may have values assigned.
  • f(X₁ = v₁, \(\ldots\), X_j)
  • f(X₁ = v₁, \(\ldots\), X_j = v_j)
• Alternative notation:
  • f(X₁, \(\ldots\), X_j)_{X1 = v1}
  • f(X₁, \(\ldots\), X_j)_{X1 = v1, \(\ldots\), Xj = vj}

Factor Examples

f(X, Y, Z) X Y Z val t t t 0.1 t t f 0.9 t f t 0.2 t f f 0.8 f t t 0.4 f t f 0.6 f f t 0.3 f f f 0.7		f(X = t, Y, Z) Y Z val t t 0.1 t f 0.9 f t 0.2 f f 0.8
		f(X = t, Y, Z = f) Y val t 0.9 f 0.8
	f(X = t, Y = f, Z = f) = 0.8

Factor Product

• The product of factors f₁(X, Y) and f₂(Y, Z), where Y are the variables in common, is the factor (f₁ \(\times\) f₂)(X, Y, Z) defined by:

  (f₁ \(\times\) f₂)(X, Y, Z) = f₁(X, Y)f₂(Y, Z)

• For example:

  f₁(X₁, Y₁, Y₂)
  f₂(Z₁, Z₂, Y₁, Y₂)
  (f₂ \(\times\) f₂)(X₁, Y₁, Y₂, Z₁, Z₂, )

Factor Product Example

f1(A, B) A B val t t 0.1 t f 0.9 f t 0.2 f f 0.8		(f1 × f2)(A, B, C) A B C val t t t 0.03 t t f 0.07 t f t 0.54 t f f 0.36 f t t 0.06 f t f 0.14 f f t 0.48 f f f 0.32		f1(t, f)f2(f, f) = 0.9 \(\cdot\) 0.4 = 0.36 = (f1 \(\times\) f2)(t, f, f)
f2(B, C) B C val t t 0.3 t f 0.7 f t 0.6 f f 0.4

Summing Out Variables

• A variable X₁ with domain { x₁, …, x_k }, can be summed out from factor f(X₁, …, X_n) with the equation

  

• resulting in a factor on X₂, … X_n.

Summing Out Example

f3 A B C f3() t t t 0.03 t t f 0.07 t f t 0.54 t f f 0.36 f t t 0.06 f t f 0.14 f f t 0.48 f f f 0.32

\(\sum _ B\)f3 A C val t t 0.57 t f 0.43 f t 0.54 f f 0.46

Evidence

• The posterior probability of Z given evidence Y₁ = v₁, \(\wedge \cdots \wedge\) Y_j = v_j is

  

• The computation reduces to the probability of Pr(Z, Y₁ = v₁, …, Y_j = v_j).

Conjunction Probability

• Given belief network variables X₁, …, X_n sum out the variables Z₁, …, Z_k = { X₁, …, X_n } - { Z } - { Y₁, …, Y_j }.

  

• Z₁, …, Z_k is the elimination ordering.

Sum Products

• Belief network computation reduces to computing sum products.
• What’s the best way to compute ab + ac efficiently?
  • Distribute out a to get a(b + c).
• What’s the best way to compute

  

  • Distribute out factors not involving Z₁.

Variable Elimination

• To compute Pr(Z | Y₁ = v₁ \(\wedge \cdots \wedge\) Y_j = v_j):
  • Construct a factor for each conditional probability.
  • Set the observed variables to their observed values.
  • Sum out each of the other variables.
  • Multiply the remaining factors.
  • Normalize by \(\sum_Z\) f(Z).

Variable Summing Out.

• To sum out a variable Z_j from a product f₁, …, f_k of factors:
  • Partition the factors into
    • Those not containing Z_j, f₁, …, f_i.
    • Those containing Z_j, f_{i + 1}, …, f_k.

Variable Summing Out..

• We know

  

• Explicitly construct a representation of the rightmost factor.
• Replace the factors f_{i + 1}, …, f_k by the new factor.

Example

Stochastic Simulation

• Get probabilities from samples.
  • Observe a random variable X m times.
  • Value x_i occurs n_i times.
  • n_i occurs with probability n_i/m.
• Sampling a posterior probability could lead to posterior probability estimates.

Generating Distribution Samples

• For a variable X with a discrete domain or a (one-dimensional) real domain:
  • Totally order the values in dom(X).
  • Generate the cumulative probability distribution

    cpd(x) = Pr(X \(\leq\) x).

  • Uniformly select y from [0..1].
  • Determine sample x such that cpd(x) = y.
  • Repeat last two steps as needed.

Cumulative Distribution

Forward Sampling

• Sample the variables one at a time; sample parents of X before you sample X.
• Given values for the parents of X, sample from the probability of X given its parents.

Rejection Sampling

• Estimate the posterior probability given evidence

  Y₁ = v₁ \(\wedge \cdots \wedge\) Y_j = v_j

• Reject samples assigning Y_i to a value other than v_i.
• Non-rejected samples are distributed by the posterior probability:

  

• considering only samples consistent with observations.

Example

Ta Fi Al Sm Le Re s1 t f t f — — × s2 f t f t f f × s3 f t t t t t √ s4 t t t t t t √ \(\vdots\) s1000 f f f f — — ×

Importance Sampling.

• Samples have weights: a real number associated with each sample that takes evidence into account.
• Probability of a proposition is weighted average of samples:

  

• If we can compute Pr(evidence | sample) we can weight the (partial) sample by this value.

Importance Sampling..

• Mix exact inference with sampling: don’t sample all of the variables, but weight each sample appropriately.
• Sample according to a proposal distribution, as long as the samples are weighted appropriately.

Pr(ta | sm, re) Example

Ta Fi Al Le Weight s1 t f t f 0.01 × 0.01 s2 f t f f 0.9 × 0.01 s3 f t t t 0.9 × 0.75 s4 t t t t 0.9 × 0.75 \(\vdots\) s1000 f f f f 0.01 × 0.75

Pr(sm | fi) = 0.9 Pr(sm | \(\neg\)fi) = 0.01

Pr(re | le) = 0.75 Pr(re | \(\neg\)le) = 0.01

Particle Filtering.

• Given evidence e₁ \(\wedge\) e₂

  	Pr(e1 \(\wedge\) e2 | sample)
  =	Pr(e1 | sample)Pr(e2 | e1 \(\wedge\) sample)

• After computing Pr(e₁ | sample), we may know the sample will have an extremely small probability.
• Idea: we use lots of samples: “particles.” A particle is a sample on some of the variables.

Particle Filtering..

• Resample the particle set using Pr(e₁ | sample).
• Some particles may be duplicated, some may be removed.

Summary

---

This page last modified on 2011 October 26.