Research map / Learning theory and algorithms / Prediction and decision losses
Fast Estimation of Partial Dependence Functions using 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 FastPD, a tree-based algorithm that consistently estimates arbitrary partial dependence functions (and hence SHAP, PD plots, and functional decompositions) with linear complexity in the number of background/evaluation samples, contrasting with inconsistent path-dependent TreeSHAP.
Problem
Partial dependence (PD) based explanations such as SHAP values, PD plots and functional decompositions are needed, but fast estimation exists only for SHAP, and the popular path-dependent TreeSHAP is inconsistent when features are correlated.
Approach
Separates tree augmentation (precomputing leaf-wise background sample lists for every feature subset on the path) from evaluation on query points, so all PD functions can be estimated consistently with complexity linear in n_b + n_e rather than quadratic in n_b * n_e.
Key results
- TreeSHAP-path MSE does not shrink with more background samples, whereas FastPD MSE decreases substantially with n_b.
- At n_b=n_e=8000, FastPD runtime is 1.26 s versus 13722 s for VanillaPD and 295 s for TreeSHAP-int (per the paper's reported means).
- On OpenML benchmarks, path-dependent attributions differed by more than ±30% from FastPD in 33 of 96 datasets (9 with FastPD-100).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace VanillaPD's repeated background-sample evaluation with FastPD's tree augmentation and evaluation | PD estimation for decision trees · All PD functions; moderately deep trees | computational complexity: O(R2^{d}n_{\text{e}}n_{\text{b}}) -> O(2^{D + F}(n_{\text{e}} +n_{\text{b}})) | Helped |
| Use path-dependent TreeSHAP instead of FastPD | TreeSHAP explanations · Correlated features; model SHAP | MSE | Hurt |
| Increase the number of background samples from 50 to 100 (ablation) | FastPD · OpenML-CTR23 and OpenML-CC18; functional component importance | datasets with relative differences exceeding ±30%: 18 -> 9 | Helped |
| Use 50 background samples rather than the path-dependent method (ablation) | Functional component importance · OpenML-CTR23 and OpenML-CC18 | datasets with relative differences exceeding ±30%: 33 -> 18 | Helped |
| Use 100 background samples rather than the path-dependent method (ablation) | Functional component importance · OpenML-CTR23 and OpenML-CC18 | datasets with relative differences exceeding ±30%: 33 -> 9 | Helped |
| Use FastPD rather than Friedman-path | XGBoost functional decomposition · Adult; age–relationship interaction | estimated interaction effect during prime working age | Mixed |
| Use FastPD-100 instead of full FastPD (ablation) | Functional component estimation · Simulated data; main-effect component m1 | component estimation accuracy | Hurt |
Surprising findings
- Even with zero feature correlation, TreeSHAP-path is less accurate than FastPD because it does not use all background information at inner nodes.
- Accurate PD estimation may require more than 100 background samples, beyond the default used by the shap Python package.
Limitations
- Space complexity grows with the number of stored lists per leaf, motivating shallow trees.
- Ground-truth PD functions are only identified under product-measure or parametric assumptions; extrapolation can distort PD explanations.
- Only tree-based models are supported; other models require a surrogate tree.
Experimental setup
Datasets: simulated Gaussian covariates (DGP 1 and DGP 2) OpenML-CTR23 OpenML-CC18 adult
Benchmarks: OpenML-CTR23 OpenML-CC18 adult simulated DGP 1 and DGP 2
Metrics: SHAP mean squared error runtime in seconds relative importance difference of functional components
Baselines: VanillaPD TreeSHAP-path TreeSHAP-int Friedman-path pltreeshap
Builds on: TreeSHAP Friedman's functional decomposition (path-dependent) interventional TreeSHAP XGBoost
Closest papers by meaning
- A Unified Framework for Provably Efficient Algorithms to Estimate Shapley Values (NeurIPS 2025 · similarity 0.87)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.86)
- Provably Accurate Shapley Value Estimation via Leverage Score Sampling (ICLR 2025 · similarity 0.86)
- shapiq: Shapley Interactions for Machine Learning (NeurIPS 2024 · similarity 0.85)
- Proxy-Based Approximation of Shapley and Banzhaf Interactions (NeurIPS 2026 · similarity 0.85)
- SHAP values via sparse Fourier representation (NeurIPS 2025 · 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.