I added return_as="generator" for memory performance which will break the tests on the CI machines that use joblib version 1.2, until the minimum version is bumped to 1.3

I added return_as="generator" for memory performance which will break the tests on the CI machines that use joblib version 1.2, until the minimum version is bumped to 1.3

You could maybe condition on the joblib version ?

You could maybe condition on the joblib version ?

We opened a PR to bump to the next version anyway as it will be old enough by next release 🤷‍♂️

Can someone give me a short summary and in particular the formulae of the implemented features importances?

Can someone give me a short summary and in particular the formulae of the implemented features importances?

The classical MDI uses the impurity of the nodes computed during training, which in binary classification is :
$H(t) = 1 - p_{t,0}^2 - (1 - p_{t,0})^2$. The authors of UFI suggest using a modified impurity measure: $H'(t) = 1 - p_{t,0} p^\prime_{t,0} - (1 - p_{t,0})(1 - p^\prime_{t,0})$ where $p_{t,0}$ and $p^\prime_{t,0}$ are the proportion of training and testing samples respectively of class 0 that go through the evaluated node $t$. Since we are doing bagging in Random Forests, these test samples are readily available in the out-of-bag (oob) samples.

Once these modified impurity measures are computed with the oob samples, we compute the same decrease in impurity as in traditional MDI : $\Delta^\prime (t) = \omega_t H^\prime (t) - \omega_l H^\prime (l) - \omega_r H^\prime (r)$ where $l$ and $r$ designate the left and right children of $t$ and $\omega_t$ is the proportion of training samples going through $t$.

This can be extended to multi-class classification and in regression we use a similar idea to compute node impurity that uses in and out of bag information : $H^\prime(t) = \frac{1}{n^\prime_t} \sum_{x^\prime_i \in R_t}(y^\prime_i - \bar{y}_t)^2$. $\bar{y}_t$ is the node value, $(x^\prime_i, y^\prime_i)_i$ are oob samples.

I went into more details in this document, where I also compare this method to the alternative proposed in this paper.

@lorentzenchr

@GaetandeCast Thanks a lot for your summary.

TLDR (summary)

What is the difference to the out-of-bag (oob) score of a random forest?

Details

The Brier score in binary classification ($y \in {0, 1}$) is a different name for the squared error: $BS(y_{obs}, p_{pred}) = (y_{obs} - p_{pred})^2$.
Each tree node minimizes this score $\sum_{i \in node} BS(y_{obs, i}, p_{pred, i})$, meaning it predicts $p_{pred} = \bar{y} = average(y \in node) = \frac{1}{n_{node}}\sum_{i \in node} y_i$ (so we predict probabilities like good statisticians).
Plugging it back into the Brier score gives the Brier score entropy, aka Gini score, $Gini = \sum_{i \in node} \bar{y}(1 - \bar{y})$.

If one wants to use the oob sample instead of the training sample then one simply can use the Brier score. The same logic applies to all (strictly consistent) loss functions (and to regression).

From the formula of the UFI suggestion, I am unable to recover the Brier score on the oob sample. Neither can I find any derivation in their paper. I also think it is plain wrong because they mix the empirical means of 2 independent data samples, i.e., $p$ and $p^\prime$. Unless I have not understood something fundamental, that, honestly, seems like nonsense to me.

Edit: If one restricts to the oob sample that flows through that fixed node, meaning p_pred is constant, than one has $\bar{BS}=\bar{y}(1-2p_{pred})+p_{pred}^2$.

If I understand correctly @lorentzenchr, you suggest computing the impurity (Gini/Brier/MSE/...) of the oob samples directly, and use those to measure feature importance.

However this is not sufficient to solve the cardinality bias of the MDI, which is why the two proposed methods suggest mixing metrics based on both in and out of bag samples. One of the reasons the bias is still seen on purely out-of-bag samples is that an impurity measure is always positive and even a random feature will manage to create purity. Therefore even when computed on oob samples, random/uninformative features will be assigned a non-zero importance.

This is actually the first approach I tested and I got feature importance measures very close to the default (biased) ones on the docs example about MDI vs permutation importance.

This idea is also mentioned in the paper of the second method, MDI-oob, in section 3.2 where they also advise against it.

UFI on the other hand is proven to give zero-importance to features independent of the target (Theorems 2 & 4), which is minimum for a feature importance measure.

If I understand correctly, you suggest computing the impurity (Gini/Brier/MSE/...) of the oob samples directly, and use those to measure feature importance.

@GaetandeCast Yes.

