PaperlayerView exact revision on arXiv

Source-linked AI summary

A Debiased MDI Feature Importance Measure for Random Forests

Xiao Li, Yu Wang, Sumanta Basu, Karl Kumbier, Bin Yu

arXiv:1906.10845v2stat.MLcs.LG

TL;DR

MDI is widely used, but it can assign high importance to noisy features, and reducing this bias through its existing analytical expression is unclear. The paper derives a finite-sample bias bound and a new out-of-bag measure; MDI-oob achieves state-of-the-art feature-selection performance in simulations and on a genomic ChIP dataset.

  • Problem

    MDI can assign high importance to noisy features, and how to reduce its feature-selection bias using its existing analytical expression is unclear.

    Source: §1 · p. 2

  • Method

    The authors bound the expected MDI bias for noisy features and derive a new analytical expression used to define MDI-oob with out-of-bag samples.

    Source: §1 · p. 2

  • Results

    Across simulated data and a genomic ChIP dataset, MDI-oob achieved state-of-the-art feature-selection performance and 5%–10% higher AUC than several package-based measures.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The bound indicates that deep trees generally have higher expected feature-selection bias than shallow trees.

    Source: §5 · p. 9

    The bias theorem requires noisy features to be independent of relevant features, limiting its scope for correlated features.

    Source: §2.2 · p. 4

Abstract

from arXiv · show

Tree ensembles such as Random Forests have achieved impressive empirical success across a wide variety of applications. To understand how these models make predictions, people routinely turn to feature importance measures calculated from tree ensembles. It has long been known that Mean Decrease Impurity (MDI), one of the most widely used measures of feature importance, incorrectly assigns high importance to noisy features, leading to systematic bias in feature selection. In this paper, we address the feature selection bias of MDI from both theoretical and methodological perspectives. Based on the original definition of MDI by Breiman et al. for a single tree, we derive a tight non-asymptotic bound on the expected bias of MDI importance of noisy features, showing that deep trees have higher (expected) feature selection bias than shallow ones. However, it is not clear how to reduce the bias of MDI using its existing analytical expression. We derive a new analytical expression for MDI, and based on this new expression, we are able to propose a debiased MDI feature importance measure using out-of-bag samples, called MDI-oob. For both the simulated data and a genomic ChIP dataset, MDI-oob achieves state-of-the-art performance in feature selection from Random Forests for both deep and shallow trees.

1 Introduction

Random Forest feature importance helps interpret predictions, but MDI can favor noisy features, motivating analysis of its bias and a new out-of-bag measure. The paper situates this work among alternative importance measures and previews its theoretical analysis, method, and evaluations.

1 Introduction

  • MDI can assign high importance to noisy numerical or many-category features, while early stopping has been shown in simulations to reduce this feature-selection bias.The paper analyzes expected bias and reports that deep trees with small leaves suffer more.Source: §1 · p. 2
  • MDI-oob uses a new analytical expression and out-of-bag samples; across simulations and a genomic dataset, it achieved 5%–10% higher AUC than several package-based measures.The comparisons include party, ranger, and scikit-learn.Source: §1 · p. 2

1.1 Related works

  • Related work covers split counts, permutation-based MDA, tree SHAP, and methods that alter tree construction or evaluate impurity using out-of-bag samples.The authors distinguish their implementation from Zhou and Hooker (34), claiming higher computational efficiency.Source: §1.1 · p. 2

1.2 Organization

  • The paper proceeds from finite-sample bias analysis to a new MDI characterization and MDI-oob, then compares feature-selection accuracy on simulated and genomic ChIP data.The final section discusses future directions.Source: §1.2 · p. 3

2 Understanding the feature selection bias of MDI

This section analyzes the finite-sample feature-selection bias of MDI, which can assign importance to noisy features. It gives a non-asymptotic bound and identifies tree depth, minimum leaf size, and feature type as relevant to controlling that bias.

2.2 Finite sample bias of MDI importance for Random Forests

  • The analysis gives a tight non-asymptotic bound on expected noisy-feature MDI, with the bound depending on tree depth and minimum leaf size.For balanced trees, the depth is at most log2 n; expected noisy-feature importance is roughly inversely proportional to minimum leaf size.Source: §2 · p. 3, §2.2 · p. 5

2.1 Background and notations

  • Random Forest trees are grown recursively by selecting candidate features and choosing splits, and MDI sums the impurity reductions contributed by a feature’s splits.The trees stop splitting when a child would contain too few samples or all responses are identical.Source: §2.1 · pp. 3–4

