GRANDE: Gradient-Based Decision Tree Ensembles for Tabular Data

Regarding the interpretability advantages of instance-wise weighting, could the authors provide a more comprehensive analysis? For instance, could they share statistics like the average node count of the highest-weighted estimators across all datasets?

TL;DR: We provided additional statistics (node count, estimator frequency, skewness, kurtosis, etc.) supporting the claims from our paper.

[Also see response to JdQZ]

Within our paper, we showed in an ablation study that our instance-wise weighting has a positive impact on the performance of GRANDE. In addition, we showcased a real-world scenario where the weighting significantly increases local interpretability by enabling the model to learn representations for simple and complex rules. We agree with the reviewer that a more comprehensive analysis of the weighting would be beneficial and therefore provide additional statistics. We summarize the main results below and provide detailed statistics for each dataset, along with an additional discussion in Appendix D.

The following statistics were obtained by calculating the post-softmax weights for each sample and averaging the values over all samples. In addition, we calculated the same statistics for the top 5% of samples with the highest weights. This provides additional insights as we argue that unique local interactions might only exist for a subset of the samples.

We can observe that on average, the highest weighted estimator comprises a small number of ~3 internal and ~4 leaf nodes, allowing for easy interpretation. Furthermore, on average, the highest weighted estimator is the same for ~33% of the data instances with a total of ~44 different estimators having the highest weight for at least one instance. If we further inspect the top 5% of instances with the highest weight for a single estimator, we can observe that the same estimator has the highest weight for ~63% of these instances and only ~5 different estimators achieve the highest weight for at least one instance. This indicates the presence of a small number of local experts for most datasets, having high weights for certain instances where the local rules can be applied.

In the subsequent analysis, we evaluate the distribution of the weights in more detail, focusing on skewness as a measure of distribution asymmetry and kurtosis as a measure of tailedness. In general, it stands out that both values increase significantly when considering only the top 5% of samples with the highest weight for a single estimator. This again indicates the presence of local expert estimators for a subset of the data, where unique local interactions were identified. As this is very dataset-specific, we will give a more detailed analysis in the following. The exact values for each dataset are summarized in the Appendix D.

We thank the reviewer for their time and for providing us with promising suggestions!

Instead of using exclusively binary class benchmark datasets, could the authors also present comparative results for multi-label classification problems?

TL;DR: GRANDE outperforms existing methods on several multi-class datasets

In our paper, we focused on binary classification tasks to present a comprehensive evaluation within the limited scope. Yet, we acknowledge the importance of demonstrating that our method is applicable beyond binary classification. Therefore, we conducted additional experiments on several openml multi-class tasks (we used the multi-class datasets from [1]) detailed below. We report the results both without HPO and with HPO (30 trials for all methods, constrained by the limited time available during the rebuttal period).

Similar to binary classification, GRANDE outperforms SOTA methods on several datasets for multi-class tasks without additional adjustments of our method. Accordingly, the results for multi-class classification are in line with the results on binary classification tasks presented in the paper. We also included the results in the appendix of our revised version.

HPO (30 trials):

Default Parameters (summarized):

It would be valuable if the authors could include comparisons with other tree ensemble methods, such as random forest and extra trees.

We included random forests and extra trees to our evaluation. The results are presented below. Due to lack of space, we were not able to adjust the results table in the main part of our paper, but included them to the Appendix C (Table 13-15). The results are consistent with the claims in our paper: GRANDE achieves superior results both with default parameters and after HPO.

HPO (250 trials):

Default:

We appreciate the reviewer's constructive feedback and further thank the reviewer for highlighting the strengths of the proposed method!

My major concern is about hyper-parameters tuning (section C of appendix): I understand that compute resources should be spared, but it seems unfair to optimize the number of trees for GRANDE but not for XGBoost and CatBoost, especially given the fact that XGBoost and CatBoost are the cheapest algorithms to train.

TL;DR: Tuning the number of estimators for XGBoost and CatBoost has only minor impact on the performance and the results remain unchanged.

We understand the concerns. The decision to use early stopping instead of tuning the number of estimators was made in line with related work [1] to increase search efficiency (not only based on the runtime). Yet, we conducted an additional experiment where we also tuned the number of estimators. Overall, this did not significantly impact the performance of tree-based methods: The average performance slightly decreased when tuning the estimators for both XGBoost (by 0.0010) and CatBoost (by 0.0003). Consequently, for both methods, performance slightly increased in 10 out of 19 datasets and decreased in the remaining 9. In the following, we summarized the comparison of all methods when tuning the number of estimators. The complete results can be found in the appendix of the revised paper (Table 21 and Table 22). These additional results are consistent with the claims in our paper.

