library(tidyverse) # should've already install.packages("tidyverse")
library(ggplot2movies) # the films; might need to install.packages("ggplot2movies")
library(randomForest) # might need to install.packages("randomForest")
library(xgboost) # version 3 or later; if xgboost(x = ...) fails, install.packages("xgboost") again
library(mgcv) # used only in the optional items; ships with R
theme_set(theme_minimal())
options(pillar.sigfig = 4) # tables print four significant digits
mse <- function(y, pred) mean((y - pred)^2)
se_loss <- function(loss) sd(loss) / sqrt(length(loss)) # standard error of a mean of lossesWeek 8 seminar
This is the student version of the notebook. The code you write goes where a line says # ... or has a ____. A code chunk with a blank starts with #| eval: false, so the file renders as it stands; delete that line once you have filled the blank. Working through the chunks one at a time in RStudio (Ctrl/Cmd+Enter) is unaffected. Answers are revealed in the seminar.
Before the seminar
The lecture proved the variance of an average of correlated variables; exercise 1 is that proof again, with the slides closed. It derived boosting as approximate gradient descent; exercise 2 takes one boosting step by hand. Do both on paper before the seminar. You may use, without proof: \(\mathrm{Var}\big(\sum_b V_b\big) = \sum_b\sum_{b'}\mathrm{Cov}(V_b, V_{b'})\), and \(\mathrm{Cov}(V, V) = \mathrm{Var}(V)\).
Each exercise has hints, collapsed below it. Do not open a hint unless you have been stuck for at least a few minutes, and open them in order. Solutions are shown in the seminar if you ask.
Exercise 1 (correlated-average variance, with the slides closed). \(V_1, \ldots, V_B\) are random variables, each with variance \(\tau^2 > 0\), and every pair has correlation \(\rho\).
Show that \(\mathrm{Var}\big(\frac1B\sum_{b=1}^B V_b\big) = \rho\tau^2 + (1 - \rho)\tau^2/B\).
What is left as \(B \to \infty\)? What does the formula give when \(\rho = 1\), and when \(\rho = 0\)?
In a bagged ensemble or a random forest, \(V_b\) is the \(b\)th tree’s prediction at one input \(x\), and the randomness is the draw of the training data and of the resampling. Which term can more trees shrink, and which term does a random forest try to shrink instead?
- Write the variance of the sum as a double sum of covariances. How many terms have \(b = b'\), and how many have \(b \ne b'\)? What is each one?
- The covariance of two variables with correlation \(\rho\) and variances \(\tau^2\) is \(\rho\tau^2\). Divide the variance of the sum by \(B^2\), then write \(\frac{B(B-1)}{B^2} = 1 - \frac1B\) and regroup.
Exercise 2 (one boosting step by hand). The five Star Wars films in the lecture’s data, with their year and average IMDb rating (in the data, which end in 2005):
| Film | Year | Rating |
|---|---|---|
| Star Wars | 1977 | 8.8 |
| The Empire Strikes Back | 1980 | 8.8 |
| Return of the Jedi | 1983 | 8.1 |
| The Phantom Menace | 1999 | 6.4 |
| Attack of the Clones | 2002 | 7.0 |
The training loss of fitted values \(\mathbf f = (f_1, \ldots, f_5)\) is \(L(\mathbf f) = \sum_i \frac12(y_i - f_i)^2\).
Start from \(f_i = \bar y\) for every film. Compute \(\bar y\) and the negative gradient of \(L\) at this \(\mathbf f\).
Fit a tree with one split on year to the negative gradient: for each of the four cutoffs halfway between consecutive years, compute the residual sum of squares of the two leaves, each predicting its mean. Which cutoff wins, and what does each leaf predict?
Take a step of size \(\gamma = 0.5\) along that tree. Give the new fitted values, and the training loss before and after the step.
- The derivative of \(\frac12(y_i - f_i)^2\) with respect to \(f_i\).
(b), (c) A leaf predicts the mean of the residuals in it. The step is \(f_i \leftarrow f_i + \gamma\,t(x_i)\), with \(t\) the tree.
Problems
Both problems use two inequalities. Markov’s inequality: if \(W \ge 0\) and \(a > 0\), then \(P(W \ge a) \le \mathbb E[W]/a\). Hoeffding’s inequality (Hoeffding 1963): if \(Z_1, \ldots, Z_m\) are independent with \(0 \le Z_i \le 1\) and \(\bar Z\) is their mean, then for every \(t > 0\), \[ P\big(|\bar Z - \mathbb E\bar Z| \ge t\big) \le 2e^{-2mt^2}. \]
Problem 1 (how far a score can be from the risk). A classifier predicts a track’s playlist genre, one of six, from its audio features (data note). It was fitted on training tracks and is now fixed; its risk \(R\) is its error rate on new tracks. On \(m = 2000\) tuning tracks, drawn independently of each other and of the training tracks, it errs on 1,062, so its score is \(\hat R = 0.531\), the mean of \(m\) losses \(\ell_i \in \{0, 1\}\) with mean \(R\). Write \(D = \hat R - R\). We want an interval \(\hat R \pm t\) that contains \(R\) with probability at least \(1 - \delta\), for \(\delta = 0.001\): a \(t\) with \(P(|D| \ge t) \le \delta\).
Show that \(\mathrm{Var}(\ell_i) \le \frac14\), so that \(\mathrm{Var}(D) \le \frac{1}{4m}\).
Apply Markov’s inequality to \(W = |D|\), using \(\mathbb E|D| \le \sqrt{\mathbb E[D^2]}\), and find \(t\).
Apply it to \(W = D^2\) instead (this is Chebyshev’s inequality), and find \(t\).
Find \(t\) from Hoeffding’s inequality.
Compute the three intervals. Guessing a genre at random errs with probability \(\frac56\): which interval rules that out for this classifier? How does each \(t\) grow as \(\delta\) shrinks?
Optional. Hoeffding’s lemma says that if \(0 \le Z \le 1\) with mean \(\mu\), then \(\mathbb E\big[e^{\lambda(Z - \mu)}\big] \le e^{\lambda^2/8}\) for every \(\lambda\). Apply Markov’s inequality to \(W = e^{\lambda D}\) with \(\lambda > 0\), and use independence and the lemma to show that \(P(D \ge t) \le e^{-\lambda t + \lambda^2/(8m)}\). Then choose \(\lambda\) to get \(P(D \ge t) \le e^{-2mt^2}\).
Problem 2 (the size of a search). A model’s risk is its expected loss on a new unit, \(R = \mathbb E[\ell]\), for a loss with \(0 \le \ell \le 1\) (for example, the 0–1 loss of a classifier). Before the tuning data are seen, \(K\) candidate models are fixed, fitted on the training data, with risks \(R_1, \ldots, R_K\); treat the fitted models as fixed, so that everything below is conditional on the training data. On \(m\) tuning units, drawn independently of each other and of the training data, candidate \(k\) scores \(\hat R_k\), the mean of its \(m\) losses.
Find \(t_K\) such that, with probability at least \(1 - \delta\), \(|\hat R_k - R_k| < t_K\) for every \(k\) at once. Did you need the \(K\) scores to be independent of each other?
Let \(\hat k\) be the candidate with the lowest tuning score and \(k^\star\) the candidate with the lowest risk. On the event of (a), show that \(R_{\hat k} < \hat R_{\hat k} + t_K\) and \(R_{\hat k} < R_{k^\star} + 2t_K\).
Take \(m = 2000\) and \(\delta = 0.05\). Compute \(t_K\) for \(K = 1\), \(10\), \(100\) and \(1{,}000{,}000\). How many candidates double \(t_1\)? How many tuning units halve \(t_K\)? What would Chebyshev’s inequality give in place of Hoeffding’s, for \(K = 100\)? What does this say about searching a larger grid?
The argument needs the \(K\) candidates to be fixed before any tuning score is seen. Give an example of a search that breaks this, and one that chooses adaptively but does not.
Coding
The lecture’s task: predict a film’s average IMDb rating from its year, length and seven genre indicators, squared loss (data note). The same split as the lecture: 5,000 training, 2,000 tuning and 3,000 test films, one seed. The tuning films choose the knobs; the test films are opened once, at the end.
mv <- movies |>
filter(length <= 200, length > 10, year > 1918, votes >= 20) |>
select(title, rating, year, length, Action, Animation, Comedy, Drama, Documentary, Romance, Short)
set.seed(310) # change this number: a different split, and different numbers below
mv_id <- sample(nrow(mv), 10000)
mv_train <- mv[mv_id[1:5000], ]
mv_tune <- mv[mv_id[5001:7000], ]
mv_test <- mv[mv_id[7001:10000], ]
mse(mv_tune$rating, mean(mv_train$rating)) # the training mean, scored on the tuning films[1] 2.003116
1. A random forest, two knobs
rf_fit(mtry, nodesize) fits a forest of 300 trees on the training films. Its two knobs: mtry, the number of inputs tried at each split (randomForest’s default for 9 inputs is 3), and nodesize, the size below which a node is not split (default 5). rf_score() returns a forest’s MSE on the tuning films.
rf_fit <- function(mtry, nodesize) {
randomForest(rating ~ year + length + Action + Animation + Comedy + Drama + Documentary + Romance + Short,
data = mv_train, ntree = 300, mtry = mtry, nodesize = nodesize)
}
rf_score <- function(mtry, nodesize) mse(mv_tune$rating, predict(rf_fit(mtry, nodesize), mv_tune))Question 1. Fit the forest with the default knobs. Compute its MSE on the training films, out of bag (predict(fit) with no new data predicts each training film from the trees that did not have it in their bootstrap sample), and on the tuning films. Which two agree, and why is the third lower? Why do we not tune the number of trees?
fit_default <- rf_fit(mtry = 3, nodesize = 5)
# c(training = mse(mv_train$rating, ____),
# out_of_bag = mse(mv_train$rating, ____),
# tuning = mse(mv_tune$rating, ____))Question 2. Tune one knob at a time, leaving the other at its default: mtry in 1, 2, 3, 5 and 9 with nodesize = 5; then nodesize in 5, 50 and 200 with mtry = 3. Which value of each wins? (Eight forests, the default twice, about 20 seconds.)
mtrys <- c(1, 2, 3, 5, 9)
nodesizes <- c(5, 50, 200)
# mse_mtry <- sapply(mtrys, function(m) ____)
# mse_node <- sapply(nodesizes, function(s) ____)
# rbind(mtry = mtrys, tune_mse = round(mse_mtry, 3))
# rbind(nodesize = nodesizes, tune_mse = round(mse_node, 3))Checkpoint (run it; if it stops, fix question 2 before going on): the default’s two scores should be close.
stopifnot(abs(mse_mtry[mtrys == 3] - mse_node[nodesizes == 5]) < 0.03)Question 3. The chunk below fits all 15 forests of the grid (about 40 seconds). Does the best nodesize depend on mtry? Did searching both knobs together find a better forest than question 2?
rf_grid <- expand_grid(mtry = c(1, 2, 3, 5, 9), nodesize = c(5, 50, 200)) |>
mutate(tune_mse = map2_dbl(mtry, nodesize, rf_score))
rf_grid |> mutate(tune_mse = round(tune_mse, 3)) |>
pivot_wider(names_from = nodesize, values_from = tune_mse, names_prefix = "nodesize ")# A tibble: 5 x 4
mtry `nodesize 5` `nodesize 50` `nodesize 200`
<dbl> <dbl> <dbl> <dbl>
1 1 1.687 1.689 1.691
2 2 1.505 1.516 1.523
3 3 1.489 1.48 1.488
4 5 1.563 1.491 1.482
5 9 1.721 1.509 1.491
2. Boosted trees, three knobs
xgboost has three knobs that matter most here: the depth of each tree, the learning rate \(\gamma\), and the number of iterations. Its defaults are depth 6, rate 0.3 and 100 iterations. One fit of 800 iterations gives the predictions after any smaller number, so the chunk below makes 12 fits (4 depths, 3 rates) and scores each after 5, 10, 25, …, 800 iterations: 96 models in a table, models, with each one’s MSE on the tuning films. loss holds every model’s squared errors on the 2,000 tuning films, one column per model, in the order of the rows of models; col is that column. (About 5 seconds.)
X_train <- as.matrix(select(mv_train, -title, -rating))
X_tune <- as.matrix(select(mv_tune, -title, -rating))
X_test <- as.matrix(select(mv_test, -title, -rating))
boost_fit <- function(depth, rate) {
xgboost(x = X_train, y = mv_train$rating, nrounds = 800, max_depth = depth, learning_rate = rate, nthread = 1)
}
iters <- c(5, 10, 25, 50, 100, 200, 400, 800)
models <- expand_grid(depth = c(1, 2, 4, 6), rate = c(0.03, 0.1, 0.3), iters = iters) |>
mutate(col = row_number())
loss <- matrix(NA, nrow(mv_tune), nrow(models))
for (d in c(1, 2, 4, 6)) for (r in c(0.03, 0.1, 0.3)) {
fit <- boost_fit(d, r)
for (b in iters) {
j <- models |> filter(depth == d, rate == r, iters == b) |> pull(col)
loss[, j] <- (mv_tune$rating - predict(fit, X_tune, iteration_range = c(1, b)))^2
}
}
models$tune_mse <- colMeans(loss)Question 4. The chunk below scores the defaults on the tuning films and on the training films. Compare with the forest and with the training mean. What has happened?
models |> filter(depth == 6, rate == 0.3, iters == 100)# A tibble: 1 x 5
depth rate iters col tune_mse
<dbl> <dbl> <dbl> <int> <dbl>
1 6 0.3 100 93 1.683
fit_default_boost <- boost_fit(depth = 6, rate = 0.3)
mse(mv_train$rating, predict(fit_default_boost, X_train, iteration_range = c(1, 100))) # training MSE[1] 0.8182678
Question 5. Tune one knob at a time, from the defaults: the number of iterations with depth 6 and rate 0.3; the depth with rate 0.3 and 100 iterations; the rate with depth 6 and 100 iterations. Before scoring the model that takes all three winners together, predict: should it be at least as good as each winner alone? Then score it.
# models |> filter(____) |> slice_min(tune_mse) # iterations alone
# models |> filter(____) |> slice_min(tune_mse) # depth alone
# models |> filter(____) |> slice_min(tune_mse) # rate alone
# models |> filter(depth == ____, rate == ____, iters == ____) # the three winners togetherQuestion 6. Tune the knobs in sequence instead: the number of iterations first (depth 6, rate 0.3), then the depth at the winning number of iterations, then the rate at the winning depth and number of iterations. Then search the whole grid. Compare the two models, and the number of fits each search needed.
# step1 <- models |> filter(____) |> slice_min(tune_mse) # iterations, at depth 6 and rate 0.3
# step2 <- models |> filter(rate == 0.3, iters == ____) |> slice_min(tune_mse)
# step3 <- models |> filter(depth == ____, iters == ____) |> slice_min(tune_mse)
# models |> slice_min(tune_mse) # the whole gridQuestion 7. The chunk below gives the best model at each depth. Boosted trees of depth 1 are an additive model: each tree splits on one input, so the sum is a sum of one-input functions. Compute the paired difference in tuning loss between the best depth-1 model and the grid’s best, with its standard error. What does it suggest about interactions between the inputs?
models |> group_by(depth) |> slice_min(tune_mse) |> ungroup()# A tibble: 4 x 5
depth rate iters col tune_mse
<dbl> <dbl> <dbl> <int> <dbl>
1 1 0.1 400 15 1.515
2 2 0.1 400 39 1.502
3 4 0.1 100 61 1.490
4 6 0.03 100 77 1.492
j_additive <- models |> filter(depth == 1) |> slice_min(tune_mse) |> pull(col)
j_best <- models |> slice_min(tune_mse) |> pull(col)
# d_add <- ____
# c(difference = ____, se = ____)3. The size of the search
Three searches over the same 96 boosting models: one model fixed in advance, the defaults (fixed); the 13 models that question 5’s one-knob-at-a-time searches looked at (one_knob); and all 96. On one split of the tuning films the effect is too small to see, so we repeat the searches on many random halves, all three on the same halves.
Question 8. Complete half_gap(cols, A): among the models in cols, find the one with the lowest MSE on the half A of the tuning films; return that MSE and the same model’s MSE on the other half. The chunk then draws 2,000 random halves, runs the three searches on each and averages. Which search’s best model looks best on the films that chose it? Which is best on the other films?
fixed <- models |> filter(depth == 6, rate == 0.3, iters == 100) |> pull(col)
one_knob <- models |> filter((depth == 6 & rate == 0.3) | (rate == 0.3 & iters == 100) | (depth == 6 & iters == 100)) |> pull(col)
all_models <- models$colhalf_gap <- function(cols, A) {
mse_A <- colMeans(loss[A, cols, drop = FALSE]) # each model's MSE on the half A
# w <- ____ # the model with the lowest MSE on A
# c(chosen_on = ____, other_half = ____)
}
halves <- replicate(2000, {
A <- sample(nrow(loss), nrow(loss) / 2) # one random half of the tuning films
rbind(fixed = half_gap(fixed, A), one_knob = half_gap(one_knob, A), all_models = half_gap(all_models, A))
})
q8 <- apply(halves, 1:2, mean) # average over the 2,000 halves
cbind(q8, gap = q8[, "other_half"] - q8[, "chosen_on"])Checkpoint: one fixed model is not chosen by anything, so on average its two halves should agree.
stopifnot(abs(q8["fixed", "other_half"] - q8["fixed", "chosen_on"]) < 0.01)4. The test films, once
Question 9. Before running the chunk below, write down which two models you will score on the test films: the forest and the boosting model that won their grids on the tuning films. Then compute each one’s test MSE with its standard error, the training mean’s, and the paired difference between the forest and the boosting model, with its standard error. Compare each test MSE with the same model’s tuning MSE, the training mean’s too. What can you conclude from the differences?
rf_best <- rf_grid |> slice_min(tune_mse) # the forest that won its grid
boost_best <- models |> slice_min(tune_mse) # the boosting model that won its grid
fit_rf <- rf_fit(rf_best$mtry, rf_best$nodesize)
fit_boost <- boost_fit(boost_best$depth, boost_best$rate)
loss_test <- tibble(
forest = (mv_test$rating - predict(fit_rf, mv_test))^2,
boosting = (mv_test$rating - predict(fit_boost, X_test, iteration_range = c(1, boost_best$iters)))^2,
training_mean = (mv_test$rating - mean(mv_train$rating))^2)
# round(sapply(loss_test, function(l) c(mse = ____, se = ____)), 3)
# d_test <- ____
# c(difference = ____, se = ____)Optional, can be done at home: a truth with an interaction
The lecture’s simulated truth, \(y = x_1^2\cos(\pi x_2/2) + \varepsilon\) with \(x_1\) uniform on \([-1, 1]\) and \(x_2\) uniform on \([-4, 4]\), independent, but with less noise (standard deviation 0.2), so that the differences are large enough to see. Fit an additive model (gam(y ~ s(x1) + s(x2))) and boosted trees of depth 1, 2 and 4 (rate 0.1, 400 iterations) on 2,000 units, and score each on 2,000 fresh units. What is the lowest MSE any model could reach, and which models come near it? What does the additive model’s curve for \(x_2\) look like?
f_true <- function(x1, x2) x1^2 * cos(pi * x2 / 2)
sim <- function(n) tibble(x1 = runif(n, -1, 1), x2 = runif(n, -4, 4)) |> mutate(y = f_true(x1, x2) + rnorm(n, 0, 0.2))
sim_train <- sim(2000)
sim_fresh <- sim(2000)
# ...Optional, can be done at home: backfitting by hand
Fit the additive model \(\text{rating} = \beta_0 + f_1(\text{length}) + f_2(\text{year})\) on the training films by backfitting: start with both curves at zero and \(\hat\beta_0\) the mean rating; then, in turn, fit a smoothing spline (smooth.spline(x, r, df = 9)) of each input’s partial residual on that input, centered to mean zero, until the fitted values stop changing. How many iterations does it take? Compare its tuning MSE with gam(rating ~ s(length) + s(year)).
y <- mv_train$rating
b0 <- mean(y)
f_len <- rep(0, nrow(mv_train))
f_yr <- rep(0, nrow(mv_train))
for (t in 1:20) {
# r_len <- ____ # the partial residual for length
# s_len <- smooth.spline(mv_train$length, r_len, df = 9)
# f_len <- predict(s_len, mv_train$length)$y; f_len <- f_len - mean(f_len)
# ... the same for year
}References
- Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30. doi:10.1080/01621459.1963.10500830
- The films: data note. The Spotify tracks in problem 1: data note.