Source-linked AI summary
Consistency of Random Survival Forests
Hemant Ishwaran, Udaya B. Kogalur
TL;DR
Random survival forests lack sufficient theory for right-censored survival data, especially for realistic mixtures of continuous and categorical variables. This paper proves uniform consistency under general splitting, bootstrapping, and random variable selection, using counting-process and bootstrap theory. It also shows that discrete embedding can accommodate continuous variables and introduces computational methodology for factors with unlimited labels.
Problem
Theoretical results for right-censored survival forests and survival trees are sparse, while continuous-feature assumptions do not directly cover categorical variables or mixed data settings.
Method
The paper proves survival-tree consistency using counting-process theory, then derives RSF consistency through bootstrap theory under general splitting rules and true RSF implementations.
Results
Uniform consistency is proved for RSF, and discrete embedding is presented as realistic for analyzing continuous variables as factors with many labels.
Takeaways & Limitations
The work introduces computational methodology for factors with unlimited labels while supporting RSF analysis with a finite but potentially very large discrete feature space.
Takeaways & Limitations
The theory assumes every feature is a factor with finitely many labels and additionally assumes event time is independent of censoring time and features are independent of censoring indicators.
Abstract
from arXiv · showhide
We prove uniform consistency of Random Survival Forests (RSF), a newly introduced forest ensemble learner for analysis of right-censored survival data. Consistency is proven under general splitting rules, bootstrapping, and random selection of variables--that is, under true implementation of the methodology. A key assumption made is that all variables are factors. Although this assumes that the feature space has finite cardinality, in practice the space can be a extremely large--indeed, current computational procedures do not properly deal with this setting. An indirect consequence of this work is the introduction of new computational methodology for dealing with factors with unlimited number of labels.
1 Introduction
Random survival forests extend random forests to right-censored survival data, but their properties are difficult to analyze. This paper proves uniform consistency using counting-process and bootstrap theory under general splitting rules and a finite discrete feature-space assumption.
- Motivation: Random survival forests extend random forests to right-censored survival settings as an ensemble learning method.Random forests aggregate randomized tree learners, while RSF applies the methodology to survival data.
- Random forests: Random forests grow trees from bootstrap samples while randomly selecting candidate variables at each split, distinguishing forests from bagging.The additional variable randomization is designed to encourage independence among trees and reduce variance and bias.
- Theory: Why random forests work remains difficult to analyze because simple algorithmic steps interact to produce a complex procedure.Existing theory frames a trade-off between tree strength and correlation as the number of candidate variables changes.
- Contribution: The paper proves uniform consistency of RSF, addressing limited theoretical results for survival trees and this newly introduced survival-forest extension.The proof covers general splitting rules, bootstrapping, and random variable selection.
- Contribution: The analysis uses counting-process theory, proving survival-tree consistency first and deriving forest consistency through bootstrap theory.This approach is intended to support true implementations rather than only idealized random splitting procedures.
- Feature-space scope: The paper assumes a finite but potentially very large discrete feature space in which all variables are factors.It argues that continuous variables can be treated as factors with many labels and introduces computational methodology for factors with unlimited labels.
2 Random survival forests algorithm
RSF grows bootstrapped recursive survival trees with randomized candidate variables and aggregates their terminal-node survival estimates. Each tree assigns individuals to terminal nodes and uses Kaplan–Meier estimates there, while the forest averages tree survival functions.
- Algorithm: RSF draws B independent bootstrap samples and grows a binary recursive survival tree for each sample.Trees are grown as near to saturation as possible, subject to a minimum event count in each terminal node.
- Algorithm: At each node, RSF randomly selects p candidate variables and chooses the split maximizing survival differences between daughter nodes.Random tie-breaking is used, and fewer than p available variables are used when necessary.
- Forest aggregation: The forest ensemble is formed by averaging the survival functions calculated for its individual trees.This averaging is the final aggregation step after terminal-node survival functions are computed.
- Tree survival function: Each individual follows its feature vector to a unique terminal node, where the tree estimates survival using that node’s Kaplan–Meier estimator.All cases assigned to the terminal node receive its estimated survival function.
3 The feature space
The theory represents every feature as a factor with finitely many labels, allowing a finite but potentially enormous feature space. Factor splits generate rapidly growing numbers of candidate partitions and possible trees.
- Feature-space assumption: Each coordinate of the d-dimensional feature vector is assumed to be a discrete nominal factor with 1 < L_j < ∞ distinct labels.The resulting feature space has cardinality L_1 × ··· × L_d, which may be very large.
- Factor splits: A factor split partitions its labels into complementary daughter-node pairings, producing 2^{L_j−1} − 1 distinct pairs for L_j labels.For three labels, the pairings are the three singleton-versus-complement partitions.
- Computational complexity: Recursive splitting across daughter nodes requires many evaluations, making the associated space of possible trees extremely large.Each evaluated split can produce a new tree, so tree-space size grows beyond the root-node split count.
4 Properties of survival forests
The paper establishes uniform consistency for survival trees and bootstrapped random survival forests, using convergence of ensemble survival functions to the population survival function. It also shows that suitably weighted forests can uniformly approximate the true survival function, a property individual trees do not possess.
- Consistency framework: Consistency is defined by convergence of the ensemble survival function to the population survival function, with forest consistency deduced from survival-tree consistency and bootstrap theory.The proof first treats survival trees, then incorporates bootstrap resampling for forests.
- Assumptions: The data consist of independent observations with discrete features, right-censored observed times, and censoring indicators under stated independence assumptions.The feature space is discrete, and the true event time is assumed independent of censoring time.
- Uniform consistency of survival trees: Under the stated censoring and hazard conditions, survival-tree estimators are uniformly consistent over times below the common endpoint τ.The result follows from uniform consistency of the Kaplan-Meier estimator.
- Uniform consistency of survival forests: Consistency for each bootstrap tree implies consistency of the ensemble survival function, while finite-sample forests may better approximate the true survival function than single trees.The paper distinguishes asymptotic consistency from practical finite-sample advantages.
- Uniform consistency of survival forests: For each time t below τ*, the bootstrapped survival-tree estimator is consistent under the same conditions as the survival-tree result.Here τ* is bounded by both the tree-consistency horizon and the support limit of the observed-time distribution.
- Uniform approximation by forests: For any ε > 0, a suitably weighted forest with B(ε) trees can uniformly approximate the true survival function, whereas individual trees lack this property.The construction uses trees with d + 1 terminal nodes when n > d.
5 Empirical results
The empirical results show that discretizing continuous variables into factors supports RSF analysis with contained prediction-error increases and robust variable-importance inference. Random splitting also mitigates selection bias and motivates computational methods for factors with unlimited labels.
- Discretizing the 10 continuous PBC variables into factors with L = 2, . . . , 30 labels enabled evaluation of increasing factor granularity.The dataset contained 312 individuals, 17 variables, seven discrete features, and 10 continuous features.
- Using only 50 randomly selected complementary pairs kept prediction error in check at granularity L = 30, despite roughly 2^30 possible pairs.Prediction error increased slowly as granularity rose, particularly with larger nsplit values.
- VIMP bootstrap confidence regions were relatively robust to factor granularity when forests used nsplit = 1024.VIMP was computed from 1000 independent bootstrap repetitions for each granularity level.
- 5.1 Remarks: With 25 continuous and 25 discrete binary noise variables added, continuous-noise VIMP distributions were wider, but nearly all contained zero even at high granularity.The result indicates that random splitting helped mitigate selection bias toward continuous variables and factors with many labels.
- 5.1 Remarks: The paper proposes using added noise variables and their combined bootstrap VIMP distribution to determine a variable-selection threshold.The proposed thresholding idea is motivated by the Figure 2 noise-variable results.
- 5.1 Remarks: The implementation supports factors with unlimited labels by using node-adaptive random splitting above 32 labels and multi-word complementary-pair representations.This avoids enumerating every complementary pair while representing large-factor splits with arrays of 32-bit unsigned integers.
6 Proofs
The proofs establish uniform consistency for survival trees and extend it to bootstrapped RSF ensembles under the paper’s assumptions. The argument constructs sufficiently refined trees, applies survival-estimation convergence results, and controls bootstrap terms uniformly in time.
- Independence of censoring and survival variables, together with positivity conditions, ensures uncensored observations and valid risk-set behavior needed by the proofs.The argument uses P{δ = 1} > 0 and related positivity statements to establish the required conditions.
- The full-length tree construction splits until terminal nodes correspond to each distinct feature value x ∈ X under the minimum-event constraint.If a node contained multiple feature values, at least one daughter would violate the required event count under any split.
- The proof combines convergence of empirical at-risk quantities and tree survival estimates with op(1) terms that are uniform in s.This yields uniform approximation of the conditional survival function over the relevant time interval.
- Bootstrap consistency is obtained by representing bootstrap samples through multinomial counts and applying a bootstrap convergence lemma to terminal-node samples.
- The proof strategy first establishes uniform consistency of survival trees, then uses bootstrap theory to prove consistency of RSF.