Elamur Research
☰
home / papers / 2016 / The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables

The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive license to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1611.00712

Summary

The reparameterization trick lets gradients pass through continuous random nodes in stochastic computation graphs. Discrete nodes cannot use it, so they usually depend on score-function estimators, which are unbiased but often noisy and need surrogate objectives. Maddison, Mnih and Teh propose the Concrete distribution, a continuous relaxation of categorical variables. It is a family of distributions on the probability simplex with closed-form densities.

A Concrete sample is built from the Gumbel-Max trick: add Gumbel noise to log-probabilities, then apply a softmax with a temperature λ in place of the hard argmax. When the temperature goes to zero, the samples become exact one-hot discrete draws. During training, the relaxed samples and their densities replace the discrete ones, which gives biased but low-variance gradients through ordinary automatic differentiation. At test time, the original discrete graph is evaluated.

On density estimation and structured prediction with MNIST and Omniglot, the relaxation is competitive with the score-function method VIMCO, sometimes better and sometimes worse. It needs no special-case gradient code.

Key points

  • Sampling a Concrete(α, λ) variable means applying a temperature-scaled softmax to log α plus independent Gumbel noise. A binary variant, BinConcrete, uses logistic noise and a sigmoid.
  • The relaxation was benchmarked against the score-function estimators VIMCO and NVIL. The score-function models needed early stopping because they overfit more readily.
  • The authors tuned temperatures separately for prior and posterior, with no annealing:
    • binary: prior 1/2, posterior 2/3
    • 4-ary: prior 2/3, posterior 1
    • 8-ary: prior 2/5, posterior 2/3
  • Training used Adam for 10⁷ steps with minibatch size 64. Hyperparameters were chosen by grid search on the MNIST validation set.
  • In the appendix results, the binary 240H∼240H∼784V model reaches 86.0 test NLL on MNIST with the m = 50 importance-weighted bound. Binary layers generally did as well as or better than 4-ary and 8-ary layers.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Other

Cited by

210 papers of our library cite it (of the 140673 whose bibliographies we read); 5 of them have a page here, 205 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1611.00712 · arXiv 1611.00712

@misc{maddison2016concrete,
  title = {{The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables}},
  author = {Maddison, Chris J. and Mnih, Andriy and Teh, Yee Whye},
  year = {2016},
  doi = {10.48550/arxiv.1611.00712},
  eprint = {1611.00712},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1611.00712}
}

References

