Elamur Research
☰
home / papers / 2021 / Structured Denoising Diffusion Models in Discrete State-Spaces

Structured Denoising Diffusion Models in Discrete State-Spaces

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 4.0 (arXiv)" does not allow redistributing the text itself. Original — arxiv.org/pdf/2107.03006

Summary

Most diffusion generative models rely on continuous Gaussian noise. That fits images and audio but not inherently discrete data such as text or quantized pixels. Earlier discrete versions spread corruption uniformly across categories and had not proven competitive at scale. The authors (Google Research) propose D3PMs (Discrete Denoising Diffusion Probabilistic Models). In this framework, the forward corruption is defined by a chosen Markov transition matrix applied independently to each token or pixel. This lets domain knowledge shape the noise. Options include a discretized Gaussian kernel for ordinal pixel values, nearest neighbours in embedding space for tokens, and an absorbing [MASK] state that links diffusion to BERT-style masked and autoregressive models. They also add an auxiliary cross-entropy term to the variational bound and introduce noise schedules based on mutual information. Experiments cover character-level text, LM1B with its large vocabulary, and CIFAR-10. On CIFAR-10, D3PMs approach the continuous DDPM in sample quality and surpass it in log-likelihood. The main lesson is that the transition matrix is a central design choice for discrete diffusion.

Key points

  • D3PM generalizes the binary diffusion of Sohl-Dickstein et al. and the uniform multinomial diffusion of Hoogeboom et al. (called D3PM-uniform here). It adds absorbing-state, discretized Gaussian and embedding nearest-neighbour transition matrices. For images, the grey pixel serves as the [MASK] token.
  • The hybrid loss L_λ combines L_vb with a cross-entropy denoising term. It worked best with λ = 0.001 and clearly beat pure L_vb training on CIFAR-10. Larger λ helped early in training but led to worse final NLL and FID.
  • On CIFAR-10 with L_vb, D3PM Gauss beat the absorbing and uniform variants on IS, FID and NLL. The best model was D3PM Gauss + logistic, trained with L_λ and using a truncated logistic reverse parameterization.
  • On text, D3PMs strongly outperform non-autoregressive baselines on character-level generation and scale to large vocabularies and long sequences on LM1B.
  • Limitations: the models still trail strong autoregressive models like Transformer XL on text, and continuous diffusion still gives better image quality. The authors also note that IS and FID are biased toward their training distributions.

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

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

Cite

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

@misc{austin2021structured,
  title = {{Structured Denoising Diffusion Models in Discrete State-Spaces}},
  author = {Austin, Jacob and Johnson, Daniel D. and Ho, Jonathan and Tarlow, Daniel and Berg, Rianne van den},
  year = {2021},
  doi = {10.48550/arxiv.2107.03006},
  eprint = {2107.03006},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2107.03006}
}

