Abstract
Random Forests (RFs) are at the cutting edge of supervised machine learning in terms of prediction performance, especially in genomics. Iterative RFs (iRFs) use a tree ensemble from iteratively modified RFs to obtain predictive and stable nonlinear or Boolean interactions of features. They have shown great promise for Boolean biological interaction discovery that is central to advancing functional genomics and precision medicine. However, theoretical studies into how tree-based methods discover Boolean feature interactions are missing. Inspired by the thresholding behavior in many biological processes, we first introduce a discontinuous nonlinear regression model, called the “Locally Spiky Sparse” (LSS) model. Specifically, the LSS model assumes that the regression function is a linear combination of piecewise constant Boolean interaction terms. Given an RF tree ensemble, we define a quantity called “Depth-Weighted Prevalence” (DWP) for a set of signed features $S^±$. Intuitively speaking, $DWP(S^±)$ measures how frequently features in $S^±$ appear together in an RF tree ensemble. We prove that, with high probability, $DWP(S^±)$ attains a universal upper bound that does not involve any model coefficients, if and only if $S^±$ corresponds to a union of Boolean interactions under the LSS model. Consequentially, we show that a theoretically tractable version of the iRF procedure, called LSSFind, yields consistent interaction discovery under the LSS model as the sample size goes to infinity. Finally, simulation results show that LSSFind recovers the interactions under the LSS model, even when some assumptions are violated.
Introduction
Random Forests (RF) have become a staple in bioinformatics and genomics due to their ability to capture complex, non-linear relationships without explicit feature engineering. In particular, the Iterative Random Forest (iRF) framework has demonstrated remarkable success in identifying "biological logic gates"—Boolean interactions where the combined state of multiple genes determines a phenotypic outcome. Despite this empirical success, a theoretical understanding of why and how tree ensembles recover these specific types of interactions has remained elusive.
Traditional statistical learning theory often relies on smoothness assumptions (e.g., Lipschitz continuity). However, biological systems frequently exhibit threshold-based, "spiky" behavior that is fundamentally discontinuous. This paper bridges the gap by introducing a new theoretical framework tailored to these discontinuous interactions.
The Locally Spiky Sparse (LSS) Model
To formally study Boolean interactions, the authors propose the Locally Spiky Sparse (LSS) model. In this model, the regression function is defined as a linear combination of piecewise constant terms representing logic gates. For example, a response might be triggered only when $X_1 > 0.5$ and $X_2 < 0.5$.
As shown in the figure above, a decision tree can isolate these "spiky" regions by splitting on the relevant features. The "red path" represents a sequence of decisions that correctly identifies the interaction region. The LSS model provides a rigorous mathematical foundation for these types of "if-then" biological rules.
Depth-Weighted Prevalence (DWP)
The core innovation for interrogating the tree ensemble is the Depth-Weighted Prevalence (DWP) metric. DWP measures the frequency with which a set of signed features $S^±$ appears together on decision paths within the forest, weighted by their depth.
A significant theoretical result is that for a true interaction set $S$, the DWP converges to a universal upper bound of $2^{-|S|}$. Remarkably, this bound is independent of the effect size (the coefficient $\beta$ in the regression model). This implies that the tree ensemble captures the qualitative structure of the interaction even when the signal is relatively weak, provided there is enough data.
Key Insights and the LSSFind Algorithm
The paper introduces LSSFind, a theoretically tractable version of the iRF procedure. LSSFind uses the DWP metric to scan the tree ensemble and identify feature sets that meet the theoretical criteria for being a true interaction.
Several critical insights emerge from the theoretical analysis:
- The $m_{try}$ Parameter: The number of features considered at each split ($m_{try}$) must be carefully balanced. If $m_{try}$ is too low, the trees fail to learn the structure; if it is too high, the trees become overly correlated, making it difficult to distinguish true interactions from noise.
- Sample Complexity: The theory confirms that recovering high-order interactions (those involving many features) is exponentially difficult, requiring a corresponding exponential increase in both sample size and the number of trees in the forest.
- Consistency: The authors provide a formal proof that LSSFind is a consistent estimator. As the sample size $n \to \infty$, the probability of recovering the exact set of true Boolean interactions approaches 1.
Empirical Validation and Robustness
The theoretical findings were validated through extensive simulations across varying feature counts ($p=20$ to $200$) and noise distributions (Gaussian, Laplace, Cauchy). Even when the model's "non-overlapping" assumption was violated—meaning a single feature participated in multiple logic gates—the algorithm remained robust. While performance naturally degrades with increased feature correlation, the core mechanism of DWP-based recovery proved resilient in "messy" data environments that mimic real-world genomic datasets.
Conclusion and Future Directions
This work provides the first rigorous theoretical foundation for Boolean interaction recovery in tree ensembles. By moving away from smoothness assumptions and embracing the "spiky" nature of biological data, the authors have opened a new path for interpreting complex machine learning models.
Future research will focus on relaxing the current assumptions, particularly the requirement for non-overlapping interactions and independent feature distributions. Extending these proofs to the full, iterative version of iRF remains a significant open challenge that could further refine our ability to decode the complex logic of life.
Summary updated