journal article
Open Access
Jan 07, 2025
Inference Plans for Hybrid Particle Filtering
Proceedings of the ACM on Programming Languages
Vol. 9
No. POPL
pp. 271-299
·
Association for Computing Machinery (ACM)
Abstract
Advanced probabilistic programming languages (PPLs) using
hybrid particle filtering
combine symbolic exact inference and Monte Carlo methods to improve inference performance. These systems use heuristics to partition random variables within the program into variables that are encoded symbolically and variables that are encoded with sampled values, and the heuristics are not necessarily aligned with the developer’s performance evaluation metrics. In this work, we present
inference plans
, a programming interface that enables developers to control the partitioning of random variables during hybrid particle filtering. We further present
Siren
, a new PPL that enables developers to use annotations to specify inference plans the inference system must implement. To assist developers with statically reasoning about whether an inference plan can be implemented, we present an abstract-interpretation-based static analysis for
Siren
for determining inference plan
satisfiability
. We prove the analysis is sound with respect to
Siren
’s semantics. Our evaluation applies inference plans to three different hybrid particle filtering algorithms on a suite of benchmarks. It shows that the control provided by inference plans enables speed ups of 1.76 x on average and up to 206 x to reach a target accuracy, compared to the inference plans implemented by default heuristics; the results also show that inference plans improve accuracy by 1.83 x on average and up to 595 x with less or equal runtime, compared to the default inference plans. We further show that our static analysis is precise in practice, identifying all satisfiable inference plans in 27 out of the 33 benchmark-algorithm evaluation settings.
hybrid particle filtering
combine symbolic exact inference and Monte Carlo methods to improve inference performance. These systems use heuristics to partition random variables within the program into variables that are encoded symbolically and variables that are encoded with sampled values, and the heuristics are not necessarily aligned with the developer’s performance evaluation metrics. In this work, we present
inference plans
, a programming interface that enables developers to control the partitioning of random variables during hybrid particle filtering. We further present
Siren
, a new PPL that enables developers to use annotations to specify inference plans the inference system must implement. To assist developers with statically reasoning about whether an inference plan can be implemented, we present an abstract-interpretation-based static analysis for
Siren
for determining inference plan
satisfiability
. We prove the analysis is sound with respect to
Siren
’s semantics. Our evaluation applies inference plans to three different hybrid particle filtering algorithms on a suite of benchmarks. It shows that the control provided by inference plans enables speed ups of 1.76 x on average and up to 206 x to reach a target accuracy, compared to the inference plans implemented by default heuristics; the results also show that inference plans improve accuracy by 1.83 x on average and up to 595 x with less or equal runtime, compared to the default inference plans. We further show that our static analysis is precise in practice, identifying all satisfiable inference plans in 27 out of the 33 benchmark-algorithm evaluation settings.
Topics
No keywords indexed for this article. Browse by subject →
References
55
[1]
Busyairah Syd Ali, Arnab Majumdar, Washington Yotto Ochieng, Wolfgang Schuster, and Thiam Kian Chiew. 2015. A causal factors analysis of aircraft incidents due to radar limitations: The Norway case study. Journal of air transport management 44 (2015). https://doi.org/10.1016/j.jairtraman.2015.03.004 10.1016/j.jairtraman.2015.03.004
[2]
Eric Arazo, Diego Ortego, Paul Albert, Noel O’Connor, and Kevin McGuinness. 2019. Unsupervised label noise modeling and loss correction. In International Conference on Machine learning.
[3]
Eric Atkinson, Guillaume Baudart, Louis Mandel, Charles Yuan, and Michael Carbin. 2021. Statically Bounded-Memory Delayed Sampling for Probabilistic Streams. In Object-oriented Programming, Systems, Languages, and Applications. https://doi.org/10.1145/3485492 10.1145/3485492
[4]
Eric Atkinson, Charles Yuan, Guillaume Baudart, Louis Mandel, and Michael Carbin. 2022. Semi-Symbolic Inference for Efficient Streaming Probabilistic Programming. In Object-oriented Programming, Systems, Languages, and Applications. https://doi.org/10.1145/3563347 10.1145/3563347
[5]
Waiss Azizian, Guillaume Baudart, and Marc Lelarge. 2023. Automatic Rao-Blackwellization for Sequential Monte Carlo with Belief Propagation. arXiv preprint arXiv:2312.09860 (2023).
[6]
Guillaume Baudart, Louis Mandel, Eric Atkinson, Benjamin Sherman, Marc Pouzet, and Michael Carbin. 2020. Reactive Probabilistic Programming. In Programming Language Design and Implementation. https://doi.org/10.1145/3385412.3386009 10.1145/3385412.3386009
[8]
[10]
Ellie Y. Cheng Eric Atkinson Guillaume Baudart Louis Mandel and Michael Carbin. 2024. Inference Plans for Hybrid Particle Filtering Artifact. https://doi.org/10.5281/zenodo.13924216 10.5281/zenodo.13924216
[11]
Ellie Y. Cheng, Todd Millstein, Guy Van den Broeck, and Steven Holtzen. 2021. flip-hoisting: Exploiting Repeated Parameters in Discrete Probabilistic Programs. arXiv preprint arXiv:2110.10284 (2021).
[12]
Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Principles of Programming Languages. https://doi.org/10.1145/512950.512973 10.1145/512950.512973
[14]
Patrick Cousot and Michael Monerau. 2012. Probabilistic Abstract Interpretation. In European Symposium on Programming. https://doi.org/10.1007/978-3-642-28869-2_9 10.1007/978-3-642-28869-2_9
[15]
Marco F. Cusumano-Towner, Feras A. Saad, Alexander K. Lew, and Vikash K. Mansinghka. 2019. Gen: A General-Purpose Probabilistic Programming System with Programmable Inference. In Programming Language Design and Implementation. https://doi.org/10.1145/3314221.3314642 10.1145/3314221.3314642
[16]
Alessandra Di Pierro and Herbert Wiklicky. 2000. Concurrent Constraint Programming: Towards Probabilistic Abstract Interpretation. In Principles and Practice of Declarative Programming. https://doi.org/10.1145/351268.351284 10.1145/351268.351284
[17]
Arnaud Doucet, Nando de Freitas, Kevin Murphy, and Stuart Russell. 2000. Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks. In Conference on Uncertainty in Artificial Intelligence.
[18]
[19]
Daniel Fink. 1997. A Compendium of Conjugate Priors.
[20]
Noah D. Goodman and Andreas Stuhlmuller. 2014. The Design and Implementation of Probabilistic Programming Languages. http://dippl.org.
[21]
N.J. Gordon, D.J. Salmond, and A.F.M. Smith. 1993. Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation. In IEE Proceedings F (Radar and Signal Processing), Vol. 140. https://doi.org/10.1049/ip-f-2.1993.0015 10.1049/ip-f-2.1993.0015
[22]
Maria Gorinova, Dave Moore, and Matthew Hoffman. 2020. Automatic Reparameterisation of Probabilistic Programs. In International Conference on Machine Learning.
[23]
Conditional Independence by Typing
Maria I. Gorinova, Andrew D. Gordon, Charles Sutton et al.
ACM Transactions on Programming Languages and Syst...
10.1145/3490421
[24]
Matthew D. Hoffman, Matthew J. Johnson, and Dustin Tran. 2018. Autoconj:Recognizing and Exploiting Conjugacy Without a Domain-Specific Language. In Conference on Neural Information Processing Systems.
[25]
Steven Holtzen, Guy Van den Broeck, and Todd Millstein. 2020. Scaling Exact Inference for Discrete Probabilistic Programs. In Object-oriented Programming, Systems, Languages, and Applications. https://doi.org/10.1145/3428208 10.1145/3428208
[26]
Daniel Huang, Jean-Baptiste Tristan, and Greg Morrisett. 2017a. Compiling Markov Chain Monte Carlo Algorithms for Probabilistic Modeling. In Programming Language Design and Implementation. https://doi.org/10.1145/3062341.3062375 10.1145/3062341.3062375
[27]
Yulong Huang, Yonggang Zhang, Bo Xu, Zhemin Wu, and Jonathon A. Chambers. 2017b. A New Adaptive Extended Kalman Filter for Cooperative Localization. IEEE Trans. Aerospace Electron. Systems 54 (2017). https://doi.org/10.1109/taes.2017.2756763 10.1109/taes.2017.2756763
[28]
Jinlin Lai, Javier Burroni, Hui Guan, and Daniel Sheldon. 2023. Automatically Marginalized MCMC in Probabilistic Programming. In International Conference on Machine Learning.
[29]
[30]
Alexander K. Lew, Marco F. Cusumano-Towner, Benjamin Sherman, Michael Carbin, and Vikash K. Mansinghka. 2019. Trace Types and Denotational Semantics for Sound Programmable Inference in Probabilistic Languages. In Principles of Programming Languages. https://doi.org/10.1145/3371087 10.1145/3371087
[32]
Daniel Lundén. 2017. Delayed Sampling in the Probabilistic Programming Language Anglican.
[33]
Daniel Lundén, Johannes Borgström, and David Broman. 2021. Correctness of Sequential Monte Carlo Inference for Probabilistic Programming Languages. In European Symposium on Programming. https://doi.org/10.1007/978-3-030-72019-3_15 10.1007/978-3-030-72019-3_15
[34]
Zhanyu Ma and Arne Leijon. 2011. Bayesian estimation of beta mixture models with variational inference. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 11 (2011). https://doi.org/10.1109/tpami.2011.63 10.1109/tpami.2011.63
10.1109/tpami.2011.63
[35]
Vikash Mansinghka, Daniel Selsam, and Yura Perov. 2014. Venture: A Higher-Order Probabilistic Programming Platform with Programmable Inference. arXiv preprint arXiv:1404.0099 (2014).
[36]
Vikash K. Mansinghka, Ulrich Schaechtle, Shivam Handa, Alexey Radul, Yutian Chen, and Martin Rinard. 2018. Probabilistic Programming with Programmable Inference. In Programming Language Design and Implementation. https://doi.org/10.1145/3192366.3192409 10.1145/3192366.3192409
[39]
Thomas P. Minka. 2001. Expectation Propagation for Approximate Bayesian Inference. In Conference on Uncertainty in Artificial Intelligence.
[41]
David Monniaux. 2001. An Abstract Monte-Carlo Method for the Analysis of Probabilistic Programs. In Principles of Programming Languages. https://doi.org/10.1145/360204.360211 10.1145/360204.360211
[42]
Lawrence Murray, Daniel Lundén, Jan Kudlicka, David Broman, and Thomas Schön. 2018. Delayed Sampling and Automatic Rao-Blackwellization of Probabilistic Programs. In International Conference on Artificial Intelligence and Statistics.
[43]
Automated learning with a probabilistic programming language: Birch
Lawrence M. Murray, Thomas B. Schön
Annual Reviews in Control
10.1016/j.arcontrol.2018.10.013
[45]
Van Chan Ngo, Quentin Carbonneaux, and Jan Hoffmann. 2018. Bounded Expectations: Resource Analysis for Probabilistic Programs. In Programming Language Design and Implementation. https://doi.org/10.1145/3192366.3192394 10.1145/3192366.3192394
[46]
Fritz Obermeyer, Eli Bingham, Martin Jankowiak, Du Phan, and Jonathan P. Chen. 2019. Functional Tensors for Probabilistic Programming. arXiv preprint arXiv:1910.10775 (2019).
[47]
Daniel Ritchie, Paul Horsfall, and Noah D. Goodman. 2016. Deep Amortized Inference for Probabilistic Programs. arXiv preprint arXiv:1610.05735 (2016).
[49]
Sam Staton. 2017. Commutative Semantics for Probabilistic Programming. In European Symposium on Programming. https://doi.org/10.1007/978-3-662-54434-1_32 10.1007/978-3-662-54434-1_32
[50]
Nazanin Tehrani, Nimar S. Arora, Yucen Lily Li, Kinjal Divesh Shah, David Noursi, Michael Tingley, Narjes Torabi, Eric Lippert, Erik Meijer, et al. 2020. Bean Machine: A Declarative Probabilistic Programming Language for Efficient Programmable Inference. In International Conference on Probabilistic Graphical Models.
Showing 50 of 55 references
Metrics
2
Citations
55
References
Details
- Published
- Jan 07, 2025
- Vol/Issue
- 9(POPL)
- Pages
- 271-299
- License
- View
Authors
Cite This Article
Ellie Y. Cheng, Eric Atkinson, Guillaume Baudart, et al. (2025). Inference Plans for Hybrid Particle Filtering. Proceedings of the ACM on Programming Languages, 9(POPL), 271-299. https://doi.org/10.1145/3704846
Related
You May Also Like
code2vec: learning distributed representations of code
Uri Alon, Meital Zilberstein · 2019
880 citations
Grounded Copilot: How Programmers Interact with Code-Generating Models
Shraddha Barke, Michael B. James · 2023
275 citations