OOB score in random forests

In the Random Forest algorithm, we build a decision tree (DT) based on a certain training dataset. This tree will be split in order to minimise some criteria function.

However, it is not desirable that individual DTs get too large with too many splits, so a common approach is to train each tree with a subset of the training data (sampled with replacement). This will ensure that individual tree maintain a manageable size, while the variance of the tree ensemble is reduced and the overall bias is not altered.

This training subset is usually called the bootstrap samples. In the image below, we can see an illustration of the sampling with replacement.