×

SampleSearch: importance sampling in presence of determinism. (English) Zbl 1216.68246

Summary: The paper focuses on developing effective importance sampling algorithms for mixed probabilistic and deterministic graphical models. The use of importance sampling in such graphical models is problematic because it generates many useless zero weight samples which are rejected yielding an inefficient sampling process. To address this rejection problem, we propose the SampleSearch scheme that augments sampling with systematic constraint-based backtracking search. We characterize the bias introduced by the combination of search with sampling, and derive a weighting scheme which yields an unbiased estimate of the desired statistics (e.g., probability of evidence). When computing the weights exactly is too complex, we propose an approximation which has a weaker guarantee of asymptotic unbiasedness. We present results of an extensive empirical evaluation demonstrating that SampleSearch outperforms other schemes in presence of significant amount of determinism.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

MiniSat; RSat; AIS-BN
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Dechter, D. Larkin, Hybrid processing of beliefs and constraints, in: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001, pp. 112-119.; R. Dechter, D. Larkin, Hybrid processing of beliefs and constraints, in: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001, pp. 112-119.
[2] D. Larkin, R. Dechter, Bayesian inference in the presence of determinism, in: Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS), 2003.; D. Larkin, R. Dechter, Bayesian inference in the presence of determinism, in: Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS), 2003.
[3] R. Dechter, R. Mateescu, Mixtures of deterministic-probabilistic networks and their AND/OR search space, in: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2004, pp. 120-129.; R. Dechter, R. Mateescu, Mixtures of deterministic-probabilistic networks and their AND/OR search space, in: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2004, pp. 120-129.
[4] Mateescu, R.; Dechter, R., Mixed deterministic and probabilistic networks, Annals of Mathematics and Artificial Intelligence (AMAI), Probabilistic Relational Learning, 54, 1-3, 3-51 (2008), Special Issue:
[5] Pearl, J., Probabilistic Reasoning in Intelligent Systems (1988), Morgan Kaufmann
[6] Dechter, R., Constraint Processing (2003), Morgan Kaufmann
[7] Marshall, A. W., The use of multi-stage sampling schemes in Monte Carlo computations, (Symposium on Monte Carlo Methods (1956)), 123-140
[8] Rubinstein, R. Y., Simulation and the Monte Carlo Method (1981), John Wiley & Sons Inc. · Zbl 0529.68076
[9] Geweke, J., Bayesian inference in econometric models using Monte Carlo integration, Econometrica, 57, 6, 1317-1339 (1989) · Zbl 0683.62068
[10] V. Gogate, R. Dechter, Approximate inference algorithms for hybrid Bayesian networks with discrete constraints, in: Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2005, pp. 209-216.; V. Gogate, R. Dechter, Approximate inference algorithms for hybrid Bayesian networks with discrete constraints, in: Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2005, pp. 209-216.
[11] Yedidia, J. S.; Freeman, W. T.; Weiss, Y., Constructing free energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, 51, 2282-2312 (2004) · Zbl 1283.94023
[12] Dechter, R.; Kask, K.; Mateescu, R., Iterative join graph propagation, (Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence (UAI) (2002), Morgan Kaufmann), 128-136 · Zbl 1192.68649
[13] Mateescu, R.; Kask, K.; Gogate, V.; Dechter, R., Join-graph propagation algorithms, Journal of Artificial Intelligence Research, 37, 279-328 (2009) · Zbl 1192.68649
[14] Bidyuk, B.; Dechter, R., Cutset sampling for Bayesian networks, Journal of Artificial Intelligence Research (JAIR), 28, 1-48 (2007) · Zbl 1182.68220
[15] N. Sorensson, N. Een, Minisat v1.13-A SAT solver with conflict-clause minimization, in: SAT 2005 Competition, 2005.; N. Sorensson, N. Een, Minisat v1.13-A SAT solver with conflict-clause minimization, in: SAT 2005 Competition, 2005.
[16] W. Wei, J. Erenrich, B. Selman, Towards efficient sampling: exploiting random walk strategies, in: Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004, pp. 670-676.; W. Wei, J. Erenrich, B. Selman, Towards efficient sampling: exploiting random walk strategies, in: Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004, pp. 670-676.
[17] C.P. Gomes, J. Hoffmann, A. Sabharwal, B. Selman, From sampling to model counting, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), 2007, pp. 2293-2299.; C.P. Gomes, J. Hoffmann, A. Sabharwal, B. Selman, From sampling to model counting, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), 2007, pp. 2293-2299.
[18] J. Roberto, J. Bayardo, J.D. Pehoushek, Counting models using connected components, in: Proceedings of 17th National Conference on Artificial Intelligence (AAAI), 2000, pp. 157-162.; J. Roberto, J. Bayardo, J.D. Pehoushek, Counting models using connected components, in: Proceedings of 17th National Conference on Artificial Intelligence (AAAI), 2000, pp. 157-162.
[19] Dechter, R., Bucket elimination: A unifying framework for reasoning, Artificial Intelligence, 113, 41-85 (1999) · Zbl 0939.68847
[20] A. Choi, A. Darwiche, An edge deletion semantics for belief propagation and its practical impact on approximation quality, in: Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI), 2006, pp. 1107-1114.; A. Choi, A. Darwiche, An edge deletion semantics for belief propagation and its practical impact on approximation quality, in: Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI), 2006, pp. 1107-1114.
[21] M. Fishelson, D. Geiger, Optimizing exact genetic linkage computations, in: Proceedings of the Seventh Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp. 114-121.; M. Fishelson, D. Geiger, Optimizing exact genetic linkage computations, in: Proceedings of the Seventh Annual International Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp. 114-121.
[22] Chavira, M. D.; Darwiche, A.; Jaeger, M., Compiling relational Bayesian networks for exact inference, International Journal of Approximate Reasoning, 42, 1-2, 4-20 (2006) · Zbl 1096.68747
[23] Yuan, C.; Druzdzel, M. J., Importance sampling algorithms for Bayesian networks: Principles and performance, Mathematical and Computer Modelling, 43, 90-10, 1189-1207 (2006) · Zbl 1459.62021
[24] V. Gogate, R. Dechter, SampleSearch: A scheme that searches for consistent samples, in: Proceedings of the 11th Conference on Artificial Intelligence and Statistics (AISTATS), 2007, pp. 147-154.; V. Gogate, R. Dechter, SampleSearch: A scheme that searches for consistent samples, in: Proceedings of the 11th Conference on Artificial Intelligence and Statistics (AISTATS), 2007, pp. 147-154.
[25] V. Gogate, R. Dechter, Approximate counting by sampling the backtrack-free search space, in: Proceedings of 22nd Conference on Artificial Intelligence (AAAI), 2007, pp. 198-203.; V. Gogate, R. Dechter, Approximate counting by sampling the backtrack-free search space, in: Proceedings of 22nd Conference on Artificial Intelligence (AAAI), 2007, pp. 198-203.
[26] Liu, J., Monte-Carlo Strategies in Scientific Computing (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0991.65001
[27] Freuder, E. C., A sufficient condition for backtrack-free search, Journal of the ACM, 29, 1, 24-32 (1982) · Zbl 0477.68063
[28] Walsh, T., SAT v CSP, (Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming (2000), Springer-Verlag: Springer-Verlag London, UK), 441-456 · Zbl 1044.68808
[29] K. Pipatsrisawat, A. Darwiche, RSAT 2.0: SAT solver description, Tech. Rep. D-153, Automated Reasoning Group, Computer Science Department, UCLA, 2007.; K. Pipatsrisawat, A. Darwiche, RSAT 2.0: SAT solver description, Tech. Rep. D-153, Automated Reasoning Group, Computer Science Department, UCLA, 2007.
[30] Cheng, J.; Druzdzel, M. J., AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks, Journal of Artificial Intelligence Research (JAIR), 13, 155-188 (2000) · Zbl 0963.68223
[31] R.D. Shachter, M.A. Peot, Simulation approaches to general probabilistic inference on belief networks, in: Proceedings of the Fifth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1990, pp. 221-234.; R.D. Shachter, M.A. Peot, Simulation approaches to general probabilistic inference on belief networks, in: Proceedings of the Fifth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1990, pp. 221-234. · Zbl 0721.68075
[32] R.M. Fung, K.-C. Chang, Weighing and integrating evidence for stochastic simulation in Bayesian networks, in: Proceedings of the Fifth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1990, pp. 209-220.; R.M. Fung, K.-C. Chang, Weighing and integrating evidence for stochastic simulation in Bayesian networks, in: Proceedings of the Fifth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1990, pp. 209-220.
[33] L. Ortiz, L. Kaelbling, Adaptive importance sampling for estimation in structured domains, in: Proceedings of the 16th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2000, pp. 446-454.; L. Ortiz, L. Kaelbling, Adaptive importance sampling for estimation in structured domains, in: Proceedings of the 16th Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2000, pp. 446-454.
[34] R. Fung, B. del Favero, Backward simulation in Bayesian networks, in: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1994, pp. 227-234.; R. Fung, B. del Favero, Backward simulation in Bayesian networks, in: Proceedings of the Tenth Annual Conference on Uncertainty in Artificial Intelligence (UAI), 1994, pp. 227-234.
[35] Kask, K.; Dechter, R.; Larrosa, J.; Dechter, A., Unifying tree decompositions for reasoning in graphical models, Artificial Intelligence, 166, 1-2, 165-193 (2005) · Zbl 1132.68680
[36] Casella, G.; Robert, C. P., Rao-blackwellisation of sampling schemes, Biometrika, 83, 1, 81-94 (1996) · Zbl 0866.62024
[37] Darwiche, A.; Hopkins, M., Using recursive decomposition to construct elimination orders, jointrees, and dtrees, (Trends in Artificial Intelligence. Trends in Artificial Intelligence, Lecture Notes in AI (2001), Springer-Verlag), 180-191 · Zbl 1001.68570
[38] B. Bidyuk, R. Dechter, On finding minimal \(w\); B. Bidyuk, R. Dechter, On finding minimal \(w\)
[39] W. Wei, B. Selman, A new approach to model counting, in: Proceedings of Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT), 2005, pp. 324-339.; W. Wei, B. Selman, A new approach to model counting, in: Proceedings of Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT), 2005, pp. 324-339. · Zbl 1128.68487
[40] Valiant, L. G., The complexity of enumeration and reliability problems, SIAM Journal of Computation, 8, 3, 105-117 (1987)
[41] T. Sang, P. Beame, H. Kautz, Heuristics for fast exact model counting, in: Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT), 2005, pp. 226-240.; T. Sang, P. Beame, H. Kautz, Heuristics for fast exact model counting, in: Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT), 2005, pp. 226-240. · Zbl 1128.68481
[42] B. Selman, H. Kautz, B. Cohen, Noise strategies for local search, in: Proceedings of the Eleventh National Conference on Artificial Intelligence, 1994, pp. 337-343.; B. Selman, H. Kautz, B. Cohen, Noise strategies for local search, in: Proceedings of the Eleventh National Conference on Artificial Intelligence, 1994, pp. 337-343.
[43] K.P. Murphy, Y. Weiss, M.I. Jordan, Loopy belief propagation for approximate inference: an empirical study, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI), 1999, pp. 467-475.; K.P. Murphy, Y. Weiss, M.I. Jordan, Loopy belief propagation for approximate inference: an empirical study, in: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI), 1999, pp. 467-475.
[44] Darwiche, A.; Dechter, R.; Choi, A.; Gogate, V.; Otten, L., Results from the probabilistic inference evaluation of UAI’08 (2008), available online at:
[45] Dechter, R.; Gogate, V.; Otten, L.; Marinescu, R.; Mateescu, R., Graphical model algorithms at UC Irvine (2009), website:
[46] Darwiche, A., A differential approach to inference in Bayesian networks, Journal of the ACM, 50, 3, 280-305 (2003) · Zbl 1325.68226
[47] A. Darwiche, New advances in compiling CNF into decomposable negation normal form, in: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI), 2004, pp. 328-332.; A. Darwiche, New advances in compiling CNF into decomposable negation normal form, in: Proceedings of the 16th European Conference on Artificial Intelligence (ECAI), 2004, pp. 328-332.
[48] Darwiche, A.; Marquis, P., A knowledge compilation map, Journal of Artificial Intelligence Research (JAIR), 17, 229-264 (2002) · Zbl 1045.68131
[49] C. Gomes, D. Shmoys, Completing quasigroups or Latin squares: a structured graph coloring problem, in: Proceedings of the Computational Symposium on Graph Coloring and Extensions, 2002.; C. Gomes, D. Shmoys, Completing quasigroups or Latin squares: a structured graph coloring problem, in: Proceedings of the Computational Symposium on Graph Coloring and Extensions, 2002.
[50] Ritter, T., Latin squares: A literature survey, available online at:
[51] T. Walsh, Permutation problems and channelling constraints, in: Proceedings of the 8th International Conference on Logic Programming and Automated Reasoning (LPAR), 2001, pp. 377-391.; T. Walsh, Permutation problems and channelling constraints, in: Proceedings of the 8th International Conference on Logic Programming and Automated Reasoning (LPAR), 2001, pp. 377-391. · Zbl 1273.68365
[52] V. Gogate, B. Bidyuk, R. Dechter, Studies in lower bounding probability of evidence using the Markov inequality, in: Proceedings of 23rd Conference on Uncertainty in Artificial Intelligence (UAI), 2007, pp. 141-148.; V. Gogate, B. Bidyuk, R. Dechter, Studies in lower bounding probability of evidence using the Markov inequality, in: Proceedings of 23rd Conference on Uncertainty in Artificial Intelligence (UAI), 2007, pp. 141-148.
[53] Simon, L.; Berre, D. L.; Hirsch, E., The SAT 2002 competition, Annals of Mathematics and Artificial Intelligence (AMAI), 43, 307-342 (2005)
[54] Ott, J., Analysis of Human Genetic Linkage (1999), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, Maryland
[55] Bilmes, J.; Dechter, R., Evaluation of probabilistic inference systems of UAI’06 (2006), available online at
[56] K. Kask, R. Dechter, A. Gelfand, BEEM: bucket elimination with external memory, in: 26th Conference on Uncertainty in Artificial Intelligence (UAI), 2010, pp. 268-276.; K. Kask, R. Dechter, A. Gelfand, BEEM: bucket elimination with external memory, in: 26th Conference on Uncertainty in Artificial Intelligence (UAI), 2010, pp. 268-276.
[57] Kokolakis, G.; Nanopoulos, P., Bayesian multivariate micro-aggregation under the Hellinger distance criterion, Research in Official Statistics, 4, 117-125 (2001)
[58] Kullback, S.; Leibler, R. A., On information and sufficiency, The Annals of Mathematical Statistics, 22, 1, 79-86 (1951) · Zbl 0042.38403
[59] R. Dechter, R. Mateescu, A simple insight into iterative belief propagation’s success, in: Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence (UAI), 2003, p. 175-183.; R. Dechter, R. Mateescu, A simple insight into iterative belief propagation’s success, in: Proceedings of the 19th Conference in Uncertainty in Artificial Intelligence (UAI), 2003, p. 175-183.
[60] V. Gogate, Sampling algorithms for probabilistic and deterministic graphical models, PhD thesis, University of California, Irvine, 2009.; V. Gogate, Sampling algorithms for probabilistic and deterministic graphical models, PhD thesis, University of California, Irvine, 2009.
[61] Eén, N.; Sörensson, N., Temporal induction by incremental SAT solving, Electronic Notes in Theoretical Computer Science, 89, 4, 543-560 (2003) · Zbl 1271.68215
[62] Dechter, R.; Mateescu, R., AND/OR search spaces for graphical models, Artificial Intelligence, 171, 2-3, 73-106 (2007) · Zbl 1168.68549
[63] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, 35, 8, 677-691 (1986) · Zbl 0593.94022
[64] Moral, S.; Salmerón, A., Dynamic importance sampling in Bayesian networks based on probability trees, International Journal of Approximate Reasoning, 38, 3, 245-261 (2005) · Zbl 1095.68117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.