# Chapter 5 lab: cross-validation and the bootstrap (R version).
# Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie and
# Tibshirani (2021), An Introduction to Statistical Learning with Applications in R, Section 5.3,
# and the applied exercises of Section 5.4.
#
# The code is my own. It asks the same questions of the same data as the R lab of the book:
#   5.3.1 the validation set approach on Auto (polynomials in horsepower, two random splits);
#   5.3.2 leave-one-out cross-validation, with cv.glm() and with the one-fit shortcut (5.2);
#   5.3.3 10-fold cross-validation;
#   5.3.4 the bootstrap: the minimum-variance allocation alpha on Portfolio, and the standard
#         errors of the Auto regression coefficients compared with the textbook formula.
# The seeds are those of the book, so the printed numbers are the book's.
# The Python version is ch05_lab.py; the lecture notes show the two side by side.
#
# Run: Rscript ch05_lab.R        (about a minute; Exercise 6 refits 1,000 logistic regressions)

suppressPackageStartupMessages({
  library(ISLR2)   # the data sets: Auto, Portfolio, Default, Weekly, Boston
  library(boot)    # cv.glm() and boot()
})
options(digits = 5)

## -- 5.3.1 The validation set approach
# Fit a polynomial in horsepower on a random half of the 392 cars and
# score it by the mean squared error on the other half.
val_mse <- function(degree, train) {
  fit <- lm(mpg ~ poly(horsepower, degree), data = Auto, subset = train)
  mean((Auto$mpg - predict(fit, Auto))[-train]^2)
}
set.seed(1)
train <- sample(392, 196)
val_seed1 <- sapply(1:3, val_mse, train = train)
val_seed1                                   # 23.27 18.72 18.79

set.seed(2)                                 # a different split, different estimates
train <- sample(392, 196)
val_seed2 <- sapply(1:3, val_mse, train = train)
val_seed2                                   # 25.73 20.43 20.39

## -- 5.3.2 Leave-one-out cross-validation
# glm() without a family is least squares, and cv.glm() refits it n times.
glm_fit <- glm(mpg ~ horsepower, data = Auto)
coef(glm_fit)                               # 39.936 -0.158, as lm()
cv_glm <- cv.glm(Auto, glm_fit)
cv_glm$delta                                # 24.23 24.23

# The shortcut (5.2): one least-squares fit, each residual divided by 1 - h_i.
loocv_shortcut <- function(fit) mean((residuals(fit) / (1 - hatvalues(fit)))^2)
loocv_shortcut(lm(mpg ~ horsepower, data = Auto))   # 24.23 again

loocv <- sapply(1:10, function(d) {
  cv.glm(Auto, glm(mpg ~ poly(horsepower, d), data = Auto))$delta[1]
})
loocv_fast <- sapply(1:10, function(d) {
  loocv_shortcut(lm(mpg ~ poly(horsepower, d), data = Auto))
})
round(loocv, 2)                              # 24.23 19.25 19.33 19.42 19.03 18.98 18.83 18.96 19.07 19.49
all.equal(loocv, loocv_fast)                 # TRUE: n refits and one fit agree

## -- 5.3.3 k-fold cross-validation
# cv.glm() draws new folds at every call, so each degree gets its own split.
set.seed(17)
cv10 <- matrix(NA, 10, 2, dimnames = list(1:10, c("CV", "adjusted")))
for (d in 1:10) {
  cv10[d, ] <- cv.glm(Auto, glm(mpg ~ poly(horsepower, d), data = Auto), K = 10)$delta
}
round(cv10[, "CV"], 2)                       # 24.27 19.27 19.35 19.29 19.03 18.90 19.12 19.15 18.87 20.96
round(cv10[, "adjusted"], 2)                 # the bias-corrected second number of delta

## -- 5.3.4 The bootstrap: a statistic of interest
# alpha_fn() returns the estimate (5.7) of the minimum-variance allocation,
# computed from the rows of the data listed in index.
alpha_fn <- function(data, index) {
  x <- data$X[index]
  y <- data$Y[index]
  (var(y) - cov(x, y)) / (var(x) + var(y) - 2 * cov(x, y))
}
alpha_fn(Portfolio, 1:100)                   # 0.576 from all 100 pairs

set.seed(7)
alpha_fn(Portfolio, sample(100, 100, replace = TRUE))   # 0.539: one bootstrap replicate

boot_alpha <- boot(Portfolio, alpha_fn, R = 1000)
boot_alpha                                   # original 0.5758, std. error 0.0897
sd(boot_alpha$t[, 1])                        # the same number, by (5.8)

## -- 5.3.4 The bootstrap: accuracy of a linear regression
boot_fn <- function(data, index) {
  coef(lm(mpg ~ horsepower, data = data, subset = index))
}
boot_fn(Auto, 1:392)                         # 39.936 -0.158

