# Discrete Tree Flows via Tree-Structured Permutations

arXiv: https://arxiv.org/abs/2207.01744 · HTML: https://mlsanity.com/paper/2207.01744/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 4 Jul 2022.

## Builds on (most cited first, 17 of 17)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Variational Inference with Normalizing Flows](https://mlsanity.com/paper/1505.05770/) (2015)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Generating Diverse High-Fidelity Images with VQ-VAE-2](https://mlsanity.com/paper/1906.00446/) (2019)
- [An Introduction to Variational Autoencoders](https://mlsanity.com/paper/1906.02691/) (2019)
- [Masked Autoregressive Flow for Density Estimation](https://mlsanity.com/paper/1705.07057/) (2017)
- [Improving Variational Inference with Inverse Autoregressive Flow](https://mlsanity.com/paper/1606.04934/) (2016)
- [Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions](https://mlsanity.com/paper/2102.05379/) (2021)
- [MADE: Masked Autoencoder for Distribution Estimation](https://mlsanity.com/paper/1502.03509/) (2015)
- [Integer Discrete Flows and Lossless Compression](https://mlsanity.com/paper/1905.07376/) (2019)
- [Discrete Flows: Invertible Generative Models of Discrete Data](https://mlsanity.com/paper/1905.10347/) (2019)
- [Latent Normalizing Flows for Discrete Sequences](https://mlsanity.com/paper/1901.10548/) (2019)
- [Categorical Normalizing Flows via Continuous Transformations](https://mlsanity.com/paper/2006.09790/) (2020)
- [IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression](https://mlsanity.com/paper/2006.12459/) (2020)
- [A Review of Multivariate Distributions for Count Data Derived from the Poisson Distribution](https://mlsanity.com/paper/1609.00066/) (2016)
- [Fitting A Mixture Distribution to Data: Tutorial](https://mlsanity.com/paper/1901.06708/) (2019)

## Abstract (arXiv)

While normalizing flows for continuous data have been extensively researched, flows for discrete data have only recently been explored. These prior models, however, suffer from limitations that are distinct from those of continuous flows. Most notably, discrete flow-based models cannot be straightforwardly optimized with conventional deep learning methods because gradients of discrete functions are undefined or zero. Previous works approximate pseudo-gradients of the discrete functions but do not solve the problem on a fundamental level. In addition to that, backpropagation can be computationally burdensome compared to alternative discrete algorithms such as decision tree algorithms. Our approach seeks to reduce computational burden and remove the need for pseudo-gradients by developing a discrete flow based on decision trees -- building upon the success of efficient tree-based methods for classification and regression for discrete data. We first define a tree-structured permutation (TSP) that compactly encodes a permutation of discrete data where the inverse is easy to compute; thus, we can efficiently compute the density value and sample new data. We then propose a decision tree algorithm to build TSPs that learns the tree structure and permutations at each node via novel criteria. We empirically demonstrate the feasibility of our method on multiple datasets.