Unbiased Gradient Boosting Decision Tree with Unbiased Feature Importance

1 Introduction

Gradient Boosting Decision Tree (GBDT) is one of the most widely used machine learning models and has been applied in numerous domains, including medicine, finance, climate science, and healthcare. GBDT is particularly popular in modeling tabular data [Chen and Guestrin, 2016; Shwartz-Ziv and Armon, 2022; Gorishniy et al., 2021; Grinsztajn et al., 2022]. In the training process of a GBDT model, we need to construct decision trees one by one. During tree construction, we need to determine the best split and the split finding algorithm is one of the most crucial components in GBDT. In the standard implementation [Friedman, 2001; Chen and Guestrin, 2016; Ke et al., 2017], the best split is chosen based on the reduction in loss (decrease in impurity) of all candidate splits in all features. However, this split finding algorithm has long been criticized for its bias towards features that exhibit more potential splits [Breiman et al., 1984; Strobl et al., 2007; Boulesteix et al., 2012; Nicodemus, 2011]. Due to the increased flexibility afforded by a larger number of potential split points, features with higher cardinality (such as continuous features and features with a large number of categories) have a higher probability of being split than features with lower cardinality (such as binary features). This bias introduces two problems in GBDT:

• Interpretability issue. The gain importance [Breiman et al., 1984; Hastie et al., 2001] in GBDT sums up the total reduction of loss in all splits for a given feature, and is frequently used to explain how influential a feature is on the models' predictions. However, gain importance is not reliable due to its bias towards features with high cardinality [Breiman et al., 1984]. As we illustrate in Example 1 in Section 4, a continuous feature independent of the target may have higher gain importance than a binary feature related to the target.
• Overfitting issue. During tree construction, the split finding algorithm biases towards choosing features with high cardinality [Breiman et al., 1984; Strobl et al., 2007]. Moreover, the split finding algorithm uses training set statistics to determine the best split and does not evaluate the generalization performance of each split.

Existing studies to address the bias problems mostly fall into two categories: 1) they propose a post hoc approach to calculate unbiased or debiased feature importance measurement [Zhou and Hooker, 2021; Li et al., 2019], and 2) they propose new tree building algorithms by redesigning split finding algorithms [Loh and Shih, 1997; Kim and Loh, 2001; Loh, 2009; Strobl et al., 2007]. However, these methods mostly focus on random forests, and cannot generalize to GBDT. One of the main reasons is that, different from most random forest implementations, existing GBDT implementations employ the second-order approximation of the objective function to evaluate split-improvement [Chen and Guestrin, 2016; Ke et al., 2017] (see more detailed discussions in the related work section). Since popular GBDT implementations, such as XGBoost [Chen and Guestrin, 2016] and CatBoost [Dorogush et al., 2018], have been dominating tabular data modeling [Gorishniy et al., 2021; Shwartz-Ziv and Armon, 2022], there is an urgent need to address the interpretability and overfitting issues caused by the bias in GBDT.

To study the causes of the bias in GBDT, we conduct a finegrained analysis, which reveals that the bias originates from: 1) the systematic bias in each split's gain estimation. We discover that the calculation of gain is a biased estimation of the split improvement, and is almost always positive. 2) The bias in the split finding algorithm due to the fact that it evaluates the split improvement and determines the best split using the same set of data. According to the analysis, first, we construct an unbiased measurement of feature importance for GBDT by using out-of-bag samples. This new measurement is unbiased in the sense that features with no predictive power for the target variable has an importance score of zero in expectation. Next, we incorporate the unbiased property into the split finding algorithm during tree construction and propose UnbiasedGBM. Compared with existing GBDT implementations (such as LightGBM [Ke et al., 2017], XGBoost [Chen and Guestrin, 2016], and CatBoost [Dorogush et al., 2018]), UnbiasedGBM has two advantages:

1. The split finding algorithm unbiasedly chooses among features with different cardinality to mitigate overfitting.
2. UnbiasedGBM evaluates the generalization performance of each split and performs leaf-wise earlystopping to avoid overfitting splits.

