Last modified: 2026-11-19
Adapted from [1, Sec. 3.2.2] and [2, Secs. 6.1.1, 6.1.3, 6.5.1].
Exercise 1 (How many models?)
Exercise 1 (How many models?) Each model below keeps the intercept and uses some subset of \(p\) candidate features.
How many such models are there?
Solution 1. Each feature is either in the model or out of it, so there are \(2^p\) models.
Exercise 2 (How many models? (part 2))
Exercise 2 (How many models? (part 2)) Use the setup of Exercise 1.
How many are there for \(8\) features, and for \(30\)?
Solution 2. For \(p = 8\) there are \(2^8 = 256\) models, few enough to fit them all. For \(p = 30\) there are \(2^{30} =\) 1,073,741,824 models, too many to fit [1, Sec. 3.2.2], p. 87. The procedures that follow fit far fewer.
Examples on the Auto data in this chapter use the objects below. The section Lab: linear regression on the Auto data builds the same objects step by step.
import numpy as np
import pandas as pd
from scipy import stats
# ISLP's load_data("Auto") reads this same file.
Auto = pd.read_csv("data/auto.csv")
y = Auto["mpg"].to_numpy()
n = len(y)
# Indicators of a European and of a Japanese car; American is the baseline.
origin = Auto["origin"].to_numpy()
european = (origin == 2).astype(float)
japanese = (origin == 3).astype(float)
def fit(columns):
"""Least-squares coefficients of mpg on an intercept and `columns`."""
Phi = np.column_stack([np.ones(n)] + columns)
beta_hat = np.linalg.lstsq(Phi, y, rcond=None)[0]
return beta_hat, PhiDefinition 1 (Forward selection)
Definition 1 (Forward selection) Forward selection starts from the model with only an intercept. At each step, it fits every model that adds one more feature, and keeps the one with the lowest residual sum of squares (RSS). It stops when a stopping rule is met [1, Sec. 3.2.2], p. 87, [3].
Example 1 (Forward selection on the Auto data)
Example 1 (Forward selection on the Auto data) Run forward selection (Definition 1) for mpg over eight candidate features: cylinders, displacement, horsepower, weight, acceleration, year, and the european and japanese indicators of the exercise Lab: use a category as a feature. Record the order in which the features enter and the RSS after each step.
candidates = {
name: Auto[name].to_numpy(float)
for name in ["cylinders", "displacement", "horsepower", "weight",
"acceleration", "year"]
}
candidates["european"] = european
candidates["japanese"] = japanese
def rss(names):
beta_hat, Phi = fit([candidates[k] for k in names])
return np.sum((y - Phi @ beta_hat) ** 2)
forward_order, forward_rss = [], []
remaining = list(candidates)
while remaining:
best = min(remaining, key=lambda k: rss(forward_order + [k]))
forward_order.append(best)
remaining.remove(best)
forward_rss.append(rss(forward_order))
print(pd.DataFrame({"added": forward_order, "rss": forward_rss})) added rss
0 weight 7321.233706
1 year 4568.952042
2 japanese 4472.554527
3 european 4310.409498
4 displacement 4271.964759
5 horsepower 4221.333733
6 cylinders 4194.483283
7 acceleration 4187.391678
auto <- dplyr::mutate(auto,
european = as.numeric(origin == 2),
japanese = as.numeric(origin == 3))
candidates <- c("cylinders", "displacement", "horsepower", "weight",
"acceleration", "year", "european", "japanese")
rss <- function(names, data) {
fit <- lm(reformulate(names, response = "mpg"), data = data)
sum(residuals(fit)^2)
}
forward_order <- character(0)
forward_rss <- numeric(0)
remaining <- candidates
while (length(remaining) > 0) {
scores <- sapply(remaining, function(k) rss(c(forward_order, k), auto))
best <- names(which.min(scores))
forward_order <- c(forward_order, best)
forward_rss <- c(forward_rss, min(scores))
remaining <- setdiff(remaining, best)
}
tibble::tibble(added = forward_order, rss = forward_rss)R also has built-in tools for this search. add1() fits each one-feature addition to a model and reports its RSS:
step() calls add1() repeatedly, but it orders the candidates by the AIC, not by RSS, \(p\)-values or cross-validation, and it stops as soon as no addition lowers the AIC. Its option k is the penalty per coefficient: the default k = 2 gives the AIC, and k = log(n) gives the BIC. Among the candidates that add one feature to the same model, the one with the lowest AIC has the lowest RSS, so step() adds features in the same order as the loop above. Setting k = 0 removes the penalty, so the search runs until every feature is in:
[1] TRUE
With the default k = 2, the search stops early:
[1] "acceleration"
The AIC search keeps 7 features and leaves out acceleration, the last feature that the loop added. MASS::stepAIC() runs the same search.
weight enters first, with RSS 7321, then year, which brings it down to 4569. After that the gains are small: the last 6 features together lower the RSS only to 4187. The RSS falls at every step, as the solution to the exercise Lab: add a second feature shows it must, so it cannot by itself say when to stop. These are training RSS values, computed on the cars used to fit, so they get no confidence intervals: the residuals are not independent draws, and the values are biased low.
Definition 2 (Backward selection)
Definition 2 (Backward selection) Backward selection starts from the model with all \(p\) features. At each step, it removes the feature whose \(t\)-test gives the largest \(p\)-value and refits. It stops when a stopping rule is met, such as every remaining \(p\)-value being below a threshold [1, Sec. 3.2.2], p. 87, [3].
Example 2 (Backward selection on the Auto data)
Example 2 (Backward selection on the Auto data) Run backward selection (Definition 2) over the eight features of Example 1, stopping when every remaining \(p\)-value is below \(0.05\).
def p_values(names):
beta_hat, Phi = fit([candidates[k] for k in names])
df = n - Phi.shape[1]
sigma2 = np.sum((y - Phi @ beta_hat) ** 2) / df
se = np.sqrt(sigma2 * np.diag(np.linalg.inv(Phi.T @ Phi)))
return 2 * stats.t.sf(np.abs(beta_hat / se), df)[1:]
backward_kept = list(candidates)
backward_dropped, backward_p = [], []
while np.max(p_values(backward_kept)) >= 0.05:
p = p_values(backward_kept)
backward_dropped.append(backward_kept[np.argmax(p)])
backward_p.append(np.max(p))
backward_kept.remove(backward_dropped[-1])
print(pd.DataFrame({"dropped": backward_dropped, "p": backward_p})) dropped p
0 acceleration 0.421101
1 cylinders 0.117742
['displacement', 'horsepower', 'weight', 'year', 'european', 'japanese']
dropped p
"acceleration" "0.42"
dropped p
"cylinders" "0.12"
[1] "displacement" "horsepower" "weight" "year" "european"
[6] "japanese"
drop1() is R’s built-in tool for one backward step. With test = "F", it tests the removal of each feature with an \(F\)-test. For a feature with one coefficient, the \(F\)-test and the \(t\)-test give the same \(p\)-value, so drop1() reports the \(p\)-values that the loop above uses:
step() with direction = "backward" repeats that step, but it orders the removals by the AIC, not by \(p\)-values, and stops when no removal lowers the AIC:
[1] "cylinders" "displacement" "horsepower" "weight" "year"
[6] "european" "japanese"
The AIC search keeps 7 features, 1 more than the \(p\)-value loop. An AIC penalty of \(2\) per coefficient is a looser bar than a \(p\)-value below \(0.05\): with many cars, removing one coefficient raises the AIC when its \(\abs{t} > \sqrt{2}\), which is roughly \(p < 0.16\). So a feature can lower the AIC without being significant at the \(0.05\) level.
Backward selection drops acceleration (\(p = 0.42\)) and then cylinders (\(p = 0.12\)), and keeps 6 features: displacement, horsepower, weight, year, european, japanese. Forward selection added those same two features last, so here the two procedures agree on which features matter least. They need not agree in general.
Exercise 3 (Finding the best model of each size for certain)
Exercise 3 (Finding the best model of each size for certain) Forward selection and backward selection each fit only some of the \(2^{\ninputvars}\) models that use a subset of \(\ninputvars\) candidate features, so neither is guaranteed to find, for a given number of features \(\subsetsize\), the model with the smallest residual sum of squares among all models with \(\subsetsize\) features.
Hint
Use the count of models in Solution 1.
Describe a way to find that model for every \(\subsetsize\) from \(0\) to \(\ninputvars\) with certainty.
Solution 3. Fit every model that uses a subset of the \(\ninputvars\) candidate features. Then, for each number of features \(\subsetsize\), keep the fitted model with the smallest residual sum of squares among those with \(\subsetsize\) features. No model is skipped, so the kept model is the best one of its size. The residual sum of squares compares only models of the same size: it never rises when a feature is added, so a different criterion has to choose among the \(\ninputvars + 1\) kept models.
Definition 3 (Best subset selection)
Definition 3 (Best subset selection) Best subset selection fits a least-squares model for every subset of the \(\ninputvars\) candidate features. For each size \(\subsetsize \in \set{0, \dots, \ninputvars}\), it keeps the subset \(\mathcal{S}_{\subsetsize}\) whose model has the smallest residual sum of squares:
\[ \mathcal{S}_{\subsetsize} \eqdef \argmin_{\mathcal{S} \subseteq \set{1, \dots, \ninputvars},\ \card{\mathcal{S}} = \subsetsize} \RSS(\mathcal{S}). \]
It then chooses one of the \(\ninputvars + 1\) kept models by an estimate of its test error, such as the cross-validation estimate, Mallows’ \(C_p\), the AIC, the BIC or the adjusted \(R^2\) [2, Sec. 6.1.1].
Example 3 (Best subset selection on baseball salaries)
Example 3 (Best subset selection on baseball salaries) Run best subset selection on the Hitters data, which hold the batting and fielding records and 1987 salaries of Major League baseball players. Predict Salary from ten candidate features: the 1986 counts AtBat, Hits, Walks and PutOuts, the career counts CAtBat, CHits, CHmRun, CRBI and CRuns, and DivisionW, which is \(1\) for a player in the West division and \(0\) otherwise. These features include all six in the model that the book’s lab chooses by the BIC [2, Sec. 6.5.1].
# Drop the players with no salary, and code the division as 1 for West.
bs_hitters <- readr::read_csv("data/hitters.csv", show_col_types = FALSE) |>
tidyr::drop_na(Salary) |>
dplyr::mutate(DivisionW = as.numeric(Division == "W"))
bs_candidates <- c("AtBat", "Hits", "Walks", "CAtBat", "CHits",
"CHmRun", "CRBI", "CRuns", "DivisionW", "PutOuts")
# The residual sum of squares of the least-squares model of Salary on `names`.
bs_rss <- function(names) { # nolint: function_location_linter
bs_formula <- reformulate(names, response = "Salary")
fit <- lm(bs_formula, data = bs_hitters)
res <- residuals(fit)
sum(res^2)
}
# Fit every subset of size k, and keep the one with the smallest RSS.
bs_best_of_size <- function(k) { # nolint: function_location_linter
subsets <- utils::combn(bs_candidates, k, simplify = FALSE)
rss_type <- numeric(1)
scores <- vapply(subsets, bs_rss, rss_type)
best <- which.min(scores)
chosen <- subsets[[best]]
chosen_names <- paste(chosen, collapse = ", ")
n_fits <- length(subsets)
tibble::tibble(size = k, features = chosen_names,
rss = scores[best], n_fits = n_fits)
}
bs_best <- bs_candidates |>
seq_along() |>
lapply(bs_best_of_size) |>
dplyr::bind_rows()
bs_bestleaps::regsubsets() is R’s built-in tool for this search. It gives the same subsets and RSS values as the loop above, without a separate least-squares solve for each candidate model:
AtBat Hits Walks CAtBat CHits CHmRun CRBI CRuns DivisionW PutOuts
1 ( 1 ) " " " " " " " " " " " " "*" " " " " " "
2 ( 1 ) " " "*" " " " " " " " " "*" " " " " " "
3 ( 1 ) " " "*" " " " " " " " " "*" " " " " "*"
4 ( 1 ) " " "*" " " " " " " " " "*" " " "*" "*"
5 ( 1 ) "*" "*" " " " " " " " " "*" " " "*" "*"
6 ( 1 ) "*" "*" "*" " " " " " " "*" " " "*" "*"
7 ( 1 ) " " "*" "*" "*" "*" "*" " " " " "*" "*"
8 ( 1 ) "*" "*" "*" "*" "*" "*" " " " " "*" "*"
9 ( 1 ) "*" "*" "*" "*" "*" " " "*" "*" "*" "*"
10 ( 1 ) "*" "*" "*" "*" "*" "*" "*" "*" "*" "*"
[1] TRUE
from itertools import combinations
import numpy as np
import pandas as pd
# Drop the players with no salary, and code the division as 1 for West.
bs_hitters = pd.read_csv("data/hitters.csv").dropna(subset=["Salary"])
bs_hitters["DivisionW"] = (bs_hitters["Division"] == "W").astype(float)
bs_candidates = ["AtBat", "Hits", "Walks", "CAtBat", "CHits",
"CHmRun", "CRBI", "CRuns", "DivisionW", "PutOuts"]
bs_y = bs_hitters["Salary"].to_numpy()
# The residual sum of squares of the least-squares model of Salary on `names`.
def bs_rss(names):
X = np.column_stack([np.ones(len(bs_y)), bs_hitters[list(names)]])
beta, *_ = np.linalg.lstsq(X, bs_y, rcond=None)
res = bs_y - X @ beta
return res @ res
# Fit every subset of size k, and keep the one with the smallest RSS.
bs_rows = []
for k in range(1, len(bs_candidates) + 1):
subsets = list(combinations(bs_candidates, k))
scores = [bs_rss(s) for s in subsets]
best = int(np.argmin(scores))
bs_rows.append({"size": k, "features": ", ".join(subsets[best]),
"rss": scores[best], "n_fits": len(subsets)})
bs_best = pd.DataFrame(bs_rows)
print(bs_best.to_string()) size features rss n_fits
0 1 CRBI 3.617968e+07 10
1 2 Hits, CRBI 3.064656e+07 45
2 3 Hits, CRBI, PutOuts 2.924930e+07 120
3 4 Hits, CRBI, DivisionW, PutOuts 2.797085e+07 210
4 5 AtBat, Hits, CRBI, DivisionW, PutOuts 2.714990e+07 252
5 6 AtBat, Hits, Walks, CRBI, DivisionW, PutOuts 2.619490e+07 210
6 7 Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts 2.590655e+07 120
7 8 AtBat, Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts 2.528358e+07 45
8 9 AtBat, Hits, Walks, CAtBat, CHits, CRBI, CRuns, DivisionW, PutOuts 2.526507e+07 10
9 10 AtBat, Hits, Walks, CAtBat, CHits, CHmRun, CRBI, CRuns, DivisionW, PutOuts 2.524095e+07 1
Figure 1 plots the smallest residual sum of squares of each size. It falls from 36.2 million with one feature, CRBI, to 30.6 million with two, and by a further 18% as the other eight features enter. The residual sum of squares never rises as a feature is added, so it cannot choose the size: one of the criteria in Definition 3 chooses the size.
# Plot the smallest RSS of each size, in millions, against the size.
bs_best |>
dplyr::mutate(rss_millions = rss / 1e6) |>
ggplot2::ggplot() +
ggplot2::aes(x = size, y = rss_millions) +
ggplot2::geom_line() +
ggplot2::geom_point() +
ggplot2::scale_x_continuous(breaks = 1:10) +
ggplot2::labs(x = "Number of features", y = "Smallest RSS (millions)")import matplotlib.pyplot as plt
# Plot the smallest RSS of each size, in millions, against the size.
fig, ax = plt.subplots(figsize=(6, 3.5), layout="constrained")
ax.plot(bs_best["size"], bs_best["rss"] / 1e6, marker="o");
ax.set_xticks(bs_best["size"]);
ax.set_xlabel("Number of features");
ax.set_ylabel("Smallest RSS (millions)");
plt.show()Salary with each number of the ten candidate features, from best subset selection on the Hitters data.
Exercise 4 (Choosing the size of the best subset by Mallows’ \(C_p\))
Exercise 4 (Choosing the size of the best subset by Mallows’ \(C_p\)) Best subset selection keeps one model of each size, and the residual sum of squares cannot choose among them, because it never rises as a feature enters. A criterion that adds a penalty for each feature can choose. Example 3 keeps the best subsets of the ten candidate features for the Salary of the players in the Hitters data, one for each number of features \(\subsetsize\) from \(1\) to \(10\). Estimate the noise variance by the residual variance of the model with all ten features.
Hint
Mallows’ \(C_p\) adds \(2 \est{\varpar}\) to the \(\RSS\) for each feature. bs_best in Example 3 holds the smallest \(\RSS\) of each size.
Which \(\subsetsize\) gives the smallest Mallows’ \(C_p\)?
Solution 4.
# Estimate the noise variance from the model with all ten features,
# then add 2 * sigma2 per feature to each size's smallest RSS.
bs_n <- nrow(bs_hitters)
bs_full_rss <- bs_best$rss[10]
bs_sigma2 <- bs_full_rss / (bs_n - 10 - 1)
bs_criteria <- bs_best |>
dplyr::select(size, rss) |>
dplyr::mutate(cp = (rss + 2 * size * bs_sigma2) / bs_n)
bs_cp_size <- bs_criteria$size[which.min(bs_criteria$cp)]
bs_criteria# Estimate the noise variance from the model with all ten features,
# then add 2 * sigma2 per feature to each size's smallest RSS.
bs_n = len(bs_hitters)
bs_sigma2 = bs_best["rss"].iloc[9] / (bs_n - 10 - 1)
bs_criteria = bs_best[["size", "rss"]].copy()
bs_criteria["cp"] = (bs_criteria["rss"] + 2 * bs_criteria["size"] * bs_sigma2) / bs_n
print(bs_criteria.to_string()) size rss cp
0 1 3.617968e+07 138327.012419
1 2 3.064656e+07 118050.227806
2 3 2.924930e+07 113499.132660
3 4 2.797085e+07 109399.816961
4 5 2.714990e+07 107040.017066
5 6 2.619490e+07 104170.547510
6 7 2.590655e+07 103835.827298
7 8 2.528358e+07 102228.810630
8 9 2.526507e+07 102920.114893
9 10 2.524095e+07 103590.119885
# Plot Cp against the number of features, and mark the smallest value in red.
bs_cp_best <- bs_criteria |> dplyr::filter(size == bs_cp_size)
bs_criteria |>
ggplot2::ggplot() +
ggplot2::aes(x = size, y = cp / 1e3) +
ggplot2::geom_line() +
ggplot2::geom_point() +
ggplot2::geom_point(data = bs_cp_best, colour = "red", size = 3) +
ggplot2::scale_x_continuous(
breaks = 1:10 # check-unexplained-choices: allow
) +
ggplot2::labs(x = "Number of features", y = "Mallows' Cp (thousands)")import matplotlib.pyplot as plt
# Plot Cp against the number of features, and mark the smallest value in red.
bs_cp_best = bs_criteria.loc[bs_criteria["cp"].idxmin()]
fig, ax = plt.subplots(figsize=(6, 3.5), layout="constrained")
ax.plot(bs_criteria["size"], bs_criteria["cp"] / 1e3, marker="o");
ax.plot(bs_cp_best["size"], bs_cp_best["cp"] / 1e3, "o", color="red", markersize=9);
ax.set_xticks(bs_criteria["size"]);
ax.set_xlabel("Number of features");
ax.set_ylabel("Mallows' Cp (thousands)");
plt.show()Hitters salaries. The red point marks the smallest value.
Figure 2 shows that the model with \(\subsetsize = 8\) features, AtBat, Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts, has the smallest Mallows’ \(C_p\). Past that size, the penalty \(2 \est{\varpar}\) for each added feature exceeds the drop in the residual sum of squares.
Exercise 5 (Choosing the size of the best subset by the BIC)
Exercise 5 (Choosing the size of the best subset by the BIC) Use the ten best subset models of the Hitters salaries from Example 3, one for each number of features \(\subsetsize\) from \(1\) to \(10\). Treat each of these models as a Gaussian linear model, whose \(\subsetsize\) slopes, intercept and noise variance are \(\subsetsize + 2\) estimated parameters.
Hint
The BIC needs the maximized log-likelihood. For a Gaussian linear model fitted by least squares to \(\nobs\) observations, it is \(-\frac{\nobs}{2} \paren{\logf{2 \pi \RSS / \nobs} + 1}\). In R, stats::BIC() of the lm() fit gives the same value.
Which \(\subsetsize\) gives the smallest BIC?
Solution 5.
# The maximized Gaussian log-likelihood of each size's best model,
# and the BIC with d + 2 estimated parameters.
bs_criteria <- bs_criteria |>
dplyr::mutate(
loglik = -bs_n / 2 * (log(2 * pi * rss / bs_n) + 1),
bic = -2 * loglik + (size + 2) * log(bs_n)
)
bs_bic_size <- bs_criteria$size[which.min(bs_criteria$bic)]
bs_criteria |> dplyr::select(size, rss, bic)# The maximized Gaussian log-likelihood of each size's best model,
# and the BIC with d + 2 estimated parameters.
bs_criteria["loglik"] = -bs_n / 2 * (np.log(2 * np.pi * bs_criteria["rss"] / bs_n) + 1)
bs_criteria["bic"] = -2 * bs_criteria["loglik"] + (bs_criteria["size"] + 2) * np.log(bs_n)
print(bs_criteria[["size", "rss", "bic"]].to_string()) size rss bic
0 1 3.617968e+07 3874.855770
1 2 3.064656e+07 3836.775921
2 3 2.924930e+07 3830.075210
3 4 2.797085e+07 3823.893218
4 5 2.714990e+07 3821.630702
5 6 2.619490e+07 3817.785232
6 7 2.590655e+07 3820.446200
7 8 2.528358e+07 3819.616756
8 9 2.526507e+07 3824.996277
9 10 2.524095e+07 3830.317297
# Plot the BIC against the number of features; mark the smallest in red.
bs_bic_best <- bs_criteria |> dplyr::filter(size == bs_bic_size)
bs_criteria |>
ggplot2::ggplot() +
ggplot2::aes(x = size, y = bic) +
ggplot2::geom_line() +
ggplot2::geom_point() +
ggplot2::geom_point(data = bs_bic_best, colour = "red", size = 3) +
ggplot2::scale_x_continuous(
breaks = 1:10 # check-unexplained-choices: allow
) +
ggplot2::labs(x = "Number of features", y = "BIC")# Plot the BIC against the number of features; mark the smallest in red.
bs_bic_best = bs_criteria.loc[bs_criteria["bic"].idxmin()]
fig, ax = plt.subplots(figsize=(6, 3.5), layout="constrained")
ax.plot(bs_criteria["size"], bs_criteria["bic"], marker="o");
ax.plot(bs_bic_best["size"], bs_bic_best["bic"], "o", color="red", markersize=9);
ax.set_xticks(bs_criteria["size"]);
ax.set_xlabel("Number of features");
ax.set_ylabel("BIC");
plt.show()Hitters salaries. The red point marks the smallest value.
Figure 3 shows that the model with \(\subsetsize = 6\) features, AtBat, Hits, Walks, CRBI, DivisionW, PutOuts, has the smallest BIC. The BIC charges \(\logf{\nobs} = 5.57\) for each parameter, more than the charge of \(2\) that the AIC makes. In Exercise 4, Mallows’ \(C_p\) chooses \(\subsetsize = 8\), and here the BIC chooses \(\subsetsize = 6\).
Exercise 6 (Choosing the size of the best subset by the adjusted \(R^2\))
Exercise 6 (Choosing the size of the best subset by the adjusted \(R^2\)) Use the ten best subset models of the Hitters salaries from Example 3, one for each number of features \(\subsetsize\) from \(1\) to \(10\).
Hint
The adjusted \(R^2\) divides the \(\RSS\) by \(\nobs - \subsetsize - 1\) and the total sum of squares \(\TSS\) by \(\nobs - 1\), so it needs the \(\TSS\) of Salary as well as bs_best.
Which \(\subsetsize\) gives the largest adjusted \(R^2\)?
Solution 6.
# The total sum of squares of Salary, and each best model's adjusted R^2.
bs_salary_dev <- bs_hitters$Salary - mean(bs_hitters$Salary)
bs_tss <- sum(bs_salary_dev^2)
bs_criteria <- bs_criteria |>
dplyr::mutate(adj_r2 = 1 - (rss / (bs_n - size - 1)) / (bs_tss / (bs_n - 1)))
bs_adjr2_size <- bs_criteria$size[which.max(bs_criteria$adj_r2)]
bs_criteria |> dplyr::select(size, rss, adj_r2) size rss adj_r2
0 1 3.617968e+07 0.318850
1 2 3.064656e+07 0.420802
2 3 2.924930e+07 0.445075
3 4 2.797085e+07 0.467273
4 5 2.714990e+07 0.480897
5 6 2.619490e+07 0.497200
6 7 2.590655e+07 0.500785
7 8 2.528358e+07 0.510871
8 9 2.526507e+07 0.509297
9 10 2.524095e+07 0.507820
# Plot the adjusted R^2 against the size; mark the largest in red.
bs_adjr2_best <- bs_criteria |> dplyr::filter(size == bs_adjr2_size)
bs_criteria |>
ggplot2::ggplot() +
ggplot2::aes(x = size, y = adj_r2) +
ggplot2::geom_line() +
ggplot2::geom_point() +
ggplot2::geom_point(data = bs_adjr2_best, colour = "red", size = 3) +
ggplot2::scale_x_continuous(
breaks = 1:10 # check-unexplained-choices: allow
) +
ggplot2::labs(x = "Number of features", y = "Adjusted R-squared")# Plot the adjusted R^2 against the size; mark the largest in red.
bs_adjr2_best = bs_criteria.loc[bs_criteria["adj_r2"].idxmax()]
fig, ax = plt.subplots(figsize=(6, 3.5), layout="constrained")
ax.plot(bs_criteria["size"], bs_criteria["adj_r2"], marker="o");
ax.plot(bs_adjr2_best["size"], bs_adjr2_best["adj_r2"], "o", color="red", markersize=9);
ax.set_xticks(bs_criteria["size"]);
ax.set_xlabel("Number of features");
ax.set_ylabel("Adjusted R-squared");
plt.show()Hitters salaries. The red dot marks the largest value.
Figure 4 shows that the model with \(\subsetsize = 8\) features, AtBat, Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts, has the largest adjusted \(R^2\). Mallows’ \(C_p\) chooses \(\subsetsize = 8\), the BIC chooses \(\subsetsize = 6\), and the adjusted \(R^2\) chooses \(\subsetsize = 8\). The book’s lab, with all nineteen candidate features, also finds the BIC choosing the smallest model of the three [2, Sec. 6.5.1].
Proposition 1 (Number of models that best subset selection fits)
Proposition 1 (Number of models that best subset selection fits) Best subset selection over \(\ninputvars\) candidate features fits \(2^{\ninputvars}\) models.
Proof
Proof. Best subset selection fits one model for each subset of the \(\ninputvars\) candidate features. A subset is fixed by choosing, for each feature, whether it is in or out: \(\ninputvars\) choices of two options each, so there are \(2^{\ninputvars}\) subsets, as Solution 1 found.
Example 4 (Counting the fits on baseball salaries)
Example 4 (Counting the fits on baseball salaries) Best subset selection on the ten candidate features of Example 3 fits 1023 models with at least one feature, and one model with no features: 1024 models in all, which is \(2^{10}\), as Proposition 1 states.
Exercise 7 (Where forward selection misses the best subset)
Exercise 7 (Where forward selection misses the best subset) Use the Hitters data and the ten candidate features for Salary of Example 3. Run forward selection over the same candidates, on all the players, scoring each step by the residual sum of squares.
Hint
Example 1 codes forward selection on the Auto data, and bs_rss() in Example 3 scores a list of features.
State the numbers of features at which forward selection’s model differs from the best subset model of the same size.
Solution 7.
# Forward selection: at each step, add the feature that lowers the RSS most.
bs_forward <- character(0)
bs_forward_rss <- numeric(0)
bs_remaining <- bs_candidates
rss_type <- numeric(1)
has_remaining <- TRUE
while (has_remaining) {
scores <- vapply(bs_remaining, \(f) {
trial <- c(bs_forward, f)
bs_rss(trial)
}, rss_type)
best <- which.min(scores)
bs_forward <- c(bs_forward, bs_remaining[best])
bs_forward_rss <- c(bs_forward_rss, scores[best])
bs_remaining <- bs_remaining[-best]
has_remaining <- length(bs_remaining) > 0
}
# Forward selection's model of size k holds the first k features to enter.
# It differs from the best subset of size k when its RSS is larger.
bs_compare <- bs_best |>
dplyr::mutate(forward_rss = bs_forward_rss,
differs = forward_rss > rss * (1 + 1e-9))
bs_differ <- bs_compare |> dplyr::filter(differs)
bs_differ |>
dplyr::select(size, features, rss, forward_rss) [1] "CRBI" "Hits" "PutOuts" "DivisionW" "AtBat" "Walks"
[7] "CRuns" "CAtBat" "CHits" "CHmRun"
# Forward selection: at each step, add the feature that lowers the RSS most.
bs_forward, bs_forward_rss = [], []
bs_remaining = list(bs_candidates)
while bs_remaining:
scores = [bs_rss(bs_forward + [f]) for f in bs_remaining]
best = int(np.argmin(scores))
bs_forward.append(bs_remaining.pop(best))
bs_forward_rss.append(scores[best])
# Forward selection's model of size k holds the first k features to enter.
# It differs from the best subset of size k when its RSS is larger.
bs_compare = bs_best.assign(forward_rss=bs_forward_rss)
bs_compare["differs"] = bs_compare["forward_rss"] > bs_compare["rss"] * (1 + 1e-9)
print(bs_compare.loc[bs_compare["differs"], ["size", "features", "rss", "forward_rss"]].to_string()) size features rss forward_rss
6 7 Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts 2.590655e+07 2.608421e+07
7 8 AtBat, Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts 2.528358e+07 2.567165e+07
['CRBI', 'Hits', 'PutOuts', 'DivisionW', 'AtBat', 'Walks', 'CRuns', 'CAtBat', 'CHits', 'CHmRun']
Forward selection’s model differs from the best subset model at 7 and 8 features. With 7 features, forward selection keeps the first 7 features to enter, CRBI, Hits, PutOuts, DivisionW, AtBat, Walks, CRuns, while the best subset is Hits, Walks, CAtBat, CHits, CHmRun, DivisionW, PutOuts, with a residual sum of squares 25.91 million against forward selection’s 26.08 million. Forward selection never removes CRBI, its first feature, but the best subsets of those sizes leave it out, so forward selection cannot reach them. At every other size the two methods agree. The book’s lab, with all nineteen candidate features, also finds the two methods first differing at seven features [2, Sec. 6.5.1].
Exercise 8 (Where backward selection misses the best subset)
Exercise 8 (Where backward selection misses the best subset) Use the Hitters data and the ten candidate features for Salary of Example 3. Run backward selection over the same candidates, on all the players, scoring each step by the residual sum of squares.
Hint
Example 2 codes backward selection on the Auto data, and Solution 7 compares forward selection with the best subset on these candidates.
State the numbers of features at which backward selection’s model differs from the best subset model of the same size.
Solution 8.
# Backward selection: start from all ten features, and at each step
# remove the feature whose removal raises the RSS least.
n_candidates <- length(bs_candidates)
bs_kept <- bs_candidates
bs_removed <- character(0)
bs_backward_rss <- numeric(n_candidates)
bs_backward_rss[n_candidates] <- bs_rss(bs_kept)
rss_type <- numeric(1)
n_kept <- n_candidates
has_more <- n_kept > 1
while (has_more) {
scores <- vapply(bs_kept, \(f) {
trial <- setdiff(bs_kept, f)
bs_rss(trial)
}, rss_type)
worst <- which.min(scores)
bs_removed <- c(bs_removed, bs_kept[worst])
bs_kept <- bs_kept[-worst]
n_kept <- length(bs_kept)
bs_backward_rss[n_kept] <- scores[worst]
has_more <- n_kept > 1
}
# Compare the model of each size with the best subset and with
# forward selection's model (forward_rss, from the forward solution).
bs_compare_bwd <- bs_compare |>
dplyr::mutate(
backward_rss = bs_backward_rss,
backward_vs_best = backward_rss > rss * (1 + 1e-9),
backward_vs_forward = abs(backward_rss - forward_rss) > rss * 1e-9
)
bs_compare_bwd |>
dplyr::select(size, rss, forward_rss, backward_rss)[1] "CHmRun" "CRuns" "AtBat" "Hits" "CRBI" "DivisionW"
[7] "PutOuts" "CAtBat" "Walks"
# Backward selection: start from all ten features, and at each step
# remove the feature whose removal raises the RSS least.
bs_kept = list(bs_candidates)
bs_removed = []
bs_backward_rss = {len(bs_kept): bs_rss(bs_kept)}
while len(bs_kept) > 1:
scores = [bs_rss([g for g in bs_kept if g != f]) for f in bs_kept]
worst = int(np.argmin(scores))
bs_removed.append(bs_kept.pop(worst))
bs_backward_rss[len(bs_kept)] = scores[worst]
# Compare the model of each size with the best subset and with
# forward selection's model (forward_rss, from the forward solution).
bs_compare_bwd = bs_compare.assign(backward_rss=bs_compare["size"].map(bs_backward_rss))
print(bs_compare_bwd[["size", "rss", "forward_rss", "backward_rss"]].to_string()) size rss forward_rss backward_rss
0 1 3.617968e+07 3.617968e+07 3.725397e+07
1 2 3.064656e+07 3.064656e+07 3.223904e+07
2 3 2.924930e+07 2.924930e+07 3.006368e+07
3 4 2.797085e+07 2.797085e+07 2.869575e+07
4 5 2.714990e+07 2.714990e+07 2.750693e+07
5 6 2.619490e+07 2.619490e+07 2.646897e+07
6 7 2.590655e+07 2.608421e+07 2.596912e+07
7 8 2.528358e+07 2.567165e+07 2.541457e+07
8 9 2.526507e+07 2.526507e+07 2.526507e+07
9 10 2.524095e+07 2.524095e+07 2.524095e+07
['CHmRun', 'CRuns', 'AtBat', 'Hits', 'CRBI', 'DivisionW', 'PutOuts', 'CAtBat', 'Walks']
Backward selection’s model differs from the best subset model at every size from 1 to 8 features, and agrees with it only at 9 and 10 features. It removes CRBI at step 5, going from 6 features to 5, and never puts it back, but the best subset of every size up to 5 contains CRBI. Its model with one feature is CHits, with a residual sum of squares of 37.25 million against 36.18 million for the best single feature, CRBI.
Backward selection’s model also differs from forward selection’s at exactly those sizes, 1 to 8. At 7 and 8 features the three methods choose three different models, as the book’s lab finds at seven features with all nineteen candidates [2, Sec. 6.5.1].
Exercise 9 (Forward selection on baseball salaries, sized by cross-validation)
Exercise 9 (Forward selection on baseball salaries, sized by cross-validation) The Hitters data hold the 1986 and career statistics of Major League baseball players, with their 1987 salaries in thousands of dollars. Drop the players whose salary is missing, and code League, Division and NewLeague as \(0/1\) indicators, which leaves \(19\) candidate features for the salary. Randomly split the players into a training half and a test half.
On the training half, run forward selection (Definition 1) with the RSS as the score, and record the order in which the features enter.
Solution 9.
hs <- na.omit(read.csv("data/hitters.csv"))
hs_x <- model.matrix(Salary ~ ., data = hs)[, -1]
hs_y <- hs$Salary
set.seed(1)
hs_train <- sample(nrow(hs), nrow(hs) / 2)
xt <- hs_x[hs_train, ]
yt <- hs_y[hs_train]
rss_of <- function(x, y, cols) {
sum(lm.fit(cbind(1, x[, cols, drop = FALSE]), y)$residuals^2)
}
# Forward selection by the RSS: the features in the order they enter.
hs_forward <- function(x, y) {
chosen <- integer(0)
while (length(chosen) < ncol(x)) {
rest <- setdiff(seq_len(ncol(x)), chosen)
scores <- sapply(rest, function(j) rss_of(x, y, c(chosen, j)))
chosen <- c(chosen, rest[which.min(scores)])
}
chosen
}
# Predictions of the model with the first `size` features of `entry`.
hs_predict <- function(x, y, entry, size, x_new) {
cols <- entry[seq_len(size)]
fit <- lm.fit(cbind(1, x[, cols, drop = FALSE]), y)
drop(cbind(1, x_new[, cols, drop = FALSE]) %*% fit$coefficients)
}
entry_all <- hs_forward(xt, yt)
colnames(xt)[entry_all] [1] "CRBI" "Walks" "DivisionW" "Years" "PutOuts"
[6] "CHits" "CAtBat" "LeagueN" "CHmRun" "Assists"
[11] "AtBat" "HmRun" "NewLeagueN" "Errors" "CRuns"
[16] "CWalks" "Hits" "Runs" "RBI"
hs_py = pd.read_csv("data/hitters.csv").dropna()
hs_x = pd.get_dummies(hs_py.drop(columns="Salary"), drop_first=True)
hs_names = list(hs_x.columns)
hs_x = hs_x.to_numpy(dtype=float)
hs_y = hs_py["Salary"].to_numpy()
hs_rng = np.random.default_rng(1)
hs_train = hs_rng.permutation(len(hs_y))[: len(hs_y) // 2]
hs_test = np.setdiff1d(np.arange(len(hs_y)), hs_train)
xt = hs_x[hs_train]
yt = hs_y[hs_train]
def hs_design(x, cols):
return np.column_stack([np.ones(len(x)), x[:, cols]])
def hs_beta(x, y, cols):
return np.linalg.lstsq(hs_design(x, cols), y, rcond=None)[0]
def hs_rss(x, y, cols):
r = y - hs_design(x, cols) @ hs_beta(x, y, cols)
return r @ r
# Forward selection by the RSS: the features in the order they enter.
def hs_forward_py(x, y):
chosen = []
while len(chosen) < x.shape[1]:
rest = [j for j in range(x.shape[1]) if j not in chosen]
chosen.append(min(rest, key=lambda j: hs_rss(x, y, chosen + [j])))
return chosen
# Predictions of the model with the first `size` features of `entry`.
def hs_predict_py(x, y, entry, size, x_new):
cols = entry[:size]
return hs_design(x_new, cols) @ hs_beta(x, y, cols)
entry_all_py = hs_forward_py(xt, yt)
[hs_names[j] for j in entry_all_py]['CRBI', 'Hits', 'Division_W', 'AtBat', 'PutOuts', 'Years', 'Assists', 'Walks', 'CWalks', 'League_N', 'CRuns', 'CAtBat', 'NewLeague_N', 'Runs', 'CHits', 'Errors', 'CHmRun', 'RBI', 'HmRun']
1. The two languages split the players at random in different ways, so their numbers differ. The numbers below are from the R split.
On the training half, the features enter in the order CRBI, Walks, DivisionW, Years, PutOuts, and so on.
Exercise 10 (Forward selection on baseball salaries, sized by cross-validation (part 2))
Exercise 10 (Forward selection on baseball salaries, sized by cross-validation (part 2)) Use the setup of Exercise 9.
Randomly assign the training players to ten folds. For each size \(\subsetsize = 1, \dots, 19\), compute the 10-fold cross-validation root mean squared error (RMSE) of the model that has the first \(\subsetsize\) features chosen by forward selection. Run the forward selection again on the other nine folds of each split.
Solution 10.
# The selection is repeated on the other nine folds of each split.
set.seed(2)
folds <- sample(rep(1:10, length.out = nrow(xt)))
cv_sq <- matrix(NA_real_, nrow(xt), ncol(xt))
for (f in 1:10) {
held <- folds == f
entry_f <- hs_forward(xt[!held, ], yt[!held])
for (m in seq_len(ncol(xt))) {
pred <- hs_predict(xt[!held, ], yt[!held], entry_f, m, xt[held, , drop = FALSE])
cv_sq[held, m] <- (yt[held] - pred)^2
}
}
cv_rmse <- sqrt(colMeans(cv_sq))
m_best <- which.min(cv_rmse)
data.frame(size = seq_along(cv_rmse), cv_rmse = round(cv_rmse))# The selection is repeated on the other nine folds of each split.
folds_py = np.random.default_rng(2).permutation(np.arange(len(yt)) % 10)
cv_sq_py = np.empty((len(yt), xt.shape[1]))
for f in range(10):
held = folds_py == f
entry_f = hs_forward_py(xt[~held], yt[~held])
for m in range(1, xt.shape[1] + 1):
pred = hs_predict_py(xt[~held], yt[~held], entry_f, m, xt[held])
cv_sq_py[held, m - 1] = (yt[held] - pred) ** 2
cv_rmse_py = np.sqrt(cv_sq_py.mean(axis=0))
m_best_py = int(np.argmin(cv_rmse_py)) + 1
print(pd.DataFrame({"size": range(1, xt.shape[1] + 1), "cv_rmse": cv_rmse_py.round()})) size cv_rmse
0 1 409.0
1 2 420.0
2 3 400.0
3 4 390.0
4 5 383.0
5 6 385.0
6 7 376.0
7 8 392.0
8 9 395.0
9 10 390.0
10 11 376.0
11 12 376.0
12 13 373.0
13 14 372.0
14 15 374.0
15 16 378.0
16 17 378.0
17 18 378.0
18 19 378.0
2. Cross-validation chooses \(\subsetsize =\) 3 features, with a cross-validation RMSE of 320 thousand dollars.
Exercise 11 (Forward selection on baseball salaries, sized by cross-validation (part 3))
Exercise 11 (Forward selection on baseball salaries, sized by cross-validation (part 3)) Use the setup of Exercise 9.
Choose the size \(\subsetsize\) with the smallest cross-validation RMSE, refit that model on the whole training half, and compute its root mean squared error on the test half.
Solution 11.
chosen size 14 - test RMSE 332 - all features 332
The model that cross-validation chooses has a test RMSE of 390 thousand dollars on the test half.
Exercise 12 (Forward selection on baseball salaries, sized by cross-validation (part 4))
Exercise 12 (Forward selection on baseball salaries, sized by cross-validation (part 4)) Use the setup of Exercise 9.
Compare it with the test error of the model that uses all \(19\) features.
Exercise 13 (Forward selection on baseball salaries, sized by cross-validation (part 5))
Exercise 13 (Forward selection on baseball salaries, sized by cross-validation (part 5)) Use the setup of Exercise 9.
Why must the forward selection be run again inside each split, rather than once on the whole training half?
Exercise 14 (Forward selection on baseball salaries, sized by cross-validation (part 6))
Exercise 14 (Forward selection on baseball salaries, sized by cross-validation (part 6)) Use the training half of the Hitters players, its ten folds, and the held-out squared errors of each size from Exercise 10.
A cross-validation estimate depends on which players land in which fold, so another assignment of players to folds would give a different value for each size. Two sizes whose values differ by less than that variation may give about equally good predictions, and the smaller of them has fewer features to record and interpret.
Plot the cross-validation estimate of the mean squared error of each size against the size, with a bar of one fold-based standard error on each side.
Hint
The fold-based standard error is the sample standard deviation of the ten fold mean squared errors, divided by \(\sqrt{10}\). Compute the fold mean squared errors of each size from the held-out squared errors of the players in each fold.
Solution 14.
# The cross-validation estimate of each size pools the held-out squared errors.
cv_est <- colMeans(cv_sq)
# The fold mean squared errors: one row per fold, one column per size.
fold_sums <- rowsum(cv_sq, folds)
fold_counts <- tabulate(folds)
fold_mse <- fold_sums / fold_counts
# The fold-based standard error of each size.
fold_sd <- apply(fold_mse, 2, sd)
cv_se <- fold_sd / sqrt(10)
# The spread of the estimates, to compare with the SE at the minimum.
cv_spread <- max(cv_est) - min(cv_est)
se_at_min <- cv_se[which.min(cv_est)]
cv_sizes <- seq_along(cv_est)
cv_tbl <- tibble::tibble(size = cv_sizes, estimate = cv_est, se = cv_se)
cv_tbl# The cross-validation estimate of each size pools the held-out squared errors.
cv_est_py = cv_sq_py.mean(axis=0)
# The fold mean squared errors: one row per fold, one column per size.
fold_mse_py = np.array([cv_sq_py[folds_py == f].mean(axis=0) for f in range(10)])
# The fold-based standard error of each size.
cv_se_py = fold_mse_py.std(axis=0, ddof=1) / np.sqrt(10)
cv_tbl_py = pd.DataFrame({"size": range(1, xt.shape[1] + 1),
"estimate": cv_est_py, "se": cv_se_py})
print(cv_tbl_py.round().to_string(index=False)) size estimate se
1 167379.0 39539.0
2 176630.0 42095.0
3 160313.0 39971.0
4 151756.0 36592.0
5 146871.0 35102.0
6 148335.0 35090.0
7 141246.0 33944.0
8 153465.0 36330.0
9 155847.0 37679.0
10 152185.0 37286.0
11 141083.0 36026.0
12 141252.0 37870.0
13 138768.0 37151.0
14 138738.0 37489.0
15 139716.0 37867.0
16 142965.0 40121.0
17 142777.0 39505.0
18 142735.0 39502.0
19 142957.0 39465.0
# Plot each size's estimate with a bar of one standard error on each side.
cv_tbl |>
ggplot2::ggplot() +
ggplot2::aes(x = size, y = estimate / 1e3) +
ggplot2::geom_linerange(
ggplot2::aes(ymin = (estimate - se) / 1e3, ymax = (estimate + se) / 1e3),
colour = "grey50"
) +
ggplot2::geom_line() +
ggplot2::geom_point() +
ggplot2::labs(
x = "Number of features",
y = "CV estimate of MSE (thousands)"
)# Plot each size's estimate with a bar of one standard error on each side.
fig, ax = plt.subplots(figsize=(6, 3.5), layout="constrained")
ax.errorbar(cv_tbl_py["size"], cv_tbl_py["estimate"] / 1e3,
yerr=cv_tbl_py["se"] / 1e3, marker="o", color="black",
ecolor="grey");
ax.set_xlabel("Number of features");
ax.set_ylabel("CV estimate of MSE (thousands)");
plt.show()Hitters training half, with bars of one fold-based standard error on each side.
Figure 5 shows the cross-validation estimates from the R split. The smallest is at 3 features, 102 thousand, with a fold-based standard error of 33 thousand. The other sizes give values from 103 to 124 thousand. The values of all sizes lie within 21 thousand of each other, less than that fold-based standard error.
Exercise 15 (Forward selection on baseball salaries, sized by cross-validation (part 7))
Exercise 15 (Forward selection on baseball salaries, sized by cross-validation (part 7)) Use the cross-validation estimates and fold-based standard errors of each size from Exercise 14.
Which size does the one-standard-error rule choose?
Hint
A model of a smaller size is less flexible than one of a larger size, so the rule looks for the smallest size whose estimate is at most the smallest estimate plus that estimate’s standard error.
Solution 15.
# The cutoff is the smallest estimate plus its own standard error.
size_min <- which.min(cv_est)
cv_cutoff <- cv_est[size_min] + cv_se[size_min]
# The rule takes the smallest size whose estimate is within the cutoff.
sizes_within <- which(cv_est <= cv_cutoff)
size_one_se <- min(sizes_within)
c(smallest_estimate = size_min, one_se_rule = size_one_se)smallest_estimate one_se_rule
3 1
# The cutoff is the smallest estimate plus its own standard error.
size_min_py = int(np.argmin(cv_est_py)) + 1
cv_cutoff_py = cv_est_py[size_min_py - 1] + cv_se_py[size_min_py - 1]
# The rule takes the smallest size whose estimate is within the cutoff.
size_one_se_py = int(np.flatnonzero(cv_est_py <= cv_cutoff_py).min()) + 1
print("smallest estimate", size_min_py, "- one-standard-error rule", size_one_se_py)smallest estimate 14 - one-standard-error rule 1
The one-standard-error rule chooses size 1 on the R split, whose feature is CRBI. That size is the smallest whose cross-validation estimate is at most 135 thousand, the smallest value (at 3 features) plus its fold-based standard error [2, Sec. 6.1.3].
Exercise 16 (Forward selection on baseball salaries, sized by cross-validation (part 8))
Exercise 16 (Forward selection on baseball salaries, sized by cross-validation (part 8)) Use the size that the one-standard-error rule chooses in Exercise 15, and the test half of the Hitters players from Exercise 9.
Compare the root mean squared error on the test half of the model of that size with the test RMSE of the model of Exercise 11, which has the size with the smallest cross-validation estimate.
Hint
Refit the model of the chosen size on the whole training half, as Exercise 11 does for its size.
Solution 16.
On the R split, the model of size 1 that the one-standard-error rule chooses has a test RMSE of 432 thousand dollars. The model of size 3 from Exercise 11 has a test RMSE of 390 thousand dollars. The smaller model’s test RMSE is higher by 42 thousand dollars, with 2 fewer features.
This section works through the part of the book’s Chapter 6 lab on subset selection [1, Sec. 6.5.1]. The methods in it predict an outcome from only some of the available variables, which reduces the number of coefficients the model has to fit.
Our prompts and solution text paraphrase [1, Sec. 6.5.1]. The Python code is adapted from the book’s Chapter 6 lab notebook [4], with pandas and statsmodels in place of the ISLP package. The R code is our own. Emil Hvitfeldt’s tidymodels version of the lab leaves out this part, because tidymodels supports neither best subset nor stepwise selection, so these exercises have no tidymodels tab.
Exercise 17 (Loading the baseball salaries)
Exercise 17 (Loading the baseball salaries) The rest of this lab predicts a player’s Salary in the Hitters data from that player’s batting and fielding records, first with forward selection and then with best subset selection. Some players have no recorded Salary.
Load the data and count the players whose Salary is missing.
Solution 17.
import numpy as np
import pandas as pd
from statsmodels.api import OLS
from functools import partial
# ISLP's load_data('Hitters') reads the same data as this file.
Hitters = pd.read_csv("data/hitters.csv")
# np.isnan() marks each missing salary, and sum() counts the marks.
np.isnan(Hitters['Salary']).sum()np.int64(59)
59 of the 322 players have no Salary.
Exercise 18 (Loading the baseball salaries (part 2))
Exercise 18 (Loading the baseball salaries (part 2)) Use the Hitters data of Exercise 17. Drop every player with a missing value in any variable. How many players and variables remain?
Solution 18.
No variable other than Salary has a missing value, so dropping the 59 players without a salary leaves 263 players and 20 variables: Salary and 19 others.
Exercise 19 (A Mallows’ Cp scorer)
Exercise 19 (A Mallows’ Cp scorer) Use the Hitters players left in Exercise 18. Forward selection needs a score for each candidate model. Write a function that takes a fitted model and the data it was fit on, and returns its Mallows’ \(C_p\) (Equation 6.2 in [1, Sec. 6.1.3]). For \(\varpar\), use the estimate \(\est{\varpar}\) given by the residual variance of the linear model on all 19 other variables.
Solution 19. Mallows’ \(C_p\) is \((\RSS + 2 d \est{\varpar}) / n\) for a model with \(d\) coefficients fit on \(n\) players. A smaller \(C_p\) is better, but the Python follows scikit-learn’s convention that a larger score is better, so its scorer nCp() returns the negative of \(C_p\). Both scorers take a fitted model and the data it was fit on, and read \(d\) and \(n\) off the shape of that data.
The estimate \(\est{\varpar}\) comes from the fit with every variable. ISLP builds the design matrix with its ModelSpec; here get_dummies() turns League, Division and NewLeague into 0/1 indicators instead.
partial() fixes the sigma2 of nCp() at \(\est{\varpar}\), which leaves a scorer that takes a fit and its data.
lab_x <- model.matrix(Salary ~ ., data = hitters)
lab_y <- hitters$Salary
full_fit <- lm.fit(lab_x, lab_y)
# The residual variance: the RSS over the residual degrees of freedom.
sigma2 <- sum(full_fit$residuals^2) / full_fit$df.residual
# A lab helper, defined where the lab uses it.
# nolint start: function_location_linter.
# Mallows' Cp of `fit`, an lm.fit() of y on the columns of x,
# with the noise variance estimate sigma2.
cp_of <- function(fit, x, y, sigma2) {
y_hat <- x %*% fit$coefficients
rss <- sum((y - y_hat)^2)
(rss + 2 * ncol(x) * sigma2) / nrow(x)
}
# nolint end
# Cp of the model with every variable.
cp_of(full_fit, lab_x, lab_y, sigma2)[1] 107164.8
\(\est{\varpar}\) is 99,591, from the linear model with all 19 features and an intercept.
Exercise 20 (Forward selection scored by Mallows’ Cp)
Exercise 20 (Forward selection scored by Mallows’ Cp) Use the Hitters players and the \(C_p\) scorer of Exercise 19. Run forward selection from the model with only an intercept, and stop at the first step where no added variable improves the score. Run it twice: once scoring each model by its mean squared error on the data it was fit on, and once by \(C_p\). Which variables does each run keep?
Solution 20. ISLP runs this search with its Stepwise.first_peak() strategy and sklearn_selected() [4]. Here a short function does the same search, so the page needs no ISLP package.
def neg_MSE(estimator, X, Y):
return -np.mean((Y - estimator.predict(X))**2)
# Forward selection from the intercept-only model,
# stopping when no added column raises the score.
def forward_first_peak(X, Y, scoring):
selected = ['intercept']
best = scoring(OLS(Y, X[selected]).fit(), X[selected], Y)
rest = [c for c in X.columns if c not in selected]
while rest:
scores = {c: scoring(OLS(Y, X[selected + [c]]).fit(), X[selected + [c]], Y)
for c in rest}
c_best = max(scores, key=scores.get)
if scores[c_best] <= best:
break
selected.append(c_best)
rest.remove(c_best)
best = scores[c_best]
return selected[1:]
hitters_MSE = forward_first_peak(X, Y, neg_MSE)
len(hitters_MSE)19
# Lab helpers, defined where the lab uses them.
# nolint start: function_location_linter.
# The in-sample mean squared error of `fit`, an lm.fit() of y on x.
mse_of <- function(fit, x, y) {
y_hat <- x %*% fit$coefficients
mean((y - y_hat)^2)
}
# Forward selection on the columns of x from the intercept-only model
# (column 1), stopping when no added column lowers the score.
# `score` takes a fit, its columns of x and y, then any arguments in `...`.
forward_first_peak <- function(x, y, score, ...) {
score_cols <- function(cols) {
x_cols <- x[, cols, drop = FALSE]
fit <- lm.fit(x_cols, y)
score(fit, x_cols, y, ...)
}
chosen <- 1
best <- score_cols(chosen)
n_cols <- ncol(x)
rest <- seq_len(n_cols)[-1]
score_with <- function(j) {
cols <- c(chosen, j)
score_cols(cols)
}
one_number <- numeric(1)
repeat {
none_left <- length(rest) == 0
if (none_left) {
break
}
scores <- vapply(rest, score_with, one_number)
pick <- which.min(scores)
no_gain <- scores[pick] >= best
if (no_gain) {
break
}
best <- scores[pick]
chosen <- c(chosen, rest[pick])
rest <- rest[-pick]
}
all_names <- colnames(x)
all_names[chosen[-1]]
}
# nolint end
forward_mse <- forward_first_peak(lab_x, lab_y, mse_of)
length(forward_mse)[1] 19
The in-sample mean squared error never rises when a variable enters, so the first run keeps all 19 variables. \(C_p\) adds \(2 \est{\varpar} / n\) for each coefficient, so the second run stops sooner, with 10 variables: CRBI, Hits, PutOuts, DivisionW, AtBat, Walks, CWalks, CRuns, CAtBat, Assists. The book’s lab also selects all 19 variables by MSE and 10 by \(C_p\) [1, Sec. 6.5.1].
Exercise 21 (Best subset selection along a path)
Exercise 21 (Best subset selection along a path) Use the Hitters players left in Exercise 18. Forward selection is greedy: each step adds one variable to the variables it already holds. Best subset selection instead searches, for each number of variables, for the best set of that many variables. Run best subset selection on all 19 other variables. Which variables are in the best model with two variables?
Solution 21. ISLP’s lab runs best subset selection with the l0bnb package [4]. It does not fix the number of variables. Instead, it charges a penalty \(\regpar_0\) for each nonzero coefficient, and returns a path of fits as \(\regpar_0\) shrinks. Penalizing the number of variables, rather than fixing it, matters once we cross-validate. l0bnb fits the intercept on its own, so the Python drops it from X. The R tab uses leaps::regsubsets(), which searches each size in turn.
Preprocessing Data.
BnB Started.
Iteration: 1. Number of non-zeros: 1
Iteration: 2. Number of non-zeros: 2
Iteration: 3. Number of non-zeros: 2
Iteration: 4. Number of non-zeros: 2
Iteration: 5. Number of non-zeros: 3
Iteration: 6. Number of non-zeros: 3
Iteration: 7. Number of non-zeros: 4
Iteration: 8. Number of non-zeros: 9
Iteration: 9. Number of non-zeros: 9
Iteration: 10. Number of non-zeros: 9
Iteration: 11. Number of non-zeros: 9
Iteration: 12. Number of non-zeros: 9
Iteration: 13. Number of non-zeros: 9
Iteration: 14. Number of non-zeros: 9
Iteration: 15. Number of non-zeros: 9
Iteration: 16. Number of non-zeros: 9
Iteration: 17. Number of non-zeros: 9
Iteration: 18. Number of non-zeros: 17
Iteration: 19. Number of non-zeros: 19
Each fit on the path holds the coefficients as B, the intercept as B0, and the penalty as lambda_0. The fourth fit has two nonzero coefficients.
{'B': array([0. , 3.25484367, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0.67775265, 0. , 0. , 0. ,
0. , 0. , 0. , 0. ]), 'B0': np.float64(-38.98216739555505), 'lambda_0': np.float64(0.011416248027450187), 'M': np.float64(0.5829861733382012), 'Time_exceeded': False}
The best model with two variables uses Hits and CRBI. They are the two variables of the fourth fit on the l0bnb path, at \(\regpar_0\) = 0.0114. regsubsets() finds the same pair. A validation set or cross-validation along \(\regpar_0\) would choose among the fits on the path [1, Sec. 6.5.1].