PaperlayerView exact revision on arXiv

Source-linked AI summary

Feature Importance in Gradient Boosting Trees with Cross-Validation Feature Selection

Afek Ilay Adler, Amichai Painsky

arXiv:2109.05468v1cs.LGstat.ML

TL;DR

GBM tree learners favor high-cardinality categorical variables, and the effect of this bias on feature-importance measures is the gap studied here. CVB is a validated boosting framework that addresses the tree’s bias. CVB attains unbiased FI with competitive generalization, while FI varies by GBM implementation even when prediction error is the same.

  • Problem

    GBM tree learners favor high-cardinality categorical variables, and the effect of this bias on feature-importance measures is the gap studied here.

    Source: §1 · p. 2

  • Method

    CVB is a validated boosting framework that addresses the tree’s bias.

    Source: §1 · p. 2

  • Results

    CVB attains unbiased FI with competitive generalization, while FI varies by GBM implementation even when prediction error is the same.

    Source: §7 · p. 24

  • Takeaways & Limitations

    FI is not model-agnostic or universal, so its behavior is specific to each GBM implementation.

    Source: §7 · p. 24

    CVB is a naive, unoptimized GBM implementation.

    Source: §7 · p. 24

Abstract

from arXiv · show

Gradient Boosting Machines (GBM) are among the go-to algorithms on tabular data, which produce state of the art results in many prediction tasks. Despite its popularity, the GBM framework suffers from a fundamental flaw in its base learners. Specifically, most implementations utilize decision trees that are typically biased towards categorical variables with large cardinalities. The effect of this bias was extensively studied over the years, mostly in terms of predictive performance. In this work, we extend the scope and study the effect of biased base learners on GBM feature importance (FI) measures. We show that although these implementation demonstrate highly competitive predictive performance, they still, surprisingly, suffer from bias in FI. By utilizing cross-validated (CV) unbiased base learners, we fix this flaw at a relatively low computational cost. We demonstrate the suggested framework in a variety of synthetic and real-world setups, showing a significant improvement in all GBM FI measures while maintaining relatively the same level of prediction accuracy.

1. Introduction

Standard GBM tree learners favor high-cardinality categorical variables, biasing feature-importance measures; the paper introduces cross-validated boosting to address this bias. Simulations and real-data case studies report improved feature-importance reliability with CVB.

1. Introduction

  • Feature importance helps interpret complex models and can support human decision-making in fields such as medicine.Source: §1 · p. 2
  • Tree base learners favor high-cardinality categorical variables, and standard GBM implementations consequently yield biased FI that can lead to misinterpreted models.Source: §1 · p. 2
  • CVB selects tree split variables by cross-validated rather than training-sample performance, comparing informative categorical features by estimated generalization ability.Source: §1 · pp. 2–3
  • CVB is the only algorithm without biased FI for high-cardinality features in simulations, and its FI is more reliable than alternatives in two real-data case studies.Source: §1 · p. 3

2. Background

This background introduces decision trees, gradient boosting, GBM implementations, and feature-importance methods for interpreting models globally or for individual observations. It explains how tree split selection can favor high-cardinality categorical features and motivates focusing on global feature importance while reducing tree bias without undermining prediction.

2.1. Decision Trees

  • At each node, CART examines all possible splits for each feature; for categorical variables with K_j categories, ordering categories by mean response reduces complexity to K_j − 1 splits, while C4.5 trees may be problematic for large-cardinality categorical features.Source: §2.1 · p. 4

2.2. Gradient Boosting Trees

  • GBM sequentially fits regression trees to gradients of the current estimator, updates the model with a learning rate, and can train each tree on a random subsample.Each tree’s step size is set by leaf-wise line search; stochastic GBM samples without replacement.Source: §2.2 · pp. 4–5

2.3. GBM Implementations

  • The cited text identifies lack of categorical-variable support as XGBoost’s main drawback; by contrast, it says LightGBM supports categorical features out of the box.Source: §2.3 · p. 6

2.4. FI Methods

  • Understanding how machine-learning algorithms make decisions is important in many applications.The passage begins to note that some setups prioritize attaining the best result, but does not complete that claim.Source: §2.4 · p. 7
  • Feature-importance measures explain a trained model, whereas feature-selection methods retrain models to reduce dimensionality or overfitting; the two are not interchangeable.Global importance assigns one score per feature, while local importance gives a feature-importance vector for each observation.Source: §2.4 · pp. 7–8

2.4.1. Global FI Methods

  • Tree-based global GBM importance includes split count, observations covered by splits, and gain, but these measures are biased toward high-cardinality categorical variables.A global model-specific measure can average individual trees’ importance across the ensemble.Source: §2.4.1 · p. 8
  • Repeated permutations make PFI computationally demanding, and correlated features can benefit from one another’s presence, inflating their PFI.PFI estimates importance from the change in prediction error after a feature is randomly permuted.Source: §2.4.1 · p. 9
  • LOCO compares test error for a model trained on all features with one omitting a specified feature, but retraining and repeated estimates increase its computational cost.The method may be unsuitable for large datasets with many observations and features.Source: §2.4.1 · p. 9
  • Global importance can also come from an interpretable surrogate’s feature scores or by averaging local importance across observations.Source: §2.4.1 · p. 10

