Research map / Learning theory and algorithms / Prediction and decision losses
Conditional Density Estimation with Histogram 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 CDTree, an MDL-regularized decision tree whose leaves are histogram density models, with a greedy algorithm that jointly searches splits and bin counts for interpretable conditional density estimation.
Problem
Interpretable conditional density estimation (CDE) is understudied; existing methods are mostly kernel-based or a single Gaussian-leaf tree (CADET), and need cross-validated regularization.
Approach
A fully non-parametric conditional density tree whose leaves are histograms, with tree structure and histogram bin counts chosen jointly by a minimum description length (MDL) score, so no regularization hyperparameter needs tuning; a greedy search finds the best split and bin count at each node.
Key results
- CDTree has the best average rank among interpretable models (2.07 vs 3.14 for next best CADET-free competitor CADET... with lowest NLL on 6 of 14 datasets) in terms of negative log-likelihood.
- CDTree is competitive with black-box LinCDE and its NLL is on par with LinCDE, while being an interpretable single tree.
- CDTree has almost zero splits on irrelevant features and nearly stable NLL when dependent noisy features are added, unlike CART and CADET.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CDTree instead of the strongest interpretable baseline on the UCI datasets | Conditional density estimation · 14 UCI datasets | NLL | Mixed |
| Use CDTree rather than CADET | Tree-based conditional density estimation · 14 UCI datasets | NLL | Helped |
| Use CDTree rather than CART-h | Tree-based conditional density estimation · 14 UCI datasets | NLL | Helped |
| Use CDTree rather than CART-k | Tree-based conditional density estimation · 14 UCI datasets | NLL | Helped |
| Use CDTree rather than LinCDE | Conditional density estimation · 14 UCI datasets | NLL | Mixed |
| Add irrelevant dependent noisy features | CDTree · 14 UCI datasets | NLL | No clear effect |
| Add irrelevant independent Gaussian features | CDTree · 14 UCI datasets | NLL | No clear effect |
| Use CDTree rather than the competing tree-based models | Tree-based conditional density estimation · Most datasets | number of leaves | Helped |
| Use CDTree rather than CKDE | Interpretable conditional density estimation · UCI datasets | runtime | Helped |
Surprising findings
- CDTree's NLL is nearly unchanged when irrelevant features are added, except on the very small slump dataset.
- CDTree is competitive with LinCDE, a boosted tree ensemble, despite being a single tree.
Limitations
- Histograms assume bounded support for the target, so boundaries must be chosen ad hoc.
- Test points outside histogram boundaries receive zero predicted density unless the model is retrained.
- Categorical features are one-hot encoded, and the greedy search is heuristic rather than globally optimal.
Experimental setup
Datasets: UCI repository datasets (14, numerical targets) medical cost dataset
Benchmarks: 14 UCI datasets
Metrics: negative log-likelihood number of leaves runtime count of splits on irrelevant features
Baselines: CADET CART-h CART-k CKDE NKDE LSCDE LinCDE NF MDN
Builds on: CADET CART LSCDE RFCDE
Closest papers by meaning
- Partition Tree: Conditional Density Estimation over General Outcome Spaces (NeurIPS 2026 · similarity 0.88)
- Classification Diffusion Models: Revitalizing Density Ratio Estimation (NeurIPS 2024 · similarity 0.85)
- Conditional Distribution Compression via the Kernel Conditional Mean Embedding (NeurIPS 2025 · similarity 0.84)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.83)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.83)
- A Black-Box Debiasing Framework for Conditional Sampling (NeurIPS 2025 · similarity 0.83)
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.