library(tidyverse) # should've already install.packages("tidyverse")
library(splines) # ns(); ships with R
library(glmnet) # might need to install.packages("glmnet")
library(rpart) # might need to install.packages("rpart")
library(randomForest) # might need to install.packages("randomForest")
library(nnet) # one-hidden-layer networks; ships with R
theme_set(theme_minimal())
mse <- function(y, pred) mean((y - pred)^2)
se_loss <- function(y, pred) sd((y - pred)^2) / sqrt(length(y)) # standard error of an MSE
# k-NN regression with several standardized inputs, as in the lecture: squared distances by
# matrix algebra, then the mean outcome of the k nearest training rows.
knn_predict <- function(Xnew, Xtrain, ytrain, k) {
d2 <- outer(rowSums(Xnew^2), rowSums(Xtrain^2), "+") - 2 * Xnew %*% t(Xtrain)
apply(d2, 1, function(d) mean(ytrain[order(d)[1:k]]))
}Week 5 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 stated one result, the optimism theorem, and left its proof to you (exercise 1). It used ridge regression without deriving its estimator (exercise 2). Do both on paper before the seminar; the seminar’s problems are variations on them. You may use, without proof: linearity of expectation; the tower property, \(\mathbb E[W] = \mathbb E\big[\mathbb E[W \mid V]\big]\); that for a symmetric matrix \(\mathbf A\) the gradient of \(\beta^T\mathbf A\beta\) is \(2\mathbf A\beta\) and its Hessian is \(2\mathbf A\); and that a symmetric matrix has real eigenvalues and an orthonormal basis of eigenvectors. Throughout, assume that every expectation that appears exists and every minimizer named exists.
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 (optimism theorem). Training data \((x_i, y_i)\), \(i = 1, \ldots, n\), independent draws from the population of \((X, Y)\); a loss \(\ell\); the risk \(R(f) = \mathbb E\,\ell(Y, f(X))\) and the training error \(\hat R_n(f) = \tfrac1n\sum_{i=1}^n \ell(y_i, f(x_i))\). A class \(\mathcal F\) is fixed before the data; \(f_{\mathcal F}\) minimizes \(R\) over \(\mathcal F\); \(\hat f\) minimizes \(\hat R_n\) over \(\mathcal F\) (the empirical risk minimizer). Expectations are over the training data.
Let \(f\) be any fixed function, chosen without looking at the data. Show that \(\mathbb E[\hat R_n(f)] = R(f)\). Which part of “independent draws from the population” did you use, and which part did you not use?
Show that \(\hat R_n(\hat f) \le \hat R_n(f_{\mathcal F})\) for every training set, and deduce \(\mathbb E[\hat R_n(\hat f)] \le R(f_{\mathcal F})\).
Show that \(R(f_{\mathcal F}) \le R(\hat f)\) for every training set, and deduce \(R(f_{\mathcal F}) \le \mathbb E[R(\hat f)]\). Of the two inequalities in the theorem, which used the sampling assumption and which used only the definitions?
A test set \((x'_j, y'_j)\), \(j = 1, \ldots, m\), of independent draws from the population, independent of the training data, scores \(\hat f\) by \(\hat R_{\text{test}}(\hat f) = \tfrac1m\sum_j \ell(y'_j, \hat f(x'_j))\). Show that \(\mathbb E[\hat R_{\text{test}}(\hat f)] = \mathbb E[R(\hat f)]\): on average, the test score equals the right end of the theorem.
- \(\hat R_n(f)\) is an average of \(n\) terms; take the expectation of each term. What is the distribution of \((x_i, y_i)\)?
- \(\hat f\) minimizes \(\hat R_n\) over \(\mathcal F\), and \(f_{\mathcal F}\) is a member of \(\mathcal F\). Then apply (a) to \(f_{\mathcal F}\): is it a fixed function?
- Condition on the training data. Given them, \(\hat f\) is a fixed function and the test rows are still draws from the population; apply (a), then the tower property.
Exercise 2 (ridge regression’s normal equations). \(\mathbf X\) is \(n \times p\) with centered columns and \(\mathbf y\) is centered, so there is no intercept to fit (the lecture’s convention: the intercept is not penalized). For \(\lambda > 0\) the ridge estimator minimizes \[ Q_\lambda(\beta) = \|\mathbf y - \mathbf X\beta\|^2 + \lambda\|\beta\|^2. \]
Expand \(Q_\lambda\), compute its gradient, and show that a stationary point satisfies \((\mathbf X^T\mathbf X + \lambda\mathbf I)\beta = \mathbf X^T\mathbf y\).
Show that \(\mathbf X^T\mathbf X + \lambda\mathbf I\) is positive definite, hence invertible, for every \(\lambda > 0\), whatever \(n\) and \(p\) are. Conclude that \(\hat\beta_\lambda = (\mathbf X^T\mathbf X + \lambda\mathbf I)^{-1}\mathbf X^T\mathbf y\) is the unique stationary point, even when \(p > n\).
Compute the Hessian of \(Q_\lambda\). What are its smallest and largest curvatures, in terms of the eigenvalues \(\mu_1 \ge \dots \ge \mu_p \ge 0\) of \(\mathbf X^T\mathbf X\)? Why is the stationary point the global minimizer, and what does the penalty do to the ratio of largest to smallest curvature, the ratio that sets the speed of gradient descent?
Show that \(\|\hat\beta_\lambda\| \le \|\mathbf X^T\mathbf y\|/\lambda\), so \(\hat\beta_\lambda \to \mathbf 0\) as \(\lambda \to \infty\). What is \(\hat\beta_\lambda\) at \(\lambda = 0\) when \(\mathbf X^T\mathbf X\) is invertible?
- \(\|\mathbf y - \mathbf X\beta\|^2 = \mathbf y^T\mathbf y - 2\beta^T\mathbf X^T\mathbf y + \beta^T\mathbf X^T\mathbf X\beta\), and \(\|\beta\|^2 = \beta^T\mathbf I\beta\). Differentiate term by term.
- For any \(v\), \(v^T\mathbf X^T\mathbf X v = \|\mathbf X v\|^2\). What is \(v^T(\mathbf X^T\mathbf X + \lambda\mathbf I)v\) when \(v \ne \mathbf 0\)?
(c), (d) \(\mathbf X^T\mathbf X\) and \(\mathbf X^T\mathbf X + \lambda\mathbf I\) have the same eigenvectors; the eigenvalues of the second are \(\mu_j + \lambda\). Write \(\mathbf X^T\mathbf y\) in the eigenvector basis.
Problems
Problem 1 (the selection winner’s score). \(K\) candidate predictors \(f_1, \ldots, f_K\) have been fitted on the training rows, say by \(K\) methods or one method at \(K\) values of its knob. A selection set of \(m\) rows, independent draws from the population and independent of the training rows, scores them: \(S_k = \tfrac1m\sum_j \ell(y_j, f_k(x_j))\). The winner is \(\hat k = \arg\min_k S_k\), and \(S_{\hat k}\) is its score, the number at the top of the leaderboard.
Show that \(\mathbb E[S_k \mid \text{training data}] = R(f_k)\) for each \(k\).
Show that \(\mathbb E[S_{\hat k} \mid \text{training data}] \le \min_k R(f_k) \le \mathbb E[R(f_{\hat k}) \mid \text{training data}]\). Which argument from exercise 1 is this, with what in place of \(\mathcal F\) and of \(\hat R_n\)?
Two candidates with the same risk \(r\), whose scores are independent and each equal to \(r - 1\) or \(r + 1\) with probability \(\tfrac12\). Compute \(\mathbb E[S_{\hat k}]\) and \(\mathbb E[R(f_{\hat k})]\). Now \(K\) such candidates: what is \(\mathbb E[S_{\hat k}]\), and what happens as \(K\) grows?
The winner is then scored once on the test set. Why does that score not have the same problem?
Problem 2 (where the proof breaks). The optimism theorem does not cover every method. Its proof needs \(\hat f\) to be the minimizer of the training error over a class fixed before the data, and that fails for ridge regression at a fixed \(\lambda\), for a tree grown greedily, and for any knob chosen on the data (problem 1). The first two cases:
A population in which \(Y = X\) exactly (no noise), \(\mathbb E X^2 > 0\), squared loss, and the class \(\mathcal F = \{x \mapsto \beta x : \beta \in \mathbb R\}\) of lines through the origin. Find \(f_{\mathcal F}\) and \(R(f_{\mathcal F})\). For a sample \(x_1, \ldots, x_n\) (not all zero) and a fixed \(\lambda > 0\), find the ridge estimate \(\hat\beta_\lambda\) and its training error \(\hat R_n(\hat\beta_\lambda)\), and show that \(\mathbb E[\hat R_n(\hat\beta_\lambda)] > R(f_{\mathcal F})\): the left inequality fails. Which hypothesis of the theorem does \(\hat\beta_\lambda\) violate?
Replace the penalty by the constraint \(|\beta| \le t\) for a fixed \(t > 0\): \(\mathcal F_t = \{x \mapsto \beta x : |\beta| \le t\}\), and \(\hat f\) the minimizer of \(\hat R_n\) over \(\mathcal F_t\). Does the theorem apply? What is \(\hat f\) here, for \(t \ge 1\) and for \(t < 1\)?
A tree of depth \(2\) grown greedily (the lecture’s splitting) is a member of the class of all depth-\(2\) trees on the same inputs. Which line of the proof is not available for it? Does that mean its training error must sit above its risk on average, or only that the theorem does not say?
Which of the theorem’s two inequalities holds for every \(\hat f \in \mathcal F\), whatever algorithm produced it?
Problem 3 (ridge as least squares on more rows). Stack \(p\) extra rows under the data: \(\tilde{\mathbf X} = \begin{pmatrix}\mathbf X \\ \sqrt\lambda\,\mathbf I_p\end{pmatrix}\), an \((n + p) \times p\) matrix, and \(\tilde{\mathbf y} = \begin{pmatrix}\mathbf y \\ \mathbf 0_p\end{pmatrix}\).
Show that \(\|\tilde{\mathbf y} - \tilde{\mathbf X}\beta\|^2 = \|\mathbf y - \mathbf X\beta\|^2 + \lambda\|\beta\|^2\), the ridge objective.
Write the least-squares normal equations for the regression of \(\tilde{\mathbf y}\) on \(\tilde{\mathbf X}\) and check that they are ridge regression’s, \((\mathbf X^T\mathbf X + \lambda\mathbf I)\beta = \mathbf X^T\mathbf y\). Show that \(\tilde{\mathbf X}\) has full column rank for every \(\lambda > 0\), even when \(p > n\).
In words: what does each of the \(p\) extra rows say, and what does \(\sqrt\lambda\) do? How would you fit ridge regression with nothing but
lm()?
Coding
1. The task and the split
The lecture’s task: predict a track’s popularity from ten audio features and its release year, squared loss (data note). Genre is left out today, so the numbers are those of the lecture’s rows without genre; an optional item at the end adds it.
feat <- c("danceability", "energy", "loudness", "speechiness", "acousticness",
"instrumentalness", "liveness", "valence", "tempo", "duration_min", "release_year")
sp <- read_csv("https://ml4ds.com/files/spotify_tracks.csv", show_col_types = FALSE) |>
distinct(track_id, .keep_all = TRUE) |> # one row per track
mutate(duration_min = duration_ms / 60000) |>
select(track_popularity, all_of(feat)) # the outcome and the eleven inputsStep 1. Split the 10,000 tracks at random into 5,000 training, 2,000 tuning and 3,000 test tracks. The test tracks are the vault: nothing before part 3 touches them.
set.seed(310) # change this number: a different split, and different numbers below
id <- sample(nrow(sp)) # a random order of the 10,000 tracks
# sp_train <- sp[id[____], ] # 5,000 tracks
# sp_tune <- ____ # 2,000
# sp_test <- ____ # 3,000Checkpoint (run it; if it stops, fix step 1 before going on):
stopifnot(nrow(sp_train) == 5000, nrow(sp_tune) == 2000, nrow(sp_test) == 3000,
length(unique(c(id[1:5000], id[5001:7000], id[7001:10000]))) == 10000)Question 1. The file has 11,554 rows for 10,000 tracks, because 1,101 tracks are in more than one playlist, and distinct() kept one row per track before the split. If you had skipped distinct() and split the rows, what could happen to a track, and which of the lecture’s rules would the test score then break?
Step 2. The baselines on the tuning tracks, as in the lecture. score() builds one leaderboard row: a competitor’s MSE on the tuning tracks and its standard error. The mean is done; add the plane (least squares on every input) and \(k\) nearest neighbors on the standardized inputs, with \(k\) chosen on the tuning tracks from ks. scale() centers and scales each column; the tuning rows get the training means and standard deviations, so that both matrices are on the same scale.
y_train <- sp_train$track_popularity
y_tune <- sp_tune$track_popularity
score <- function(name, pred)
tibble(competitor = name, tune_mse = mse(y_tune, pred), se = se_loss(y_tune, pred))
mu <- colMeans(sp_train[, feat])
s <- apply(sp_train[, feat], 2, sd)
X_train <- scale(sp_train[, feat], mu, s)
X_tune <- scale(sp_tune[, feat], mu, s)
ks <- c(1, 5, 10, 20, 50, 100, 200)# fit_plane <- lm(____)
# knn_tune <- sapply(ks, function(k) ____) # the tuning MSE at each k
# k_best <- ____
lb <- bind_rows(
score("the mean", rep(mean(y_train), nrow(sp_tune)))
# , score("least squares", ____)
# , score("k-NN", ____)
)
lb2. Five structures, each tuned on the tuning tracks
The pattern is the same for every family: fit on the training tracks at each value of the knob, score each fit on the tuning tracks, keep the best. Each step adds one row to lb.
Step 3. The lasso. glmnet() fits the whole path of \(\lambda\) values at once, on the standardized matrix; predict() on the tuning matrix then gives one column of predictions per \(\lambda\). Choose \(\lambda\), and count the coefficients that are exactly zero at it.
lasso_fit <- glmnet(X_train, y_train, standardize = FALSE) # the columns already are
# lasso_tune <- apply(predict(lasso_fit, X_tune), 2, function(pred) ____)
# lam_best <- lasso_fit$lambda[____]
# coefficients at lam_best: coef(lasso_fit, s = lam_best); how many are zero?
# ...
# lb <- bind_rows(lb, score("lasso", ____))Step 4. Additive splines: lm() on a natural-spline basis of size \(J\) for each input, all in one least-squares fit, as in the lecture. spline_fit(J, data) writes the formula out. Choose \(J\) from Js.
spline_fit <- function(J, data)
lm(track_popularity ~ ns(danceability, J) + ns(energy, J) + ns(loudness, J) + ns(speechiness, J) +
ns(acousticness, J) + ns(instrumentalness, J) + ns(liveness, J) + ns(valence, J) +
ns(tempo, J) + ns(duration_min, J) + ns(release_year, J), data)
Js <- c(2, 3, 4, 6)
# spline_tune <- sapply(Js, function(J) ____)
# J_best <- ____
# fit_spline <- spline_fit(J_best, sp_train)
# lb <- bind_rows(lb, score("additive splines", ____))Step 5. A tree and a forest. tree_fit(d, data) grows a tree of depth \(d\); choose the depth from depths. The forest has no knob today: randomForest() with its defaults, 300 trees (the slowest fit of the seminar, about half a minute).
tree_fit <- function(d, data)
rpart(track_popularity ~ ., data, control = rpart.control(maxdepth = d, cp = 0, minbucket = 10))
depths <- c(2, 3, 4, 6, 8)
# tree_tune <- sapply(depths, function(d) ____)
# d_best <- ____
# fit_tree <- tree_fit(d_best, sp_train)
fit_rf <- randomForest(track_popularity ~ ., sp_train, ntree = 300)
# lb <- bind_rows(lb, score("tree", ____), score("forest", ____))Step 6. A network with one hidden layer of \(M\) units: nnet() on the standardized matrix, linout = TRUE for a numeric outcome, decay a small ridge penalty on the weights (fixed today), and maxit = 300 a fixed budget of iterations rather than a convergence test. The weights start at random values, so two fits of the same network differ slightly. Choose \(M\) from Ms.
net_fit <- function(M, X, y) nnet(X, y, size = M, decay = 0.1, linout = TRUE, maxit = 300, trace = FALSE)
Ms <- c(2, 4, 8, 16)
# net_tune <- sapply(Ms, function(M) ____)
# M_best <- ____
# fit_net <- net_fit(M_best, X_train, y_train)
# lb <- bind_rows(lb, score("network", ____))The tuning leaderboard, with each competitor’s chosen knob:
lb |> arrange(tune_mse) |> mutate(across(c(tune_mse, se), round))
ggplot(lb, aes(tune_mse, fct_reorder(competitor, -tune_mse))) +
geom_errorbar(aes(xmin = tune_mse - se, xmax = tune_mse + se), width = 0.3, colour = "grey60") +
geom_point(size = 3) +
labs(x = "MSE on the 2,000 tuning tracks", y = NULL, caption = "bars: one standard error")c(k = k_best, lambda = signif(lam_best, 2), J = J_best, depth = d_best, M = M_best)Question 2. Which competitors lead, and by how much against the plane? The bars are each score’s own standard error: do they settle the order among the leaders? Which rows of this leaderboard are unbiased estimates of their competitor’s risk, and which are not (problem 1)?
3. The vault
Step 7. Refit every competitor on the training and tuning tracks together, each at the knob it chose, and predict the test tracks. The standardized matrices are rebuilt with the 7,000 rows’ means and standard deviations. \(k\)-NN has nothing to refit: its “model” is the rows it averages over, now 7,000 of them. Refit only the competitors you fitted in part 2; the solution skips the others.
sp_both <- bind_rows(sp_train, sp_tune)
y_both <- sp_both$track_popularity
y_test <- sp_test$track_popularity
mu_both <- colMeans(sp_both[, feat])
s_both <- apply(sp_both[, feat], 2, sd)
X_both <- scale(sp_both[, feat], mu_both, s_both)
X_test <- scale(sp_test[, feat], mu_both, s_both)
pred_test <- list(
"the mean" = rep(mean(y_both), nrow(sp_test))
# , "least squares" = ____
# , "k-NN" = ____
# , "lasso" = ____
# , "additive splines" = ____
# , "tree" = ____
# , "forest" = ____
# , "network" = ____
)Checkpoint:
stopifnot(all(sapply(pred_test, length) == nrow(sp_test)))Step 8. Open the vault once: every competitor’s test MSE with its standard error, in one table. Then one paired comparison, decided before the vault was opened: the two leaders of the tuning leaderboard, the per-track difference of their squared errors, its mean and its standard error.
# vault <- imap_dfr(pred_test, ~ tibble(competitor = .y, test_mse = ____, se = ____)) |> arrange(test_mse)
# leaders <- ____ # the top two of the tuning leaderboard, not of the vault
# d <- ____ # their squared errors, track by track
# c(mean = mean(d), se = ____)Question 3. Compare the vault with the tuning leaderboard: the order, and each competitor’s test score against its tuning score. Problem 1 says a tuned competitor’s tuning score is too good on average. Can you see that here? What else changed between the two leaderboards?
Question 4. The forest’s training error against its test error, and the plane’s: compute both and compare the gaps. Which competitor does the optimism theorem cover, and does the uncovered one behave any differently?
# c(forest_train = ____, forest_test = ____, plane_train = ____, plane_test = ____)Optional, can be done at home: ridge two ways
Problem 3 says ridge regression is least squares on an augmented dataset. Check it on the training matrix: fit ridge with \(\lambda = 100\) by the formula of exercise 2 and by lm() on the augmented rows, and compare the two coefficient vectors.
lambda <- 100
X_c <- scale(X_train, scale = FALSE) # centered columns, as in exercise 2
y_c <- y_train - mean(y_train)
# b_formula <- ____
# X_aug <- rbind(X_c, ____); y_aug <- c(y_c, ____)
# b_lm <- coef(lm(y_aug ~ X_aug - 1))
# max(abs(b_formula - b_lm))solve(A, b) solves \(\mathbf A\beta = \mathbf b\). diag(p) is \(\mathbf I_p\). The augmented fit has no intercept: - 1 in the formula.
Optional, can be done at home: the lasso path on the tracks
The lecture drew the lasso’s solution path on these tracks. Draw it from your lasso_fit with plot(lasso_fit, xvar = "lambda", label = TRUE), and find the step of the path at which each input enters: the path starts at the end where every coefficient is zero (the largest \(\lambda\); which side of the plot that is depends on your version of glmnet) and the coefficients leave zero one by one as \(\lambda\) falls. Where are the release year and loudness, the two inputs the lecture’s component plots bent most?
Optional, can be done at home: add genre
The lecture’s leaderboard also used the playlist’s genre, a factor with six levels. Add it to the training and tuning tracks (playlist_genre in the file, matched by row after distinct()), refit the plane and the additive splines with + genre, and score them on the tuning tracks. Which methods take a factor as it is, and which need it as 0/1 columns (model.matrix()) first?