Article

Component caching in hybrid domains with piecewise polynomial densities

Authors:

Guy Van den Broeck,

Andrea PasseriniAuthors Info & Claims

AAAI'16: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence

Pages 3369 - 3375

Published: 12 February 2016 Publication History

Abstract

Counting the models of a propositional formula is an important problem: for example, it serves as the backbone of probabilistic inference by weighted model counting. A key algorithmic insight is component caching (CC), in which disjoint components of a formula, generated dynamically during a DPLL search, are cached so that they only have to be solved once. In the recent years, driven by SMT technology and probabilistic inference in hybrid domains, there is an increasing interest in counting the models of linear arithmetic sentences. To date, however, solvers for these are block-clause implementations, which are nonviable on large problem instances. In this paper, as a first step in extending CC to hybrid domains, we show how propositional CC systems can be leveraged when limited to piecewise polynomial densities. Our experiments demonstrate a large gap in performance when compared to existing approaches based on a variety of block-clause strategies.

References

[1]

Bacchus, F.; Dalmao, S.; and Pitassi, T. 2009. Solving #SAT and Bayesian inference with backtracking search. Journal of Artificial Intelligence Research 34(1):391-442.

Digital Library

[2]

Baldoni, V.; Berline, N.; De Loera, J.; Köppe, M.; and Vergne, M. 2011. How to integrate a polynomial over a simplex. Mathematics of Computation 80(273):297-325.

[3]

Barrett, C.; Sebastiani, R.; Seshia, S. A.; and Tinelli, C. 2009. Satisfiability modulo theories. In Handbook of Satisfiability. chapter 26, 825-885.

[4]

Belle, V.; Passerini, A.; and Van den Broeck, G. 2015. Probabilistic inference in hybrid domains by weighted model integration. In Proc. IJCAI.

Digital Library

[5]

Belle, V.; Van den Broeck, G.; and Passerini, A. 2015. Hashing-based approximate probabilistic inference in hybrid domains. In UAI.

[6]

Boyen, X., and Koller, D. 1998. Tractable inference for complex stochastic processes. In UAI, 33-42.

Digital Library

[7]

Chakraborty, S.; Fremont, D. J.; Meel, K. S.; Seshia, S. A.; and Vardi, M. Y. 2014. Distribution-aware sampling and weighted model counting for sat. Proc. AAAI.

Digital Library

[8]

Chavira, M., and Darwiche, A. 2005. Compiling Bayesian networks with local structure. In IJCAI, volume 19, 1306.

Digital Library

[9]

Chavira, M., and Darwiche, A. 2008. On probabilistic inference by weighted model counting. Artificial Intelligence 172(6-7):772-799.

Digital Library

[10]

Chistikov, D.; Dimitrova, R.; and Majumdar, R. 2015. Approximate counting in smt and value estimation for probabilistic programs. In TACAS, volume 9035. 320-334.

Digital Library

[11]

Curds, R. M. 1997. Propagation techniques in probabilistic expert systems. Ph.D. Dissertation, Department of Statistical Science, University College London.

[12]

Darwiche, A. 2001. Recursive conditioning. Artificial Intelligence 126(1):5-41.

Digital Library

[13]

Darwiche, A. 2004. New advances in compiling CNF to decomposable negation normal form. In Proceedings of ECAI, 328-332.

[14]

Dechter, R. 1996. Bucket elimination: A unifying framework for probabilistic inference. In UAI, 211-219.

Digital Library

[15]

Dyer, M. E., and Frieze, A. M. 1988. On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17(5):967-974.

Digital Library

[16]

Fredrikson, M., and Jha, S. 2014. Satisfiability modulo counting: A new approach for analyzing privacy properties. In LICS, 42:1-42:10. New York, NY, USA: ACM.

Digital Library

[17]

Gogate, V., and Dechter, R. 2005. Approximate inference algorithms for hybrid bayesian networks with discrete constraints. UAI.

[18]

