  Due to their power and ease of use, tree-based machine learning models, such
as random forests and gradient-boosted tree ensembles, have become very
popular. To interpret them, local feature attributions based on marginal
expectations, e.g. marginal (interventional) Shapley, Owen or Banzhaf values,
may be employed. Such methods are true to the model and implementation
invariant, i.e. dependent only on the input-output function of the model. We
contrast this with the popular TreeSHAP algorithm by presenting two
(statistically similar) decision trees that compute the exact same function for
which the "path-dependent" TreeSHAP yields different rankings of features,
whereas the marginal Shapley values coincide. Furthermore, we discuss how the
internal structure of tree-based models may be leveraged to help with computing
their marginal feature attributions according to a linear game value. One
important observation is that these are simple (piecewise-constant) functions
with respect to a certain grid partition of the input space determined by the
trained model. Another crucial observation, showcased by experiments with
XGBoost, LightGBM and CatBoost libraries, is that only a portion of all
features appears in a tree from the ensemble. Thus, the complexity of computing
marginal Shapley (or Owen or Banzhaf) feature attributions may be reduced. This
remains valid for a broader class of game values which we shall axiomatically
characterize. A prime example is the case of CatBoost models where the trees
are oblivious (symmetric) and the number of features in each of them is no
larger than the depth. We exploit the symmetry to derive an explicit formula,
with improved complexity and only in terms of the internal model parameters,
for marginal Shapley (and Banzhaf and Owen) values of CatBoost models. This
results in a fast, accurate algorithm for estimating these feature
attributions.
