1
$\begingroup$

I am looking for a proof or intuition as to why the absolute limit of a random forest estimator is the expectancy of a single tree (see citation below), i.e:

$$ \hat{f}_{rf}(x) = \lim_{B \to \infty}[\hat{f}^B_{rf}(x)] = \lim_{B \to \infty}[\frac{1}{B}\sum_{b=1}^BT(x;\Theta_b)]=E_{\Theta|Z}[T(x;\Theta(Z))] \tag{1}\\ $$

where $Z$ = current sample (not bootstrap); $T(x;\Theta_b)$ = prediction for the tree grown on the $b^{th}$ bootstrapped sample with parameters $\Theta_b$ (split variables, split points, leaf values).

Since random forest / bagging is an average and a tree is a random variable, how can the limit converge absolutely? I thought a LLN or CLT could be applicable, but those are based on convergence in probability ($plim = \overset{p}{\to}$) or in distribution ($dlim = \overset{d}{\to}$). Since the trees are not independent (only $id$ identically distributed, not $iid$), not even a basic WLLN is applicable because the variance never fully vanishes (see convergence in mean-square).


Source: (1) is cited from

2008. Elements of Statistical Learning 2nd Ed, Equation 15.3. Hastie, Tibshirani, Friedman

2008. Elements of Statistical Learning 2nd Ed, Equation 15.3. Hastie, Tibshirani, Friedman

2008. Elements of Statistical Learning 2nd Ed, Equation 15.4. Hastie, Tibshirani, Friedman

2008. Elements of Statistical Learning 2nd Ed, Equation 15.4. Hastie, Tibshirani, Friedman


Resources: I could not find the answer (so far) in the following papers:

Stefan Wager. Asymptotic Theory For Random Forest (https://arxiv.org/pdf/1405.0352.pdf)

Jason M. Klusowski. Sharp analysis of a simple model for random forests (https://arxiv.org/pdf/1805.02587.pdf)

Gilles Louppe. UNDERSTANDING RANDOM FORESTS From Theory To Practice (https://arxiv.org/pdf/1407.7502.pdf)

$\endgroup$
2
  • $\begingroup$ What makes random forest id, instead of iid? Which "i" do you think not hold? $\endgroup$ – Kota Mori Oct 30 '20 at 13:36
  • $\begingroup$ Trees in a random forest / bagging are not independent since they are all generated from the same sample through bootstrapping. They are only identically distributed. I am assuming because they are generated by the same algorithm (see EoSL link). I edited the question for clarity. $\endgroup$ – PaulG Oct 30 '20 at 15:22
1
$\begingroup$

Your concern is in the independence part, and the reason is that the trees are generated from a same training dataset. To this point, the equation (15.3) and the paragraph just below that states that (emphasis added and typo fixed):

$$ \hat{f}_{rf}(x) = \mathrm{E}_\Theta T(x; \Theta) = \lim_{B\to\infty} \hat{f}^{B}_{rf}(x)$$ ... The distribution of $\Theta$ is conditional on the training data.

Conditional on the training data, the randomness of trees only comes from the sampling process of the learning algorithm. So tree estimators can be seen as samples from an identical and independent and distribution.

$\endgroup$
2
  • $\begingroup$ So conditioned on the training set the trees are iid. I edited the expectancy to show conditionality. However, even if they are iid, why does the average converge absolutely and not in probability? $\endgroup$ – PaulG Oct 30 '20 at 18:46
  • $\begingroup$ That part I am not sure. Given that a random forest prediction $\hat{f}^{B}_{rf}$ for a given $B$ is random, I suppose this should be "plim" or "a.s. lim". But I'm not sure if this is just lazy notation or the authors actually mean "deterministic" convergence rather than "probabilistic" for some reason. I hope some other folks kindly clarify this. $\endgroup$ – Kota Mori Oct 30 '20 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.