Source-linked AI summary
Variable importance in binary regression trees and forests
Hemant Ishwaran
TL;DR
Variable-importance measures are widely used for variable screening, but their theoretical properties for trees and forests remain limited. The paper develops a theory for binary regression trees and forests using a simpler surrogate VIMP, showing that maximal subtrees and their node mean squared errors are central to the analysis and extending the framework to paired associations and forests.
Problem
Variable-importance values are used to select variables and reduce dimensionality, including in high-throughput genomic data, yet systematic theory for trees remains needed.
Method
The paper defines VIMP through prediction-error differences under random left-right daughter assignment and analyzes maximal subtrees, node mean squared errors, paired associations, and forests.
Results
Maximal subtrees and their node mean squared errors play a fundamental role in VIMP theory, while paired associations reflect overlap between variable-specific subtrees and correlated forest effects can yield positive association values.
Takeaways & Limitations
The framework provides a theoretical starting point for understanding VIMP in random forests and for identifying paired variable associations.
Takeaways & Limitations
The surrogate noising procedure can make a non-informative variable appear informative in a single tree, although the effect will most likely be washed out over a forest.
Abstract
from arXiv · showhide
We characterize and study variable importance (VIMP) and pairwise variable associations in binary regression trees. A key component involves the node mean squared error for a quantity we refer to as a maximal subtree. The theory naturally extends from single trees to ensembles of trees and applies to methods like random forests. This is useful because while importance values from random forests are used to screen variables, for example they are used to filter high throughput genomic data in Bioinformatics, very little theory exists about their properties.
1. Introduction
The paper develops a theoretical study of variable importance in binary regression trees and forests, motivated by their use in variable selection despite limited existing theory. It introduces a simpler VIMP definition and identifies maximal subtrees and their node mean squared errors as fundamental to the analysis.
- CART and random forests rank variables by importance to support exploratory analysis, variable selection, and dimensionality reduction.Random-forest VIMP commonly compares prediction error before and after randomly permuting a variable.
- The paper addresses the need for systematic theory on VIMP and pairwise variable associations in binary regression trees and forests for continuous outcomes.
- The analysis finds that maximal subtrees and their node mean squared errors play a fundamental role in characterizing VIMP.
- The paper defines VIMP as the prediction-error difference between noising a variable through random left-right daughter assignment and leaving it unchanged.This definition is simpler to analyze theoretically than random-forest permutation VIMP while retaining similar key features.
2. Binary regression trees
A binary regression tree recursively partitions covariate space through binary splits and assigns each terminal region the mean observed outcome. Its basis functions form a nonoverlapping, orthogonal partition that supports the paper’s theory.
- A binary regression tree is grown through successive recursive binary splits of the form x_v ≤ c and x_v > c.Split values are chosen from observed covariate values, and each terminal value is the mean outcome among cases assigned to that node.
- The tree’s basis functions are product splines that indicate membership in hyper-rectangular regions defined by variables and split values.
- Recursive partitioning makes the basis functions define a nonoverlapping partition of covariate space.
- The resulting basis functions are orthogonal, a property that plays a key role in the theoretical development.
3. A surrogate VIMP
The surrogate VIMP procedure noises a variable by randomizing left-right choices in the tree, yielding a random predictor whose error reflects the locations and terminal values of variable-specific subtrees. Maximal subtrees provide the structural representation used to analyze this perturbation.
- 3. A surrogate VIMP: VIMP is defined as the difference between prediction error after noising x_v and prediction error without noising.The noising process randomly chooses daughter nodes after encountering an x_v split and continues random choices until reaching a terminal node.
- 3. A surrogate VIMP: Variables splitting closer to the root produce larger perturbations of the randomized tree and can therefore have higher VIMP.The mechanism links split location to prediction degradation under the surrogate noising process.
- 3. A surrogate VIMP: The surrogate procedure differs from random-forest permutation VIMP, which permutes x_v in out-of-bag data before dropping cases through trees grown on in-bag data.
- 3.1. Comparison to random forests: A non-informative variable can appear informative for a single tree when an early split selected through mtry is non-informative and later splits are predictive.The random path then disrupts downstream predictive splits, increasing apparent prediction error.
- 3.1. Comparison to random forests: Over a forest, this single-tree artifact will most likely be washed out because high splits on a non-informative variable occur in few trees and average toward zero VIMP.
- 3.2. Subtrees: A v-subtree begins at a node whose daughters depend on an x_v split, while a maximal v-subtree is not contained in any larger v-subtree.The large boxed tree in Figure 1 is maximal, whereas the smaller boxed subtree is not.
- 3.2. Subtrees: The predictor under noising decomposes into an unchanged component outside M_v and a random component involving terminal nodes reached through maximal v-subtrees.
- 3.3. Prediction error: Under L2-loss, VIMP compares prediction errors based on squared error, with the noised predictor requiring an additional expectation over randomized terminal values.
4. A theoretical framework for VIMP
The framework analyzes VIMP under a simplifying signal-topology assumption and connects VIMP to node mean squared error in maximal subtrees. In the limiting case, VIMP is non-negative and subtree contributions are weighted by test-point node membership.
- Assumptions: The analysis assumes the fitted signal approximates the true signal and has similar topology to the tree.The paper treats the true signal as a population parameter even though its basis functions depend on learning data.
- Derivation: Orthogonality simplifies the VIMP expression under the stated assumption, yielding a theorem involving maximal-subtree quantities.The derivation uses orthogonality, conditioning, and integration over test-point-dependent basis functions.
- Node mean squared error: Node mean squared error is defined as a weighted squared deviation between random terminal-node values and their corresponding terminal values.The weights are given by the distribution of the random terminal node reached through a maximal subtree.
- Limiting behavior: As fitted terminal values converge to their true values, each maximal v-subtree contributes equally to Δv through its node mean squared error.The subtree error is a weighted average, so nodes with larger membership probabilities contribute more to the overall error.
- Limiting behavior: All VIMP values are non-negative in the limiting case because θ0(k, v) ≥ 0.
5. Forests
The forest extension defines an ensemble predictor by combining binary-tree predictors and establishes that forests can approximate any square-integrable signal under stated support conditions. For sufficiently rich and nearly orthogonal trees, VIMP is characterized through maximal-subtree node mean squared error.
- Forest construction: A forest is an ensemble predictor formed from a finite collection of binary trees grown from the learning data.Unlike individual trees, forests do not assign node-membership values.
- Approximation: For any μ ∈ L2(P0) and δ > 0, a forest with trees having M > d terminal nodes can approximate μ under the stated support condition.The construction represents rectangle indicators with binary trees and uses finite linear combinations of such predictors.
- Approximation: Trees with at least d + 1 terminal nodes are treated as sufficiently deep for the forest predictor to approximate the true signal.
- Forest VIMP: Forest VIMP is computed by perturbing the target variable in every tree, averaging the perturbed tree predictors, and comparing the resulting forest predictor.
- Forest VIMP: Under the approximation and terminal-value assumptions, Theorem 3 gives a forest VIMP result involving maximal-subtree node mean squared errors.The forest result uses terminal values replaced by their true counterparts and extends the preceding tree-level theory.
- Conditions and implications: The bound becomes tighter as forest trees become more orthogonal, while positive and fully characterized VIMP requires trees rich enough to approximate μ(x).The prescription combines sufficient tree richness with near-orthogonality among trees.
6. Paired importance values and associations
The paper defines paired VIMP by jointly noising two variables and compares it with their additive individual effects to measure association. For single trees, association is nonpositive and reflects subtree overlap, whereas forests can also produce positive associations through interactions across trees.
- Paired VIMP: Paired VIMP is the prediction-error difference between jointly noising variables xv and xw and leaving them unnoised.Noising assigns random left-right paths when a case enters a maximal v- or w-subtree, producing a random tree predictor.
- Paired VIMP: The association measure At is the difference between paired VIMP and the sum of the individual VIMP effects.This comparison identifies pairs whose joint effect differs from the additive contribution of their separate variables.
- Single trees: In single trees, At cannot be positive because individual VIMPs overcount overlapping maximal v- and w-subtrees.When variables are orthogonal, their maximal subtrees do not overlap and At = 0; greater overlap makes At more negative.
- Forests: In forests, association values can be either negative or positive.Negative values arise from within-tree subtree overlap, while positive values can arise when correlated variables compete across trees and joint noising perturbs more trees than either individual perturbation.
- Forests: When v and w are orthogonal within each tree, forest association converges to zero; increasingly overlapping maximal subtrees yield increasingly negative At.The forest characterization averages node mean squared error terms over trees.
7. Air pollution
The air-pollution analysis uses random forests to estimate paired variable importance and associations, then compares those results with conditional ozone relationships. Temperature–wind shows the strongest association, while solar–temperature is also substantial and consistent with the coplot.
- Association analysis: Random-forest VIMP is computed from the change in out-of-bag mean squared error after randomly permuting a variable.The paired-importance analysis uses separate training and test subsets, with forests grown using 1000 trees and mtry = 3.
- Association analysis: The analysis records paired VIMP, additive individual effects, association values, and standardized association percentages.The association value is paired VIMP minus additive effects; standardization divides by training-data out-of-bag mean squared error and multiplies by 100.
- Results: The table values are averaged over 1000 independent replicates, with each random forest containing 1000 trees.These averages summarize the air-pollution paired-association analysis.
- Results: Temperature and wind have the largest association value, followed by solar radiation and temperature; wind–solar association is substantially smaller.After these leading associations, the remaining association values drop off dramatically.
- Results: The coplot shows ozone increasing with solar radiation, with radiation slopes increasing at higher temperatures for fixed wind ranges.At high temperatures, slope also increases with wind, whereas this pattern does not apply at lower temperatures, supporting the reported solar–temperature and temperature–wind associations.
8. Simulation
The simulation tests paired association values on data generated from a nonlinear model containing interactions and a noise variable. The largest standardized associations identify the simulated interactions, with negative values attributed to high subtree overlap.
- Simulation design: The simulated outcome includes interactions x1x2 and x1x4, nonlinear terms, a linear x5 term, and independent standard-normal noise.All variables, including noise variable x6, are uniformly distributed on [0, 1].
- Simulation design: The simulation uses n = 100 observations, randomForest settings matching the preceding analysis, and 100 independent repetitions.Table 2 reports values averaged over the repetitions, coding variables 1–6 as a–f.
- Results: The two largest standardized association values are a:b and a:d, corresponding to interactions between x1–x2 and x1–x4.These associations match the interaction terms specified in the simulated outcome model.
- Results: The leading standardized association values are negative, unlike the significant associations in the preceding air-pollution analysis, and reflect high overlap between variable subtrees.For x1 and x2, the stated pattern is that splits on one variable are likely to be followed underneath by splits on the other.