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/