set.seed(1)
boot_fn(Auto, sample(392, 392, replace = TRUE))   # 40.341 -0.164
boot_fn(Auto, sample(392, 392, replace = TRUE))   # 40.119 -0.158
boot_lin <- boot(Auto, boot_fn, 1000)
se_boot_lin <- apply(boot_lin$t, 2, sd)
se_boot_lin                                  # 0.8413 0.0073

lin_fit <- lm(mpg ~ horsepower, data = Auto)
se_formula_lin <- summary(lin_fit)$coef[, "Std. Error"]
se_formula_lin                               # 0.7175 0.0064: smaller than the bootstrap

# The heteroscedasticity-robust (sandwich) standard errors, by hand:
# (X'X)^{-1} X' diag(e^2) X (X'X)^{-1}. They agree with the bootstrap, not with the formula.
sandwich_se <- function(fit) {
  X <- model.matrix(fit)
  e <- residuals(fit)
  bread <- solve(crossprod(X))
  sqrt(diag(bread %*% crossprod(X * e) %*% bread))
}
se_sandwich_lin <- sandwich_se(lin_fit)
se_sandwich_lin                              # 0.8536 0.0074

boot_fn2 <- function(data, index) {
  coef(lm(mpg ~ horsepower + I(horsepower^2), data = data, subset = index))
}
set.seed(1)
boot_quad <- boot(Auto, boot_fn2, 1000)
se_boot_quad <- apply(boot_quad$t, 2, sd)
se_boot_quad                                 # 2.0300 0.0324 0.0001
quad_fit <- lm(mpg ~ horsepower + I(horsepower^2), data = Auto)
se_formula_quad <- summary(quad_fit)$coef[, "Std. Error"]
se_formula_quad                              # 1.8004 0.0311 0.0001: now close
se_sandwich_quad <- sandwich_se(quad_fit)
se_sandwich_quad

## ===========================================================================
## Applied exercises (Section 5.4)
## ===========================================================================

## -- Exercise 2(h): how often is observation 4 in a bootstrap sample of size 100?
set.seed(1)
ex2_store <- replicate(10000, any(sample(100, replace = TRUE) == 4))
mean(ex2_store)                              # close to 1 - (1 - 1/100)^100 = 0.634

## -- Exercise 5: validation-set error of a logistic regression on Default
val_error <- function(seed, formula) {
  set.seed(seed)
  train <- sample(nrow(Default), nrow(Default) / 2)
  fit <- glm(formula, data = Default, subset = train, family = binomial)
  prob <- predict(fit, Default[-train, ], type = "response")
  mean(ifelse(prob > 0.5, "Yes", "No") != Default$default[-train])
}
ex5_two <- sapply(1:4, val_error, formula = default ~ income + balance)
ex5_three <- sapply(1:4, val_error, formula = default ~ income + balance + student)
round(rbind(ex5_two, ex5_three), 4)

## -- Exercise 6: bootstrap standard errors of logistic coefficients
def_fit <- glm(default ~ income + balance, data = Default, family = binomial)
ex6_formula <- summary(def_fit)$coef[2:3, "Std. Error"]
ex6_formula                                  # income 4.985e-06, balance 2.274e-04
boot_fn_logit <- function(data, index) {
  coef(glm(default ~ income + balance, data = data, subset = index, family = binomial))[2:3]
}
set.seed(1)
boot_logit <- boot(Default, boot_fn_logit, R = 1000)
ex6_boot <- apply(boot_logit$t, 2, sd)
ex6_boot

## -- Exercise 7: LOOCV for a logistic regression on Weekly, by a loop
wk_fit <- glm(Direction ~ Lag1 + Lag2, data = Weekly, family = binomial)
wk_fit_1 <- glm(Direction ~ Lag1 + Lag2, data = Weekly[-1, ], family = binomial)
ex7_p1 <- predict(wk_fit_1, Weekly[1, ], type = "response")
c(prob_up = ex7_p1, truth = as.character(Weekly$Direction[1]))   # predicts Up, truth Down
n_wk <- nrow(Weekly)
wrong <- numeric(n_wk)
for (i in seq_len(n_wk)) {
  fit_i <- glm(Direction ~ Lag1 + Lag2, data = Weekly[-i, ], family = binomial)
  p_up <- predict(fit_i, Weekly[i, ], type = "response")
  wrong[i] <- as.numeric((p_up > 0.5) != (Weekly$Direction[i] == "Up"))
}
ex7_loocv <- mean(wrong)
ex7_loocv                                    # 0.4500

