Importance Sampling Algorithm

See: Sampling Algorithm, Stratified Sampling Algorithm, EPIS-BN Algorithm, AISBN Algorithm.

---

---

References

2012

• http://en.wikipedia.org/wiki/Importance_sampling
  • QUOTE:In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution rather than the distribution of interest. It is related to Umbrella sampling in computational physics. Depending on the application, the term may refer to the process of sampling from this alternative distribution, the process of inference, or both.

2002

• (Yuan et al., 2002) ⇒ Changhe Yuan, and Marek J. Druzdzel. (2002). “An Importance Sampling Algorithm based on Evidence Pre-propagation.” In: Proceedings of the Nineteenth conference on Uncertainty in Artificial Intelligence.
  • QUOTE:Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. To address this problem, we propose the Evidence Pre-propagation Importance Sampling algorithm (EPIS-BN), an importance sampling algorithm that computes an approximate importance function using two techniques: loopy belief propagation [19, 25] and ε-cutoff heuristic [2]. We tested the performance of EPIS-BN on three large real Bayesian networks: ANDES [3], CPCS [21], and PATHFINDER[11]. We observed that on each of these networks the EPIS-BN algorithm outperforms AISBN [2], the current state of the art algorithm, while avoiding its costly learning stage.

---