Random Forests

Inside the paper

The problem

Combining decision trees by voting can improve classification, but making the individual trees different without making them too weak is a central challenge. The paper asks how random choices in tree construction affect an ensemble's accuracy.

The idea

Grow many trees with independently randomized construction and aggregate their predictions. One practical version chooses a fresh random subset of features when considering a split at each node.

How it works

• Draw a bootstrap sample of the training examples for each tree and grow the trees without pruning.
• At each node, examine a randomly selected set of input variables and choose the best split among those candidates.
• For classification, let the trees vote; for regression, average their numerical predictions.
• Use the examples omitted from each tree's bootstrap sample to estimate error and assess the effect of disturbing individual variables.

What it showed

The paper derives a relationship between forest error, the strength of the individual classifiers and their correlation. Its experiments compare random forests with boosting on several datasets and examine how label noise affects their errors.

Read it for

Begin with Sections 1 and 2 for the definition and the strength–correlation argument, then read Section 4 for the construction. Section 8 examines noisy labels; the detailed regression results in Section 12 can wait if classification is your focus.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.