{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:45:09Z","timestamp":1780994709252,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T00:00:00Z","timestamp":1639008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EPSRC Centre for Doctoral Training in Data Science"},{"DOI":"10.13039\/501100000266","name":"UK Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/L016427\/1"],"award-info":[{"award-number":["EP\/L016427\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000848","name":"University of Edinburgh","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000848","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["895827"],"award-info":[{"award-number":["895827"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>A central goal of probabilistic programming languages (PPLs) is to separate modelling from inference. However, this goal is hard to achieve in practice. Users are often forced to re-write their models to improve efficiency of inference or meet restrictions imposed by the PPL. Conditional independence (CI) relationships among parameters are a crucial aspect of probabilistic models that capture a qualitative summary of the specified model and can facilitate more efficient inference.<\/jats:p>\n          <jats:p>\n            We present an information flow type system for probabilistic programming that captures conditional independence (CI) relationships and show that, for a well-typed program in our system, the distribution it implements is guaranteed to have certain CI-relationships. Further, by using type inference, we can statically\n            <jats:italic>deduce<\/jats:italic>\n            which CI-properties are present in a specified model.\n          <\/jats:p>\n          <jats:p>\n            As a practical application, we consider the problem of how to perform inference on models with mixed discrete and continuous parameters. Inference on such models is challenging in many existing PPLs, but can be improved through a workaround, where the discrete parameters are used\n            <jats:italic>implicitly<\/jats:italic>\n            , at the expense of manual model re-writing. We present a source-to-source semantics-preserving transformation, which uses our CI-type system to automate this workaround by eliminating the discrete parameters from a probabilistic program. The resulting program can be seen as a hybrid inference algorithm on the original program, where continuous parameters can be drawn using efficient gradient-based inference methods, while the discrete parameters are inferred using variable elimination.\n          <\/jats:p>\n          <jats:p>\n            We implement our CI-type system and its example application in SlicStan: a compositional variant of Stan.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n          <\/jats:p>","DOI":"10.1145\/3490421","type":"journal-article","created":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T16:36:47Z","timestamp":1639067807000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Conditional Independence by Typing"],"prefix":"10.1145","volume":"44","author":[{"given":"Maria I.","family":"Gorinova","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew D.","family":"Gordon","sequence":"additional","affiliation":[{"name":"Microsoft Research and University of Edinburgh, Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles","family":"Sutton","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthijs","family":"V\u00e1k\u00e1r","sequence":"additional","affiliation":[{"name":"Utrecht University, Utrecht, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,9]]},"reference":[{"key":"e_1_3_3_2_1","first-page":"147","volume-title":"Symposium on Principles of Programming Languages","author":"Abadi Mart\u00edn","year":"1999","unstructured":"Mart\u00edn Abadi, Anindya Banerjee, Nevin Heintze, and Jon G. Riecke. 1999. A core calculus of dependency. In Symposium on Principles of Programming Languages. ACM, 147\u2013160."},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9180-4"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372895"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_3_3_6_1","first-page":"1","volume-title":"36th Annual ACM\/IEEE Symposium on Logic in Computer Science","author":"Bao Jialu","year":"2021","unstructured":"Jialu Bao, Simon Docherty, Justin Hsu, and Alexandra Silva. 2021. A bunched logic for conditional independence. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science. IEEE, 1\u201314."},{"key":"e_1_3_3_7_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3371123","article-title":"A probabilistic separation logic","volume":"4","author":"Barthe Gilles","year":"2019","unstructured":"Gilles Barthe, Justin Hsu, and Kevin Liao. 2019. A probabilistic separation logic. Proc. ACM on Program. Lang. 4, POPL (2019), 1\u201330.","journal-title":"Proc. ACM on Program. Lang."},{"key":"e_1_3_3_8_1","first-page":"30","article-title":"Hamiltonian Monte Carlo for hierarchical models","volume":"79","author":"Betancourt Michael","year":"2015","unstructured":"Michael Betancourt and Mark Girolami. 2015. Hamiltonian Monte Carlo for hierarchical models. Curr. Trends Bayesian Methodol. Applic. 79 (2015), 30.","journal-title":"Curr. Trends Bayesian Methodol. Applic."},{"key":"e_1_3_3_9_1","first-page":"115","volume-title":"12th International Conference on Uncertainty in Artificial Intelligence","author":"Boutilier Craig","year":"1996","unstructured":"Craig Boutilier, Nir Friedman, Moises Goldszmidt, and Daphne Koller. 1996. Context-specific independence in Bayesian networks. In 12th International Conference on Uncertainty in Artificial Intelligence. 115\u2013123."},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.18637\/jss.v076.i01"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314642"},{"key":"e_1_3_3_12_1","article-title":"A tutorial on hidden Markov models using Stan","author":"Damiano Luis","year":"2018","unstructured":"Luis Damiano, Brian Peterson, and Michael Weylandt. 2018. A tutorial on hidden Markov models using Stan. StanCon (2018). DOI:https:\/\/doi.org\/10.5281\/zenodo.1284341.","journal-title":"StanCon"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01379404"},{"key":"e_1_3_3_15_1","first-page":"257","volume-title":"19th Conference on Uncertainty in Artificial Intelligence","author":"Frey Brendan J.","year":"2002","unstructured":"Brendan J. Frey. 2002. Extending factor graphs so as to unify directed and undirected graphical models. In 19th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., San Francisco, CA, 257\u2013264."},{"key":"e_1_3_3_16_1","first-page":"1682","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Ge Hong","year":"2018","unstructured":"Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: A language for flexible probabilistic inference. In International Conference on Artificial Intelligence and Statistics. 1682\u20131690. DOI:http:\/\/proceedings.mlr.press\/v84\/ge18b.html."},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_4"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386006"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.3102\/1076998615606113"},{"key":"e_1_3_3_20_1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"European Symposium on Programming Languages and Systems","author":"Gordon Andrew D.","year":"2015","unstructured":"Andrew D. Gordon, Claudio V. Russo, Marcin Szymczak, Johannes Borgstr\u00f6m, Nicolas Rolland, Thore Graepel, and Daniel Tarlow. 2015. Probabilistic programs as spreadsheet queries. In European Symposium on Programming Languages and Systems(Lecture Notes in Computer Science, Vol. 9032). Springer, 1\u201325."},{"key":"e_1_3_3_21_1","first-page":"35","article-title":"Probabilistic programming with densities in SlicStan: Efficient, flexible, and deterministic","volume":"3","author":"Gorinova Maria I.","year":"2019","unstructured":"Maria I. Gorinova, Andrew D. Gordon, and Charles Sutton. 2019. Probabilistic programming with densities in SlicStan: Efficient, flexible, and deterministic. Proce. ACM Program. Lang. 3, POPL (2019), 35.","journal-title":"Proce. ACM Program. Lang."},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717761"},{"issue":"1","key":"e_1_3_3_23_1","first-page":"1593","article-title":"The No-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo.","volume":"15","author":"Hoffman Matthew D.","year":"2014","unstructured":"Matthew D. Hoffman and Andrew Gelman. 2014. The No-U-turn sampler: Adaptively setting path lengths in Hamiltonian Monte Carlo. J. Mach. Learn. Res. 15, 1 (2014), 1593\u20131623.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_3_24_1","article-title":"Dice: Compiling discrete probabilistic programs for scalable inference","author":"Holtzen Steven","year":"2020","unstructured":"Steven Holtzen, Guy Van den Broeck, and Todd Millstein. 2020. Dice: Compiling discrete probabilistic programs for scalable inference. arXiv preprint arXiv:2005.09089 (2020).","journal-title":"arXiv preprint arXiv:2005.09089"},{"key":"e_1_3_3_25_1","unstructured":"Uffe Kj\u00e6rulff. 1990. Triangulation of graphs-Algorithms giving small total state space. Research Report R 90-09. Department of Mathematics and Computer Science Aalborg University Denmark."},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1795555"},{"key":"e_1_3_3_27_1","first-page":"411","volume-title":"IEEE Symposium on Security and Privacy","author":"Lobo-Vesga Elisabet","year":"2020","unstructured":"Elisabet Lobo-Vesga, Alejandro Russo, and Marco Gaboardi. 2020. A programming framework for differential privacy with accuracy concentration bounds. In IEEE Symposium on Security and Privacy. IEEE, 411\u2013428."},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192409"},{"key":"e_1_3_3_29_1","volume-title":"Advances in Neural Information Processing Systems","author":"Minka Tom","year":"2009","unstructured":"Tom Minka and John Winn. 2009. Gates. In Advances in Neural Information Processing Systems, D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (Eds.), Vol. 21. Curran Associates, Inc. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2008\/file\/4b0a59ddf11c58e7446c9df0da541a84-Paper.pdf."},{"key":"e_1_3_3_30_1","unstructured":"T. Minka J. M. Winn J. P. Guiver S. Webster Y. Zaykov B. Yangel A. Spengler and J. Bronskill. 2014. Infer.NET 2.6. Microsoft Research Cambridge. Retrieved from http:\/\/research.microsoft.com\/infernet."},{"key":"e_1_3_3_31_1","article-title":"Effect handling for composable program transformations in Edward2","author":"Moore Dave","year":"2018","unstructured":"Dave Moore and Maria I. Gorinova. 2018. Effect handling for composable program transformations in Edward2. In International Conference on Probabilistic Programming. https:\/\/arxiv.org\/abs\/1811.06150.","journal-title":"I"},{"key":"e_1_3_3_32_1","volume-title":"Machine Learning: A Probabilistic Perspective","author":"Murphy Kevin P.","year":"2012","unstructured":"Kevin P. Murphy. 2012. Machine Learning: A Probabilistic Perspective. The MIT Press."},{"key":"e_1_3_3_33_1","first-page":"1037","article-title":"Delayed sampling and automatic Rao-Blackwellization of probabilistic programs","author":"Murray Lawrence M.","year":"2018","unstructured":"Lawrence M. Murray, Daniel Lund\u00e9n, Jan Kudlicka, David Broman, and Thomas B. Sch\u00f6n. 2018. Delayed sampling and automatic Rao-Blackwellization of probabilistic programs. In 21st International Conference on Artificial Intelligence and Statistics. 1037\u20131046. Retrieved from http:\/\/proceedings.mlr.press\/v84\/murray18a.html.","journal-title":"I"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2018.10.013"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29604-3_5"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1201\/b10905-6"},{"key":"e_1_3_3_37_1","article-title":"Discontinuous Hamiltonian Monte Carlo for sampling discrete parameters","author":"Nishimura Akihiko","year":"2017","unstructured":"Akihiko Nishimura, David Dunson, and Jianfeng Lu. 2017. Discontinuous Hamiltonian Monte Carlo for sampling discrete parameters. arXiv preprint arXiv:1705.08510 (2017).","journal-title":"arXiv preprint arXiv:1705.08510"},{"key":"e_1_3_3_38_1","article-title":"Tensor variable elimination for plated factor graphs","author":"Obermeyer Fritz","year":"2019","unstructured":"Fritz Obermeyer, Eli Bingham, Martin Jankowiak, Justin Chiu, Neeraj Pradhan, Alexander Rush, and Noah Goodman. 2019. Tensor variable elimination for plated factor graphs. In International Conference on Machine Learning.","journal-title":"I"},{"key":"e_1_3_3_39_1","article-title":"Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions","author":"Pakman A.","year":"2013","unstructured":"A. Pakman and L. Paninski. 2013. Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions. In International Conference on Advances in Neural Information Processing Systems.","journal-title":"I"},{"key":"e_1_3_3_40_1","article-title":"Composable effects for flexible and accelerated probabilistic programming in NumPyro","author":"Phan Du","year":"2019","unstructured":"Du Phan, Neeraj Pradhan, and Martin Jankowiak. 2019. Composable effects for flexible and accelerated probabilistic programming in NumPyro. arXiv preprint arXiv:1912.11554 (2019).","journal-title":"arXiv preprint arXiv:1912.11554"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345100"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.18626"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.55"},{"key":"e_1_3_3_44_1","article-title":"Stan language reference manual","author":"Team Stan Development","year":"2019","unstructured":"Stan Development Team. 2019a. Stan language reference manual. Version 2.26.0. Retrieved from http:\/\/mc-stan.org.","journal-title":"Version 2.26.0. Retrieved from http:\/\/mc-stan.org"},{"key":"e_1_3_3_45_1","article-title":"Stan user\u2019s guide","author":"Team Stan Development","year":"2019","unstructured":"Stan Development Team. 2019b. Stan user\u2019s guide. Version 2.26.0. Retrieved from http:\/\/mc-stan.org.","journal-title":"Version 2.26.0. Retrieved from http:\/\/mc-stan.org"},{"key":"e_1_3_3_46_1","unstructured":"Dustin Tran Matthew D. Hoffman Srinivas Vasudevan Christopher Suter Dave Moore Alexey Radul Matthew Johnson and Rif A. Saurous. 2018. Edward2: Simple distributed accelerated. Retrieved from https:\/\/github.com\/tensorflow\/probability\/tree\/master\/tensorflow_probability\/python\/edward2."},{"key":"e_1_3_3_47_1","article-title":"Pyro: A deep probabilistic programming language","author":"Labs Uber AI","year":"2017","unstructured":"Uber AI Labs. 2017. Pyro: A deep probabilistic programming language. Retrieved from http:\/\/pyro.ai\/.","journal-title":"http:\/\/pyro.ai\/"},{"key":"e_1_3_3_48_1","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-1996-42-304"},{"key":"e_1_3_3_49_1","first-page":"1314","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Winn John","year":"2012","unstructured":"John Winn. 2012. Causality with gates. In International Conference on Artificial Intelligence and Statistics. 1314\u20131322. Retrieved from http:\/\/proceedings.mlr.press\/v22\/winn12.html."},{"key":"e_1_3_3_50_1","first-page":"1024","volume-title":"17th International Conference on Artificial Intelligence and Statistics","author":"Wood Frank","year":"2014","unstructured":"Frank Wood, Jan Willem van de Meent, and Vikash Mansinghka. 2014. A new approach to probabilistic programming inference. In 17th International Conference on Artificial Intelligence and Statistics. 1024\u20131032."},{"key":"e_1_3_3_51_1","first-page":"171","volume-title":"Conference of the Canadian Society for Computational Studies of Intelligence","author":"Zhang Nevin Lianwen","year":"1994","unstructured":"Nevin Lianwen Zhang and David Poole. 1994. A simple approach to Bayesian network computations. In Conference of the Canadian Society for Computational Studies of Intelligence. Canadian Information Processing Society, 171\u2013178."},{"key":"e_1_3_3_52_1","first-page":"3194","volume-title":"Advances in Neural Information Processing Systems","author":"Zhang Yichuan","year":"2012","unstructured":"Yichuan Zhang, Zoubin Ghahramani, Amos J. Storkey, and Charles A. Sutton. 2012. Continuous relaxations for discrete Hamiltonian Monte Carlo. In Advances in Neural Information Processing Systems, F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (Eds.). Curran Associates, Inc., 3194\u20133202. Retrieved from http:\/\/papers.nips.cc\/paper\/4652-continuous-relaxations-for-discrete-hamiltonian-monte-carlo.pdf."},{"key":"e_1_3_3_53_1","volume-title":"International Conference on Advances in Neural Information Processing Systems","author":"Zhou Guangyao","year":"2020","unstructured":"Guangyao Zhou. 2020. Mixed Hamiltonian Monte Carlo for mixed discrete and continuous variables. In International Conference on Advances in Neural Information Processing Systems."},{"key":"e_1_3_3_54_1","volume-title":"International Conference on Artificial Intelligence and Statistics","author":"Zhou Yuan","year":"2019","unstructured":"Yuan Zhou, Bradley J. Gram-Hansen, Tobias Kohn, Tom Rainforth, Hongseok Yang, and Frank Wood. 2019. LF-PPL: A low-level first order probabilistic programming language for non-differentiable models. In International Conference on Artificial Intelligence and Statistics. Retrieved from http:\/\/proceedings.mlr.press\/v89\/zhou19b.html."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:43Z","timestamp":1750188643000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,9]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3490421"],"URL":"https:\/\/doi.org\/10.1145\/3490421","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,9]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}