The results of GRANDE are good on several datasets, but become less impressive when the number of features is high

In general, our method excels in handling datasets with a small to medium number of features. For very high-dimensional datasets, learning GRANDE becomes more challenging (as the matrices $I \in \mathbb{R}^{2^d-1 \times n}$ and $T \in \mathbb{R}^{2^d-1 \times n}$ scale with the number of features). This challenge is addressed by using a feature subset for each estimator, supported by our instance-wise weighting, which allows assigning higher weights to estimators focusing on more important features. Although GRANDE showed comparatively modest results on the madelon dataset (500 features) and the Bioresponse dataset (1,776 features), it outperformed other methods on the SpeedDating dataset (256 features).

The 2^d term in the sums suggests that the depth is a real limitation of the method.

Theoretically, depth is a limitation of the method. However, in practice, GRANDE can be efficiently trained up to a depth of 10. Preliminary experiments indicated that a depth of 6 is sufficient to achieve SOTA performance, as increasing the depth further does not significantly impact performance.

We thank the reviewer for their time and providing us with valuable feedback!

Because the final results are weighted by Softmax, the prediction of each tree is not separate now. If we cut off one tree, the contributions of the other tree are also changed. This is different from XGB and NODE, but the authors did not point out it.

Thank you for pointing this out. Indeed, when employing a softmax function to calculate the weights for GRANDE, the individual tree predictions are not separated. Therefore, the contributions of individual trees change. This occurs not only in scenarios such as removing one tree from the ensemble but also during instance-wise weighting: Assume we have two data instances that are very similar and the prediction of our ensemble differs only in one tree. For this particular tree, depending on the different paths taken by the samples, we select two distinct logits. Consequently, when calculating the softmax to generate the weights, the contribution of each tree changes.

This aspect is crucial in enabling the learning of "local experts" within GRANDE. If the path capturing a unique local interaction is traversed by a sample, the corresponding tree should have a very high weight, resulting in reduced weights for the remaining trees.

We acknowledge that this aspect was not adequately addressed in the current version of the paper, and have therefore provided clarification in the revised version (Section 3.3).

Moreover, it is better to analysis the distribution of instance weights. For example: a) Is it long-tailed? b) Are some trees very important for most of the samples?

TL;DR: (a) In most cases, the distributions are long-tailed (and heavy-tailed). (b) On average, for 38% of the samples, the same tree is the most important one, but this is very dataset- and instance-specific (see discussion below).

[Also see response to SMN1]

Within our paper, we showed in an ablation study that our instance-wise weighting has a positive impact on the performance of GRANDE. In addition, we showcased a real-world scenario where the weighting significantly increases local interpretability by enabling the model to learn representations for simple and complex rules. We agree with the reviewer that a more comprehensive analysis of the weighting would be beneficial and therefore provide additional statistics. We summarize the main results below and provide detailed statistics for each dataset, along with an additional discussion in Appendix D.

The following statistics were obtained by calculating the post-softmax weights for each sample and averaging the values over all samples. In addition, we calculated the same statistics for the top 5% of samples with the highest weights. This provides additional insights as we argue that unique local interactions might only exist for a subset of the samples.

We can observe that on average, the highest weighted estimator comprises a small number of ~3 internal and ~4 leaf nodes, allowing for easy interpretation. Furthermore, on average, the highest weighted estimator is the same for ~33% of the data instances with a total of ~44 different estimators having the highest weight for at least one instance. If we further inspect the top 5% of instances with the highest weight for a single estimator, we can observe that the same estimator has the highest weight for ~63% of these instances and only ~5 different estimators achieve the highest weight for at least one instance. This indicates the presence of a small number of local experts for most datasets, having high weights for certain instances where the local rules can be applied.

Too many hyperparameters, i.e. 11 are tuned for the proposed method. While the number of hyperparameters is no more than 4 for compared methods. We have reason to doubt that the performance gain is obtained by finer hyperparameter tuning. Could you reduce your number of hyperparameters to 4 and retrain your model for comparison?