References

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

  1. Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-Level language modeling with deeper Self-Attention. arXiv preprint arXiv:1808.04444, August 2018. find
  2. Yoshua Bengio, Li Yao, Guillaume Alain, and Pascal Vincent. Generalized denoising Auto-Encoders as generative models. arXiv preprint arXiv:1305.6663, May 2013. — [arXiv:1305.6663](https://arxiv.org/abs/1305.6663) find
  3. James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/google/jax. ↗
  4. Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2019. find
  5. William Chan, Chitwan Saharia, Geoffrey Hinton, Mohammad Norouzi, and Navdeep Jaitly. Imputer: Sequence modelling via imputation and dynamic programming. In International Conference on Machine Learning, pages 1403–1413. PMLR, 2020. find
  6. Ciprian Chelba, Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, and Tony Robinson. One billion word benchmark for measuring progress in statistical language modeling. arXiv preprint arXiv:1312.3005, December 2013. find our card
  7. Nanxin Chen, Yu Zhang, Heiga Zen, Ron J Weiss, Mohammad Norouzi, and William Chan. WaveGrad: Estimating gradients for waveform generation. arXiv preprint arXiv:2009.00713, September 2020. — [arXiv:2009.00713](https://arxiv.org/abs/2009.00713) find
  8. Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel. PixelSNAIL: An improved autoregressive generative model. In International Conference on Machine Learning, pages 863–871, 2018. find
  9. Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904.10509, 2019. find
  10. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdinov. Transformer-XL: Attentive language models beyond a Fixed-Length context. arXiv preprint arXiv:1901.02860, January 2019. find
  11. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, October 2018. find
  12. Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using Real NVP. arXiv preprint arXiv:1605.08803, 2016. — [arXiv:1605.08803](https://arxiv.org/abs/1605.08803) find
  13. W Feller. On the theory of stochastic processes, with particular reference to applications. In Proceedings of the [First] Berkeley Symposium on Mathematical Statistics and Probability. The Regents of the University of California, 1949. find
  14. Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer. Mask-Predict: Parallel decoding of conditional masked language models. arXiv preprint arXiv:1904.09324, April 2019. find our card
  15. Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pages 2672–2680, 2014. find
  16. Jiatao Gu, Changhan Wang, and Jake Zhao. arXiv:1905.11006, May 2019. — [arXiv:1905.11006](https://arxiv.org/abs/1905.11006) find
  17. Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee. Flax: A neural network library and ecosystem for JAX, 2020. URL http://github.com/google/flax. ↗
  18. Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local Nash equilibrium. In Advances in Neural Information Processing Systems, pages 6626–6637, 2017. find
  19. Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems, pages 6840–6851, 2020. find
  20. Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Towards non-autoregressive language models. arXiv preprint arXiv:2102.05379, 2021. — [arXiv:2102.05379](https://arxiv.org/abs/2102.05379) find
  21. Aapo Hyvärinen, Juha Karhunen, and Erkki Oja. Independent component analysis, volume 46. John Wiley & Sons, 2004. find
  22. Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. arXiv preprint arXiv:2006.06676v1, 2020. — [arXiv:2006.06676](https://arxiv.org/abs/2006.06676) find
  23. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015. find
  24. Diederik P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, pages 10215–10224, 2018. find
  25. Diederik P Kingma and Max Welling. Auto-encoding variational Bayes. arXiv preprint arXiv:1312.6114, 2013. find our card
  26. Zhifeng Kong, Wei Ping, Jiaji Huang, Kexin Zhao, and Bryan Catanzaro. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint arXiv:2009.09761, 2020. — [arXiv:2009.09761](https://arxiv.org/abs/2009.09761) find
  27. Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009. find
  28. Matt Mahoney. Text8 dataset. http://mattmahoney.net/dc/textdata, 2011. Accessed: 2021-5-24. ↗
  29. Gautam Mittal, Jesse Engel, Curtis Hawthorne, and Ian Simon. Symbolic music generation with diffusion models. arXiv preprint arXiv:2103.16091, March 2021. — [arXiv:2103.16091](https://arxiv.org/abs/2103.16091) find
  30. Alex Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. arXiv preprint arXiv:2102.09672, 2021. — [arXiv:2102.09672](https://arxiv.org/abs/2102.09672) find
  31. Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. arXiv preprint arXiv:2003.00638, March 2020. — [arXiv:2003.00638](https://arxiv.org/abs/2003.00638) find
  32. George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. arXiv preprint arXiv:1912.02762, 2019. — [arXiv:1912.02762](https://arxiv.org/abs/1912.02762) find
  33. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683, 2020. Levenshtein transformer. arXiv preprint find
  34. Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International Conference on Machine Learning, pages 1530–1538, 2015. find
  35. Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International Conference on Machine Learning, pages 1278–1286, 2014. find our card
  36. Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-Net: Convolutional networks for biomedical image segmentation. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 234–241. Springer, 2015. find our card
  37. Laura Ruis, Mitchell Stern, Julia Proskurnia, and William Chan. Insertion-deletion transformer. arXiv preprint arXiv:2001.05540, 2020. — [arXiv:2001.05540](https://arxiv.org/abs/2001.05540) find
  38. Chitwan Saharia, William Chan, Saurabh Saxena, and Mohammad Norouzi. Non-autoregressive machine translation with latent alignments. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1098–1108, 2020. find
  39. Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, pages 901–909, 2016. find
  40. Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, pages 2234–2242, 2016. find our card
  41. Tim Salimans, Andrej Karpathy, Xi Chen, and Diederik P Kingma. PixelCNN++: Improving the PixelCNN with discretized logistic mixture likelihood and other modifications. In International Conference on Learning Representations, 2017. find
  42. Ari Seff, Wenda Zhou, Farhan Damani, Abigail Doyle, and Ryan P Adams. Discrete object generation with reversible inductive construction. arXiv preprint arXiv:1907.08268, July 2019. — [arXiv:1907.08268](https://arxiv.org/abs/1907.08268) find
  43. Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256–2265, 2015. find our card
  44. Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference on Learning Representations, 2021. find our card
  45. Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems, pages 11895–11907, 2019. find our card
  46. Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. arXiv preprint arXiv:2006.09011, 2020. — [arXiv:2006.09011](https://arxiv.org/abs/2006.09011) find
  47. Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456, November 2020. find our card
  48. Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016. find
  49. Dustin Tran, Keyon Vafa, Kumar Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. In Advances in Neural Information Processing Systems, volume 32, 2019. find
  50. Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. WaveNet: A generative model for raw audio. arXiv preprint arXiv:1609.03499, 2016. find our card
  51. Aaron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural networks. International Conference on Machine Learning, 2016. find
  52. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998–6008, 2017. find
  53. Pascal Vincent. A connection between score matching and denoising autoencoders. Neural Computation, 23(7):1661–1674, 2011. find
  54. Alex Wang and Kyunghyun Cho. BERT has a mouth, and it must speak: BERT as a markov random field language model. arXiv preprint arXiv:1902.04094, February 2019. find our card
  55. Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European Conference on Computer Vision (ECCV), pages 3–19, 2018. find
  56. Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016. — [arXiv:1605.07146](https://arxiv.org/abs/1605.07146) find
  57. Zachary M Ziegler and Alexander M Rush. Latent normalizing flows for discrete sequences. arXiv preprint arXiv:1901.10548, January 2019. Wide residual networks. arXiv preprint — [arXiv:1901.10548](https://arxiv.org/abs/1901.10548) find