Reference Issues/PRs

Fixes #20059

What does this implement/fix? Explain your changes.

This implements two methods that correct the cardinality bias of the feature_importances_ attribute of random forest estimators by leveraging out-of-bag (oob) samples.
The first method is derived from Unbiased Measurement of Feature Importance in Tree-Based Methods, Zhengze Zhou & Giles Hooker. The corresponding attribute is named ufi_feature_importances_.
The second method is derived from A Debiased MDI Feature Importance Measure for Random Forests, Xiao Li et al.. The corresponding attribute is named mdi_oob_feature_importances_.
The names are temporary, we are still seeking a way of favoring one method over the other (currently investigating whether one of the two reaches asymptotic behavior faster than the other).

These attributes are set by the fit method after training, if the parameter oob_score is set to True. In this case we send the oob samples to a Cython method at tree level that propagates them through the tree and returns the corresponding oob prediction function and feature importance measure.

This new feature importance measure has a similar behavior to regular Mean Decrease Impurity but mixes the in-bag and out-of-bag values of each node instead of using the in-bag impurity. The two proposed method differ in the way they mix in-bag and oob samples.

This PR also includes these two new feature importance measures to the test suite, specifically in test_forest.py. Existing tests are widened to test these two measures and new tests are added to make sure they behave correctly (e.g. they coincide with values given by the code of the cited papers, they recover traditional MDI when used on in-bag samples).

Any other comments?

The papers only suggest fixes for trees built with the Gini (classification) and Mean Squared Error (regression) criteria, but we would like the new methods to support the other available criteria in scikit-learn. log_loss support was added for classification with the ufi method by generalizing the idea of mixing in-bag and oob samples.

Some CPU and memory profiling was done to ensure that the computational overhead was controlled enough compared to the cost of model fitting for large enough datasets.

Support for sparse matrix input should be added soon.

This work is done in close colaboration with @ogrisel.

TODO:

• Fix the tests related to oob_score_
  Done in d198f20
• Add support for sparse input data (scipy sparse matrix and scipy sparse array containers).
  support: 8329b3b
  test: 0b48af4
• Add support and tests for sample_weight
  Support added in f10721e. Test in 241de66
• Expose the feature for GradientBoostingClassifier and GradientBoostintRegressor when row-wise (sub)sampling is enabled at training time.
  Done in ce52159
• Shall we expose some public method to allow the user to pass held-out data instead of just computing the importance using OOB samples identified at training time?
• Separate gradient boosting from this pr
  8a09b39
• Update doc example on permutation vs mdi to include ufi & mdi_oob
  229cc4d
• Think about an API to expose feature importance confidence intervals based on tree level booststraping

Edit: We noticed a discrepancy between the formula defined by the authors of mdi_oob and what their code does. This is detailed here, in part 5. We will therefore focus on refining the implementation of UFI and might later discard the code related to mdi_oob before merging