The contributions of this paper are summarized as follows:

1. We propose unbiased gain, an unbiased measurement of feature importance in GBDT to address the interpretability issue due to the bias in the split finding algorithm.
2. We propose UnbiasedGBM by integrating the unbiased property into the split finding algorithm to mitigate overfitting.
3. We provide a large-scale empirical study comprising 60 datasets to show that: 1) UnbiasedGBM exhibits better performance on average than LightGBM, XGBoost, and Catboost, and 2) unbiased gain achieves better average performance in feature selection than gain importance, permutation feature importance, and SHAP importance.

2 RelatedWork

Existing methods to correct the bias in the split finding algorithm fall primarily into two categories: 1) they propose a new method to compute debiased or unbiased feature importance measurement. 2) They propose new tree construction algorithms by redesigning the split finding algorithm.

There has been a line of work to develop new methods for computing debiased or unbiased feature importance. Quinlan [Quinlan, 1986] proposed information gain ratio to overcome the bias in classification trees. Sandri and Zuccolotto [Sandri and Zuccolotto, 2008] decomposed splitimprovement into the reduction in loss and a positive bias. They used a pseudo dataset to estimate and subtract the bias. Nembrini et al. [Nembrini et al., 2018] then improved the computing efficiency of this approach. Li et al. [Li et al., 2019] proposed a debiased feature importance measure. However, their method still yields biased results. Zhou and Hooker [Zhou and Hooker, 2021] proposed an unbiased measurement of feature importance in random forests. Nonetheless, the theoretical analysis relies on using mean squared error to justify the unbiased property of their method and cannot be generalized to GBDT, which often employs different loss functions for tree construction. In this paper, we propose unbiased gain, an unbiased measurement of feature importance in GBDT. Our method enjoys several advantages compared with previous methods: 1) Our method does not generate pseudo data that incurs additional cost as in Sandri and Zuccolotto [Sandri and Zuccolotto, 2008] and Nembrini et al. [Nembrini et al., 2018]. 2) Our method can be easily used in GBDT implementations and has the theoretical guarantee of being unbiased, whereas Zhou and Hooker [Zhou and Hooker, 2021] cannot generalize to GBDT.

There has been another line of works that develop new tree building algorithms to remove the bias, such as QUEST [Loh and Shih, 1997], CRUISE [Kim and Loh, 2001], GUIDE [Loh, 2009], and cforest [Strobl et al., 2007]. However, these methods cannot generalize to GBDT for a variety of reasons. For example, QUEST, CRUISE, and GUIDE use classification trees, whereas GBDT uses regression trees for both classification and regression tasks and supports various loss functions. cforest [Strobl et al., 2007] separates the variable selection and the splitting procedure to remove the bias. However, this method incurs an excessive amount of computational overhead, as variable selection is typically costly. We are the first to integrate the unbiased property into GBDT and develop UnbiasedGBM to address the overfitting problem caused by the bias in GBDT.

3 Background

We briefly introduce the GBDT model in which the second order approximation is used in the training (e.g., XGBoost [Chen and Guestrin, 2016], LightGBM [Ke et al., 2017]). Note that we formulate the GBDT objective under the population distribution as opposed to the traditional formulation of GBDT utilizing the empirical distribution [Chen and Guestrin, 2016; Li, 2012]. This formulation is essential, and it allows us to examine and comprehend the bias in GBDT.

3.1 Gradient Boosting Decision Trees

Consider the dataset D = {(x, y)}, where (x, y) are independent and identically distributed from an unknown distribution T . A tree ensemble model uses K additive functions to model the distribution T and predict the output:

where F = {f(x) = wq(x)} is the space of regression trees. Here q represents the tree structure and q(x) maps an example x to the leaf index. We construct the tree ensemble in an additive manner to minimize the objective function L(ϕ) = Ex,y [l(ϕ(x), y)] . Let ϕt be the model at the t-th iteration and ˆ yt be the corresponding prediction. We greedily add a new regression tree ft that most improves the objective function L(ϕt-1 + ft). This is achieved by using the secondorder approximation:

