Generative Trees: Adversarial and Copycat

Richard Nock, Mathieu Guillame-Bert

TL;DR

While Generative Adversarial Networks (GANs) have revolutionized image generation, they often struggle with the messy, heterogeneous nature of tabular data. This paper introduces Generative Trees (GTs), a novel framework that brings the power and efficiency of decision trees to the generative world, outperforming neural-network-based GANs in both speed and accuracy while virtually eliminating the dreaded problem of mode collapse.

The Tabular Data Chasm

In the world of supervised learning, there is a famous "chasm": neural networks dominate unstructured data like images and audio, but Gradient Boosted Decision Trees (GBDTs) remain the undisputed kings of tabular data (think spreadsheets and databases).

However, on the generative side, the story is different. Most state-of-the-art generative models, like GANs, are built on neural networks. When applied to tabular data, these neural GANs often struggle with discrete variables, require massive hyperparameter tuning, and frequently suffer from "mode collapse"—where the model only learns to generate a few types of data points, ignoring the diversity of the real dataset. The authors aim to bridge this gap by creating a generative model that mirrors the strengths of decision trees: interpretability, handling of mixed data types, and algorithmic efficiency.

Methods: Building Generative Trees

The authors propose two primary ways to build and train Generative Trees:

  1. Generative Tree (GT) Architecture: Unlike a standard decision tree that outputs a single prediction at its leaves, a GT uses stochastic (probabilistic) activations at its branches. When you "run" the tree, you traverse it based on Bernoulli trials at each node until you reach a leaf, which then samples data from a specific region of the feature space.
Comparison of a standard Decision Tree (left) and a Generative Tree (right).
  1. Adversarial Training: The authors develop a top-down induction algorithm to train GTs against a discriminator. A key theoretical insight here is that for a wide class of "proper" loss functions, the optimal strategy for the generator is simply to minimize the $\chi^2$ divergence between real and fake data. This provides a "one loss to train them all" approach.
  2. Copycat Training: This is a highly efficient, non-traditional training method. The generator "peeks" at the discriminator’s tree structure and copies its graph. By matching the probabilities at the branches to the distribution of real data seen by the discriminator, the generator can very quickly learn to mimic the target distribution.

Key Insights: Goodbye, Mode Collapse

Because GTs partition the data space into distinct boxes (leaves) and refine them greedily, they are naturally resistant to mode collapse. While a neural GAN might "forget" a cluster of data to focus on a bigger one, a GT simply adds more leaves to cover all discovered modes.

Visualizing density plots: GTs (left) capture the distinct modes of the datasets much more accurately than CTGAN (middle).

Furthermore, the paper proves that if a discriminator is "calibrated" (which decision trees naturally are), the generator's risk is bounded by the $\chi^2$ divergence. This simplifies the GAN game significantly for tree-based models. Finally, the "Copycat" method allows for generative modeling with almost no additional computational overhead beyond training a standard classifier.

Key Results and Datasets

The authors evaluated their models on a diverse set of 15 domains, ranging from simulated benchmarks (like randGauss) to public tabular datasets (iris, abalone, dna) and real-world large-scale data (Hartford, CT traffic stops).

  • Superior Quality: In "Training on Generated Data" (TRAIN-GEN) tests—where a classifier is trained on fake data and tested on real data—GTs consistently outperformed CTGAN, a popular neural GAN for tabular data.
  • Speed: On the dna dataset, GTs were 10x to 100x faster to train than neural network alternatives.
  • Imputation Power: GTs proved highly effective for missing data imputation. On the dna dataset, a single GT could impute missing values in under 5 minutes, whereas the standard mice (Random Forest) approach took over two hours.

Limitations and Future Work

While powerful, GTs have limitations. Like all standard decision trees, they partition space using lines parallel to the axes, which can be inefficient for data with strong diagonal correlations. Additionally, the "Copycat" method requires the generator to see the discriminator's internal structure, potentially raising privacy concerns in sensitive adversarial settings. Finally, this paper focuses on single generative trees; scaling this architecture to "Generative Forests" (ensembles) remains a major open problem that could further boost performance.

Summary updated

Abstract

While Generative Adversarial Networks (GANs) achieve spectacular results on unstructured data like images, there is still a gap on <em>tabular data</em>, data for which state of the art <em>supervi...
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