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.

本文提出了一种构建基于决策树的离散流来降低计算负担和消除伪梯度需求的方法，包括定义一种树结构的置换来高效地计算密度值和样本新数据，以及使用新的标准在每个节点上学习树结构和置换，并在多个数据集上通过实验证明了我们方法的可行性。