where

We can simplify the objective function by removing the constant terms:

For a leaf node I in the tree structure, the loss L(I) contributed by the leaf is

where µg(I) = Ex,y [g(x, y)] and µh(I) = Ex,y [h(x, y)]. We can calculate the optimal weight wI of leaf I by

and compute the corresponding optimal loss by

Consider a split on feature Xj at a splitting point s, which results in two child nodes IL = {(x, y)∣xj ≤ s} and IR = {(x, y)∣xj > s}. The gain of the split θ = (j, s) is defined as the reduction in loss:

In practice, the distribution T is usually unknown, therefore we cannot directly calculate µg(I) and µh(I). Instead, we use the training dataset to estimate µg(I) and µh(I). Given a training dataset with n examples and m features Dtr = (X,Y ) = {(xi, yi)}, where ∣Dtr∣ = n and (xi, yi) iid ∼ T , we estimate the loss on leaf I and the gain of a split by

where GI = ∑i∈I gi, HI = ∑i∈I hi, and nI is the number of samples on node I.

3.2 Gain Importance

Gain importance [Breiman et al., 1984; Hastie et al., 2001], also known as mean decrease in impurity, is a kind of feature importance in tree-based methods. It is frequently used to explain how influential a feature is on the model's predictions. Gain importance is calculated by summing up the split gain in Eq 4 of all the splits for each feature respectively.

4 Analysis of Bias in GBDT

We analyze the bias in GBDT and demonstrate that it stems from the systematic bias in the gain estimation and the bias in the split finding algorithm. We show how this bias might lead to serious interpretability and overfitting problems in GBDT.

4.1 Bias in The Gain Estimation

̃ Gain estimates the reduction in loss of a given split on a feature, which is used in both tree construction and the interpretation of a feature's importance in the tree ensemble model. Intuitively, we would like the ̃ Gain to be unbiased, i.e., it should be zero in expectation when randomly splitting on a feature that is independent of the target. However, ̃ Gain is always non-negative for any split on any feature.

Theorem 1. For a dataset (X,Y ) sampled from a distribution T , for any split θ of node I on a given feature Xj, we always have

According to the theorem, the split gain for a random split on a feature independent of the target is almost always positive (the split gain is zero in very rare cases, see the proof and more discussions in Appendix A). This implies that 1) we may split on an uninformative feature, and 2) a positive split gain does not necessarily indicate that the feature contributes to the model. One of the reasons causing this bias is that, ( 1n ∑ni=1 gi)2 is not an unbiased estimation of µ2g :

For an uninformative feature that is independent of the target, any split on the feature yields µg(I) = µg(IL) = µg(IR) and σg(I) = σg(IL) = σg(IR). Consider a regression problem with the MSE loss where the hessian is always a constant, according to Eq. 3 we have

• (a) Gain importance of GBDT

feature

• (b) Unbiased gain of GBDT

Figure 1: The features' importance under different importance measurements in the synthetic dataset. The box plot is based on 1000 repetitions. Unbiased gain correctly assigns the highest importance to X1 and an importance of zero in expectation to X2 and X3.

hence the split gain on the uninformative feature is

4.2 Bias in The Split Finding Algorithm

One of the main challenges in tree learning is to find the optimal split that maximize the reduction of the loss, as shown in Eq. 2. To do this, a split finding algorithm iterates over candidate splits on all features to identify the optimal split that minimizes loss on the training dataset. This strategy for identifying the optimal split introduces two problems in tree learning: 1) the split finding algorithm favors features with high cardinality (such as continuous features or categorical features with many categories). Higher cardinality features have a greater number of candidate splits, and thus a greater likelihood of being split. 2) The split finding algorithm always selects the best split on the training set, without evaluating the generalization performance of each split. The two problems together lead to the overfitting problem in GBDT. We use an example to illustrate how these two problems adversely affect tree learning.

