Research map / Learning theory and algorithms / Prediction and decision losses
Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm
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.
Introduces TreeHFD, a least-squares algorithm that estimates the hierarchically orthogonal Hoeffding functional decomposition of a tree ensemble from a data sample, and empirically links it to TreeSHAP.
Problem
Estimating the Hoeffding (ANOVA) functional decomposition of a tree ensemble when inputs are dependent and only a data sample (not the input distribution) is available.
Approach
Approximates each tree's HFD with piecewise-constant components on the Cartesian tree partition, imposes discretized hierarchical orthogonality constraints, and solves a least-squares problem per tree using the data sample, with a linear dependence on sample size.
Key results
- On the analytical case, TreeHFD with XGBoost achieves component MSEs around 0.002-0.04 versus 0.06-0.73 for TreeSHAP relative to the HFD target.
- TreeHFD residual MSE is about 1% of output variance on most real datasets, with maximum interaction-main effect correlations around 0.05 versus often above 0.5 for TreeSHAP.
- Cumulated MSE of TreeHFD decreases with sample size (1.94 at n=100 to 0.14 at n=10000), while TreeSHAP plateaus around 1.2-1.3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TreeHFD instead of TreeSHAP to estimate the HFD | xgboost tree ensemble · Analytical case, η^(1,2) | MSE: 0.35 -> 0.04 | Helped |
| Use TreeHFD instead of glex to estimate the HFD | xgboost tree ensemble · Analytical case, η^(1,2) | MSE: 1.2 -> 0.04 | Helped |
| Increase the TreeHFD fitting sample size (ablation) | TreeHFD on xgboost · Analytical case | cumulative MSE: 1.94 -> 0.14 | Helped |
| Set tree depth to 1 instead of the default depth 6 (ablation) | TreeHFD on xgboost · Analytical case | cumulative MSE: 0.20 -> 1.49 | Hurt |
| Vary tree depth from 2 to 7 rather than use depth 6 (ablation) | TreeHFD on xgboost · Analytical case | cumulative MSE: 0.34; 0.26; 0.20; 0.19; 0.20; 0.26 | No clear effect |
Surprising findings
- TreeSHAP estimates the HFD more accurately than the interventional and observational SHAP theoretical decompositions in the analytical case.
- TreeSHAP's error plateaus for n>=1000, suggesting it does not converge to the HFD.
Limitations
- Computational complexity grows exponentially with tree depth for large p, requiring pruning hyperparameters d_T and d_V.
- Requires access to internal tree structures, which proprietary tools may not expose.
- Orthogonality holds only approximately for the global ensemble decomposition, controlled by input density variation within cells.
Experimental setup
Datasets: simulated Gaussian analytical case Abalone Airfoil Bike Sharing Housing (California) Concrete Nutrition Parkinson Power Plant Superconductivity
Benchmarks: analytical Gaussian case UCI nine real datasets
Metrics: MSE with respect to analytical decompositions residual MSE relative to output variance maximum absolute correlation (orthogonality) local variability over nearest neighbors accuracy (explained variance)
Baselines: TreeSHAP interventional SHAP observational SHAP glex EBM
Builds on: Hoeffding decomposition TreeSHAP Lemma of Chastaing et al. on hierarchical orthogonality glex
Closest papers by meaning
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.86)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.86)
- Compressing tree ensembles through Level-wise Optimization and Pruning (ICML 2025 · similarity 0.85)
- Invariant Random Forest: Tree-Based Model Solution for OOD Generalization (AAAI 2024 · similarity 0.85)
- Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles (AAAI 2025 · similarity 0.84)
- Proxy-Based Approximation of Shapley and Banzhaf Interactions (NeurIPS 2026 · similarity 0.84)
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.