CS109A Introduction to Data Science

Lab 9: Decision Trees, Bagged Trees, Random Forests and Boosting - Solutions¶

Harvard University
Fall 2018
Instructors: Pavlos Protopapas and Kevin Rader
Lab Instructor: Kevin Rader (today at least)
Authors: Kevin Rader, Rahul Dave

---

---

We will look here into the practicalities of fitting regression trees, random forests, and boosted trees. These involve out-of-bound estmates and cross-validation, and how you might want to deal with hyperparameters in these models. Along the way we will play a little bit with different loss functions, so that you start thinking about what goes in general into cooking up a machine learning model.

Dataset¶

First, the data. We will be attempting to predict the presidential election results (at the county level) from 2016, measured as 'votergap' = (trump - clinton) in percentage points, based mostly on demographic features of those counties. Let's quick take a peak at the data:

How would you describe these variables?

General Trees¶

We could use a simple Decision Tree regressor to predict votergap. Thats not the aim of this lab, so we'll run a few of these models without any cross-validation or 'regularization' just to illustrate what is going on.

This is what you ought to keep in mind about decision trees.

from the docs:

max_depth : int or None, optional (default=None)
The maximum depth of the tree. If None, then nodes are expanded until all leaves are pure or until all leaves contain less than min_samples_split samples.
min_samples_split : int, float, optional (default=2)

• The deeper the tree, the more prone you are to overfitting.
• The smaller min_samples_split, the more the overfitting. One may use min_samples_leaf instead. More samples per leaf, the higher the bias.

Which of the two versions of 'minority' would be a better choice to use as a predictor for inference? For prediction?

1. Perform 5-fold cross-validation to determine what the best max_depth would be for a single regression tree using the entire 'Xtrain' feature set.
2. Visualize the results with mean +/- 2 sd's across the validation sets.

Based on the plot above, it's clear that the training $R^2$ increases towards zero as max_depth increases, while the test set's $R^2$ maxes out around 62-63% around a max_depth of 7-9. Any of those values would be reasonable to choose for a best predictive model. To prevent overfitting and for parsimony, Iwould choose a max_depth of 7.

Ok with this discussion in mind, lets improve this model by Bagging.

Bootstrap-Aggregating (called Bagging)¶

Whats the basic idea?

• A Single Decision tree is likely to overfit.
• So lets introduce replication through Bootstrap sampling.
• Bagging uses bootstrap resampling to create different training datasets. This way each training will give us a different tree.
• Added bonus: the left off points can be used to as a natural "validation" set, so no need to
• Since we have many trees that we will average over for prediction, we can choose a large max_depth and we are ok as we will rely on the law of large numbers to shrink this large variance, low bias approach for each individual tree.

1. Edit the code below (which is just copied from above) to refit many bagged trees on the entire Xtrain feature set (without the plot...lots of predictors now so difficult to plot).
2. Summarize how each of the separate trees performed (both numerically and visually) using $R^2$ as the metric. How do they perform on average?
3. Combine the trees into one prediction and evaluate it using $R^2$.
4. Briefly discuss the results. How will the results above change if 'max_depth' is increased? What if it is decreased?

1. Notice that the aggregated results, by averaging the predictions across the 500 different Regression Tree models, scores and $R^2$ in the test set of 64.9% which outperforms all of the separate individual models. We would expect this to improve further for larger values of max_depth, and in fact should imrpove quite a lot. This Bagging improves the variability of 'high variance' models by leveraging the law of large numbers, but does not improve bias nearly as much. Essentially, it is an indirect way of 'smoothing' these discretized step function by essentially jittering where those jumps occur. See the visual above. If we do change max_depth to something larger in the code above, we do see quite an improvement in predictive ability in the test set. A max_depth of 20 led to a test $R^2$ of 78.5%, for example.

Random Forests¶

What's the basic idea?

Bagging alone is not enough randomization, because even after bootstrapping, we are mainly training on the same data points using the same variablesn, and will retain much of the overfitting.

So we will build each tree by splitting on "random" subset of predictors at each split (hence, each is a 'random tree'). This can't be done in with just one predcitor, but with more predictors we can choose what predictors to split on randomly and how many to do this on. Then we combine many 'random trees' together by averaging their predictions, and this gets us a forest of random trees: a random forest.

Below we create a hyper-param Grid. We are preparing to use the bootstrap points not used in training for validation.

max_features : int, float, string or None, optional (default=”auto”)
- The number of features to consider when looking for the best split.

• max_features: Default splits on all the features and is probably prone to overfitting. You'll want to validate on this.
• You can "validate" on the trees n_estimators as well but many a times you will just look for the plateau in the trees as seen below.
• From decision trees you get the max_depth, min_samples_split, and min_samples_leaf as well but you might as well leave those at defaults to get a maximally expanded tree.

