Week 8 seminar

Author

Joshua Loftus

Note

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.

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 losses

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)\).

WarningHints

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\).

  1. Show that \(\mathrm{Var}\big(\frac1B\sum_{b=1}^B V_b\big) = \rho\tau^2 + (1 - \rho)\tau^2/B\).

  2. What is left as \(B \to \infty\)? What does the formula give when \(\rho = 1\), and when \(\rho = 0\)?

  3. 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?

  1. 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?
  1. 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\).

  1. Start from \(f_i = \bar y\) for every film. Compute \(\bar y\) and the negative gradient of \(L\) at this \(\mathbf f\).

  2. 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?

  3. 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.

  1. 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\).

  1. Show that \(\mathrm{Var}(\ell_i) \le \frac14\), so that \(\mathrm{Var}(D) \le \frac{1}{4m}\).

  2. Apply Markov’s inequality to \(W = |D|\), using \(\mathbb E|D| \le \sqrt{\mathbb E[D^2]}\), and find \(t\).

  3. Apply it to \(W = D^2\) instead (this is Chebyshev’s inequality), and find \(t\).

  4. Find \(t\) from Hoeffding’s inequality.

  5. 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?

  6. 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.

  1. 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?

  2. 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\).

  3. 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?

  4. 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 together

Question 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 grid

Question 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 = ____)

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