{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,24]],"date-time":"2026-08-24T22:42:19Z","timestamp":1787611339231,"version":"build-2736575974"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T00:00:00Z","timestamp":1704153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,1,2]]},"abstract":"<jats:p>Computing the posterior distribution of a probabilistic program is a hard task for which no one-fit-for-all solution exists. We propose Gaussian Semantics, which approximates the exact probabilistic semantics of a bounded program by means of Gaussian mixtures. It is parametrized by a map that associates each program location with the moment order to be matched in the approximation. We provide two main contributions. The first is a universal approximation theorem stating that, under mild conditions, Gaussian Semantics can approximate the exact semantics arbitrarily closely. The second is an approximation that matches up to second-order moments analytically in face of the generally difficult problem of matching moments of Gaussian mixtures with arbitrary moment order. We test our second-order Gaussian approximation (SOGA) on a number of case studies from the literature. We show that it can provide accurate estimates in models not supported by other approximation methods or when exact symbolic techniques fail because of complex expressions or non-simplified integrals. On two notable classes of problems, namely collaborative filtering and programs involving mixtures of continuous and discrete distributions, we show that SOGA significantly outperforms alternative techniques in terms of accuracy and computational time.<\/jats:p>","DOI":"10.1145\/3632905","type":"journal-article","created":{"date-parts":[[2024,1,5]],"date-time":"2024-01-05T20:48:51Z","timestamp":1704487731000},"page":"1882-1912","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Inference of Probabilistic Programs with Moment-Matching Gaussian Mixtures"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-3489-9600","authenticated-orcid":false,"given":"Francesca","family":"Randone","sequence":"first","affiliation":[{"name":"IMT School for Advanced Studies Lucca, Lucca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8874-4001","authenticated-orcid":false,"given":"Luca","family":"Bortolussi","sequence":"additional","affiliation":[{"name":"University of Trieste, Trieste, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6895-6517","authenticated-orcid":false,"given":"Emilio","family":"Incerto","sequence":"additional","affiliation":[{"name":"IMT School for Advanced Studies Lucca, Lucca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6018-5989","authenticated-orcid":false,"given":"Mirco","family":"Tribastone","sequence":"additional","affiliation":[{"name":"IMT School for Advanced Studies Lucca, Lucca, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,1,5]]},"reference":[{"key":"e_1_3_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133904"},{"key":"e_1_3_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_3"},{"key":"e_1_3_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45190-5_28"},{"key":"e_1_3_1_5_1","volume-title":"Probability and measure","author":"Billingsley Patrick","year":"2008","unstructured":"Patrick Billingsley. 2008. Probability and measure. John Wiley & Sons."},{"key":"e_1_3_1_6_1","volume-title":"Convergence of probability measures","author":"Billingsley Patrick","year":"2013","unstructured":"Patrick Billingsley. 2013. Convergence of probability measures. John Wiley & Sons."},{"key":"e_1_3_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3322734"},{"key":"e_1_3_1_8_1","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop Christopher M","year":"2006","unstructured":"Christopher M Bishop and Nasser M Nasrabadi. 2006. Pattern Recognition and Machine Learning. Vol. 4. Springer."},{"key":"e_1_3_1_9_1","unstructured":"Xavier Boyen and Daphne Koller. 1998. Tractable inference for complex stochastic processes. In Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence. 33\u201342."},{"key":"e_1_3_1_10_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_1_11_1","unstructured":"Arun Chaganty Aditya Nori and Sriram Rajamani. 2013. Efficiently sampling probabilistic programs via program analysis. In Artificial Intelligence and Statistics. PMLR 153\u2013160."},{"key":"e_1_3_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10936-7_6"},{"key":"e_1_3_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1809028.1806629"},{"key":"e_1_3_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_22"},{"key":"e_1_3_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13185-1_5"},{"key":"e_1_3_1_16_1","doi-asserted-by":"crossref","unstructured":"Patrick Cousot and Radhia Cousot. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. 238\u2013252.","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_1_17_1","volume-title":"Elements of information theory","author":"Cover Thomas M","year":"1999","unstructured":"Thomas M Cover. 1999. Elements of information theory. John Wiley & Sons."},{"key":"e_1_3_1_18_1","volume-title":"Markov processes: characterization and convergence","author":"Ethier Stewart N","year":"2009","unstructured":"Stewart N Ethier and Thomas G Kurtz. 2009. Markov processes: characterization and convergence. John Wiley & Sons."},{"key":"e_1_3_1_19_1","doi-asserted-by":"crossref","unstructured":"Antonio Filieri Corina S Pasareanu and Willem Visser. 2013. Reliability analysis in symbolic pathfinder. In 2013 35th International Conference on Software Engineering (ICSE). IEEE 622\u2013631.","DOI":"10.1109\/ICSE.2013.6606608"},{"key":"e_1_3_1_20_1","article-title":"Estimating mutual information for discrete-continuous mixtures","volume":"30","author":"Gao Weihao","year":"2017","unstructured":"Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. 2017. Estimating mutual information for discrete-continuous mixtures. Advances in Neural Information Processing Systems 30 (2017).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_3_1_22_1","doi-asserted-by":"publisher","DOI":"10.1201\/b16018"},{"key":"e_1_3_1_23_1","unstructured":"Noah D Goodman Vikash K Mansinghka Daniel Roy Keith Bonawitz and Joshua B Tenenbaum. 2008. Church: a language for generative models. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence. 220\u2013229."},{"key":"e_1_3_1_24_1","doi-asserted-by":"crossref","unstructured":"Andrew D Gordon Thomas A Henzinger Aditya V Nori and Sriram K Rajamani. 2014. Probabilistic programming. In Future of Software Engineering Proceedings. 167\u2013181.","DOI":"10.1145\/2593882.2593900"},{"key":"e_1_3_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479892241287"},{"key":"e_1_3_1_26_1","doi-asserted-by":"publisher","DOI":"10.1057\/9780230280830_13"},{"key":"e_1_3_1_27_1","doi-asserted-by":"crossref","unstructured":"W Keith Hastings. 1970. Monte Carlo sampling methods using Markov chains and their applications. (1970).","DOI":"10.2307\/2334940"},{"key":"e_1_3_1_28_1","unstructured":"Matthew D Hoffman David M Blei Chong Wang and John Paisley. 2013. Stochastic variational inference. Journal of Machine Learning Research (2013)."},{"key":"e_1_3_1_29_1","article-title":"Latent class models for collaborative filtering","volume":"99","author":"Hofmann Thomas","year":"1999","unstructured":"Thomas Hofmann and Jan Puzicha. 1999. Latent class models for collaborative filtering. In IJCAI, Vol. 99.","journal-title":"IJCAI"},{"key":"e_1_3_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428208"},{"key":"e_1_3_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-6080(89)90020-8"},{"key":"e_1_3_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-88885-5_16"},{"key":"e_1_3_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007665907178"},{"key":"e_1_3_1_34_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2017.1322092"},{"key":"e_1_3_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15769-1_24"},{"key":"e_1_3_1_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.2967"},{"key":"e_1_3_1_37_1","doi-asserted-by":"crossref","unstructured":"Yehuda Koren Steffen Rendle and Robert Bell. 2021. Advances in collaborative filtering. Recommender systems handbook (2021) 91\u2013142.","DOI":"10.1007\/978-1-0716-2197-4_3"},{"key":"e_1_3_1_38_1","doi-asserted-by":"crossref","unstructured":"Dexter Kozen. 1979. Semantics of probabilistic programs. In 20th Annual Symposium on Foundations of Computer Science (FOCS 1979). IEEE 101\u2013114.","DOI":"10.1109\/SFCS.1979.38"},{"key":"e_1_3_1_39_1","doi-asserted-by":"crossref","unstructured":"Dexter Kozen. 1983. A probabilistic PDL. In Proceedings of the fifteenth annual ACM Symposium on Theory of computing. 291\u2013297.","DOI":"10.1145\/800061.808758"},{"key":"e_1_3_1_40_1","article-title":"Automatic variational inference in Stan","volume":"28","author":"Kucukelbir Alp","year":"2015","unstructured":"Alp Kucukelbir, Rajesh Ranganath, Andrew Gelman, and David Blei. 2015. Automatic variational inference in Stan. Advances in Neural Information Processing Systems 28 (2015).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_41_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729694"},{"key":"e_1_3_1_42_1","doi-asserted-by":"publisher","DOI":"10.1142\/p665"},{"key":"e_1_3_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_14"},{"key":"e_1_3_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1972.1054885"},{"key":"e_1_3_1_45_1","unstructured":"Vikash Mansinghka Daniel Selsam and Yura Perov. 2014. Venture: a higher-order probabilistic programming platform with programmable inference. arXiv preprint arXiv:1404.0099 (2014)."},{"key":"e_1_3_1_46_1","unstructured":"Brian Milch Bhaskara Marthi and Stuart Russell. 2004. BLOG: Relational modeling with unknown objects. In ICML 2004 workshop on statistical relational learning and its connections to other fields. 67\u201373."},{"key":"e_1_3_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3563341"},{"key":"e_1_3_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_1_49_1","unstructured":"Radford M Neal. 1999. Erroneous results in \u201cMarginal likelihood from the Gibbs output\u201d. minmeo University of Toronto (1999)."},{"key":"e_1_3_1_50_1","unstructured":"Robert Nishihara Thomas Minka and Daniel Tarlow. 2013. Detecting parameter symmetries in probabilistic models. arXiv preprint arXiv:1312.5386 (2013)."},{"key":"e_1_3_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-016-5558-8"},{"key":"e_1_3_1_52_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.9060"},{"key":"e_1_3_1_53_1","unstructured":"Fritz Obermeyer Eli Bingham Martin Jankowiak Neeraj Pradhan Justin Chiu Alexander Rush and Noah Goodman. 2019. Tensor variable elimination for plated factor graphs. In International Conference on Machine Learning. PMLR 4871\u20134880."},{"key":"e_1_3_1_54_1","unstructured":"Dilcia P\u00e9rez and Yamilet Quintana. 2006. A survey on the Weierstrass approximation theorem. arXiv preprint math\/0611038 (2006)."},{"key":"e_1_3_1_55_1","first-page":"733","volume-title":"IJCAI","author":"Pfeffer Avi","year":"2001","unstructured":"Avi Pfeffer. 2001. IBAL: A probabilistic rational programming language. In IJCAI. Citeseer, 733\u2013740."},{"key":"e_1_3_1_56_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-015-0805-z"},{"key":"e_1_3_1_57_1","doi-asserted-by":"crossref","unstructured":"Feras A Saad Martin C Rinard and Vikash K Mansinghka. 2021. SPPL: probabilistic programming with fast exact symbolic inference. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 804\u2013819.","DOI":"10.1145\/3453483.3454078"},{"key":"e_1_3_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64546-9"},{"key":"e_1_3_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1410219"},{"key":"e_1_3_1_60_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1986.10478240"},{"key":"e_1_3_1_61_1","doi-asserted-by":"crossref","unstructured":"David Tolpin Jan-Willem van de Meent Hongseok Yang and Frank Wood. 2016. Design and implementation of probabilistic programming language anglican. In Proceedings of the 28th Symposium on the Implementation and Application of Functional programming Languages. 1\u201312.","DOI":"10.1145\/3064899.3064910"},{"key":"e_1_3_1_62_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.72.1.20"},{"key":"e_1_3_1_63_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"e_1_3_1_64_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.80.268"},{"key":"e_1_3_1_65_1","unstructured":"Wolfram Research Inc. [n.d.]. Mathematica. https:\/\/www.wolfram.com\/mathematica"},{"key":"e_1_3_1_66_1","unstructured":"Yi Wu Siddharth Srivastava Nicholas Hay Simon Du and Stuart Russell. 2018. Discrete-continuous mixtures in probabilistic programming: Generalized semantics and inference algorithms. In International Conference on Machine Learning. PMLR 5343\u20135352."},{"key":"e_1_3_1_67_1","doi-asserted-by":"crossref","unstructured":"Xiaoxue Zhao Weinan Zhang and Jun Wang. 2013. Interactive collaborative filtering. In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. 1411\u20131420.","DOI":"10.1145\/2505515.2505690"},{"key":"e_1_3_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2019.06.004"},{"key":"e_1_3_1_69_1","unstructured":"Yuan Zhou Hongseok Yang Yee Whye Teh and Tom Rainforth. 2020. Divide conquer and combine: a new inference strategy for probabilistic programs with stochastic support. In International Conference on Machine Learning. PMLR 11534\u201311545."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632905","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3632905","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:02:04Z","timestamp":1751659324000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3632905"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,2]]},"references-count":68,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2024,1,2]]}},"alternative-id":["10.1145\/3632905"],"URL":"https:\/\/doi.org\/10.1145\/3632905","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,2]]},"assertion":[{"value":"2024-01-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}