Using the OOB score.¶

We have been putting "validate" in quotes. This is because the bootstrap gives us left-over points! So we'll now engage in our very own version of a grid-search, done over the out-of-bag scores that sklearn gives us for free

Finally you can find the feature importance of each predictor in this random forest model. Whenever a feature is used in a tree in the forest, the algorithm will log the decrease in the splitting criterion (such as gini). This is accumulated over all trees and reported in est.feature_importances_

Since our response isn't very symmetric, we may want to suppress outliers by using the mean_absolute_error instead.

1. Tune the 'RandomForestRegressor' above to minimize 'mean_absolute_error' instead of the default __

Note: sklearn supports this (criterion='mae') since v0.18, but does not have completely arbitrary loss functions for Random Forests.

This model would be expected to perform better in the test set when measuring mean absolute error, but not as good at mean squared error (but this is not guaranteed). Here, we do not cross-validate, so that might explain why mean absolute error is worse.

Note: instead of using oob scoring, we could do cross-validation (with GridSearchCV), and a cv of 3 will roughly be comparable (same approximate train-vs.-validation set sizes). But this will take much more time as you are doing the fit 3 times plus the bootstraps. So at least three times as long!

1. What are the 3 hyperparameters for a random forest (one of the hyperparameters come in many flavors)?
2. Which hyperparameters need to be tuned?

Answers

1. The 3 hyperparameters are max_features, max_depth (or something related, like min_samples_split, so control the complexity of each tree), and n_estimators (in classification, the splitting criteria is another one you could consider)

2. max_features and max_depth need to be tuned, while the higher n_estimators the better (though there is clearly diminishing return, so just use someting 'largish' in the hundreds). The best tuned max_features and max_depth will depend on the number of predictors you are considering, the number of observations in the training set, and whether it is a regression or a classification problem. There are lots of rules of thumb out there, but cross-validate if you can.

Seeing error as a function of the proportion of predictors at each split¶

Let's look to see how max_features affects performance on the training set.

Boosting Regression Trees¶

Adaboost Classification, which you will be doing in your homework, is a special case of a gradient-boosted algorithm. Gradient Bossting is very state of the art, and has major connections to logistic regression, gradient descent in a functional space, and search in information space. See Schapire and Freund's MIT Press book for details (Google is a wonderful thing).

But briefly, let us cover the idea here. The idea is that we will use a bunch of weak 'learners' (aka, models) which are fit sequentially. The first one fits the signal, the second one the first model's residual, the third the second model's residual, and so on. At each stage we upweight the places that our previous model did badly on. First let us illustrate.

Ok, so this demonstration helps us understand some things about boosting.

• n_estimators is the number of trees, and thus the stage in the fitting. It also controls the complexity for us. The more trees we have the more we fit to the tiny details.
• staged_predict gives us the prediction at each step
• once again max_depth from the underlying decision tree tells us the depth of the tree. But here it tells us the amount of features interactions we have, not just the scale of our fit. But clearly it increases the variance again.

Ideas from decision trees remain. For example, increase min_samples_leaf or decrease max_depth to reduce variance and increase the bias.

1. What do you expect to happen if you increase max_depth to 5? Edit the code above to explore the result.
2. What do you expect to happen if you put max_depth back to 1 and decrease the learning_rate to 0.1? Edit the code above to explore the result.
3. Do a little work to find some sort of 'best' values of max_depth and learning_rate. Does this result make sense?

Answers

1. Increasing max_depth for each model does not really improve things. It will make each model more complex, which may not be a good thing. We want lots of little models that each are not overfit, so allowing any single model to have a lot of complexity (and thus overfit) could be a problem.
2. The model will progress much more slowly to fitting to the data well. This may be a good thing: this is essentially a form of 'regularization' in each model and will help prevent overfitting to any one model. It allows future models to have more 'error' to be able to explain.
3. See code below.

Note: what's the relationship between residuals and the gradient?¶

Pavlos showed in class that for the squared loss, taking the gradient in the "data point functional space", ie a N-d space for N data points with each variable being $f(x_i)$ just gives us the residuals. It turns out that the gradient descent is a more general idea, and one can use this for different losses. And the upweighting of poorly fit points in AdaBoost is simply a weighing by gradient. If the gradient (or residual) is high it means you are far away from optimum in this functional space, and if you are at 0, you have a flat gradient!

The ideas from the general theory of gradient descent tell us this: we can slow the learning by shrinking the predictions of each tree by some small number, which is called the learning_rate (learning_rate). This "shrinkage" helps us not overshoot, but for a finite number of iterations also simultaneously ensures we dont overfit by being in the neighboorhood of the minimum rather than just at it! But we might need to increase the iterations some to get into the minimum area.

---