Coarse-to-Fine Sequential Monte Carlo for Probabilistic Programs
Open accessAbstract
Many practical techniques for probabilistic inference require a sequence of distributions that interpolate between a tractable distribution and an intractable distribution of interest. Usually, the sequences used are simple, e.g., based on geometric averages between distributions. When models are expressed as probabilistic programs, the models themselves are highly structured objects that can be used to derive annealing sequences that are more sensitive to domain structure. We propose an algorithm for transforming probabilistic programs to coarse-to-fine programs which have the same marginal distribution as the original programs, but generate the data at increasing levels of detail, from coarse to fine. We apply this algorithm to an Ising model, its depth-from-disparity variation, and a factorial hidden Markov model. We show preliminary evidence that the use of coarse-to-fine models can make existing generic inference algorithms more efficient.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Using probabilistic programming, one can leverage sequential Monte Carlo methods to gradually infer a theory represented as a probabilistic program as new data is observed, or by incrementally refining an initially coarse 3D world model.
“Using probabilistic programming, one can leverage sequential Monte Carlo (SMC) methods to gradually infer a theory T (represented as probabilistic program) as new data is observed (Saad et al., 2023), or by incrementally refining an initially coarse 3D world model (Gothoskar et al., 2023;Stuhlmüller et al., 2015).”
From Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems (2024) · cites this paper as Stuhlmüller et al., 2015
The Introduction (p. 2) describes using SMC to refine a probabilistic model from coarse to fine. The stereo-matching experiment (p. 9) applies this to a disparity map that can provide a rough measure of depth, but it does not describe incrementally refining a 3D world model. (LLM, conf=0.86)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
No references could be resolved yet.
Research works printed but not linked: 20
- Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. Pattern Analysis and Machine Intelligence, IEEE Transactions on , 23(11):1222-1239, 2001.
- Eugene Charniak, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, Jeremy Moore, Michael Pozar, and Theresa Vu. Multilevel Coarse-to-fine PCFG Parsing. Proceedings of the Human Language Technology Conference of the NAACL, Main Conference , pages 168-175, 2006.
- Patrick Cousot and Michael Monerau. Probabilistic abstract interpretation. In Programming Languages and Systems , volume 7211 of Lecture Notes in Computer Science , pages 169-193. Springer, 2012.
- Cameron E Freer, Vikash K Mansinghka, and Daniel M Roy. When are probabilistic programs probably computationally tractable? NIPS 2010 Workshop on Monte Carlo Methods in Modern Applications , 2010.
- Zoubin Ghahramani and Michael I Jordan. Factorial Hidden Markov Models. Machine Learning , 29(2-3): 245-273, November 1997.
- Noah D Goodman, Vikash Mansinghka, Daniel M Roy, K A Bonawitz, and Joshua B Tenenbaum. Church: a language for generative models. Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence , pages 220-229, 2008.
- Chlo´ e Kiddon and Pedro Domingos. Coarse-to-Fine Inference and Learning for First-Order Probabilistic Models. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence , pages 10491056, August 2011.
- Daphne Koller, David McAllester, and Avi Pfeffer. Effective Bayesian Inference for Stochastic Programs. In Proceedings of the National Conference on Artificial Intelligence , pages 740-747, 1997.
- Tejas D Kulkarni, Ardavan Saeedi, and Samuel Gershman. Variational Particle Approximations. arXiv preprint arXiv:1402.5715 , pages 1-11, 2014. · arXiv
- Edward Lyman and Daniel M. Zuckerman. Resolution exchange simulation with incremental coarsening. Journal of Chemical Theory and Computation , 2: 656-666, 2006. ISSN 15499618.
- Michael D Menz and Ralph D Freeman. Stereoscopic depth processing in the visual cortex: a coarse-to-fine mechanism. Nature neuroscience , 6(1):59-65, 2003.
- David Monniaux. Abstract interpretation of probabilistic semantics. In Static Analysis , volume 1824 of Lecture Notes in Computer Science , pages 322-339. Springer, 2000.
- Slav Petrov, Aria Haghighi, and Dan Klein. Coarseto-fine syntactic machine translation using language projections. Empirical Methods in Natural Language , pages 108-116, 2008.
- Daniel Scharstein and Richard Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International journal of computer vision , 47(1-3):7-42, 2002.
- Jacob Steinhardt and Percy Liang. Filtering with Abstract Particles. In Proceedings of The ThirtyFirst International Conference on Machine Learning , pages 727-735, June 2014.
- Neural Information Processing Systems (NIPS) 27 , 2013.
- Richard Szeliski, Ramin Zabih, Daniel Scharstein, Olga Veksler, Vladimir Kolmogorov, Aseem Agarwala, Marshall Tappen, and Carsten Rother. A comparative study of energy minimization methods for markov random fields with smoothness-based priors. Pattern Analysis and Machine Intelligence, IEEE Transactions on , 30(6):1068-1080, 2008.
- Yun Tang, Wen-Ju Liu, Hua Zhang, Bo Xu, and GuoHong Ding. One-pass coarse-to-fine segmental speech decoding algorithm. In Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on , volume 1, pages I-I. IEEE, 2006.
- Kenneth G Wilson. The renormalization group: Critical phenomena and the Kondo problem. Reviews of Modern Physics , 47(4):773, 1975.
- David Wingate, Andreas Stuhlm¨ uller, and Noah D Goodman. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In Proceedings of the 14th international conference on Artificial Intelligence and Statistics , 2011.
Cited by
Sorted by citations
Towards Guaranteed Safe AI: A Framework for Ensuring Robust and Reliable AI Systems
Dalrymple, D. "., Skalse, J., Bengio, Y., Russell, S., Tegmark, M., Seshia, S., Omohundro, S., Szegedy, C., Goldhaber, B., Ammann, N., et al. (2024) · arXiv · doi:10.48550/arxiv.2405.06624 · Cited by 12 · see citing works
- Authors
- Stuhlmüller, A., Hawkins, R. X. D., Siddharth, N., & Goodman, N. D.
- Affiliations
- Stanford University (US)
- ORCID
- Goodman, Noah D.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2015
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1509.02962
- OpenAlex
- W2223465455
- Cited by
- 1
- References
- 0
- Citations by year
- 2015: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation
- Defense Advanced Research Projects Agency (FA8750, FA8750‐14‐2‐0009)
- Topics
- Physical Sciences › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Physical Sciences › Computer Science › Artificial Intelligence › Gaussian Processes and Bayesian Inference
- Keywords
- sequential Monte Carlo, probabilistic programs, marginal distributions, Ising model, factorial hidden Markov model, probabilistic inference
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