50 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Martı́n Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenbe… find
  2. J Aitchison. A general class of distributions on the simplex. Journal of the Royal Statistical Society. Series B (Methodological), pp. 136–146, 1985. find
  3. J Atchison and Sheng M Shen. Logistic-normal distributions: Some properties and uses. Biometrika, 67(2):261–272, 1980. find
  4. Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432, 2013. find
  5. David Blei and John Lafferty. Correlated topic models. 2006. find
  6. Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. ICLR, 2016. find
  7. Robert J Connor and James E Mosimann. Concepts of independence for proportions with a generalization of the dirichlet distribution. Journal of the American Statistical Association, 64(325): 194–206, 1969. find
  8. Stefano Favaro, Georgia Hadjicharalambous, and Igor Prünster. On a class of distributions on the simplex. Journal of Statistical Planning and Inference, 141(9):2987 – 3004, 2011. find
  9. Brendan Frey. Continuous sigmoidal belief networks trained using slice sampling. In NIPS, 1997. find
  10. Michael C Fu. Gradient estimation. Handbooks in operations research and management science, 13:575–616, 2006. find
  11. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Aistats, volume 9, pp. 249–256, 2010. find
  12. Peter W Glynn. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33(10):75–84, 1990. find
  13. Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538 (7626):471–476, 2016. find
  14. Evan Greensmith, Peter L. Bartlett, and Jonathan Baxter. Variance reduction techniques for gradient estimates in reinforcement learning. JMLR, 5, 2004. find
  15. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems, pp. 1828–1836, 2015. find
  16. Karol Gregor, Ivo Danihelka, Andriy Mnih, Charles Blundell, and Daan Wierstra. Deep autoregressive networks. arXiv preprint arXiv:1310.8499, 2013. — [arXiv:1310.8499](https://arxiv.org/abs/1310.8499) find
  17. Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Jimenez Rezende, and Daan Wierstra. Draw: A recurrent neural network for image generation. arXiv preprint arXiv:1502.04623, 2015. find
  18. Shixiang Gu, Sergey Levine, Ilya Sutskever, and Andriy Mnih. MuProp: Unbiased backpropagation for stochastic neural networks. ICLR, 2016. find
  19. Emil Julius Gumbel. Statistical theory of extreme values and some practical applications: a series of lectures. Number 33. US Govt. Print. Office, 1954. find
  20. Tamir Hazan and Tommi Jaakkola. On the partition function and random maximum a-posteriori perturbations. In ICML, 2012. find
  21. Tamir Hazan, George Papandreou, and Daniel Tarlow. Perturbation, Optimization, and Statistics. MIT Press, 2016. find
  22. Matthew D Hoffman, David M Blei, Chong Wang, and John William Paisley. Stochastic variational inference. JMLR, 14(1):1303–1347, 2013. find
  23. E. Jang, S. Gu, and B. Poole. Categorical Reparameterization with Gumbel-Softmax. ArXiv e-prints, November 2016. find our card
  24. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. find
  25. Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013. find our card
  26. Diederik P Kingma and Max Welling. Auto-encoding variational bayes. ICLR, 2014. find our card
  27. Tomáš Kočiský, Gábor Melis, Edward Grefenstette, Chris Dyer, Wang Ling, Phil Blunsom, and Karl Moritz Hermann. Semantic parsing with semi-supervised sequential autoencoders. In EMNLP, 2016. find
  28. R. Duncan Luce. Individual Choice Behavior: A Theoretical Analysis. New York: Wiley, 1959. find
  29. Chris J Maddison. A Poisson process model for Monte Carlo. In Tamir Hazan, George Papandreou, and Daniel Tarlow (eds.), Perturbation, Optimization, and Statistics, chapter 7. MIT Press, 2016. find
  30. Chris J Maddison, Daniel Tarlow, and Tom Minka. A ∗ Sampling. In NIPS, 2014. find
  31. Andriy Mnih and Karol Gregor. Neural variational inference and learning in belief networks. In ICML, 2014. find
  32. Andriy Mnih and Danilo Jimenez Rezende. Variational inference for monte carlo objectives. In ICML, 2016. find
  33. Volodymyr Mnih, Nicolas Heess, Alex Graves, and koray kavukcuoglu. Recurrent Models of Visual Attention. In NIPS, 2014. find
  34. Christian A Naesseth, Francisco JR Ruiz, Scott W Linderman, and David M Blei. Rejection sampling variational inference. arXiv preprint arXiv:1610.05683, 2016. — [arXiv:1610.05683](https://arxiv.org/abs/1610.05683) find
  35. John William Paisley, David M. Blei, and Michael I. Jordan. Variational bayesian inference with stochastic search. In ICML, 2012. find
  36. George Papandreou and Alan L Yuille. Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. In ICCV, 2011. find
  37. Tapani Raiko, Mathias Berglund, Guillaume Alain, and Laurent Dinh. Techniques for learning binary stochastic feedforward neural networks. arXiv preprint arXiv:1406.2989, 2014. — [arXiv:1406.2989](https://arxiv.org/abs/1406.2989) find
  38. Rajesh Ranganath, Sean Gerrish, and David M. Blei. Black box variational inference. In AISTATS, 2014. find
  39. William S Rayens and Cidambi Srinivasan. Dependence properties of generalized liouville distributions on the simplex. Journal of the American Statistical Association, 89(428):1465–1470, 1994. find
  40. Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In ICML, 2014. find our card
  41. Francisco JR Ruiz, Michalis K Titsias, and David M Blei. The generalized reparameterization gradient. arXiv preprint arXiv:1610.02287, 2016. — [arXiv:1610.02287](https://arxiv.org/abs/1610.02287) find
  42. Ruslan Salakhutdinov and Geoffrey Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7):969–978, 2009. find
  43. Ruslan Salakhutdinov and Iain Murray. On the quantitative analysis of deep belief networks. In ICML, 2008. find
  44. John Schulman, Nicolas Heess, Theophane Weber, and Pieter Abbeel. Gradient estimation using stochastic computation graphs. In NIPS, 2015. find
  45. Theano Development Team. Theano: A Python framework for fast computation of mathematical expressions. arXiv e-prints, abs/1605.02688, May 2016. URL http://arxiv.org/abs/1605.02688. ↗ our card
  46. Michalis Titsias and Miguel Lázaro-Gredilla. Doubly stochastic variational bayes for non-conjugate inference. In Tony Jebara and Eric P. Xing (eds.), ICML, 2014. find
  47. Michalis Titsias and Miguel Lázaro-Gredilla. Local expectation gradients for black box variational inference. In NIPS, 2015. find
  48. Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229–256, 1992. find
  49. Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In ICML, 2015. find our card
  50. John I Yellott. The relationship between luce’s choice axiom, thurstone’s theory of comparative judgment, and the double exponential distribution. Journal of Mathematical Psychology, 15(2): 109–144, 1977. find