“Controlling procedural modeling programs with stochastically-ordered sequential Monte Carlo” by Ritchie, Mildenhall, Goodman and Hanrahan

We present a method for controlling the output of procedural modeling programs using Sequential Monte Carlo (SMC). Previous probabilistic methods for controlling procedural models use Markov Chain Monte Carlo (MCMC), which receives control feedback only for completely-generated models. In contrast, SMC receives feedback incrementally on incomplete models, allowing it to reallocate computational resources and converge quickly. To handle the many possible sequentializations of a structured, recursive procedural modeling program, we develop and prove the correctness of a new SMC variant, Stochastically-Ordered Sequential Monte Carlo (SOSMC). We implement SOSMC for general-purpose programs using a new programming primitive: the stochastic future. Finally, we show that SOSMC reliably generates high-quality outputs for a variety of programs and control scoring functions. For small computational budgets, SOSMC’s outputs often score nearly twice as high as those of MCMC or normal SMC.

1. Andrieu, C., Doucet, A., and Holenstein, R. 2010. Particle Markov Chain Monte Carlo Methods. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 72, 3.Google ScholarCross Ref
2. Beneš, B., Šava, O., Měch, R., and Miller, G. 2011. Guided Procedural Modeling. In Proc. Eurographics 2011.Google Scholar
3. Bisiani, R. 1987. Beam Search. In Encyclopedia of Artificial Intelligence, S. Shapiro, Ed.Google Scholar
4. de Moura, A. L., and Ierusalimschy, R. 2004. Revisiting Coroutines. Tech. rep.Google Scholar
5. DeVito, Z., Hegarty, J., Aiken, A., Hanrahan, P., and Vitek, J. 2013. Terra: A Multi-stage Language for High-performance Computing. In Proc. PLDI 2013. Google ScholarDigital Library
6. Douc, R., and Cappe, O. 2005. Comparison of Resampling Schemes for Particle Filtering. In Proc. ISPA 2005.Google Scholar
7. Doucet, A., De Freitas, N., and Gordon, N., Eds. 2001. Sequential Monte Carlo Methods in Practice. Springer.Google Scholar
8. Fan, S. 2006. Sequential Monte Carlo Methods for Physically Based Rendering. PhD thesis. Google ScholarDigital Library
9. Gershman, S., and Goodman, N. D. 2014. Amortized Inference in Probabilistic Reasoning. In Proceedings of the Thirty-Sixth Annual Conference of the Cognitive Science Society.Google Scholar
10. Gilks, W. R., and Berzuini, C. 2001. Following a moving target—Monte Carlo inference for dynamic Bayesian models. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 63, 1.Google ScholarCross Ref
11. Goodman, N. D., and Stuhlmüller, A., 2014. The Design and Implementation of Probabilistic Programming Languages. Retrieved 2014/12/15 from http://dippl.org.Google Scholar
12. Goodman, N. D., Mansinghka, V. K., Roy, D. M., Bonawitz, K., and Tenenbaum, J. B. 2008. Church: a language for generative models. In Proc. of UAI 2008.Google Scholar
13. Gordon, N., Salmond, D., and Smith, A. 1993. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. Radar and Signal Processing, IEE Proceedings F 140, 2.Google Scholar
14. Halstead, Jr., R. H. 1985. MULTILISP: A Language for Concurrent Symbolic Computation. ACM Trans. Program. Lang. Syst. 7, 4. Google ScholarDigital Library
15. Hammersley, J. M., and Morton, K. W. 1954. Poor Man’s Monte Carlo. Journal of the Royal Statistical Society. Series B (Methodological) 16, 1.Google Scholar
16. Hello Games, 2014. No Man’s Sky. Retrieved 2014/12/18 from http://www.no-mans-sky.com/.Google Scholar
17. Hmlinen, P., Eriksson, S., Tanskanen, E., Kyrki, V., and Lehtinen, J. 2014. Online Motion Synthesis Using Sequential Monte Carlo. In Proc. SIGGRAPH 2014.Google Scholar
18. Kulkarni, T. D., Mansinghka, V. K., Kohli, P., and Tenenbaum, J. B. 2014. Inverse Graphics with Probabilistic CAD Models. CoRR.Google Scholar
19. Levy, R. P., Reali, F., and Griffiths, T. L. 2009. Modeling the effects of memory on human online sentence processing with particle filters. In In Proc. NIPS 2009.Google Scholar
20. Lindsten, F., Jordan, M. I., and Schön, T. B. 2014. Particle Gibbs with Ancestor Sampling. J. Mach. Learn. Res. 15, 1. Google ScholarDigital Library
21. Müller, P., Wonka, P., Haegler, S., Ulmer, A., and Van Gool, L. 2006. Procedural Modeling of Buildings. In In Proc. SIGGRAPH 2006. Google ScholarDigital Library
22. Měch, R., and Prusinkiewicz, P. 1996. Visual Models of Plants Interacting with Their Environment. In Proc. SIGGRAPH 1996. Google ScholarDigital Library
23. Paige, B., and Wood, F. 2014. A Compilation Target for Probabilistic Programming Languages. In Proc. ICML 2014.Google Scholar
24. Paige, B., Wood, F., Doucet, A., and Teh, Y. 2014. Asynchronous Anytime Sequential Monte Carlo. In Proc. NIPS 2014.Google Scholar
25. Pegoraro, V., Wald, I., and Parker, S. G. 2008. Sequential Monte Carlo Adaptation in Low-Anisotropy Participating Media. Computer Graphics Forum 27, 4. Google ScholarDigital Library
26. Procedural Reality, 2014. Limit Theory. Retrieved 2014/12/18 from http://ltheory.com.Google Scholar
27. Prusinkiewicz, P., JAMES, M., and Měch, R. 1994. Synthetic Topiary. In Proc. SIGGRAPH 1994. Google ScholarDigital Library
28. Ritchie, D., Lin, S., Goodman, N. D., and Hanrahan, P. 2015. Generating Design Suggestions under Tight Constraints with Gradient-based Probabilistic Programming. In Proc. Eurographics 2015.Google Scholar
29. Rosenbluth, M. N., and Rosenbluth, A. W. 1955. Monte Carlo Calculation of the Average Extension of Molecular Chains. The Journal of Chemical Physics 23, 2.Google ScholarCross Ref
30. Smith, A. F. M., and Gelfand, A. E. 1992. Bayesian Statistics without Tears: A Sampling-Resampling Perspective. The American Statistician 46, 2.Google Scholar
31. Stava, O., Pirk, S., Kratt, J., Chen, B., Mch, R., Deussen, O., and Benes, B. 2014. Inverse Procedural Modelling of Trees. Computer Graphics Forum 33, 6.Google ScholarDigital Library
32. Stewart, L., and McCarty, Jr., P. 1992. Use of Bayesian belief networks to fuse continuous and discrete information for target recognition, tracking, and situation assessment. Proc. SPIE.Google ScholarCross Ref
33. Talton, J. O., Lou, Y., Lesser, S., Duke, J., Měch, R., and Koltun, V. 2011. Metropolis Procedural Modeling. ACM Trans. Graph. 30, 2. Google ScholarDigital Library
34. Vanegas, C. A., Garcia-Dorado, I., Aliaga, D. G., Benes, B., and Waddell, P. 2012. Inverse Design of Urban Procedural Models. In Proc. SIGGRAPH Asia 2012. Google ScholarDigital Library
35. Veach, E., and Guibas, L. J. 1995. Optimally Combining Sampling Techniques for Monte Carlo Rendering. In Proc. SIGGRAPH 1995, SIGGRAPH ’95. Google ScholarDigital Library
36. Wingate, D., Stuhlmüller, A., and Goodman, N. D. 2011. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In Proc. AISTATS 2011.Google Scholar
37. Wong, M. T., Zongker, D. E., and Salesin, D. H. 1998. Computer-generated Floral Ornament. In In Proc. SIGGRAPH 1998. Google ScholarDigital Library
38. Wood, F., van De Meent, J. W., and Mansinghka, V. 2014. A New Approach to Probabilistic Programming Inference. In Proc. AISTATS 2014.Google Scholar
39. Xu, K., Zhang, H., Cohen-Or, D., and Chen, B. 2012. Fit and diverse: Set evolution for inspiring 3d shape galleries. In Proc. SIGGRAPH 2012, SIGGRAPH ’12. Google ScholarDigital Library
40. Yeh, Y.-T., Yang, L., Watson, M., Goodman, N. D., and Hanrahan, P. 2012. Synthesizing Open Worlds with Constraints Using Locally Annealed Reversible Jump MCMC. In Proc. SIGGRAPH 2012. Google ScholarDigital Library