4.3 Trees and Weak Learners

4.3.1 Classification and Regression Trees

Classification and Regression Trees (CART) is a tree-based method that recursively splits the data into two groups based on feature values, producing a model that can predict either a category or a numerical value.

In order to choose a more optimal tree, we “trim” the tree back by regularizing the size of the tree. Given a starting tree \(T\) and a cost complexity parameter \(\alpha \), we find the subtree that minimizes \begin{equation} \text {Cost complexity}\,(T') = \sum _{t \in T'} \sum _{n \in t} (y_n - \hat {y}_t)^2 + \alpha |T'|, \end{equation} where \(t \in T'\) means \(t\) is a leaf node of \(T'\), \(n \in t\) means \(\mathbf {x}_n\) is assigned to leaf node \(t\), and \(|T'|\) counts the number of leaf nodes.

4.3.2 Bootstrapping

Let \(Y_1, \ldots , Y_N\) be i.i.d. observations from an unknown distribution \(F\), and let \(\hat {\mu } = s(\boldsymbol {Y})\) be an estimator of a parameter \(\mu \). The bootstrap approximates the sampling distribution of \(\hat {\mu }\) by replacing \(F\) with the empirical distribution \[ \hat {F}(y) \;=\; \frac {1}{N}\sum _{i=1}^{N} \mathbb {I}(Y_i \le y), \] and resampling from the data itself. For \(b = 1, \ldots , R\), draw \(\boldsymbol {Y}^{*b} = (Y_1^{*b}, \ldots , Y_N^{*b})\) with replacement from \(\{Y_1, \ldots , Y_N\}\) and compute the bootstrap replicate \(\hat {\mu }^{*b} = s(\boldsymbol {Y}^{*b})\). The empirical distribution of \(\{\hat {\mu }^{*1}, \ldots , \hat {\mu }^{*R}\}\) then serves as a proxy for the sampling distribution of \(\hat {\mu }\).

4.3.3 Bagging

Suppose we’re using squared error loss, and we have a learner that is approximately unbiased but high variance. That is, for a particular fixed \(x\), we have \(\hat {f}(x; \mathcal {D})\), where \(\hat {f}(\cdot ; \mathcal {D})\) depends on the training data \(\mathcal {D}\), which satisfies \[ \mathbb {E}_{\mathcal {D}}\left [\hat {f}(x; \mathcal {D})\right ] \approx f^*(x) \quad \text {and} \quad \mathrm {Var}_{\mathcal {D}}\left (\hat {f}(x; \mathcal {D})\right ) \text { is large.} \] Here, \(\mathbb {E}\left [y \mid x\right ] = f^*(x)\) is the best possible prediction we could make.

One might think of deep regression trees as being a possible example. Intuitively, one might expect such a predictor to be over-fitting the particular dataset at hand.

Recall that we showed earlier that the expected squared error decomposes into \[ \mathbb {E}_{\mathcal {D}}\left [(\hat {f}(x; \mathcal {D}) - f^*(x))^2\right ] = \underbrace {\mathbb {E}_{\mathcal {D}}\left [\left (\hat {f}(x; \mathcal {D}) - \mathbb {E}_{\mathcal {D}}\left [\hat {f}(x; \mathcal {D})\right ]\right )^2\right ]}_{\text {Variance}} + \underbrace {\left (\mathbb {E}_{\mathcal {D}}\left [\hat {f}(x; \mathcal {D})\right ] - f^*(x)\right )^2}_{\text {Bias}}. \]

The variance only increases the expected squared error, so if we could get a lower-variance estimator without changing the bias, we’d improve our loss. Ideally, we might imagine getting \(B\) different, new datasets \(\mathcal {D}_1, \ldots , \mathcal {D}_B\), and then using \[ \hat {f}_{\text {Ideal}}(x) = \frac {1}{B} \sum _{b=1}^{B} \hat {f}(x; \mathcal {D}_b) \approx \mathbb {E}_{\mathcal {D}}\left [\hat {f}(x; \mathcal {D})\right ]. \]

Of course, if we could actually do this, we should just combine the datasets into one giant dataset. But this idea motivates the feasible “bagging” estimator: \[ \hat {f}_{\text {Bagging}}(x) = \frac {1}{B} \sum _{b=1}^{B} \hat {f}(x; \mathcal {D}_b^*), \] where \(\mathcal {D}_b^*\) is a bootstrap sample from the original dataset. The bootstrap distribution is a random distribution conditional on the original dataset \(\mathcal {D}\), with probability distribution \[ \mathbb {P}\left ((x_n^*, y_n^*) = (x_n, y_n)\right ) = \frac {1}{N} \quad \text {for} \quad n = 1, \ldots , N. \]

The problem is, of course, that bootstrap draws are not draws from \(\mathcal {D}\). Why does bagging work? In my opinion, the theory is not very clear, but it appears in practice that bagging tends to improve highly variable and expressive estimators, but can make less variable estimators worse.

4.3.4 Boosting

For boosting, we first find the \(\hat {f}_1(\cdot )\) that best predicts \(y_n\), then the one that makes the biggest improvement when added to \(\hat {f}_1(\cdot )\), and so on. Note that at each step all we need to be able to do is make a small improvement, since over \(M\) steps these small improvements accumulate. For example, we might take \(\hat {\phi }_m(\cdot )\) to simply be a “stump”: a regression tree with a single split. In this sense, boosting can improve on high-biased estimators by adding up a large number of them in an increasingly expressive way.