AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks Stochastic sampling algorithms, while an attractive alternative to exact algorithms in very large Bayesian network models, have been observed to perform poorly in evidential reasoning with extremely unlikely evidence. To address this problem, we propose an adaptive importance sampling algorithm, AIS-BN, that shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Three sources of this performance improvement are (1) two heuristics for initialization of the importance function that are based on the theoretical properties of importance sampling in finite-dimensional integrals and the structural advantages of Bayesian networks, (2) a smooth learning method for the importance function, and (3) a dynamic weighting function for combining samples from different stages of the algorithm. par We tested the performance of the AIS-BN algorithm along with two state of the art general purpose sampling algorithms, likelihood weighting and self-importance sampling. We used in our tests three large real Bayesian network models available to the scientific community: the CPCS network, the PathFinder network, and the ANDES network, with evidence as unlikely as $10^-41$. While the AIS-BN algorithm always performed better than the other two algorithms, in the majority of the test cases it achieved orders of magnitude improvement in precision of the results. Improvement in speed given a desired precision is even more dramatic, although we are unable to report numerical results here, as the other algorithms almost never achieved the precision reached even by the first few iterations of the AIS-BN algorithm.

References in zbMATH (referenced in 23 articles , 1 standard article )

Showing results 1 to 20 of 23.
Sorted by year (citations)

1 2 next

  1. Abbal, Philippe; Sablayrolles, Jean-Marie; Matzner-Lober, Éric; Boursiquot, Jean-Michel; Baudrit, Cedric; Carbonneau, Alain: A decision support system for vine growers based on a Bayesian network (2016)
  2. Gogate, Vibhav; Dechter, Rina: Importance sampling-based estimation over AND/OR search spaces for graphical models (2012)
  3. Cheng, Jian; Druzdzel, Marek J.: AIS-BN: an adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks (2011)
  4. Gogate, Vibhav; Dechter, Rina: SampleSearch: importance sampling in presence of determinism (2011)
  5. Korb, Kevin B.; Nicholson, Ann E.: Bayesian artificial intelligence. (2011)
  6. Luque, Manuel; Díez, Francisco Javier: Variable elimination for influence diagrams with super value nodes (2010)
  7. Yu, Haohai; van Engelen, Robert: Arc refractor methods for adaptive importance sampling on large Bayesian networks under evidential reasoning (2010)
  8. Haider, Saijjad; Zaidi, Abbas K.; Levis, Alexander H.: Identification of best sets of actions in influence nets (2008)
  9. Zolda, Michael: INFER: interactive timing profiles based on Bayesian networks (2008)
  10. Bidyuk, B.; Dechter, R.: Cutset sampling for Bayesian networks (2007)
  11. Dechter, Rina; Mateescu, Robert: AND/OR search spaces for graphical models (2007)
  12. Garcia-Sanchez, Daniel; Druzdzel, Marek J.: An efficient exhaustive anytime sampling algorithm for influence diagrams (2007)
  13. Jeong, I-J.; Leon, V.J.; Villalobos, J.R.: Integrated decision-support system for diagnosis, maintenance planning, and scheduling of manufacturing systems (2007)
  14. Yuan, Changhe; Druzdzel, Marek J.: Theoretical analysis and practical insights on importance sampling in Bayesian networks (2007)
  15. Gugiu, Ionela Claudia: Bayesian networks (2006)
  16. Rosales, Rómer; Sclaroff, Stan: Combining generative and discriminative models in a framework for articulated pose estimation (2006)
  17. Yuan, Changhe; Druzdzel, Marek J.: Importance sampling algorithms for Bayesian networks: Principles and performance (2006)
  18. Moral, Serafín; Salmerón, Antonio: Dynamic importance sampling in Bayesian networks based on probability trees (2005)
  19. Ramos, Fabio Tozeto; Cozman, Fabio Gagliardi: Anytime anyspace probabilistic inference (2005)
  20. Hsu, William H.: Genetic wrappers for feature selection in decision tree induction and variable ordering in Bayesian network structure learning (2004)

1 2 next