8
$\begingroup$

I am reading the description of RF here.

In the "How random forests work" section, it is written that:

When the training set for the current tree is drawn by sampling with replacement, about one-third of the cases are left out of the sample. This oob (out-of-bag) data is used to get a running unbiased estimate of the classification error as trees are added to the forest

I am unable to understand if the one-third of the cases (out-of-bag samples size) is:

  • an arbitrary value defined in the algorithm
  • an estimate (e.g. on average, sampling with replacement will leave out one-third of the cases)

or something else.

$\endgroup$
1

1 Answer 1

17
$\begingroup$

It comes from the construction of a bootstrap sample: you're sampling $n$ observations with replacement to a sample size of $n$. The probability that an observation is omitted is $(1-\frac{1}{n})^n.$* Now consider the definition of $\exp(-1)=\lim \limits_{n\to\infty}(1-\frac{1}{n})^n$ and observe that $\exp(-1)=0.3678...\approx\frac{1}{3}.$


*To verify this, I will define the probability space of the bootstrap: $\Omega=\{x_1, x_2, x_3, \dots, x_n\}$ where each $x_{i\in I=\{i\in\mathbb{N}:i\le n\}}$ is an observation, $\mathcal{F}=2^\Omega$. We will denote the boostrap sample as $B$. Note that we can take this $\sigma$-field $\mathcal{F}$ because we must have a finite number of observations. Collecting our bootstrap sample one observation at a time, our event of interest $E$ occurs when some observation $x_i$ is selected for the bootstrap sample, and we must define a probability measure for it. That is, $P(E)=P(\{x_i \in B\})$.

We can think of drawing a bootstrap sample as an experiment where there are $n$ trials. Each trial is selecting one of our observations uniformly at random with replacement, so it will either include $x_i$ with probability $P(E)=\frac{|E|}{|\Omega|}=\frac{1}{n},$ or exclude $x_i$ with probability $P(E^c)=\frac{|\Omega|-|E|}{|\Omega|}=1-\frac{1}{n}.$ Our probability space $(\Omega, \mathcal{F}, P)$ is now completely defined. The experiment we're performing has $n$ trials, so the probability that $x_i$ is omitted from all of them is $(\bigcup_{i=1}^n P(E))^c=\bigcap_{i=1}^n P(E^c)=(1-\frac{1}{n})^n$.

$\endgroup$
5
  • 1
    $\begingroup$ +1. Could you please remind us how to get the $(1-\frac{1}{n})^{n}$ result? I know everyone should know that, but in reality that may not be the case so I think that would be helpful. $\endgroup$
    – Antoine
    Commented Sep 24, 2015 at 17:16
  • $\begingroup$ @Antoine I just learned about probability spaces this semester, so my expansion is probably overkill... $\endgroup$
    – Sycorax
    Commented Sep 24, 2015 at 21:36
  • $\begingroup$ Excellent explanation, thanks. The right side of your last line holds because the events are independent right? (independence coming from the fact that sampling is done with replacement). $\endgroup$
    – Antoine
    Commented Sep 25, 2015 at 9:07
  • $\begingroup$ The trials must be independent by construction: each event has a specified probability that does not depend on anything but the cardinality of $E$ and $\Omega$ because we're sampling with replacement. $\endgroup$
    – Sycorax
    Commented Sep 25, 2015 at 11:10
  • $\begingroup$ @Antoine it's because of the Taylor series that generates e^(n). Here's a proof: aleph0.clarku.edu/~djoyce/ma122/elimit.pdf $\endgroup$
    – riders994
    Commented Apr 19, 2017 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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