“Synthesizing open worlds with constraints using locally annealed reversible jump MCMC” by Yeh, Yang, Watson, Goodman and Hanrahan

We present a novel Markov chain Monte Carlo (MCMC) algorithm that generates samples from transdimensional distributions encoding complex constraints. We use factor graphs, a type of graphical model, to encode constraints as factors. Our proposed MCMC method, called locally annealed reversible jump MCMC, exploits knowledge of how dimension changes affect the structure of the factor graph. We employ a sequence of annealed distributions during the sampling process, allowing us to explore the state space across different dimensionalities more freely. This approach is motivated by the application of layout synthesis where relationships between objects are characterized as constraints. In particular, our method addresses the challenge of synthesizing open world layouts where the number of objects are not fixed and optimal configurations for different numbers of objects may be drastically different. We demonstrate the applicability of our approach on two open world layout synthesis problems: coffee shops and golf courses.

1. Alexander, C., Ishikawa, S., and Silverstein, M. 1977. A Pattern Language: Towns, Buildings, Construction. Oxford University Press, New York.Google Scholar
2. Frey, B. 2003. Extending factor graphs so as to unify directed and undirected graphical models. In Proceedings of the Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03), Morgan Kaufmann, San Francisco, CA, 257–26. Google ScholarDigital Library
3. Frydenberg, M. 1990. The chain graph Markov property. Scandinavian Journal of Statistics 17, 4, pp. 333–353.Google Scholar
4. Geman, S., and Geman, D. 1984. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6, 721–741. Google ScholarDigital Library
5. Goodman, N. D., Mansinghka, V. K., Roy, D. M., Bonawitz, K., and Tenenbaum, J. B. 2008. Church: a language for generative models. Uncertainty in Artificial Intelligence 2008, 220–229.Google Scholar
6. Graves, R., and Cornish, G. 1998. Golf course design. J. Wiley.Google Scholar
7. Green, P. J., and Mira, A. 1999. Delayed rejection in reversible jump metropolis-hastings. Biometrika 88, 1035–1053.Google ScholarCross Ref
8. Green, P. J. 1995. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika 82, 711–732.Google ScholarCross Ref
9. Hastings, W. K. 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 1, pp. 97–109.Google ScholarCross Ref
10. Koller, D., and Friedman, N. 2009. Probabilistic graphical models. MIT Press. Google ScholarDigital Library
11. Kschischang, F. R., Frey, B. J., and Loeliger, H.-A. 2001. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory 47, 498–519. Google ScholarDigital Library
12. Liu, J. S., Liang, F., and Wong, W. H. 2000. The multiple-try method and local optimization in Metropolis sampling. Journal of the American Statistical Association 95, 449 (Mar.), 121+.Google ScholarCross Ref
13. Lunn, D. J., Thomas, A., Best, N., and Spiegelhalter, D. 2000. Winbugs – a Bayesian modelling framework: Concepts, structure, and extensibility. Statistics and Computing 10, 4, 325–337. Google ScholarDigital Library
14. McCallum, A., Schultz, K., and Singh, S. 2009. FACTORIE: Probabilistic programming via imperatively defined factor graphs. In Advances in Neural Information Processing Systems 22, Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, Eds., 1249–1257.Google Scholar
15. Merrell, P., Schkufza, E., Li, Z., Agrawala, M., and Koltun, V. 2011. Interactive furniture layout using interior design guidelines. ACM Trans. Graph. 30 (August), 87:1–87:10. Google ScholarDigital Library
16. Milch, B., Marthi, B., Russell, S., Sontag, D., Ong, D. L., and Kolobov, A. 2005. BLOG: Probabilistic models with unknown objects. In IJCAI’05: Proceedings of the 19th international joint conference on Artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1352–1359. Google ScholarDigital Library
17. Mira, A. 2001. On Metropolis-Hastings algorithms with delayed rejection. Metron 59, 3–4.Google Scholar
18. Neal, R. 1994. Sampling from multimodal distributions using tempered transitions. Statistics and Computing 6, 353–366.Google ScholarCross Ref
19. Pfeffer, A. 2007. Sampling with memoization. In AAAI’07, 1263–1270. Google ScholarDigital Library
20. Richardson, M., and Domingos, P. 2006. Markov logic networks. Machine Learning 62, 1, 107–136. Google ScholarDigital Library
21. Talton, J. O., Lou, Y., Lesser, S., Duke, J., Měch, R., and Koltun, V. 2011. Metropolis procedural modeling. ACM Trans. Graph. 30 (April), 11:1–11:14. Google ScholarDigital Library
22. Tjelmeland, H., and Hegstad, B. K. 1999. Mode jumping proposals in MCMC. Scandinavian Journal of Statistics 28, 205–223.Google ScholarCross Ref
23. Yu, L.-F., Yeung, S. K., Tang, C.-K., Terzopoulos, D., Chan, T. F., and Osher, S. 2011. Make it home: Automatic optimization of furniture arrangement. ACM Transactions on Graphics 30, 4, 86. Google ScholarDigital Library