publication . Preprint . 2012

AND/OR Importance Sampling

Gogate, Vibhav; Dechter, Rina;
Open Access English
  • Published: 13 Jun 2012
Abstract
The paper introduces AND/OR importance sampling for probabilistic graphical models. In contrast to importance sampling, AND/OR importance sampling caches samples in the AND/OR space and then extracts a new sample mean from the stored samples. We prove that AND/OR importance sampling may have lower variance than importance sampling; thereby providing a theoretical justification for preferring it over importance sampling. Our empirical evaluation demonstrates that AND/OR importance sampling is far more accurate than importance sampling in many cases.
Subjects
free text keywords: Computer Science - Artificial Intelligence
Funded by
NSF| Strategies for High Performance Graph-Based Reasoning
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0412854
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Information and Intelligent Systems
,
NSF| RI: High Performance Algorithms for Probabilistic and Deterministic Graphical Models
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0713118
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Information and Intelligent Systems
,
NSF| Information Technology Research (ITR): Responding to the Unexpected
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0331707
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Information and Intelligent Systems
,
NIH| Efficient software and algorithms for analyzing markers data on general pedigree
Project
  • Funder: National Institutes of Health (NIH)
  • Project Code: 1R01HG004175-01A1
  • Funding stream: NATIONAL HUMAN GENOME RESEARCH INSTITUTE
Download from

[Bidyuk and Dechter, 2003] Bidyuk, B. and Dechter, R. (2003). An empirical study of w-cutset sampling for bayesian networks. In Proceedings of the 19th Annual Conference on Uncertainty in Artificial Intelligence (UAI-03).

[Cheng and Druzdzel, 2000] Cheng, J. and Druzdzel, M. J. (2000). Ais-bn: An adaptive importance sampling algorithm for evidential reasoning in large bayesian networks. J. Artif. Intell. Res. (JAIR), 13:155-188. [OpenAIRE]

[Dawid et al., 1994] Dawid, A. P., Kjaerulff, U., and Lauritzen, S. L. (1994). Hybrid propagation in junction trees. In IPMU'94, pages 87-97.

[Dechter and Mateescu, 2007] Dechter, R. and Mateescu, R. (2007). AND/OR search spaces for graphical models. Artificial Intelligence, 171(2-3):73-106. [OpenAIRE]

[Fishelson and Geiger, 2003] Fishelson, M. and Geiger, D. (2003). Optimizing exact genetic linkage computations. In RECOMB 2003.

[Geweke, 1989] Geweke, J. (1989). Bayesian inference in econometric models using monte carlo integration. Econometrica, 57(6):1317-39. [OpenAIRE]

[Gogate and Dechter, 2005] Gogate, V. and Dechter, R. (2005). Approximate inference algorithms for hybrid bayesian networks with discrete constraints. UAI2005.

[Gogate and Dechter, 2007] Gogate, V. and Dechter, R. (2007). Samplesearch: A scheme that searches for consistent samples. AISTATS 2007.

[Hernndez and Moral, 1995] Hernndez, L. D. and Moral, S. (1995). Mixing exact and importance sampling propagation algorithms in dependence graphs. International Journal of Approximate Reasoning, 12(8):553-576.

[Kjaerulff, 1995] Kjaerulff, U. (1995). Hugs: Combining exact inference and gibbs sampling in junction trees. In UAI, pages 368-375.

[Paskin, 2004] Paskin, M. A. (2004). Sample propagation. In Thrun, S., Saul, L., and Scho¨lkopf, B., editors, Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA.

[Rubinstein, 1981] Rubinstein, R. Y. (1981). Simulation and the Monte Carlo Method. John Wiley & Sons, Inc., New York, NY, USA.

[Yuan and Druzdzel, 2006] Yuan, C. and Druzdzel, M. J. (2006). Importance sampling algorithms for Bayesian networks: Principles and performance. Mathematical and Computer Modelling. [OpenAIRE]

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue