1 Search Results for "Samuel, Selva"


Document
A Provably Correct Sampler for Probabilistic Programs

Authors: Chung-Kil Hur, Aditya V. Nori, Sriram K. Rajamani, and Selva Samuel

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)


Abstract
We consider the problem of inferring the implicit distribution specified by a probabilistic program. A popular inference technique for probabilistic programs called Markov Chain Monte Carlo or MCMC sampling involves running the program repeatedly and generating sample values by perturbing values produced in "previous runs". This simulates a Markov chain whose stationary distribution is the distribution specified by the probabilistic program. However, it is non-trivial to implement MCMC sampling for probabilistic programs since each variable could be updated at multiple program points. In such cases, it is unclear which values from the "previous run" should be used to generate samples for the "current run". We present an algorithm to solve this problem for the general case and formally prove that the algorithm is correct. Our algorithm handles variables that are updated multiple times along the same path, updated along different paths in a conditional statement, or repeatedly updated inside loops, We have implemented our algorithm in a tool called InferX. We empirically demonstrate that InferX produces the correct result for various benchmarks, whereas existing tools such as R2 and Stan produce incorrect results on several of these benchmarks.

Cite as

Chung-Kil Hur, Aditya V. Nori, Sriram K. Rajamani, and Selva Samuel. A Provably Correct Sampler for Probabilistic Programs. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 475-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{hur_et_al:LIPIcs.FSTTCS.2015.475,
  author =	{Hur, Chung-Kil and Nori, Aditya V. and Rajamani, Sriram K. and Samuel, Selva},
  title =	{{A Provably Correct Sampler for Probabilistic Programs}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{475--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.475},
  URN =		{urn:nbn:de:0030-drops-56553},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.475},
  annote =	{Keywords: Probabilistic Programming, Program Correctness, Probabilistic Inference, Markov Chain Monte Carlo Sampling}
}
  • Refine by Author
  • 1 Hur, Chung-Kil
  • 1 Nori, Aditya V.
  • 1 Rajamani, Sriram K.
  • 1 Samuel, Selva

  • Refine by Classification

  • Refine by Keyword
  • 1 Markov Chain Monte Carlo Sampling
  • 1 Probabilistic Inference
  • 1 Probabilistic Programming
  • 1 Program Correctness

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail