Incremental inference for probabilistic programs. Cusumano-Towner, M. F., Bichsel, B., Gehr, T., Vechev, M., & Mansinghka, V. K. In *PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation*, pages 571–585, 2018. ACM.

Paper Link abstract bibtex

Paper Link abstract bibtex

We present a novel approach for approximate sampling in probabilistic programs based on incremental inference. The key idea is to adapt the samples for a program $P$ into samples for a program $Q$, thereby avoiding the expensive sampling computation for program $Q$. To enable incremental inference in probabilistic programming, our work: (i) introduces the concept of a trace translator which adapts samples from $P$ into samples of $Q$, (ii) phrases this translation approach in the context of sequential Monte Carlo (SMC), which gives theoretical guarantees that the adapted samples converge to the distribution induced by $Q$, and (iii) shows how to obtain a concrete trace translator by establishing a correspondence between the random choices of the two probabilistic programs. We implemented our approach in two different probabilistic programming systems and showed that, compared to methods that sample the program $Q$ from scratch, incremental inference can lead to orders of magnitude increase in efficiency, depending on how closely related $P$ and $Q$ are.

@inproceedings{towner2018incremental, title = {Incremental inference for probabilistic programs}, author = {Cusumano-Towner, Marco F. and Bichsel, Benjamin and Gehr, Timon and Vechev, Martin and Mansinghka, Vikash K.}, year = 2018, booktitle = {PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation}, pages = {571--585}, publisher = {ACM}, url_paper = {https://files.sri.inf.ethz.ch/website/papers/pldi18_interemental_inference_for_probabilistic_programs.pdf}, url_link = {https://dl.acm.org/citation.cfm?id=3192399}, abstract = {We present a novel approach for approximate sampling in probabilistic programs based on incremental inference. The key idea is to adapt the samples for a program $P$ into samples for a program $Q$, thereby avoiding the expensive sampling computation for program $Q$. To enable incremental inference in probabilistic programming, our work: (i) introduces the concept of a trace translator which adapts samples from $P$ into samples of $Q$, (ii) phrases this translation approach in the context of sequential Monte Carlo (SMC), which gives theoretical guarantees that the adapted samples converge to the distribution induced by $Q$, and (iii) shows how to obtain a concrete trace translator by establishing a correspondence between the random choices of the two probabilistic programs. We implemented our approach in two different probabilistic programming systems and showed that, compared to methods that sample the program $Q$ from scratch, incremental inference can lead to orders of magnitude increase in efficiency, depending on how closely related $P$ and $Q$ are.}, }

Downloads: 0

{"_id":"gMZkycoiy2vorShtc","bibbaseid":"cusumanotowner-bichsel-gehr-vechev-mansinghka-incrementalinferenceforprobabilisticprograms-2018","downloads":7,"creationDate":"2018-04-20T17:49:55.778Z","title":"Incremental inference for probabilistic programs","author_short":["Cusumano-Towner, M. F.","Bichsel, B.","Gehr, T.","Vechev, M.","Mansinghka, V. K."],"year":2018,"bibtype":"inproceedings","biburl":"probcomp.csail.mit.edu/papers.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"Incremental inference for probabilistic programs","author":[{"propositions":[],"lastnames":["Cusumano-Towner"],"firstnames":["Marco","F."],"suffixes":[]},{"propositions":[],"lastnames":["Bichsel"],"firstnames":["Benjamin"],"suffixes":[]},{"propositions":[],"lastnames":["Gehr"],"firstnames":["Timon"],"suffixes":[]},{"propositions":[],"lastnames":["Vechev"],"firstnames":["Martin"],"suffixes":[]},{"propositions":[],"lastnames":["Mansinghka"],"firstnames":["Vikash","K."],"suffixes":[]}],"year":"2018","booktitle":"PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation","pages":"571–585","publisher":"ACM","url_paper":"https://files.sri.inf.ethz.ch/website/papers/pldi18_interemental_inference_for_probabilistic_programs.pdf","url_link":"https://dl.acm.org/citation.cfm?id=3192399","abstract":"We present a novel approach for approximate sampling in probabilistic programs based on incremental inference. The key idea is to adapt the samples for a program $P$ into samples for a program $Q$, thereby avoiding the expensive sampling computation for program $Q$. To enable incremental inference in probabilistic programming, our work: (i) introduces the concept of a trace translator which adapts samples from $P$ into samples of $Q$, (ii) phrases this translation approach in the context of sequential Monte Carlo (SMC), which gives theoretical guarantees that the adapted samples converge to the distribution induced by $Q$, and (iii) shows how to obtain a concrete trace translator by establishing a correspondence between the random choices of the two probabilistic programs. We implemented our approach in two different probabilistic programming systems and showed that, compared to methods that sample the program $Q$ from scratch, incremental inference can lead to orders of magnitude increase in efficiency, depending on how closely related $P$ and $Q$ are.","bibtex":"@inproceedings{towner2018incremental,\ntitle = {Incremental inference for probabilistic programs},\nauthor = {Cusumano-Towner, Marco F. and Bichsel, Benjamin and Gehr, Timon and Vechev, Martin and Mansinghka, Vikash K.},\nyear = 2018,\nbooktitle = {PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation},\npages = {571--585},\npublisher = {ACM},\nurl_paper = {https://files.sri.inf.ethz.ch/website/papers/pldi18_interemental_inference_for_probabilistic_programs.pdf},\nurl_link = {https://dl.acm.org/citation.cfm?id=3192399},\nabstract = {We present a novel approach for approximate sampling in probabilistic programs based on incremental inference. The key idea is to adapt the samples for a program $P$ into samples for a program $Q$, thereby avoiding the expensive sampling computation for program $Q$. To enable incremental inference in probabilistic programming, our work: (i) introduces the concept of a trace translator which adapts samples from $P$ into samples of $Q$, (ii) phrases this translation approach in the context of sequential Monte Carlo (SMC), which gives theoretical guarantees that the adapted samples converge to the distribution induced by $Q$, and (iii) shows how to obtain a concrete trace translator by establishing a correspondence between the random choices of the two probabilistic programs. We implemented our approach in two different probabilistic programming systems and showed that, compared to methods that sample the program $Q$ from scratch, incremental inference can lead to orders of magnitude increase in efficiency, depending on how closely related $P$ and $Q$ are.},\n}\n\n","author_short":["Cusumano-Towner, M. F.","Bichsel, B.","Gehr, T.","Vechev, M.","Mansinghka, V. K."],"key":"towner2018incremental","id":"towner2018incremental","bibbaseid":"cusumanotowner-bichsel-gehr-vechev-mansinghka-incrementalinferenceforprobabilisticprograms-2018","role":"author","urls":{" paper":"https://files.sri.inf.ethz.ch/website/papers/pldi18_interemental_inference_for_probabilistic_programs.pdf"," link":"https://dl.acm.org/citation.cfm?id=3192399"},"metadata":{"authorlinks":{"mansinghka, v":"http://probcomp.csail.mit.edu/","cusumano-towner, m":"http://web.mit.edu.en2id.search.translate.goog/marcoct/www/"}},"html":""},"search_terms":["incremental","inference","probabilistic","programs","cusumano-towner","bichsel","gehr","vechev","mansinghka"],"keywords":[],"authorIDs":["3BTqPkyp87F3LdfbT","3C5h85woMNd5GaRiP","3aLDT4CEdr9WQpBic","3h44YL555EzhtTyov","3jwRKfKrCK8r4asRv","3sWyAGovNzzFZeFzb","464Mzt2HES7jktmMC","4KchZvW7W2rh3TFan","4QwQPXfYWxAfrqD3x","4YcH7NwtDKS68uEYh","585Ntjij9LqzHgJec","58e5112f03d5065b4a0000a9","5GyX8nSxnzPXAAriL","5XYQacne4xXLAyusX","5bff192d01686f1000000115","5de6d709abd988de010000f4","5de832ff4e3c5af301000218","5de928165d589edf01000191","5defe8db14db5cdf01000055","5deff4d314db5cdf0100012e","5df1cf751070c8ef010000ac","5df1d5751070c8ef010000fc","5df2c3bc79c00ade01000032","5df2e966b91ab0de010000b9","5df35944d617e5de010000c0","5df3ba9bec6029de010001ff","5df41f6d9d2522de010000b6","5df6ad3a31a37ade0100013e","5df6ca73f9318fdf01000177","5df76ca5952c76df0100011e","5df7b1c892a8e4df01000005","5df7bbc092a8e4df0100008a","5df7e63edc100cde010001c1","5df85415a0ca62df0100016c","5df86547b99bcff30100005e","5df92329d04b27df0100004c","5dfbb80bf6f0aede010000ec","5dfbd8534705b7de01000164","5dfbf6da4d4fb9de0100018d","5dfbff4fb371afde0100004b","5e011c2c28320fde010000e6","5e0429e6c51eb3de01000070","5e053342709177de01000196","5e095d9572022bde010000af","5e0b6a25e73cd6de0100009a","5e0df6ae45d2fdde010000c4","5e0e8d100a1d80f20100000a","5e0f3a572c4a31df01000054","5e0f48172c4a31df010000de","5e11ba8b2af340df010000ab","5e12af1b3f181ade01000090","5e1352de697554de010000ea","5e135a70697554de0100016f","5e13adfa0d0b99de01000133","5e14863808c265de010000d3","5e159116f1f31adf01000135","5e15aa3ee8bfcff20100016d","5e162fc6df1bb4de01000184","5e16ee965e8bcfdf010000be","5e175ca74df69dde010000a9","5e179848d954d8df01000083","5e18969f779abfdf010000ef","5e18a2b8779abfdf010001ee","5e191880412c5ade01000002","5e1a11a2cde53bde01000116","5e1aed275f3d2cdf01000123","5e1b8a407c0fe1df01000077","5e1ba2c361cb16df01000032","5e1c5c86e556c6de01000176","5e1cdc1dabed9bde010000bf","5e1dde194986afdf0100015b","5e1e26c2407a20de01000019","5e1e5c672e41a7de01000166","5e1f2d8107379ade010000b6","5e1f7bc108195af301000066","5e1f7f8008195af301000090","5e20acde5c2065de0100000d","5e20ba3d5c2065de010000db","5e2125b7d78fbbdf01000062","5e2205fa024c69df010000ca","5e24b9fb1a6264de0100011c","5e251a51b55b9edf01000074","5e25cf83f299d4de010001cc","5e2639f624c8a6de010000cb","5e2666dd581147f201000031","5e26822ad297d6de0100001f","5e270ca3f51e02de0100001f","5e2778b858994fde01000224","5e286c6b6ae365de0100011b","5e28a71d88416fde01000173","5e28e19ca3df5bdf010000ff","5e2a741f881468de01000008","5e2c8658ce5606de01000102","5e2ca638cca05fde01000009","5e2de707133023de0100009b","5e2e2f1ecc9e90e401000118","5e2ea7efb84405df0100007c","5e2ebda3c2015cde01000015","5e2ec219c2015cde01000055","5e2effa8e374eede01000104","5e2f54c926e5cadf0100012c","5e2f5fa326e5cadf01000312","5e305ee457a222df01000221","5e31c760b5384fde01000176","5e31c93cb5384fde01000193","5e329a80e17accde01000069","5e3312fe200286df01000117","5e3433c641f782de01000167","5e3495dc53b794de010000b4","5e34be67ed2109df010000b7","5e353ab3ba591ddf0100000f","5e36a8d77b975dde01000016","5e36e37db26a0fde0100003c","5e382c240691b8de010001ee","5e3880661f8af9e0010001d9","5e388c7d030bcadf010000a3","5e397ce6346d7cde010001fd","5e3991c6d14579de010001db","5e39cc6dd6538cdf0100015e","5e39d34cd6538cdf010001d1","5e39d6493687dddf01000020","5e39f362aa2adade01000038","5e3ad4901b85fadf01000033","5e3ae1bc1b85fadf01000133","5e3af26b55f0f2df01000041","5e3b098555f0f2df010001b9","5e3b2960255dcade01000047","5e3b3442255dcade0100011b","5e3b9b1b69c38bde0100002a","5e3c2ec634cd37de010000e9","5e3c6e9d67788ede01000110","5e3c9dcdf99721de01000076","5e3cdde75cd237de010000a4","5e3d2557c405ecde01000034","5e3d7fc696e576de010000c4","5e3dd760d51253de010000d6","5e3ecf0086a596de01000058","5e3ef0a4382e41df010000ba","5e3f47c777baf5df0100009f","5e3f4d0277baf5df010000d4","5e3f9974cecf86de0100017a","5e40136f17f17dde0100019b","5e4041f7668183de0100008a","5e40f69bfd6934df0100015f","5e420517ebe241de010000ff","5e42754de4402ade010000c3","5e428bc75ea111df010000bd","5e42c7eee7fe39df010000e7","5e43359c8957d0de0100009e","5e436014a37866de01000174","5e43f473547b4cdf0100004c","5e4418e1fdc393de010000de","5e445a86df3c2af301000191","5e445b80df3c2af3010001a0","5e4487f5ec14b3de01000094","5e44ce167759a7df0100013e","5e44ec83ab9cedde0100011d","5e453154605639de01000088","5e46bd088573d1de010000e5","5e49612b16841dde01000076","5e49c95eb63120f201000048","5e4abc2c15f6c7df010001ef","5e4b94db2d0ef5de010000aa","5e4ba4bb733a18de0100004e","5e4cc8630cc7d3de01000075","5e4da098e671efde0100007f","5e4dcfef682c99de01000169","5e4e0047cc196bde0100014c","5e4ea27764b624de010000a8","5e4f2095e5389bde0100011e","5e4f42208a3535f301000013","5e50af6de3d144df01000001","5e50afb4e3d144df01000002","5e50b11be3d144df01000013","5e54502988d190df01000016","5e553b5dca58a8df010000e3","5e55586ae89e5fde010000a6","5e557e89e11ab9df0100010f","5e55aa627d0846de01000096","5e55f822819fabdf01000028","5e56c16a96127bde010000ac","5e57501b18f14bdf01000058","5e5c1f8315d8f5de01000027","5e5c1fcb15d8f5de01000029","5e5cada2a9598ddf01000029","5e5d3b9b73eb2edf0100008b","5e5d5e1ead47bcde010000d8","5e5d676cad47bcde01000156","5e5d74840b73f6de01000093","5e5d7c490b73f6de01000142","5e5fb85c19c3fade010001f8","5e5fb8c519c3fade01000205","5e5fe2f05241b5de010000b5","5e6008bb13e3aede01000165","5e60094513e3aede01000172","5e600bbd13e3aede010001d7","5e600bec13e3aede010001e0","5e601c3ec064fcde010001c4","5e6108ef31c7d3de010001ef","5e613ef497c182e90100017c","5e613fea97c182e9010001b2","5e61451497c182e901000288","5e6177a5417d19de010001ca","5e61c964abaeaede0100010d","5e62a99408ebcade01000152","5e63c4ac74499adf01000108","5e659b015dd5c8de01000086","5e676de810be53de0100000a","5e67ef260e29d3de01000223","5e6866a7149172de010001c2","5e69a3dc23ebccde01000062","5e6b9b4138517edf0100000b","5kT7ojhuB22wGn6pt","5x3AEdxLnChwvZa8g","69vAtG6YtnrsSoazH","6Ffmir77DS8x3E6sx","6JEETkGR6ZRiAfczM","6TLgrWa44XWGyNXgP","6e2XFy229hLbFR99A","6huhEvSXfaqHXmkc3","6kmTHHgnc3REXGdrg","6oMC7fHcQChwbQx7f","6unES8FZeSC2g78sm","75bFNvjwbxXRG4yCg","7PnbdWfd9vxcGEmqs","7RNLSS6XLDPMrYuex","7RXMsKBr98X9uDG4u","7qwQRtBSKxFLoshsT","8DgYrcAKTA9mYeYdE","8eeAa2j6MpLZi53zn","9x6sTTNqAw2FaeeWG","9yWXZ5ebx92nLDhL2","A7MG4bLJGjd3nScQN","AM32xxyWAQ9cnvNr5","ANKFWzBqWy9E3pEaZ","BSch39FbG778QEiy5","BaD4cmvBYjC63mtCM","BkX37EvGx8eMaKWi2","BnEmPPGyZFoaBxcTQ","Bv3Zb4Heu6oao7LnR","CLPkk3fjJiHBM3Y8f","CqY7Kc6gRRDohbtu9","D8TuWoWXbPtuvvx2B","DY9xcsoTYxu4PcDug","DzywbfM9RtjEziNni","E3FPR2oSan5tuHkyw","E7NDYosNnpGkNTzcR","EEpw2vd5BnZwztHEi","EJPgdgL8DokTQ6b7a","EMHqbcQFmnuR7ii4v","EPdu3Was7iFf72Be8","EcbrbYRcyh2MnmkHB","Edfq2hw3azcDSTkEs","EtCE2kkfYCoWt2Ejw","G2XSrL9u7Zo4p75tM","GCTSKzhfXdZe7pE7k","GFWEb4Anh3SGRhyEm","GQFnFjkwarniwEv3W","Gnixb3SyT3PNWGhjd","HJLuNjpriEJ9QwHXT","J7d7XjpSZNthLLmzm","JJEoktem7ALREKDcG","JK4SPS2cSvf3cPQDP","Jf5chFhctxFvLLKoo","JwNWZf5AdLXSWjuq5","JyTgdrqLHBijngADE","K9aT6kJgHab2BrDZw","KCHLdJic3Xti28ycM","KtCvweD8r92ANqQ9s","LQ6EMYcvRAdqc6L5s","Lny2nNi3DiKEBXHpH","LpMtemC267GDsxYm7","M6GzhRQYa78gtC6P3","MeD9daTp4MWxpo7wi","MpjduyZMdMMeTCQar","MtTEKC4XxAQntH2m9","MzrNu3MqSeatEHDuB","N2AiqindFhfTWwzG9","NFGnmR7f5ZLhR3Y83","NjsqzFAPLtjHWDutm","NoLrzXojJ2yK7v3je","NuNFTPoNEJsvXiAdw","PEv4bHqvu98SoC7Nr","PGr3aYEWEcRsJTTMM","PMapsNxgG98GENsPZ","PbKBaE9nWH4yrgQsn","PyejnXwfbytABY8Ss","QcgXmZjQQehLf48uz","QxKTEMRJ7TMGuP2EX","R9CzgnpThCKSYQYQJ","RPDNs66wjvQvGCnmW","RX4f9LrmJvdsJgGNq","RXnvExamjXDBvfZ4T","RrA8QrSukyQLZuFLS","SCDCkFXictWDuwRnP","SDQcntjjZvnPFcWuS","ScZRPZu5ALEREpZNG","SvAeHjtw8uYu3ihPg","TGjnzins6tGHL8EPq","TRnXA3ibpxC4vKmBA","ThXMseKr9ALxxrwB7","W7GKJMGm3FPMm8wN3","W8ge27yKHbWdSnoWv","W93qCNzi5rc6NmKjR","WCiQS7jgbNPDayDoD","WEbj6a2uMBxmTmCZd","WK33EBjTc5HFEx9LY","Wza44JooxKS6dBCSY","XE66B9odchJ462xqj","XJAj2ncSnpwZq3Zuv","XQj7AQR5JurFtAY2c","YLFYg6mMNR3TckeMp","Ya8tcBERqHrtvpK5A","YhFgPXemga3EjrY4C","Yir99o9uLrhJXN4Yr","YrKg4oQjK3AC2nW89","ZP9wcHrqSwjcfXinA","ZcxBp4JDcaxLGykuQ","Zg27qChSFKznWgS3n","ZqkHZRiLR5QK4FFqt","aBumSK6KzzzLcQCcD","aWmEXD5Bd2HATh5f9","aa2t7mJiERxoLJcxW","azzu48Y9BFosGy6pT","bgWkatnia6jr5xayi","bnEjdLAA8CEAzfpS8","borKKcT3xxBpudQ64","bsgRA4rZFfBc8QYoc","cCeCRM6h4ucLQPJ4d","cFdSiDByk4WjY8CAq","cLDzEBnirbtjJNiiP","ccbF82t7WawnKZ4Rn","cdFMvAfHGmZgC2mf5","d8wXTv3AWGbjzpBHg","dH287JHPXSQxmbkaY","dXWXguojmFwXfC343","dahunb7yhMc7bg3P6","dcS3nv4fRYtjWdi2q","dmuH2prrwszZRG4Gy","enDRSjARpfJEky8wM","evFHRXtQiNy2Rbex6","fGznKFztBFTWKbXcC","fT5agwbbQsrQvHwjr","fxAe3pLLGAQzMiXtf","gvdAgNaohyM8q557x","h3bBqQSncYe7y9sBo","h7nTPA8M5zbg5J7xG","hFXd3NHqjqjt6EYoc","hPyxgq8atsySd5xn2","hd3fRad58ComrShen","hfdKshgYhSgxvHWPG","hnRkpQqfbxyJ3tkn9","hskMGaWwn79efdrq5","iAdbPwiGXYhkdQBWH","iR3L6GjNhtwHoEoFy","iRYtDaK9r3m8jN2Sn","iRiXZZjhB3zha5oX9","iiCzWFNEcEPqwcKvw","iqMpMab3yd9vLzPYB","jAL37CjxprJspwLaH","jSeZSdTc7fKqYKPus","jsDXue2QRhPNtXGQ4","kQFiTFKuns8wR9LzZ","kRND6owHip8yssCor","kx87asWLN6yk7X9fk","kyq6KHQpzZAdmThEk","mQFywaq3wPjebF2eL","mb8ShRjKsCuSuGHG8","mjqJxNnciHwXH7moa","n7WdrYhwgBQCu5kr8","nT3poDttXANjYSX6e","nqnh7MctWtHu9Eeri","o5tJCNRb3b7NvZM5q","oLh7xWSFokQyudb2P","pacmtwPmLBxQTyyCw","pc2Qt8icchs4CFKgX","pd36XDsh7HiCEHrnM","phaSyHZTTwLDFpqRo","pjdBNzfX6Fg3iNg3R","ptW8XHwvHRcc9fKB2","q2LtMHAiQoMT8Xchg","q8M8ogFCtJPP9gjRD","qWaJKLfpRcauovktX","qYp2Mk8JqoRXq7ESf","qZzTbPCMTYnccLMQF","qcv8BfuqP46w5TCgm","qid5XCfkD2WwgLS8R","rM5SKh2zyNfWuFtQq","rPbeYkxxnMztRpYJN","rTokX5ZPqXH7AW8Q3","rhHcLAtTLZ9L6wkZQ","rjMjv9Zs6uN62LBCw","rosk3uCrKbm4zsN9c","sEznPCcFHEgm6k4Jo","sJLcitenvms8PQKwq","sP5RZMXoWEGtK54L5","sbkDfL3X95r7RcQmj","snzsZS4ZoQsssH7jo","t59nTA2vifvAL62fu","tEzfQHo2dSBAcxkST","tGstYCAK9uNSeBdMr","tPh5GGfDKphEBoZQh","tf3aDwmjr4hxPxPhj","uZtecZgDRcNbzjRrS","ukjxjyKEfh7uZAsio","urrAXbxgWcpAZZYFn","uyux8pktYF6ssDoZf","v7a3d8AxWiyo9n8Fn","vj7jDESLnfMknrEuB","vsMXhpr8ETj9TD5z9","w8y4yWYWuWTzE6rjb","wBP9jvakyv829nNA4","wBghPtRisDCyTwmXo","x8CXyEP24LcT2oWjZ","xNSyGLEfPK8b9jsnn","xkufTn8vsJ3BtChuK","xmw7Z7X9BxL2T4TXF","yFdTcfMKi3gzMMyph","yQFLKvbmphB4J32Ju","yY2QrRhTF3HZGJMSj","yY6GA8DJonrxgDYB7","yjrJ3sgEPED7nwj9d","yjvi3LGSByST2m4p6","ynu4jgHH2ccNtszqw","zDXKsbAfHdB9Ng3Mc","zRWju2ET6AQ8fCBJD","zsfGvcy74bAeDKAiM"],"dataSources":["KjwPBikSY3GLxsjaT","PGvySWpKSvwM9TdfF"]}