2.4.2. Local FI Methods

  • Local tree-specific importance averages scores across an ensemble, while Saabas measures expected-value changes around splits and LIME fits an interpretable model near one observation.Source: §2.4.2 · p. 10
  • LIME estimates an observation’s FI by training an interpretable model on an artificial dataset and using that model’s global FI.The artificial data are created for each observation.Source: §2.4.2 · p. 10
  • SHAP estimates feature contributions using Shapley values—the average marginal contribution across possible feature subsets—and Lundberg & Lee (2017) connect this approach to surrogate models.The passage notes that Shapley values have theoretical guarantees and desirable properties.Source: §2.4.2 · p. 10
  • Exact model-agnostic Shapley values require exponential time, while TreeSHAP computes exact values for trees and ensembles in polynomial time but can credit features with no prediction influence.TreeSHAP was introduced by Lundberg et al. (2018a).Source: §2.4.2 · p. 10
  • The paper focuses on global FI because it is more popular and shows high-cardinality categorical-feature bias most clearly and concisely.Unless stated otherwise, the paper uses FI to mean global FI.Source: §2.4.2 · p. 11

2.5. Bias in Tree Based Algorithms

  • Categorical features with many categories are favored at tree splits because they offer more candidate splits, making even an observation-unique ID feature appear attractive.Splits are selected to minimize training error, so this bias can arise without genuine predictive information.Source: §2.5 · p. 11
  • Unbiased variable-selection methods include hypothesis-testing approaches such as QUEST and conditional inference trees.QUEST tests feature-label association, using ANOVA F-statistics for numerical features and χ2 tests for categorical features.Source: §2.5 · p. 11
  • These methods can require unrealistic a-priori assumptions or computationally demanding tests, and their selection criteria may reduce CART predictive performance (Painsky & Rosset, 2016).The computational burden is especially pronounced when trees are built sequentially, as in GBM.Source: §2.5 · p. 12
  • ALOOF uses leave-one-out estimates to compare numerical and categorical variables fairly, selecting a high-cardinality feature when it proves effective out of sample (Painsky & Rosset, 2016).It adapts leave-one-out variable selection to binary trees.Source: §2.5 · p. 12

3. Formulation Of CVB

CVB selects tree-node splits using cross-validation, then applies CART’s splitting rule. Its stopping criterion is based on estimated generalization error, and the authors report fewer trees and leaves.

3. Formulation Of CVB

  • CVB chooses node splits by cross-validation, then divides the node using CART’s splitting rule.It partitions the node’s observations into T equal, non-overlapping sets.Source: §3 · p. 12
  • For each fold, CVB finds an optimal split on the other folds and evaluates its performance on the held-out fold.The feature’s rank is based on average performance across folds, and the split with the lowest rank is chosen.Source: §3 · pp. 12–13
  • The authors describe CVB as similar in spirit to the K-fold cross-validation approach of Painsky and Rosset (2016).They also state that a Python implementation is publicly available.Source: §3 · p. 13

3.1. CVB Stopping Criteria

  • Minimum gain decrease is harder to interpret because its units depend on the impurity criterion and vary across datasets.In that approach, a branch stops when the best split’s gain falls below a predefined hyperparameter.Source: §3.1 · p. 13
  • CVB stops a tree branch when the best estimated generalization error across features exceeds the impurity before the split.The paper describes this as a built-in regularization mechanism resembling minimum gain decrease.Source: §3.1 · p. 13
  • CVB demonstrates a significant reduction in the number of trees and leaves.The authors say this leads to more interpretable models.Source: §3.1 · p. 13

4. Methods

The methods compare GBM implementations with built-in categorical-variable handling using Gain, permutation, and SHAP feature importance. Experiments use fixed tree settings, repeated permutations for PFI, and cross-validation on real datasets.

4. Methods

  • The study compares CatBoost, LGBM, and Friedman’s GBM, focusing on implementations with built-in categorical-variable handling.XGBoost is outside the study’s scope because one-hot encoding would make runtime unfeasible on the studied problems.Source: §4 · p. 13
  • The evaluated feature-importance measures are Gain, PFI, and global SHAP FI.The paper derives global FI from SHAP because SHAP is a local method.Source: §4 · p. 14
  • Across studied algorithms, trees have maximum depth 3, 100 base learners, and learning rate 0.1, with other defaults and no bagging.Regression error is measured by MSE and binary classification error by log-loss.Source: §4 · p. 14
  • PFI uses twenty permutations, while real-dataset error and FI metrics use K-fold cross-validation with K = 30 unless stated otherwise.CVB uses T = 5 for node selection.Source: §4 · p. 14
  • Reported FI values are scaled so that their values over all variables sum to one.Some studied implementations do not directly integrate all the FI measures.Source: §4 · p. 14

5. Bias In Gradient Boosting FI

In synthetic null and power experiments, CVB’s feature-importance results are reported as nearly unbiased, outperforming the compared GBM implementations. The experiments also show cardinality-related bias in conventional methods.