## -- Exercise 8: cross-validation on simulated data
set.seed(1)
x <- rnorm(100)
y <- x - 2 * x^2 + rnorm(100)
sim <- data.frame(x = x, y = y)
loocv_poly <- function(data) {
  sapply(1:4, function(d) cv.glm(data, glm(y ~ poly(x, d), data = data))$delta[1])
}
ex8_loocv <- loocv_poly(sim)
ex8_loocv                                    # degree 2 is best
set.seed(2)
all.equal(loocv_poly(sim), ex8_loocv)        # TRUE: LOOCV has no random element
ex8_pvalues <- summary(lm(y ~ poly(x, 4), data = sim))$coef[, "Pr(>|t|)"]
signif(ex8_pvalues, 3)                       # only the linear and quadratic terms are significant

## -- Exercise 9: the bootstrap on Boston$medv
medv <- Boston$medv
ex9_mu <- mean(medv)
ex9_se <- sd(medv) / sqrt(length(medv))
c(mu = ex9_mu, se = ex9_se)                  # 22.533 0.409
set.seed(1)
boot_mean <- boot(medv, function(v, i) mean(v[i]), R = 1000)
ex9_se_boot <- sd(boot_mean$t[, 1])
ex9_ci_boot <- ex9_mu + c(-2, 2) * ex9_se_boot
ex9_ci_t <- t.test(medv)$conf.int
rbind(bootstrap = ex9_ci_boot, t.test = as.numeric(ex9_ci_t))
boot_med <- boot(medv, function(v, i) median(v[i]), R = 1000)
ex9_median <- median(medv)
ex9_se_median <- sd(boot_med$t[, 1])
boot_q10 <- boot(medv, function(v, i) quantile(v[i], 0.1), R = 1000)
ex9_q10 <- quantile(medv, 0.1)
ex9_se_q10 <- sd(boot_q10$t[, 1])
c(median = ex9_median, se = ex9_se_median, q10 = unname(ex9_q10), se = ex9_se_q10)

## -- key numbers, saved for the course's own records
.key <- c(
  setNames(val_seed1, paste0("val_seed1_d", 1:3)), setNames(val_seed2, paste0("val_seed2_d", 1:3)),
  loocv_glm_d1 = cv_glm$delta[1], setNames(loocv, paste0("loocv_d", 1:10)),
  setNames(loocv_fast, paste0("loocv_fast_d", 1:10)),
  setNames(cv10[, "CV"], paste0("cv10_d", 1:10)), setNames(cv10[, "adjusted"], paste0("cv10adj_d", 1:10)),
  alpha_hat = alpha_fn(Portfolio, 1:100), alpha_se_boot = sd(boot_alpha$t[, 1]),
  setNames(coef(lin_fit), c("lin_b0", "lin_b1")),
  setNames(se_boot_lin, c("lin_se_boot_b0", "lin_se_boot_b1")),
  setNames(se_formula_lin, c("lin_se_formula_b0", "lin_se_formula_b1")),
  setNames(se_sandwich_lin, c("lin_se_sandwich_b0", "lin_se_sandwich_b1")),
  setNames(coef(quad_fit), c("quad_b0", "quad_b1", "quad_b2")),
  setNames(se_boot_quad, c("quad_se_boot_b0", "quad_se_boot_b1", "quad_se_boot_b2")),
  setNames(se_formula_quad, c("quad_se_formula_b0", "quad_se_formula_b1", "quad_se_formula_b2")),
  setNames(se_sandwich_quad, c("quad_se_sandwich_b0", "quad_se_sandwich_b1", "quad_se_sandwich_b2")),
  ex2_mean = mean(ex2_store),
  setNames(ex5_two, paste0("ex5_two_seed", 1:4)), setNames(ex5_three, paste0("ex5_three_seed", 1:4)),
  setNames(ex6_formula, c("ex6_se_formula_income", "ex6_se_formula_balance")),
  setNames(ex6_boot, c("ex6_se_boot_income", "ex6_se_boot_balance")),
  ex7_p1 = unname(ex7_p1), ex7_loocv = ex7_loocv, setNames(ex8_loocv, paste0("ex8_loocv_d", 1:4)),
  ex9_mu = ex9_mu, ex9_se = ex9_se, ex9_se_boot = ex9_se_boot, ex9_median = ex9_median,
  ex9_se_median = ex9_se_median, ex9_q10 = unname(ex9_q10), ex9_se_q10 = ex9_se_q10,
  ex9_t_lo = ex9_ci_t[1], ex9_t_hi = ex9_ci_t[2]
)
.dir <- local({
  a <- grep("^--file=", commandArgs(FALSE), value = TRUE)
  if (length(a)) dirname(normalizePath(sub("^--file=", "", a[1]))) else getwd()
})
dir.create(file.path(.dir, "cache"), showWarnings = FALSE)
write.csv(data.frame(key = names(.key), value = unname(.key)),
          file.path(.dir, "cache", "ch05_lab_R.csv"), row.names = FALSE)
