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
- 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
- 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.
- 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)