Research map / Learning theory and algorithms / Prediction and decision losses
Accurate Estimation of Feature Importance Faithfulness for Tree Models
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 PGI², a squared-prediction-gap faithfulness metric that tree ensembles can compute exactly in O(n²) time, and a greedy PG²-based feature ranking that is compared against SHAP.
Problem
Perturbation-based faithfulness metrics such as PGI for feature attributions are computed by Monte Carlo sampling, which is inaccurate, and the absolute-value form is intractable to compute in closed form even for tree models.
Approach
Replace the absolute prediction gap with the squared prediction gap, which makes the expectation over independent feature perturbations decomposable over pairs of tree leaves, enabling an exact O(n²) algorithm for tree ensembles; also uses a greedy PG²-maximizing feature ordering as an attribution method.
Key results
- Exact PG² algorithm is accurate and numerically stable; MC and QMC converge to it, and at equal time budget MC NMAE is 0.009-0.136 and QMC is lower (e.g., 0.001-0.054) across settings.
- Greedy PG² ranking gives higher average PGI² than SHAP for Bigger models in almost all settings (e.g., Parkinson σ'=1.0: 16.3 for SHAP vs 34.0 for PG² σ=1.0).
- On remove-and-retrain, SHAP picks the most important features more accurately than the PG²-based ranking; on feature randomization results are mixed by dataset.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Quasi Monte Carlo instead of Monte Carlo at comparable runtime | Sampling estimation of PG² · Red Wine Quality, California Housing, and Parkinson Telemonitoring; σ=0.3 | NMAE: 0.136 -> 0.049; 0.14 -> 0.043; 0.064 -> 0.011 (single trees); 0.014 -> 0.002; 0.011 -> 0.001; 0.009 -> 0.002 (bigger mod | Helped |
| Use greedy PG² feature ranking instead of SHAP | XGBoost bigger tree ensembles · PGI² across Red Wine Quality, California Housing, and Parkinson Telemonitoring, σ'=0.3 | average PGI²: Red Wine Quality: 0.051 vs 0.068, 0.078, 0.067; California Housing: 1.209e+09 vs 1.297e+09, 1.374e+09, 1.259e+09; Parkin | Helped |
| Use greedy PG² ranking with σ=0.1 or σ=0.3 instead of SHAP | XGBoost California Housing bigger model · Feature randomising, k=1 | RMSE: 1.32e+05 -> 1.412e+05; 1.32e+05 -> 1.379e+05 | Mixed |
| Use greedy PG² ranking instead of SHAP | XGBoost bigger tree ensembles · Remove-and-retrain feature removal | RMSE | Hurt |
| Increase sampling iteration count | Monte Carlo and Quasi Monte Carlo PG² estimates · Tree ensembles | NMAE | Helped |
| Use a bigger tree ensemble rather than a single tree | Monte Carlo and Quasi Monte Carlo estimation · All evaluated datasets | NMAE | Helped |
| Increase Gaussian perturbation standard deviation | Monte Carlo PG² estimation · Tree ensembles | NMAE | Helped |
| Use greedy PG² ranking instead of SHAP | Feature randomising evaluation · Red Wine Quality and Parkinson Telemonitoring models | RMSE | No clear effect |
Surprising findings
- Top-1 feature agreement between greedy PG² rankings and SHAP is below 76% even for single-tree models, so the rankings differ substantially.
Limitations
- Exact computation is restricted to tree ensemble models and independent feature perturbations with computable CDFs.
- Greedy PG² ranking is a heuristic with no optimality guarantee for PGI².
- Experiments use only three tabular datasets and small XGBoost models (max depth up to 4, up to 40 trees).
Experimental setup
Datasets: Red Wine Quality California Housing Parkinson Telemonitoring
Benchmarks: Red Wine Quality California Housing Parkinson Telemonitoring
Metrics: NMAE PGI² score feature randomization RMSE remove-and-retrain RMSE top-k ranking agreement with SHAP
Baselines: SHAP Monte Carlo sampling Quasi Monte Carlo sampling
Builds on: PGI (OpenXAI prediction gap) SHAP tree path-dependent XGBoost
Closest papers by meaning
- TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees (ICLR 2026 · similarity 0.88)
- Conditional Feature Importance with Generative Modeling Using Adversarial Random Forests (AAAI 2025 · similarity 0.84)
- Feature Attribution with Necessity and Sufficiency via Dual-stage Perturbation Test for Causal Explanation (ICML 2024 · similarity 0.82)
- Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles (AAAI 2024 · similarity 0.82)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.82)
- Testing Semantic Importance via Betting (NeurIPS 2024 · similarity 0.82)
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.