  Random Forests (RF) are at the cutting edge of supervised machine learning in
terms of prediction performance, especially in genomics. Iterative Random
Forests (iRF) use a tree ensemble from iteratively modified RF to obtain
predictive and stable non-linear 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 novel 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.
