Guillaume Claret
Johannes Borgström
ABSTRACT
We present a new algorithm for Bayesian inference over probabilistic programs, based on data flow analysis techniques from the program analysis community. Unlike existing techniques for Bayesian inference on probabilistic programs, our data flow analysis algorithm is able to perform inference directly on probabilistic programs with loops. Even for loop-free programs, we show that data flow analysis offers better precision and better performance benefits over existing techniques. We also describe heuristics that are crucial for our inference to scale, and present an empirical evaluation of our algorithm over a range of benchmarks.
- R. I. Bahar, E. A. Frohm, C. M. Gaona, G. D. Hachtel, E. Macii, A. Pardo, and F. Somenzi. Algebraic decision diagrams and their applications. Formal Methods in System Design, 10(2/3):171–206, 1997. Google Scholar
Digital Library
- G. Barthe, B. Grégoire, and S. Zanella Béguelin. Formal certification of code-based cryptographic proofs. In Principles of Programming Languages (POPL), pages 90–101, 2009. Google ScholarDigital Library
- J. Borgström, A. D. Gordon, M. Greenberg, J. Margetson, and J. Van Gael. Measure transformer semantics for Bayesian machine learning. In European Symposium on Programming (ESOP), pages 77–96, 2011. Extended version available as Technical Report MSR–TR–2011–18. Google ScholarDigital Library
- M. Bozga and O. Maler. On the representation of probabilities over structured domains. In Computer Aided Verification (CAV), pages 261–273, 1999. Google ScholarDigital Library
- R. E. Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 24(3):293–318, September 1992. Google ScholarDigital Library
- A. T. Chaganty, A. V. Nori, and S. K. Rajamani. Efficiently sampling probabilistic programs via program analysis. In Artificial Intelligence and Statistics (AISTATS), 2013.Google Scholar
- M. Chavira and A. Darwiche. Compiling bayesian networks using variable elimination. In International Joint Conference on on Artificial Intelligence (IJCAI), pages 2443–2449, 2007. Google ScholarDigital Library
- G. Claret, S. K. Rajamani, A. V. Nori, A. D. Gordon, and J. Borgström. Bayesian inference for probabilistic programs via symbolic execution. Technical Report MSR-TR-2012-86, Microsoft Research, 2012.Google Scholar
- P. Cousot and R. Cousot. Abstract interpretation: a unified lattice model for the static analysis of programs by construction or approximation of fixpoints. In Principles of Programming Languages (POPL), pages 238–252, 1977. Google ScholarDigital Library
- T. M. Cover and J. A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, 2006. Google ScholarDigital Library
- A. Darwiche. SamIam. Software available from http://reasoning.cs.ucla.edu/samiam.Google Scholar
- J. Geldenhuys, W. Visser, and M. B. Dwyer. Probabilistic symbolic execution. In International Symposium on Software Testing and Analysis (ISSTA), pages 166–176, 2012. Google ScholarDigital Library
- W. R. Gilks, A. Thomas, and D. J. Spiegelhalter. A language and program for complex Bayesian modelling. The Statistician, 43(1):169–177, 1994.Google ScholarCross Ref
- N. D. Goodman, V. K. Mansinghka, D. M. Roy, K. Bonawitz, and J. B. Tenenbaum. Church: a language for generative models. In Uncertainty in Artificial Intelligence (UAI), pages 220–229, 2008.Google Scholar
- A. D. Gordon, M. Aizatulin, J. Borgström, G. Claret, T. Graepel, A. V. Nori, S. K. Rajamani, and C. Russo. A model-learner pattern for Bayesian reasoning. In Principles of Programming Languages (POPL), pages 403–416, 2013. Google ScholarDigital Library
- R. Herbrich, T. Minka, and T. Graepel. TrueSkill(TM): A Bayesian skill rating system. In Advances in Neural Information Processing Systems (NIPS), pages 569–576, 2007.Google Scholar
- J.-P. Katoen, A. McIver, L. Meinicke, and C. C. Morgan. Linear-invariant generation for probabilistic programs: - automated support for proof-based methods. In Static Analysis Symposium (SAS), pages 390–406, 2010. Google ScholarDigital Library
- G. A. Kildall. A unified approach to global program optimization. In Principles of Programming Languages (POPL), pages 194–206, 1973. Google ScholarDigital Library
- S. Kok, M. Sumner, M. Richardson, P. Singla, H. Poon, D. Lowd, and P. Domingos. The Alchemy system for statistical relational AI. Technical report, University of Washington, 2007. http://alchemy.cs.washington.edu.Google Scholar
- D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009. Google ScholarDigital Library
- D. Koller, D. A. McAllester, and A. Pfeffer. Effective Bayesian inference for stochastic programs. In National Conference on Artificial Intelligence (AAAI), pages 740–747, 1997. Google ScholarDigital Library
- D. Kozen. Semantics of probabilistic programs. Journal of Computer and System Sciences (JCSS), 22(3):328–350, 1981.Google Scholar
- M. Z. Kwiatkowska, G. Norman, and D. Parker. Probabilistic symbolic model checking with prism: a hybrid approach. International Journal on Software Tools for Technology Transfer (STTT), 6(2):128–142, 2004. Google ScholarDigital Library
- S. Malik, A. R. Wang, R. K. Brayton, and A. S. Vincentelli. Logic verification using binary decision diagrams in a logic synthesis environment. In International Conference on Computer-Aided Design (ICCAD), pages 6–9, 1988.Google ScholarCross Ref
- P. Mardziel, S. Magill, M. Hicks, and M. Srivatsa. Dynamic enforcement of knowledge-based security policies using probabilistic abstract interpretation. Journal of Computer Security, January 2013.Google ScholarDigital Library
- T. Minka, J. Winn, J. Guiver, and A. Kannan. Infer.NET 2.3, Nov. 2009. Software available from http://research.microsoft.com/infernet.Google Scholar
- J. Pearl. Probabilistic reasoning in intelligent systems – networks of plausible inference. I-XIX. Morgan Kaufmann, 1989. Google ScholarDigital Library
- A. Pfeffer. Statistical Relational Learning, chapter The design and implementation of IBAL: A General-Purpose Probabilistic Language. MIT Press, 2007.Google Scholar
- G. Ramalingam. Data flow frequency analysis. In Programming Languages Design and Implementation (PLDI), pages 267–277, 1996. Google ScholarDigital Library
- S. Sankaranarayanan, A. Chakarov, and S. Gulwani. Static analysis of probabilistic programs: Inferring whole program properties from finitely many executions. In Programming Languages Design and Implementation (PLDI), 2013. Google ScholarDigital Library
- S. Sanner and D. A. McAllester. Affine Algebraic Decision Diagrams (AADDs) and their application to structured probabilistic inference. In International Joint Conference on on Artificial Intelligence (IJCAI), pages 1384–1390, 2005. Google ScholarDigital Library
- F. Somenzi. CUDD: CU decision diagram package, release 2.5.0. Software available from http://vlsi.colorado.edu.Google Scholar
Index Terms
- Bayesian inference using data flow analysis
Recommendations
Automatic differentiation variational inference
Probabilistic modeling is iterative. A scientist posits a simple model, fits it to her data, refines it according to her analysis, and repeats. However, fitting complex models to large data is a bottleneck in this process. Deriving algorithms for new ...
Probabilistic abductive logic programming using Dirichlet priors
Probabilistic programming is an area of research that aims to develop general inference algorithms for probabilistic models expressed as probabilistic programs whose execution corresponds to inferring the parameters of those models. In this paper, we ...
Bayesian Inference Using Gibbs Sampling in Applications and Curricula of Decision Analysis
Applications and curricula of decision analysis currently do not include methods to compute Bayes' rule and obtain posteriors for nonconjugate prior distributions. The current convention is to force the decision maker's belief to take the form of a ...
Comments