Example 1. We generate a synthetic dataset, so that X1 is a binary feature, X2 is a categorical feature with 6 categories (each category has equal probability), and X3 ∼ N(0, 1) is continuous. Consider a regression problem with y = 0.1X1+ϵ where ϵ ∼ N(0, 1). We train a GBDT on the synthetic dataset and plot the gain importance of each feature in Figure 1(a). We can see that the importance of X2 and X3 is larger than that of X1, even if X2 and X3 are independent with the target variable. This shows that GBDT overfits on the noise due to the bias in the split finding algorithm. In addition, this bias introduces interpretability issues, as X2 and X3 are more important than X1 based on the gain importance.

5 Our Method

To solve the interpretability issue caused by the bias in GBDT, we propose "unbiased gain", an unbiased measurement of feature importance in Section 5.1. Then we incorporate the unbiased property into the split finding algorithm and propose UnbiasedGBM in Section 5.2 to address the issue of overfitting caused by the bias in GBDT.

5.1 Unbiased Gain

Our earlier analysis revealed that there are two sources of the bias in gain importance. First, gain importance biases towards features with high cardinality due to the split finding algorithm. Second, gain importance is always non-negative due to the biased estimation of Eq 2. Our goal is to propose an unbiased measurement of feature importance (unbiased gain). This new measurement is unbiased in a sense that an uninformative feature will receive an importance score of zero in expectation.

In order to design an unbiased measurement of feature importance, we need to eliminate two sources of bias in the current gain importance measurement mentioned above. The intuitive rationale for the first source of bias is that we should not determine the best split and assess its performance using the same set of data. Therefore, a separate validation set is considered to estimate the gain importance. However, directly computing gain importance using the validation set still suffers from the second source of bias. Therefore, we construct a new form of estimation using the validation set that meets the zero-expectation criterion.

Assume we have a training dataset D = {(xi, yi)} and a validation dataset D′ = {(x′i , y′i )}. For a given leaf node I and a given split I = IL ∪ IR, there are nI, nL, nR training examples and n′I , n′L, n′R validation examples that fall into leaf node I, IL, and IR. First, we estimate µg(I) using the training examples

Then, we randomly select k examples from n′I validation examples, where k = min(n′L, n′R). Next, we estimate µg(I) and µh(I) using k randomly selected validation examples

where δ(I, i) is a binary indicator showing whether a validation sample has been selected. Finally we can calculate the loss of leaf node I by

Here, GI is computed using the training set while G′I and H′I are computed using the validation set. We can also calculate ̃ L(IL) and ̃ L(IR) in a similar way (the number of selected validation example k is the same for I, IL, and IR).

Finally, the unbiased gain is calculated as

Theorem 2. For a feature Xj, a leaf node I, and a split θ, if Xj is marginally independent of y within the region defined by the leaf node I, then

A critical design in the unbiased gain is that, instead of estimating µg(I), µg(IL), and µg(IR) using all the validation examples on node I, IL, and IR, we randomly select k examples from node I, IL, and IR respectively for estimation. This design is critical for the unbiased property of Eq 5 (see the proof of Theorem 2 and more explanations in Appendix B)

The unbiased gain we propose serves as a post hoc method to address the interpretability issue. In Figure 1(b), we plot the unbiased gain of the GBDT trained on the synthetic data. We can see that the unbiased gain correctly assigns X1 with the highest importance, and the importance of X2 and X3 is zero in expectation.

5.2 UnbiasedGBM

We propose UnbiasedGBM to address the overfitting problem introduced by the bias in GBDT: 1) The choice of each split biases towards features with high cardinality. 2) We always choose the best split on the training set, without evaluating the generalization performance of each split.

