Generative Trees: Adversarial and Copycat

Richard Nock, Mathieu Guillame-Bert

Abstract: While Generative Adversarial Networks (GANs) achieve spectacular results on unstructured data like images, there is still a gap on tabular data, data for which state of the art supervised learning still favours to a large extent decision tree (DT)-based models. This paper proposes a new path forward for the generation of tabular data, exploiting decades-old understanding of the supervised task's best components for DT induction, from losses (properness), models (tree-based) to algorithms (boosting). The properness condition on the supervised loss -- which postulates the optimality of Bayes rule -- leads us to a variational GAN-style loss formulation which is tight when discriminators meet a calibration property trivially satisfied by DTs, and, under common assumptions about the supervised loss, yields "one loss to train against them all" for the generator: the $\chi^2$. We then introduce tree-based generative models, generative trees (GTs), meant to mirror on the generative side the good properties of DTs for classifying tabular data, with a boosting-compliant adversarial training algorithm for GTs. We also introduce copycat training, in which the generator copies at run time the underlying tree (graph) of the discriminator DT and completes it for the hardest discriminative task, with boosting compliant convergence. We test our algorithms on tasks including fake/real distinction, training from fake data and missing data imputation. Each one of these tasks displays that GTs can provide comparatively simple -- and interpretable -- contenders to sophisticated state of the art methods for data generation (using neural network models) or missing data imputation (relying on multiple imputation by chained equations with complex tree-based modeling).

Introduction

In machine learning, a significant performance gap exists between unstructured data (images, audio) and tabular data (spreadsheets, databases). While neural networks dominate the former, Gradient Boosted Decision Trees (GBDTs) and Random Forests remain the gold standard for tabular classification and regression. However, when generating synthetic tabular data for privacy or augmentation, researchers often default to neural GANs like CT-GAN. These models can be difficult to tune and lack the inherent interpretability of the tree models used to analyze the same data. This paper introduces Generative Trees (GTs), a tree-based generative model designed to mirror the strengths of decision trees in a generative context.

Generative Tree Architecture

Unlike a standard decision tree that outputs a single deterministic prediction, a Generative Tree is a stochastic model. It operates through two primary mechanisms:

  1. Stochastic Traversal: The model traverses the tree based on Bernoulli trials (coin flips) at each internal node. The probability of taking a specific branch is learned during training.
  2. Leaf Sampling: Upon reaching a leaf, the model samples an observation uniformly from the specific region of the feature space defined by the path to that leaf.
Comparison of a standard decision tree and a generative tree with stochastic traversal probabilities.

Theoretical Foundation: The $\chi^2$ Universal Loss

A key contribution of this work is the discovery of a "universal loss" for generative trees. By leveraging the property of properness in supervised losses—which assumes the optimality of the Bayes rule—the authors derive a variational loss formulation.

Because decision trees are naturally calibrated discriminators, the authors prove that minimizing the $\chi^2$ (chi-squared) divergence is theoretically sufficient to optimize against any "proper" discriminator. This simplifies the training process significantly, providing a single, robust objective for the generator regardless of the specific loss used by the discriminator.

Supervised losses and their dual representations, supporting the derivation of the $\chi^2$ universal loss.

Training Paradigms

The paper introduces two novel training algorithms for GTs:

  • Adversarial Training: A top-down induction algorithm where the generator GT iteratively splits nodes to minimize the $\chi^2$ divergence between real and synthetic data distributions.
  • Copycat Training: An efficient shortcut where the generator "copies" the tree structure (the graph) of the discriminator. By adopting the discriminator's map of the data, the generator can focus its capacity on the regions the discriminator finds most difficult to distinguish, leading to geometric convergence.

Key Results and Performance

The researchers evaluated GTs across 15 diverse domains, including complex simulated benchmarks and real-world UCI datasets.

  • Fidelity: In "fake-real" discrimination tasks, GTs consistently outperformed state-of-the-art neural models like CT-GAN, producing synthetic data that was harder for classifiers to distinguish from real data.
  • Efficiency: GTs demonstrated remarkable speed. On the high-dimensional dna dataset, GTs completed missing data imputation in less than 5 minutes, whereas the standard mice (Multivariate Imputation by Chained Equations) approach required over two hours.
  • Data Augmentation: Adding GT-generated data to training sets often yielded higher accuracy improvements than data from neural GANs, which were more prone to overfitting.
  • Interpretability: Unlike "black-box" neural networks, GTs maintain the transparency of tree models. The generation rules (e.g., "Generate a specific feature value with 90% probability if condition X is met") are explicitly visible in the tree structure.

Conclusion

Generative Trees offer a powerful, interpretable, and efficient alternative to neural GANs for tabular data. By aligning the generative model with the inductive biases of decision trees, GTs bridge the gap between classification and generation in structured data domains. Future work includes extending these models to "Generative Forests" and exploring oblique splits to better capture diagonal correlations.

Summary updated

Abstract

While Generative Adversarial Networks (GANs) achieve spectacular results on unstructured data like images, there is still a gap on tabular data, data for which state of the art supervised learning still favours to a large extent decision tree (DT)-based models. This paper proposes a new path forward for the generation of tabular data, exploiting decades-old understanding of the supervised task's best components for DT induction, from losses (properness), models (tree-based) to algorithms (boosting). The \textit{properness} condition on the supervised loss -- which postulates the optimality of Bayes rule -- leads us to a variational GAN-style loss formulation which is \textit{tight} when discriminators meet a calibration property trivially satisfied by DTs, and, under common assumptions about the supervised loss, yields "one loss to train against them all" for the generator: the $\chi^2$. We then introduce tree-based generative models, \textit{generative trees} (GTs), meant to mirror on the generative side the good properties of DTs for classifying tabular data, with a boosting-compliant \textit{adversarial} training algorithm for GTs. We also introduce \textit{copycat training}, in which the generator copies at run time the underlying tree (graph) of the discriminator DT and completes it for the hardest discriminative task, with boosting compliant convergence. We test our algorithms on tasks including fake/real distinction, training from fake data and missing data imputation. Each one of these tasks displays that GTs can provide comparatively simple -- and interpretable -- contenders to sophisticated state of the art methods for data generation (using neural network models) or missing data imputation (relying on multiple imputation by chained equations with complex tree-based modeling).
BibTeX
@inproceedings{nock2022generative,
  author = {Richard Nock and Mathieu Guillame-Bert},
  title = {{Generative Trees: Adversarial and Copycat}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=56m72faLE1},
}
Figure