Bayesian program synthesis

<h2 id="the-framework">The framework</h2>
<p>Bayesian program synthesis has been described as a framework related to and utilizing probabilistic programming. In BPS, probabilistic programs are generated that are themselves priors over a space of probabilistic programs. This strategy allows automatic synthesis of new programs via probabilistic inference and is achieved by the composition of modular component programs. 
</p><p>The modularity in BPS allows inference to work on and test smaller probabilistic programs before being integrated into a larger model.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p><p>This framework can be contrasted with the family of automated <a href="/facts/Program_synthesis/IK3gcrfp">program synthesis</a> fields, which include <a href="/facts/Programming_by_example/p3Qo41Kb">programming by example</a> and <a href="/facts/Programming_by_demonstration/k4Kewbkx">programming by demonstration</a>. The goal in such fields is to find the best program that satisfies some constraint. In traditional program synthesis, for instance, verification of logical constraints reduce the state space of possible programs, allowing more efficient search to find an optimal program. Bayesian program synthesis differs both in that the constraints are probabilistic and the output is itself a distribution over programs that can be further refined.
</p><p>Additionally, Bayesian program synthesis can be contrasted to the work on Bayesian program learning, where probabilistic program components are hand-written, pre-trained on data, and then hand assembled in order to recognize handwritten characters.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Probabilistic_programming_language/73uGIo5w">Probabilistic programming language</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li>Commentary on BPS by David Garrity: <a href="http://www.bnn.ca/video/artificial-intelligence-to-see-significant-progress-in-2017-gva~1082352">Artificial Intelligence to see Significant Progress in 2017</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Saad, Feras A.; Cusumano-Towner, Marco F.; Schaechtle, Ulrich; Rinard, Martin C.; Mansinghka, Vikash K. (January 2019). "Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling". Proc. ACM Program. Lang. 3 (POPL): 37:1–37:32. arXiv:1907.06249. Bibcode:2019arXiv190706249S. doi:10.1145/3290350. ISSN 2475-1421. S2CID 53697125. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Talking Machines: Probabilistic programming, with Ben Vigoda | Robohub". robohub.org. Retrieved 2017-03-04. <a href="http://robohub.org/talking-machines-probabilistic-programming-with-ben-vigoda/" target="_blank">http://robohub.org/talking-machines-probabilistic-programming-with-ben-vigoda/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Lake, Brenden M.; Salakhutdinov, Ruslan; Tenenbaum, Joshua B. (2015-12-11). "Human-level concept learning through probabilistic program induction". Science. 350 (6266): 1332–1338. Bibcode:2015Sci...350.1332L. doi:10.1126/science.aab3050. ISSN 0036-8075. PMID 26659050. <a href="https://doi.org/10.1126%2Fscience.aab3050" target="_blank">https://doi.org/10.1126%2Fscience.aab3050</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Bayesian program synthesis open-in-new

Bayesian program synthesis