Lauritzen, S. L., and Jensen, F. 2001. Stable local computation with conditional gaussian distributions. Statistics and Computing 11(2):191-203.

Digital Library

[19]

Lunn, D. J.; Thomas, A.; Best, N.; and Spiegelhalter, D. 2000. Winbugs - a Bayesian modelling framework: concepts, structure, and extensibility. Statistics and computing 10(4):325-337.

Digital Library

[20]

Murphy, K. P. 1999. A variational approximation for bayesian networks with discrete and continuous latent variables. In UAI, 457-466.

Digital Library

[21]

Salzmann, M. 2013. Continuous inference in graphical models with polynomial energies. In CVPR, 1744-1751.

Digital Library

[22]

Sang, T.; Beame, P.; and Kautz, H. A. 2005. Performing bayesian inference by weighted model counting. In AAAI.

Digital Library

[23]

Sanner, S., and Abbasnejad, E. 2012. Symbolic variable elimination for discrete and continuous graphical models. In AAAI.

Digital Library

[24]

Shenoy, P., and West, J. 2011. Inference in hybrid bayesian networks using mixtures of polynomials. International Journal of Approximate Reasoning 52(5):641-657.

Digital Library

[25]

Valiant, L. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing 8(3):410-421.

Digital Library

[26]

Wang, S.; Schwing, A. G.; and Urtasun, R. 2014. Efficient inference of continuous markov random fields with polynomial potentials. In NIPS, 936-944.

Digital Library

Cited By

Kolb SMladenov MSanner SBelle VKersting K(2018)Efficient symbolic integration for probabilistic inferenceProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304709(5031-5037)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304709
Lüdtke SSchröder MKrüger FBader SKirste T(2018)State-space abstractions for probabilistic inferenceJournal of Artificial Intelligence Research10.1613/jair.1.1126163:1(789-848)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1613/jair.1.11261
Belle V(2017)Logic meets probabilityProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3172026(5116-5120)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3172026
Show More Cited By

Recommendations

Piecewise quadratic trigonometric polynomial curves

Analogous to the quadratic B-spline curve, a piecewise quadratic trigonometric polynomial curve is presented in this paper. The quadratic trigonometric polynomial curve has C² continuity, while the quadratic B-spline curve has C¹ continuity. The ...
Piecewise quartic polynomial curves with a local shape parameter
Special issue: The international symposium on computing and information (ISCI2004)

Piecewise quartic polynomial curves with a local shape parameter are presented in this paper. The given blending function is an extension of the cubic uniform B-splines. The changes of a local shape parameter will only change two curve segments. With ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches

Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AAAI'16: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence

February 2016

4406 pages

Sponsors

Association for the Advancement of Artificial Intelligence

Publisher

AAAI Press

Publication History

Published: 12 February 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kolb SMladenov MSanner SBelle VKersting K(2018)Efficient symbolic integration for probabilistic inferenceProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304652.3304709(5031-5037)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304652.3304709
Lüdtke SSchröder MKrüger FBader SKirste T(2018)State-space abstractions for probabilistic inferenceJournal of Artificial Intelligence Research10.1613/jair.1.1126163:1(789-848)Online publication date: 1-Sep-2018
https://dl.acm.org/doi/10.1613/jair.1.11261
Belle V(2017)Logic meets probabilityProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3172026(5116-5120)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3172026
Merrell DAlbarghouthi AD'Antoni L(2017)Weighted model integration with orthogonal transformationsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171932(4610-4616)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171932
Morettin PPasserini ASebastiani R(2017)Efficient weighted model integration via SMT-based predicate abstractionProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171745(720-728)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171745
Albarghouthi AD'Antoni LDrews SNori A(2017)FairSquare: probabilistic verification of program fairnessProceedings of the ACM on Programming Languages10.1145/31339041:OOPSLA(1-30)Online publication date: 12-Oct-2017
https://dl.acm.org/doi/10.1145/3133904

View Options

View options

Figures

Tables

Media

View Table of Conten