Left Out of the Bag

Question

Bagging builds each tree on a bootstrap sample: n rows drawn with replacement from the n training rows. For one fixed row, what is the probability it appears nowhere in a given bootstrap sample, and what does this probability converge to as n grows? What do random forests do with the left-out rows?

Accepted Answer

The computation. Each of the n independent draws picks the fixed row with probability frac1n, so it is missed by all of them with probability left(1 - frac1nright)^n xrightarrown to infty e^-1 approx mathbf0.368. Convergence is fast: n = 10 gives 0.9^10 approx 0.349 and n = 100 gives 0.366. So every bootstrap sample omits roughly 37% of the data and, by the complement, contains about 63% of the distinct rows (many of them duplicated). What forests do with the leftovers. The omitted rows are the tree's out-of-bag (OOB) set: a validation set the tree never touched, obtained for free. To score the ensemble, each row is predicted using only the trees for which it was out-of-bag (about 37% of them), and the aggregated error is the OOB estimate, behaving much like cross-validation without any extra fitting. OOB error is also the engine behind the classic permutation-importance recipe. The trap in a trading context: the OOB guarantee assumes rows are exchangeable. With serially correlated market data, the calendar neighbors of an out-of-bag day are usually in the bag, and they carry nearly the same information (overlapping labels, slow features). The tree has effectively seen a near-copy

Left Out of the Bag

Problem

Your answer

Hints