TL,DR: When reducing the number of hyperparameters or the number of trials, GRANDE still achieves SOTA performance

We understand the concerns regarding the number of hyperparameters. We already tried to account for this with the default hyperparameter experiment included in the original version of the paper (Table 3 and Table 8), demonstrating that GRANDE achieved superior results even without hyperparameter optimization. Acknowledging the importance of this topic, we have included two additional experiments focusing on hyperparameter optimization:

1. Reduced number of trials to 30: We reduced the number of trials in the HPO from originally 250 trials to 30 for all methods (similar to [1]) to compare the performance with a less extensive search. We can observe that GRANDE has the greatest benefit when increasing the number of trials. Yet, even with only 30 trials, GRANDE achieves the highest mean reciprocal rank (MRR) and normalized mean, as well as the most wins. The detailed results on all datasets along with a discussion are included in the appendix of the revised paper version and summarized in the following table:

   	GRANDE	XGBoost	CatBoost	NODE
   Normalized Mean	0.694	0.430	0.676	0.336
   Mean Reciprocal Rank (MRR)	0.636	0.434	0.579	0.434
   Count	8	3	5	3

2. Reduce grid for GRANDE to 4 parameters: Following the reviewer's suggestion, we reduced the number of hyperparameters for GRANDE to four (one learning_rate, dropout, loss, and cosine_decay) and conducted an additional HPO with 250 trials. Unfortunately, we could not complete the search for all datasets during the rebuttal period (nomao and adult datasets are pending and will be included in the camera-ready version). Reducing the grid results in a slightly worse performance for GRANDE. Especially, optimizing separate learning rates for different components (split values, split indices, leaf probabilities, and leaf weights) using a larger grid did further enhances GRANDE's performance. Yet, the results are in line with the claims from the paper and GRANDE still has the highest normalized mean, MRR and number of wins.

   	GRANDE	XGBoost	CatBoost	NODE
   Normalized Mean	0.736	0.428	0.710	0.364
   Mean Reciprocal Rank (MRR)	0.652	0.358	0.608	0.466
   Count	7	0	6	4

[1] McElfresh, Duncan C., et al. ‘When Do Neural Nets Outperform Boosted Trees on Tabular Data?’ Thirty-Seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023, https://openreview.net/forum?id=CjVdXey4zT.

"WindTunnel: Towards Differentiable ML Pipelines Beyond a Single Model" also seems closely related, though they only fine-tune existing tree models with gradient descent.

WindTunnel tries to bring the advantage of a joint, global optimization inherent in DL frameworks to a complete ML pipeline. For GBDTs in the pipeline, this is achieved by smoothing the non-differentiable operations. Thereby, the beneficial inductive bias of axis-aligned splits, which is maintained using GRANDE, is lost. However, we believe that it is an interesting direction for future research to integrate GRANDE in a differentiable pipeline (as proposed by WindTunnel) as this would maintain the inductive bias of axis-aligned splits while still allowing an optimization of the pipeline with gradient descent.

I find it also somewhat confusing that it is claimed that gradient boosted models are the defacto state-of-the-art on tabular data, when there has been a lot of recent work on neural networks for tabular data, often outperforming gradient boosting models, see "Well-tuned Simple Nets Excel on Tabular Datasets" by Kadra for example. It would be great to include at least one other neural approach in the comparison.

TL;DR: We included SAINT as additional gradient-based benchmark and GRANDE demonstrates superior results.

We are aware that there also exist papers highlighting the strengths of DL methods on tabular data, like the mentioned paper by Kadra et al. However, it is important to note that their evaluation primarily focused on balanced datasets[1], reporting the accuracy and did not consider advanced encoding techniques for GBDT methods. Furthermore, their experiments included an extensive HPO with up to 4 days of time limit for each dataset [1]. Yet, several recent papers still claim that, even though the gap is diminishing, GBDT are still considered SOTA [2,3,4]. At NeurIPS2023 there is an additional survey paper by McElfresh, Duncan C., et al.[5] accepted that confirms superior results of GBDT methods over a total of 176 datasets (even though they highlight that the gap to gradient-based methods is diminishing). Based on your feedback, we included Kadra et al. [1] to the related work section of our revised paper.

