Decision trees

Bagging

• bagging is a general-purpose procedure for reducing the variance of a statistical learning method (outside of just trees)

Bagging

• bagging is a general-purpose procedure for reducing the variance of a statistical learning method (outside of just trees)
• It is particularly useful and frequently used in the context of decision trees

Bagging

• Mathematically, why does this work? Let's go back to intro to stat!

Bagging

• Mathematically, why does this work? Let's go back to intro to stat!
• If you have a set of$n$ independent observations: $Z_1,\dots ,Z_n$, each with a variance of ${\sigma }^2$, what would the variance of the mean, $\overline{Z}$ be?

Bagging

• Mathematically, why does this work? Let's go back to intro to stat!
• If you have a set of$n$ independent observations: $Z_1,\dots ,Z_n$, each with a variance of ${\sigma }^2$, what would the variance of the mean, $\overline{Z}$ be?
• The variance of $\overline{Z}$ is ${\sigma }^2/n$

Bagging

• Mathematically, why does this work? Let's go back to intro to stat!
• If you have a set of$n$ independent observations: $Z_1,\dots ,Z_n$, each with a variance of ${\sigma }^2$, what would the variance of the mean, $\overline{Z}$ be?
• The variance of $\overline{Z}$ is ${\sigma }^2/n$
• In other words, averaging a set of observations reduces the variance.

Bagging

• Averaging a set of observations reduces the variance. This is generally not practical because we generally do not have multiple training sets.

Bagging process

• generate $B$ different bootstrapped training sets

Bagging process

• generate $B$ different bootstrapped training sets
• Train our method on the $b$th bootstrapped training set to get ${\hat{f}}^{\ast b}\left(x\right)$, the prediction at point $x$

Bagging process

• generate $B$ different bootstrapped training sets
• Train our method on the $b$th bootstrapped training set to get ${\hat{f}}^{\ast b}\left(x\right)$, the prediction at point $x$
• Average all predictions to get:

$${\hat{f}}_{bag}\left(x\right)=\frac{1}{B}\sum _{b=1}^B{\hat{f}}^{\ast b}\left(x\right)$$

Bagging classification trees

• for each test observation, record the class predicted by the $B$ trees

Out-of-bag Error Estimation

• You can estimate the test error of a bagged model

Out-of-bag Error Estimation

• You can estimate the test error of a bagged model
• The key to bagging is that trees are repeatedly fit to bootstrapped subsets of the observations

Out-of-bag Error Estimation

• You can estimate the test error of a bagged model
• The key to bagging is that trees are repeatedly fit to bootstrapped subsets of the observations
• On average, each bagged tree makes use of about 2/3 of the observations (you can prove this if you'd like!, not required for this course though)

Out-of-bag Error Estimation

• You can predict the response for the $i$th observation using each of the trees in which that observation was OOB

Out-of-bag Error Estimation

• You can predict the response for the $i$th observation using each of the trees in which that observation was OOB

Out-of-bag Error Estimation

• You can predict the response for the $i$th observation using each of the trees in which that observation was OOB

• This will yield $B/3$ preditions for the $i$th observations. We can average this!