In order to eliminate these two biases, we need two validation sets. Assume we divide the training set into a subtraining set D and two validation sets D′1 and D′2 . UnbiasedGBM eliminates the bias by redesigning the split finding algorithm. The design is conceptually simple but requires a good understanding of the bias in GBDT. First, we calculate the gain of each split ̃ Gain1 in the original fashion using the sub-training set D. We determine the best split of each feature using ̃ Gain1 of each split. Next, we calculate the gaiñ Gain2 of each feature's best split using the validation set D′1 . We determine which feature to split using̃ Gain2 of each feature's best split. Since we determine the best split of each feature and the feature to split using different data, we only need to consider the best split of each feature when choosing the feature to split, thus eliminating the bias towards features with high cardinality. Finally, we use the data set D′2 to calculate the unbiased gain ̃ Gainub of the best split. ̃ Gainub measures the generalization performance of the best split. We split on the leaf node if̃ Gainub > 0 and stop if ̃ Gainub ≤ 0.

Remark. We perform early-stopping on a leaf node when the best split has̃ Gainub ≤ 0. However, this negativẽ Gainub is taken into account when computing the importance of each feature in UnbiasedGBM to maintain the unbiased property.

To sum up, UnbiasedGBM enjoys two advantages over the existing GBDT: 1) UnbiasedGBM unbiasedly chooses among features with different cardinality to mitigate overfitting. 2) UnbiasedGBM measures the generalization performance of each split and performs leaf-wise early-stopping to avoid overfitting splits.

Discussion. Existing GBDT implementations can also perform leaf-wise early-stopping by using the minimal gain to split. However, this method and our method have two conceptual differences. First, we measure the generalization performance of each split, whereas existing methods only use statistics on the training set. Second, our "minimal gain to split" is zero on a theoretic basis, whereas existing methods require heuristic tuning of the minimal gain to split.

Implementation details. An important detail is how to divide the dataset into D, D′1 , and D′2 . We experiment with different ratios of splitting the dataset and find out that we achieve the best performance when ∣D∣ = ∣D′1 ∣ = ∣D′2 ∣ (see more details in Appendix E). An intuitive explanation is that different datasets are equally important in our algorithm and should have the same number of samples.

6 Experiments

In this section, we aim at answering two questions through extensive experiments:

• Q1. How does UnbiasedGBM perform compared with well-developed GBDT implementations such as XGBoost, LightGBM, and CatBoost?
• Q2. How does the proposed unbiased gain perform in terms of feature selection compared with existing feature importance methods?

6.1 Datasets

We collect 60 classification datasets in various application domains provided by Kaggle, UCI [Dua and Graff, 2017], and OpenML [Vanschoren et al., 2013] platforms. We select datasets according to the following criteria: 1) Realworld data. We remove artificial datasets that are designed to test specific models. 2) Not high dimensional. We remove datasets with m/n ratio above 1. 3) Not too small. We remove datasets with too few samples (< 500). 4) Not too easy. We remove datasets if a LightGBM with the default hyperparameters can reach a score larger than 0.95. The detailed properties of datasets are presented in Appendix C.

6.2 Q1. UnbiasedGBM

In this subsection, we answer the Q1 question by comparing UnbiasedGBM with XGBoost, LightGBM, and CatBoost using extensive experiments.

Evaluation Metrics

We use the area under the ROC curve (AUC) in the test set to measure the model performance. In order to aggregate results across datasets of different difficulty, we employ a metric similar to the distance to the minimum, which is introduced in [Wistuba et al., 2015] and used in [Feurer et al., 2020; Grinsztajn et al., 2022]. This metric normalize each test AUC between 0 and 1 via a min-max normalization using the worst AUC and the best AUC of all the models on the dataset.

Baseline Methods

We compare with the following baseline methods:

• XGBoost [Chen and Guestrin, 2016].
• LightGBM [Ke et al., 2017].

• (c) 10 medium-scale datasets with only numerical features.
• (d) 10 medium-scale datasets with num. and cat. features.

Table 1: The average rank (where lower is better) over 60 datasets and the p-value of Nemenyi test between UnbiasedGBM and the baseline methods.

• CatBoost [Dorogush et al., 2018].
• UnbiasedGBM-w/o-SE. UnbiasedGBM without separating the determination of the best split of each feature and the feature to split. One of two validation sets is merged with the subtraining set.
• UnbiasedGBM-w/o-UB. UnbiasedGBM without computing the unbiased gaiñ Gainub to measure the generalization performance of the best split. Two validation sets are merged into one to determine the best feature to split and perform early stopping.

For each method, we perform hyperparameter optimization using the popular Optuna [Akiba et al., 2019] Python package. See more details in Appendix D.

Results

In order to better present the advantage of UnbiasedGBM on datasets with different properties, we classify 60 datasets into four types of datasets, including small-scale (datasets with less than 4000 samples) or medium-scale datasets with only numerical features or both numerical and categorical features. We present the results in Figure 2. The x-axis is the number of tuning iterations, visualizing the influence of the tuning budget on the model performance. We can see that UnbiasedGBM significantly outperforms XGBoost, LightGBM, and CatBoost in both small and medium datasets. In addition, UnbiasedGBM is effective even if there is only numerical features in the datasets. Categorical features are not the only source of performance improvement in UnbiasedGBM. We also visualize the comparison of each dataset in Figure 3 that demonstrates the improvement of our method. We leverage the Nemenyi test [Demsar, 2006] to perform statistical analyses using the rank of each method after hyper-parameter tuning of 100 iterations on 60 datasets. We present the results in Table 1, where the Nemenyi test p-values show that UnbiasedGBM significantly outperforms the baselines. Moreover, comparisons between UnbiasedGBM, UnbiasedGBMw/o-SE, and UnbiasedGBM-w/o-UB demonstrate that separating the determination of the best split of each feature and the feature to split is the primary source of improvement in UnbiasedGBM. In most cases, computing the unbiased gain to evaluate generalization performance of the best split can also result in performance improvement.

(a) UnbiasedGBM vs. LightGBM

6.3 Q2. Unbiased Gain

In this subsection, we demonstrate the performance of unbiased gain in feature selection.

Baseline Methods

We compare unbiased gain with different feature importance measurements:

• Gain importance [Breiman et al., 1984].
• Permutation feature importance (PFI) [Breiman, 2001].
• SHAP [Lundberg et al., 2018].

Evaluation

We follow the standard approach [Forman and others, 2003] to evaluate different feature importance measurements in feature selection. For a given dataset, we first estimate the feature importance on the training set. Then, we select top k% features according to the feature importance, where k ∈ {10, 20, 30}. Next, we build a GBDT model according to the selected feature subset. Finally, we calculate the AUC of the model on the test set. Higher AUC indicates that the feature importance performs better in feature selection.

Results

We evaluate these methods on 14 out of 60 datasets with more than 30 features. Datasets with too few features may not need feature selection. We consider selecting top k% features for k ∈ {10, 20, 30}. For each method, we report the mean and variance of the test AUC across these 14 datasets. The results are presented in Figure 4. We can see that unbiased gain achieves better average performance than baseline methods in feature selection.

6.4 Analyses of Features withMany Categories

We present an analysis of the QSAR Bioconcentration dataset in Table 2 to show that UnbiasedGBM can address the overfitting issue of LightGBM on categorical features with many categories. The details are in the caption of Table 2.

7 Conclusion

In this paper, we investigate the bias in GBDT and the consequent interpretability and overfitting issues. We give a finegrained analysis of bias in GBDT. Based on the analysis, we propose the unbiased gain and UnbiasedGBM to address the interpretability and overfitting issues. Extensive experiments on 60 datasets show that UnbiasedGBM has better average performance than XGBoost, LightGBM, and Catboost and unbiased gain can outperform popular feature importance estimation methods in feature selection.

Acknowledgements

The authors are supported in part by the National Natural Science Foundation of China Grant 62161146004, Turing AI Institute of Nanjing and Xi'an Institute for Interdisciplinary Information Core Technology.

Contribution Statement

This paper is the result of collaborative work between Zheyu Zhang and Tianping Zhang, who contributed equally to the conception, implementation, experimentation, and paper writing. Jian Li served as the corresponding author, contributing to the overall idea of the project as well as providing computing resources.