2.2 Finite sample bias of MDI importance for Random Forests

  • The analysis assumes noisy features are independent of relevant features, although relevant features need not be mutually independent.The authors note that correlated features are common in practice and difficult for feature-selection methods.Source: §2.2 · p. 4
  • Noisy-feature importance can be better controlled when features are categorical rather than numerical.The passage attributes this difference to fewer candidate split points for categorical features.Source: §2.2 · p. 5
  • Relevant-feature MDI may also decrease as minimum leaf size increases, but simulations show a slower decrease, especially for sparse underlying models.The theorem’s noisy-feature bound is roughly inversely proportional to minimum leaf size.Source: §2.2 · p. 5

3 MDI using out-of-bag samples (MDI-oob)

The section develops MDI-oob by expressing MDI as a response–feature-function covariance and evaluating that covariance on out-of-bag samples. This targets the greater feature-selection bias associated with smaller leaves and usually deeper trees.

3 MDI using out-of-bag samples (MDI-oob)

  • Smaller minimum leaf sizes, which usually correspond to deeper trees, are associated with more severe MDI feature-selection bias.For balanced trees, the noisy-feature importance bound is of order log(p)/mn when log(n) terms are ignored.Source: §3 · p. 5

3.2 Evaluating MDI using out-of-bag samples

  • MDI-oob evaluates a new covariance expression for MDI using out-of-bag samples, and the results also apply to forests.For each tree, it computes fT,k for out-of-bag samples and evaluates the covariance; its computational cost is roughly that of predicting those samples.Source: §3 · p. 6, §3.2 · pp. 6–7

3.1 A new characterization of MDI

  • MDI importance for feature k can be expressed as the sample covariance between the response and fT,k, motivating out-of-bag evaluation.The original definition sums impurity decreases at inner nodes split on feature k.Source: §3.1 · p. 6
  • The functions fT,k also represent per-sample feature contributions previously used to interpret Random Forest predictions [24].The paper notes that these functions can be computed with the treeinterpreter package.Source: §3.1 · p. 6
  • For classification, one-hot encoding makes response variance equivalent to the Gini index, so the results also apply to classification trees.The paper states this equivalence for categorical responses.Source: §3.1 · p. 6

3.2 Evaluating MDI using out-of-bag samples

  • Directly computing node impurity decreases on out-of-bag samples is not a suitable substitute, since decreases remain positive and deep-tree bias may still be large.MDI-oob's approach depends on the new analytical expression, and its evaluation cost is roughly that of predicting the out-of-bag samples.Source: §3.2 · p. 7

4 Simulation experiments

The simulations examine MDI’s sensitivity to tree settings and compare feature-importance methods on simulated and genomic data. MDI-oob leads the simulated comparisons and usually ranks among the best on genomic data.

4 Simulation experiments

Noisy feature identification using the simulated data

Noisy feature identification using a genomic ChIP dataset

Noisy feature identification using the simulated data

5 Discussion and future directions

The discussion connects MDI-oob to reducing finite-sample bias through out-of-bag estimation and identifies unresolved extensions involving correlated features, ranking, and tighter bias bounds.

  • MDI-oob shows state-of-the-art AUC feature-selection performance on simulated and genomic ChIP data, while its expected noisy-feature bias bound decreases with minimum leaf size.Source: §5 · p. 9
  • The authors report that SHAP’s feature-selection bias increases with tree depth in their simulations and suggest OOB samples as a possible improvement.Source: §5 · p. 9
  • MDI-oob shares the honest-estimation rationale that using separate OOB data for estimation can reduce finite-sample bias from reusing tree-growing data.Source: §5 · p. 9
  • Future work asks how to accommodate correlated features, rank relevant features, and tighten the theoretical bound on MDI’s selection bias.Source: §5 · p. 9

Appendix: Proofs

The appendix proof defines sample counts and impurity decreases, then combines a tail-bound lemma with a union-bound argument to obtain an expectation bound.

  • For a region A, Nn(A) counts samples whose feature vectors lie in A; ∆I(A, k) is the largest impurity decrease over splits on feature k.Source: Appendix: Proofs · p. 12
  • The proof first establishes a tail bound for ∆I(A, k), then applies the lemma and a union bound to upper-bound G0(T).Source: Appendix: Proofs · p. 12
  • A separate argument using Gaussian comparison inequalities supplies the lower bound in the theorem’s proof.Source: Appendix: Proofs · p. 12
  • The lemma concerns impurity decrease for a feature outside the relevant set in an axis-aligned hyper-rectangle.Source: Appendix: Proofs · p. 12

Proof of the upper bound in Theorem 1

The upper-bound proof organizes candidate tree regions as rectangles induced by splits, bounds noisy-feature impurity decreases across these regions, and applies a union bound.

Proof of the lower bound in Theorem 1

The proof builds a balanced binary tree, lower-bounds impurity reduction using its deepest level, and controls node sample counts and noisy-feature splits to establish the lower bound.

Proof of the lower bound in Theorem 1

Related papers

Loading 1906.10845v2…