5.1. Null Case

  • In the null case, CVB assigns zero importance to every uninformative feature, while the other methods show greater PFI variance as cardinality rises.CatBoost has around 10 times smaller PFI for uninformative variables than LGBM and Vanilla GBM; CVB scores them at zero.Source: §5.1 · p. 15
  • In the null case, high-cardinality categorical features tend to receive greater Gain FI despite all features being uninformative.The effect is more evident in Vanilla GBM and LGBM, where X3 and X4 together account for almost 90% of overall FI.Source: §5.1 · p. 15, Figure 1 · p. 16

5.2. Power Case

  • For α = 0.2, CVB assigns 99.5% FI to informative X1, compared with 91% for CatBoost, 42% for LGBM, and 37% for Vanilla GBM.The experiment defines X1 as informative and the remaining features as uninformative.Source: §5.2 · p. 16
  • In the power case, PFI variance increases with category size for all algorithms besides CVB.CatBoost’s variance is an order of magnitude smaller than LGBM and Vanilla GBM.Source: §5.2 · p. 17
  • For scaled PFI in the power case, X1 receives 95.4% importance in LGBM, 99.4% in CatBoost, and 99.9% in CVB.The reported SHAP FI for X1 is 55.3% in LGBM and 90.0% in CatBoost.Source: §5.2 · p. 17
  • Across the power experiment, CVB is reported superior even to CatBoost, with a reliable FI measure and almost no bias.Vanilla GBM and LGBM are described as most prone to overfitting high-cardinality categorical features; CatBoost has smaller bias than those alternatives.Source: §5.2 · p. 17

6. Real Data Case Studies

Real-data studies compare FI methods on Amazon and Criteo datasets, where true FI values are unknown, and assess prediction accuracy on additional datasets. The authors report CVB’s accuracy as competitive with, and sometimes superior to, state-of-the-art methods.

6. Real Data Case Studies

  • The real-data comparisons focus on datasets where the methods disagree because the true FI values are unknown.The examined datasets are preprocessed to remove allegedly uninformative features such as indexing and group-membership indicators.Source: §6 · p. 17

6.1. Amazon Dataset

  • On Amazon, Vanilla GBM tends to favor high-cardinality features, while Resource receives significantly large FI in every method except CVB.The reported significance level for Resource is 1%. Vanilla GBM and LGBM perform better without Resource; for CatBoost and CVB, it is unclear whether Resource contributes to performance.Source: §6.1 · pp. 19–20
  • On Amazon, CVB’s FI methods are consistent with one another, so even Gain FI performs well without more complex FI methods.The paper reports CVB’s mean values as 0.186, 0.181, 0.166, and 0.145 for Vanilla GBM, LGBM, CatBoost, and CVB, respectively.Source: §6 · p. 18, §6.1 · p. 20

6.2. Criteo CTR Dataset

  • On Criteo, Vanilla GBM is biased toward high-cardinality variables and overfits the training set for Device ip.LGBM and CatBoost also assign larger scores to high-cardinality features than CVB; LGBM’s Device ip SHAP value contrasts with its other FI measures.Source: §6.2 · pp. 21–22
  • On Criteo, CVB’s FI results are assessed by comparing prediction error with all features against the subset receiving positive CVB FI.The reported results are described as quite similar to those on Amazon.Source: §6.2 · p. 22, Figure 6 · p. 22

6.3. Prediction Accuracy

  • Across the prediction-accuracy experiments, CVB is competitive with and sometimes superior to state-of-the-art methods.The comparison covers regression and classification datasets.Source: §6.3 · pp. 22–23

Classification log-loss

The supplied passages identify a classification log-loss table and mention Amazon and Criteo CTR datasets.

Classification log-loss

  • Table 2 reports the mean and standard deviation of log loss across 10 folds, as indicated by the available caption text.Source: Table 2 · p. 24
  • Amazon and Criteo CTR datasets are mentioned in the classification results context.Source: Classification log-loss · p. 24

7. Discussion And Conclusion

Common GBM implementations can perform well while producing biased feature importance; the discussion presents CVB with unbiased decision trees as a remedy that retains competitive generalization. It also emphasizes that FI varies by GBM implementation and identifies local FI and implementation improvements as future directions.

7. Discussion And Conclusion

  • CVB uses unbiased decision trees to attain unbiased FI while maintaining competitive generalization abilities.Source: §7 · p. 24
  • Different GBM implementations can yield relatively similar prediction error but substantially different FI scores.The discussion therefore describes FI as implementation-specific rather than model-agnostic or universal.Source: §7 · p. 24
  • Even the naive, unoptimized CVB implementation improves FI while retaining competitive accuracy.The authors leave optimized CVB performance as an open question.Source: §7 · pp. 24–25
  • Future CVB work may examine more efficient validation, state-of-the-art GBM enhancements, and stochastic GBM with out-of-bag feature selection.Source: §7 · p. 25
  • The authors propose applying CVB to correct bias in local FI for accurate personalization measures.Source: §7 · p. 25

Appendix A

The appendix captions identify SHAP feature-importance figures for null and power cases and for Amazon and Criteo CTR datasets.

Appendix A

Loading 2109.05468v1…