On marginal feature attributions of tree-based models

Overview

• Tree-based machine learning models, such as random forests and gradient-boosted tree ensembles, are popular due to their power and ease of use.
• To interpret these models, local feature attributions based on marginal expectations, like marginal Shapley, Owen or Banzhaf values, can be employed.
• Such methods are true to the model and implementation invariant, meaning they depend only on the input-output function of the model.
• The paper contrasts this with the popular TreeSHAP algorithm and presents decision trees that compute the same function but yield different feature rankings with TreeSHAP.

Plain English Explanation

Tree-based machine learning models, like random forests and gradient-boosted trees, have become very popular because they are powerful and easy to use. To understand how these models make their predictions, researchers often look at the "importance" or "attribution" of each input feature.

One approach is to use marginal feature attributions, which consider how much each input feature contributes to the model's output on average. Methods like Shapley, Owen, and Banzhaf values can be used to calculate these marginal attributions. These methods are reliable because they depend only on the overall behavior of the model, not its internal structure.

In contrast, the popular TreeSHAP algorithm looks at the model's internal structure to estimate feature importance. The paper shows that TreeSHAP can give different feature rankings for two decision trees that compute the exact same function. The marginal Shapley values, however, coincide for these two trees.

Technical Explanation

The paper explores how the internal structure of tree-based models can be leveraged to efficiently compute marginal feature attributions, such as Shapley, Owen, or Banzhaf values. The key observations are:

1. Tree-based models define piecewise-constant functions over a grid partition of the input space determined by the model structure.
2. Only a subset of all features typically appears in the trees of an ensemble model, reducing the complexity of computing marginal feature attributions.
3. For CatBoost models, where the trees are "oblivious" (symmetric), the number of features in each tree is no larger than the tree depth. This symmetry can be exploited to derive an explicit formula for marginal Shapley, Banzhaf, and Owen values, resulting in a fast and accurate algorithm.

Experiments with XGBoost, LightGBM, and CatBoost libraries confirm these insights and demonstrate the efficiency gains of the proposed approach compared to standard Shapley value estimation methods.

Critical Analysis

The paper provides a thorough analysis and a novel approach to efficiently computing marginal feature attributions for tree-based models. However, a few potential limitations and areas for further research are worth considering:

1. The paper focuses on tree-based models, but it would be valuable to explore the applicability of the proposed techniques to other model types, such as neural networks.
2. The paper assumes that the internal structure of the tree-based models is available, which may not always be the case, especially for deployed models.
3. The paper does not address the potential issues with Shapley-based explanations in certain scenarios, such as when the feature dependencies are complex.

Further research could investigate ways to overcome these limitations and explore the broader implications of the efficient marginal feature attribution techniques presented in the paper.

Conclusion

This paper makes a significant contribution to the interpretation of tree-based machine learning models. By leveraging the internal structure of these models, the authors present efficient algorithms for computing marginal feature attributions, such as Shapley, Owen, and Banzhaf values. These techniques can provide reliable and fast model interpretations, which is crucial for the responsible deployment of powerful tree-based models in real-world applications.