To be very honest but without intent to be disrepectful to any researcher, I find the literature that I have seen on bias of MDI feature importance¹ partially poor (again, may be due to my ignorance). Does anybody actually define the bias they talke about? Why should in-sample (training) impurity be biased for measuring feature importance of a tree? I know that the loss is biased, but the feature importance? How is feature importance defined statistically (not empirically), I mean in terms of statistical quantities like distributions, expectations, etc? If you can't define what you are talking about, how can you talk about bias of that object. Why do we interprete the high importance of random features (or high cardinality) as bias? Why don't interprete it as a tree/random forest (RF) poorly overfitting those features? If so, the whole question would shift away from bias of feature importance to fixing the fitting algorithms of trees/RF to avoid overfitting. We would even interprete the high importance not as a sign of bias of the importance but as a valuable tool to measure overfitting.

If you want to use the statistical risk/expected loss as measure for feature importance, out-of-bag is the best cheapest thing you have for random forests, otherwise you would need to use a so far unused (test) sample (similar to honest trees).

And yes, all impurity measures are non-negative. They are generalized entropies and a free constant term is usually set such that the minimum is 0, hence non-negative. Example: The entropy of the squared error (=minimum of expected squared error) is the variance, entropy of log loss is Shannon entropy. Why blame the loss/entropy (impurity), why not define feature importance in a different way?

I have not looked yet deeper into the 2nd paper (MDI-oob).

¹ Strobl et al (2007) https://doi.org/10.1186/1471-2105-8-25 correctly identifies the root cause: variable selection bias (not MDI bias).

I understand the concern and I agree that the UFI paper does not do a great job of defining the issue and setting a theoretical framework. This is done in a much better way in section 2 of MDI-oob, where they give non asymptotic bounds on the sum of importance of irrelevant features. The bounds are proportional to the size of the leafs (deeper trees lead to more biased FI) and the upper bound is stricter when features are categorical (matches empirical result about cardinality).

The most convincing framework to define feature importance mathematically is that of Shapley values from game theory. In this framework, we want to satisfy the four axioms of TU-values, among which is the null player: a feature independent of the output should receive zero importance. This paper shows that in asymptotic regime and under quite specific conditions (Extra-tree with max_feature=1, categorical features and output) the MDI recovers Shapley values. In this context, empirical results show that UFI converges quite sooner than MDI to these asymptotic values. I am currently investigating how well this result holds when relaxing the conditions.

In a nutshell, the two methods modify the MDI to try to get the desirable properties of Shapley values, while being much cheaper to compute.

This paper shows that in asymptotic regime and under quite specific conditions (Extra-tree with max_feature=1, categorical features and output) the MDI recovers Shapley values.

To be more specific, MDI recovers Shapley values of the loss improvement w.r.t the null model (i.e. MSE, Brier score or log-loss depending on the choice of the splitting criterion: MSE, Gini or Shannon entropy). @GaetandeCast has already conducted some experiments to validate that this is empirically the case. I think this is an interesting property, but it's only valid under restrictive conditions: extra trees with asymptotic regime, binary valued features, max_features=1, ... For regular random forests trained on continuous features, we can sometimes empirically observe small but significant discrepancy with the estimated SAGE values.

By the way, in the asymptotic regime, all three methods (train MDI, UFI and MDI-oob) converge to the same values. So the Shapley value interpretation of any MDI variant is rarely possible in general. One could argue that UFI has a faster convergence than train MDI towards SAGE values, for many datasets/model combinations, but I am not sure if this is always the case.

In my opinion, UFI (and MDI-oob) are mostly interesting as a very cheap yet robust way to find out which features can be safely discarded because they do not help the model generalize, irrespective of the relative cardinality of the features. Train MDI (or naive OOB MDI) cannot achieve this because they can assign larger importance values to large cardinality features that are independent of the target than lower cardinality features with a small to medium association with the target.

SAGE values in particular are computationally expensive to compute and require a test set.

Permutation importance are also quite expensive to compute (but cheaper than SAGE) and also require a test set. MDI-based importances are much cheaper (nearly free) and do not require extra training data (when computed for bagging ensemble of trees).

Let me rephrase: Are we trying to solve the wrong problem?
Decision trees have a training problem. They prefer splits of features with many split points (even when the feature has no correlation with y). Shouldn’t we rather fix the tree learning instead of the (in my point of view - correct) feature importance measure like MDI.

Shouldn’t we rather fix the tree learning instead of the (in my point of view - correct) feature importance measure like MDI.

How would you translate this into an implementable setting?

One possible way would be to user recommend to always use Random Forests on KBinsDiscretizer pre-preprocessed data and tune the number of bins jointly with the RF hyper-parameters. Then look at the MDI of the resulting pipeline and see if we still have possibly misleading MDI values or not.

@glouppe @mnwright @mayer79 your advice and insights would be very valuable for this issue in scikit-learn.