In summary, we agree that an additional, gradient-based benchmark would be beneficial and therefore added SAINT to our evaluation (which is according to [2] the superior gradient-based method). The new results are summarized in the following and are also included in the revised paper version (in the appendix due to lack of space in the main part). We provide the results with default parameters and after HPO. Due to the high computational demands of SAINT, we limited the HPO to 30 trials for all methods, which is in line the experiments in [5]. Furthermore, SAINT resulted in a OOM error (on an RTX A6000 with 47.55GB VRAM) for Bioresponse (1,776 features) which is why we excluded this dataset. The results are summarized in the following and detailed results for each datasets can be found in the Appendix C.

SAINT achieves competitive results on many datasets (best method for one datasets), but also exhibits very poor performance on some datasets (e.g. for madelon only the majority class is predicted). As a result, the claims from our paper remain unchanged and GRANDE achieved superior results on most datasets, significantly outperforming existing gradient-based methods.

HPO (30 trials):

Default Parameters:

We thank the reviewer for their time and valuable feedback!

Given the popularity of gradient-based tree models in recent years, I feel like a more thorough comparison with competing methods would be warranted. In particular relating this work to work on learning weighting for fixed tree structures would be interesting, as first discussed in "Practical Lessons from Predicting Clicks on Ads at Facebook" by He et.al. "Deep Neural Decision Trees" by Yang et al also seems relevant, as well as "Deep Neural Decision Forests" by Kontschieder et al, "SDTR: Soft Decision Tree Regressor for Tabular Data" by Luo and ". The tree ensemble layer: Differentiability meets conditional computation." by Hazimeh et al.

We are aware that due to lack of space, the related work section was comparatively short and did not cover all related, gradient-based tree methods in detail. We adjusted the related work section (and the section on instance-wise weighting) to cover the mentioned works and provide a more detailed differentiation of our approach as follows:

• "Practical Lessons from Predicting Clicks on Ads at Facebook": They use GBDTs as feature transformers to generate categorical input features for a sparse linear classifier which can be seen as learning a weighting for the GBDT. There are two main differences to our work (now discussed in Section 3.3):

  1. Instead of learning a post-hoc weighting, we incorporate the weighting into the training procedure.
  2. We learn instance-wise weights that are calculated individually for each instance based on the selected paths in the ensemble.

  These two aspects allow learning unique local interactions ("local experts") during the training of our model as showcased in the case study (Section 4.3).

• "Deep Neural Decision Trees": DNDTs in contrast to GRANDE uses soft trees. However, similar to our trees, they use axis-aligned splits which differentiates DNDTs to most hierarchical, gradient-based methods. The GradTree paper [6] also discussed the similarities and differences and includes an empirical comparison. During the empirical comparison, they showed that GradTree (the tree structure we adopted) significantly outperformed DNDTs. In the following we will shortly summarize the differences; a more detailed discussion can also be found in [6]:

  1. As already mentioned, the trees are soft.
  2. The use of the Kronecker product for building the tree with comes with two major limitations:
     • The tree size depends on the number of features and therefore scales poorly for large datasets (only a maximum number of 12 features per tree is possible according to the authors).
     • The use of the Kronecker product prevents splitting on the same feature multiple times within one tree which is often important.

The following methods have in common that they learn soft, oblique trees. We will first give a short summary of the method and then discuss their differences to GRANDE:

• "Deep Neural Decision Forests": NDFs use a stochastic routing (soft splits) with oblique splits with the goal of guiding representation learning in the lower layers of a CNN.
• "SDTR: Soft Decision Tree Regressor for Tabular Data": SDTR tries to imitate binary decision trees by a neural model and therefore optimizes soft decision trees (SDTs) e.g. using additional regularization. Their model outperforms non-interpretable MLP structures, but only achieved comparable (slightly worse) performance to non-gradient-based methods (i.e., CatBoost and XGBoost outperformed SDTR).
• "The tree ensemble layer: Differentiability meets conditional computation.": Similarly, they use a stochastic routing and oblique splits with the goal of designing a differentiable layer that can be incorporated in a DL framework.

All the previously mentioned works have a hierarchical tree ensemble structure, achieving differentiability by employing soft and oblique split functions. Therefore, they are very similar to NODE which we benchmarked against in our evaluation as it is according to recent surveys [2,3] the superior hierarchical tree ensemble method. The main difference in the tree structure between existing work and GRANDE is that we employ the ST-operator to maintain hard, axis-aligned splits which provides a beneficial inductive bias (see discussion in Section 3.2 and Section 5).