Research map / Learning theory and algorithms / Prediction and decision losses
Generative Model for Decision Trees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GENTREE, which learns a latent space of decision trees with a tree VAE trained on CART/RF-induced trees and then searches it with a genetic algorithm to find shallow, accurate trees.
Problem
Greedy top-down decision tree induction yields locally optimal, overly complex trees, while optimal decision tree methods are computationally prohibitive; the paper seeks accurate and shallow interpretable trees in between.
Approach
Combine a variational autoencoder over matrix-encoded decision trees (learned from pre-trained trees) with a genetic algorithm that searches the continuous latent tree space, using a fitness that rewards accuracy and penalizes leaves.
Key results
- GENTREE averages 0.779 accuracy versus 0.753 for CART and 0.858 for Random Forest, and is tied with ODT in accuracy rank.
- GENTREE's complexity averages 62.7 versus 128.1 for CART and 124.3 for Random Forest, second only to ODT (32.5) in complexity.
- GENTREE is slower than CART and RF (about 2.2x the runtime of RF per Table 4), with a TVAE-induced bottleneck.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace CART with GENTREE | Decision tree induction · 18 UCI datasets (average) | accuracy: .753 -> .779 | Helped |
| Replace CART with GENTREE | Decision tree induction · 18 UCI datasets (average) | complexity (number of nodes): 128.1 -> 62.7 | Helped |
| Use fitness function (2) instead of fitness function (1) (ablation) | GENTREE with CART trees · Sensitivity analysis datasets | accuracy: .832 ± .12 -> 0.638 ± .16 | Hurt |
| Use fitness function (2) instead of fitness function (1) (ablation) | GENTREE with CART trees · Sensitivity analysis datasets | complexity: 13.0 ± 10.46 -> 2.0 ± 1.15 | Helped |
| Use fitness function (2) instead of fitness function (1) (ablation) | GENTREE with Random Forest trees · Sensitivity analysis datasets | accuracy: 0.699 ± .20 -> 0.653 ± .28 | Hurt |
| Use fitness function (2) instead of fitness function (1) (ablation) | GENTREE with Random Forest trees · Sensitivity analysis datasets | complexity: 11.5 ± 10.75 -> 5.0 ± 1.63 | Helped |
| Use Random Forest rather than CART as the tree-learning function (ablation) | GENTREE with fitness function (1) · Sensitivity analysis datasets | accuracy: .832 ± .12 -> .699 ± .20 | Mixed |
| Use Random Forest rather than CART as the tree-learning function (ablation) | GENTREE with fitness function (1) · Sensitivity analysis datasets | complexity: 13.0 ± 10.46 -> 11.5 ± 10.75 | No clear effect |
| Increase the number of input trees beyond 100 (ablation) | GENTREE · cars, dbn, iris, pima | accuracy | No clear effect |
| Increase the genetic iteration count beyond 10 (ablation) | GENTREE · cars, dbn, iris, pima | accuracy | Hurt |
Surprising findings
- Fitness that also rewards shallowness (fitness 2) over-prunes trees into very small but inaccurate trees.
Limitations
- Trained only on datasets with continuous attributes; categorical attributes left for future work.
- The TVAE does not enforce structurally valid trees; validity is handled only by the GA fitness.
- Runtime is markedly higher than CART and random forest.
Experimental setup
Datasets: aus bnk bnote brst cars dbn ecoli glass heart iris iso led7
Benchmarks: 18 UCI classification datasets
Metrics: accuracy complexity (nodes and leaves) runtime average rank Nemenyi critical difference
Baselines: CART Optimal Decision Trees (ODT) GENESIM Random Forest
Builds on: Tree-VAE (Sohn, Lee, and Yan 2015) GENESIM CART Optimal Decision Trees
Closest papers by meaning
- Decision Tree Induction Through LLMs via Semantically-Aware Evolution (ICLR 2025 · similarity 0.89)
- Generative Forests (NeurIPS 2024 · similarity 0.88)
- Learning Small Decision Trees with Few Outliers: A Parameterized Perspective (AAAI 2024 · similarity 0.88)
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity (ICML 2025 · similarity 0.88)
- Near-Optimal Decision Trees in a SPLIT Second (ICML 2025 · similarity 0.87)
- Leveraging Predictive Equivalence in Decision Trees (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.