Random Forest

Problem with bagged decision trees:
- Even with bagging, it is likely that most trees will be similar: highly correlated errors
Random Forest:
- Create a bagged ensemble of fully-grown decision trees
- During tree construction, each split only has access to a randomly selected subset of attributes
- Typically $\sqrt{d}$ or $\log_{2} (d) + 1$

Extremely Randomized Trees

Geurts et. al., Machine Learning (2006) 63: 3-42
No bootstrapping
Instead, both attribute choices and split points are randomized.
Instead of exhaustively checking each possible split, generate $K$ random splits and pick the best
- This can significantly speed up the tree construction process