Exact inference is NP-hard, so approximate methods are best option for loopy BN

Stochastic simulation in BN

Belief network defines “generative model”, so we can easily draw samples from the joint distribution.

However, it is hard to draw samples from posterior distribution

Rejection sampling

• Generate N joint samples from joint distribution.
• Count number of samples N(Q=q, E=e) and N(E=e)
• Estimate P(Q=q|E=e) ~ N(Q=q, E=e) / N(E=e)

This will converge as N reaches infinity, but it is very inefficient:

• Discards all samples without E=e
• Takes large number of samples for queries with unlikely evidence

Likelihood weighting

• Instantiate evidence nodes instead of sampling them
• Weight each sample using CPTs
  • For evidence nodes in numerator and denominator. P(E=e|Parent(E))

This will also converge as N reaches infinity.
Likelihood weighting is much faster than Rejection sampling since all samples are used. However, it is still slow for rare events.

MCMC Simulation

• Fix evidence nodes to observed values
• Initialize non-evidence nodes to any values
• Repeat N times:
  • Pick non-evidence nodes at random
  • Use Bayes rule to compute P(X=x|Bx) where Bx is fixed to current values
  • Resample X~P(X=x|Bx)

MCMC simulation is about reformulating the sampling as a Markov Chain between samples… This term is rather ambiguous, but the following link seems helpful!

LW sample non-evidence nodes from P(X|Parent(X))
MCMC sample non-evidence nodes from P(X|Bx)

Good material

https://courses.csail.mit.edu/6.034s/handouts/spring12/chapter14_mod_b.pdf
https://students.ics.uci.edu/~stewarm1/doku.php?id=sampling
https://ermongroup.github.io/cs228-notes/inference/sampling/