"""Chapter 5 lab: cross-validation and the bootstrap (Python version).

Course: Applied Statistical Learning in R and Python, following James, Witten, Hastie, Tibshirani
and Taylor (2023), An Introduction to Statistical Learning with Applications in Python, Section 5.3,
and the applied exercises of Section 5.4.

The code is my own, written with numpy, pandas, statsmodels and scikit-learn (not the book's ISLP
package). It asks the same questions of the same data as the Python 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, by n refits and by the one-fit shortcut (5.2);
  5.3.3 10-fold cross-validation, and the validation set approach as a ShuffleSplit;
  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 random seeds are those of the book's Python lab, so the printed numbers are the book's
(except that the bootstrap standard error divides by B - 1, as in (5.8); see the notes).
The R version is ch05_lab.R; the lecture notes show the two side by side.

Run: python3 ch05_lab.py        (about a minute; Exercise 6 refits 1,000 logistic regressions)
"""
import os

for _v in ("OPENBLAS_NUM_THREADS", "MKL_NUM_THREADS", "OMP_NUM_THREADS"):
    os.environ.setdefault(_v, "1")

import json

import numpy as np
import pandas as pd
import statsmodels.api as sm
from scipy import stats
from sklearn.model_selection import KFold, ShuffleSplit, train_test_split

from common import isl_data

np.set_printoptions(precision=4, suppress=True)
HERE = os.path.dirname(os.path.abspath(__file__))
KEY = {}                       # key numbers, saved for the course's own records


def show(label, value):
    print(label, value if not isinstance(value, float) else round(value, 4))


# -- data
Auto = isl_data("Auto", na_values="?").dropna().reset_index(drop=True)   # 392 cars
Portfolio = isl_data("Portfolio")                                        # 100 pairs of returns
H, Y = Auto["horsepower"].to_numpy(float), Auto["mpg"].to_numpy(float)


# -- orthogonal polynomials, as R's poly()
class Poly:
    """Orthogonal polynomials of one variable. fit() learns the three-term recurrence on the
    training values (as R's poly() does); transform() evaluates the basis at any values. The
    columns span the same space as x, x^2, ..., x^d, so every fit and prediction is the
    ordinary polynomial one, but the least-squares problem stays well conditioned."""

    def __init__(self, degree):
        self.degree = degree

    def fit(self, x):
        x = np.asarray(x, float)
        d = self.degree
        self.alpha, self.norm2 = np.zeros(d), np.zeros(d + 2)
        self.norm2[0], self.norm2[1] = 1.0, len(x)
        p_old, p = np.zeros_like(x), np.ones_like(x)
        for k in range(d):
            self.alpha[k] = np.sum(x * p ** 2) / np.sum(p ** 2)
            p_old, p = p, (x - self.alpha[k]) * p - self.norm2[k + 1] / self.norm2[k] * p_old
            self.norm2[k + 2] = np.sum(p ** 2)
        return self

    def transform(self, x):
        x = np.asarray(x, float)
        Z = [np.ones_like(x), x - self.alpha[0]]
        for k in range(1, self.degree):
            Z.append((x - self.alpha[k]) * Z[k] - self.norm2[k + 1] / self.norm2[k] * Z[k - 1])
        Z = np.column_stack(Z[1:self.degree + 1]) / np.sqrt(self.norm2[2:])
        return np.column_stack([np.ones_like(x), Z])          # intercept first


def lstsq(X, y):
    return np.linalg.lstsq(X, y, rcond=None)[0]


# ==== 5.3.1 The validation set approach =================================================
# Fit a polynomial in horsepower on a random half of the cars and score it on the other half.
def val_mse(degree, train, valid):
    P = Poly(degree).fit(train["horsepower"])
    beta = lstsq(P.transform(train["horsepower"]), train["mpg"])
    pred = P.transform(valid["horsepower"]) @ beta
    return np.mean((valid["mpg"] - pred) ** 2)


Auto_train, Auto_valid = train_test_split(Auto, test_size=196, random_state=0)
val_seed0 = [val_mse(d, Auto_train, Auto_valid) for d in (1, 2, 3)]
show("validation, random_state=0:", np.round(val_seed0, 2))      # 23.62 18.76 18.80

Auto_train, Auto_valid = train_test_split(Auto, test_size=196, random_state=3)
val_seed3 = [val_mse(d, Auto_train, Auto_valid) for d in (1, 2, 3)]
show("validation, random_state=3:", np.round(val_seed3, 2))      # 20.76 16.95 16.97

# ==== 5.3.2 Leave-one-out cross-validation =============================================
# By definition (5.1): leave each car out in turn, refit, predict it.
def loocv_brute(X, y):
    n = len(y)
    err = np.empty(n)
    for i in range(n):
        keep = np.arange(n) != i
        err[i] = (y[i] - X[i] @ lstsq(X[keep], y[keep])) ** 2
    return err.mean()


# By the shortcut (5.2): one fit; the leverages h_i are the squared row norms of Q in X = QR.
def loocv_shortcut(X, y):
    Q, _ = np.linalg.qr(X)
    h = np.sum(Q ** 2, axis=1)
    resid = y - Q @ (Q.T @ y)
    return np.mean((resid / (1 - h)) ** 2)


X1 = np.column_stack([np.ones_like(H), H])
show("LOOCV, 392 refits:", loocv_brute(X1, Y))                  # 24.2315
show("LOOCV, shortcut (5.2):", loocv_shortcut(X1, Y))           # the same
loocv = np.array([loocv_shortcut(Poly(d).fit(H).transform(H), Y) for d in range(1, 11)])
show("LOOCV, degrees 1-10:", np.round(loocv, 4))

# ==== 5.3.3 k-fold cross-validation =====================================================
# The same ten folds for every degree; CV(10) is the average of the ten fold MSEs (5.3).
def kfold_cv(degree, splitter):
    fold_mse = []
    for tr, te in splitter.split(H):
        P = Poly(degree).fit(H[tr])
        beta = lstsq(P.transform(H[tr]), Y[tr])
        fold_mse.append(np.mean((Y[te] - P.transform(H[te]) @ beta) ** 2))
    return np.mean(fold_mse), np.array(fold_mse)


folds = KFold(n_splits=10, shuffle=True, random_state=0)
cv10 = np.array([kfold_cv(d, folds)[0] for d in range(1, 11)])
show("10-fold CV, degrees 1-10:", np.round(cv10, 4))           # 24.2077 19.1853 19.2763 19.4785 19.1372 ...

# The validation set approach is a one-split "cross-validation": ShuffleSplit.
one_split = ShuffleSplit(n_splits=1, test_size=196, random_state=0)
show("validation via ShuffleSplit:", kfold_cv(1, one_split)[0])  # 23.6166
ten_splits = ShuffleSplit(n_splits=10, test_size=196, random_state=0)
val10 = kfold_cv(1, ten_splits)[1]
show("ten validation splits, mean and sd:", (round(val10.mean(), 4), round(val10.std(), 4)))   # 23.8022 1.4218

# ==== 5.3.4 The bootstrap: a statistic of interest =====================================
def alpha_func(D, idx):
    """The estimate (5.7) of the minimum-variance allocation from the rows idx of D."""
    c = np.cov(D[["X", "Y"]].loc[idx], rowvar=False)
    return (c[1, 1] - c[0, 1]) / (c[0, 0] + c[1, 1] - 2 * c[0, 1])


show("alpha-hat from all 100 pairs:", alpha_func(Portfolio, range(100)))     # 0.5758
rng = np.random.default_rng(0)
show("one bootstrap replicate:", alpha_func(Portfolio, rng.choice(100, 100, replace=True)))   # 0.6074


def boot_se(func, D, B=1000, seed=0):
    """Bootstrap standard error (5.8) of func(D, idx): B resamples of the rows of D,
    drawn with replacement; returns the standard error and the B replicates."""
    rng = np.random.default_rng(seed)
    reps = np.array([func(D, rng.choice(D.index, len(D), replace=True)) for _ in range(B)])
    return reps.std(axis=0, ddof=1), reps


alpha_se, alpha_reps = boot_se(alpha_func, Portfolio, B=1000, seed=0)
show("bootstrap SE of alpha-hat:", alpha_se)                    # 0.0912

# ==== 5.3.4 The bootstrap: accuracy of a linear regression =============================
def boot_ols(degree, D, idx):
    """Least-squares coefficients of mpg on raw powers of horsepower, from the rows idx."""
    D_ = D.loc[idx]
    X = np.vander(D_["horsepower"].to_numpy(float), degree + 1, increasing=True)
    return lstsq(X, D_["mpg"].to_numpy(float))


def hp_func(D, idx):
    return boot_ols(1, D, idx)


def quad_func(D, idx):
    return boot_ols(2, D, idx)


rng = np.random.default_rng(0)
print(np.array([hp_func(Auto, rng.choice(392, 392, replace=True)) for _ in range(10)]))
se_boot_lin, _ = boot_se(hp_func, Auto, B=1000, seed=10)
show("bootstrap SEs, linear:", se_boot_lin)                     # 0.8488 0.0074

lin_fit = sm.OLS(Y, sm.add_constant(H)).fit()
se_formula_lin = lin_fit.bse
show("formula SEs, linear:", se_formula_lin)                    # 0.7175 0.0064: smaller


def sandwich_se(X, resid):
    """Heteroscedasticity-robust standard errors (X'X)^{-1} X' diag(e^2) X (X'X)^{-1}."""
    bread = np.linalg.inv(X.T @ X)
    meat = (X * resid[:, None] ** 2).T @ X
    return np.sqrt(np.diag(bread @ meat @ bread))


se_sandwich_lin = sandwich_se(lin_fit.model.exog, lin_fit.resid)
show("sandwich SEs, linear:", se_sandwich_lin)                  # 0.8536 0.0074: as the bootstrap

se_boot_quad, _ = boot_se(quad_func, Auto, B=1000, seed=0)
show("bootstrap SEs, quadratic:", se_boot_quad)                 # 2.0679 0.0330 0.0001
Xq = np.column_stack([np.ones_like(H), H, H ** 2])
quad_fit = sm.OLS(Y, Xq).fit()
se_formula_quad = quad_fit.bse
show("formula SEs, quadratic:", se_formula_quad)                # 1.8004 0.0311 0.0001: now close
se_sandwich_quad = sandwich_se(Xq, quad_fit.resid)

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

# -- Exercise 2(h): how often is observation 4 in a bootstrap sample of size 100?
rng = np.random.default_rng(10)
store = np.array([np.any(rng.choice(100, 100, replace=True) == 4) for _ in range(10000)])
show("Exercise 2(h):", store.mean())                            # close to 0.634
# The book's line rng.choice(100, replace=True) draws ONE number, not a sample of 100:
rng = np.random.default_rng(10)
show("  as printed in the book:", np.mean([rng.choice(100, replace=True) == 4 for _ in range(10000)]))

# -- Exercise 5: validation-set error of a logistic regression on Default
Default = isl_data("Default")
Default["y"] = (Default["default"] == "Yes").astype(float)
Default["stud"] = (Default["student"] == "Yes").astype(float)


def val_error(seed, cols):
    train, valid = train_test_split(Default, test_size=0.5, random_state=seed)
    fit = sm.GLM(train["y"], sm.add_constant(train[cols]), family=sm.families.Binomial()).fit()
    prob = fit.predict(sm.add_constant(valid[cols]))
    return np.mean((prob > 0.5) != (valid["y"] == 1))


ex5_two = [val_error(s, ["income", "balance"]) for s in (1, 2, 3, 4)]
ex5_three = [val_error(s, ["income", "balance", "stud"]) for s in (1, 2, 3, 4)]
show("Exercise 5, income + balance:", np.round(ex5_two, 4))
show("Exercise 5, + student:", np.round(ex5_three, 4))

# -- Exercise 6: bootstrap standard errors of logistic coefficients
def logit_coef(D, idx):
    D_ = D.loc[idx]
    fit = sm.GLM(D_["y"], sm.add_constant(D_[["income", "balance"]]), family=sm.families.Binomial()).fit()
    return fit.params.to_numpy()[1:]


def_fit = sm.GLM(Default["y"], sm.add_constant(Default[["income", "balance"]]),
                 family=sm.families.Binomial()).fit()
ex6_formula = def_fit.bse.to_numpy()[1:]
ex6_boot, _ = boot_se(logit_coef, Default, B=1000, seed=0)
print("Exercise 6, formula SEs:", " ".join("%.4g" % v for v in ex6_formula))    # 4.985e-06 0.0002274
print("Exercise 6, bootstrap SEs:", " ".join("%.4g" % v for v in ex6_boot))

# -- Exercise 7: LOOCV for a logistic regression on Weekly, by a loop
Weekly = isl_data("Weekly")
Xw = sm.add_constant(Weekly[["Lag1", "Lag2"]]).to_numpy()
yw = (Weekly["Direction"] == "Up").to_numpy(float)
binom = sm.families.Binomial()
fit_1 = sm.GLM(yw[1:], Xw[1:], family=binom).fit()
ex7_p1 = float(fit_1.predict(Xw[:1])[0])
show("Exercise 7(c), P(Up) for week 1:", ex7_p1)                # 0.5714 -> Up, but it went Down
wrong = np.empty(len(yw))
for i in range(len(yw)):
    keep = np.arange(len(yw)) != i
    p_up = sm.GLM(yw[keep], Xw[keep], family=binom).fit().predict(Xw[i:i + 1])[0]
    wrong[i] = (p_up > 0.5) != (yw[i] == 1)
ex7_loocv = wrong.mean()
show("Exercise 7, LOOCV error:", ex7_loocv)                     # 0.4500

# -- Exercise 8: cross-validation on simulated data
rng = np.random.default_rng(1)
x = rng.normal(size=100)
y = x - 2 * x ** 2 + rng.normal(size=100)
ex8_loocv = np.array([loocv_shortcut(Poly(d).fit(x).transform(x), y) for d in (1, 2, 3, 4)])
show("Exercise 8, LOOCV degrees 1-4:", np.round(ex8_loocv, 4))  # degree 2 is best
ex8_pvalues = sm.OLS(y, Poly(4).fit(x).transform(x)).fit().pvalues
print("Exercise 8(f), p-values:", " ".join("%.3g" % p for p in ex8_pvalues))

# -- Exercise 9: the bootstrap on Boston medv
Boston = isl_data("Boston")
medv = Boston["medv"].to_numpy(float)
ex9_mu, ex9_se = medv.mean(), medv.std(ddof=1) / np.sqrt(len(medv))
show("Exercise 9(a,b), mean and SE:", (round(ex9_mu, 4), round(ex9_se, 4)))   # 22.5328 0.4089
D9 = pd.DataFrame({"medv": medv})
stat = lambda f: (lambda D, idx: f(D["medv"].to_numpy()[idx]))      # noqa: E731
ex9_se_boot, _ = boot_se(stat(np.mean), D9, B=1000, seed=0)
ex9_ci_boot = (ex9_mu - 2 * ex9_se_boot, ex9_mu + 2 * ex9_se_boot)
ex9_ci_t = stats.t.interval(0.95, len(medv) - 1, loc=ex9_mu, scale=ex9_se)
show("Exercise 9(d), bootstrap and t intervals:", (np.round(ex9_ci_boot, 3), np.round(ex9_ci_t, 3)))
ex9_se_median, _ = boot_se(stat(np.median), D9, B=1000, seed=0)
ex9_q10 = np.percentile(medv, 10)
ex9_se_q10, _ = boot_se(stat(lambda v: np.percentile(v, 10)), D9, B=1000, seed=0)
show("Exercise 9(e-h), median, SE, 10th percentile, SE:",
     (np.median(medv), round(ex9_se_median, 4), ex9_q10, round(ex9_se_q10, 4)))

# -- key numbers, saved for the course's own records
KEY.update({"val_seed0": val_seed0, "val_seed3": val_seed3, "loocv": loocv.tolist(),
            "loocv_brute_d1": loocv_brute(X1, Y), "cv10": cv10.tolist(),
            "shuffle1": kfold_cv(1, one_split)[0], "shuffle10_mean": val10.mean(), "shuffle10_sd": val10.std(),
            "alpha_hat": alpha_func(Portfolio, range(100)), "alpha_se_boot": float(alpha_se),
            "lin_beta": lin_fit.params.tolist(), "lin_se_boot": se_boot_lin.tolist(),
            "lin_se_formula": se_formula_lin.tolist(), "lin_se_sandwich": se_sandwich_lin.tolist(),
            "quad_beta": quad_fit.params.tolist(), "quad_se_boot": se_boot_quad.tolist(),
            "quad_se_formula": se_formula_quad.tolist(), "quad_se_sandwich": se_sandwich_quad.tolist(),
            "ex2_mean": float(store.mean()), "ex5_two": ex5_two, "ex5_three": ex5_three,
            "ex6_formula": ex6_formula.tolist(), "ex6_boot": ex6_boot.tolist(), "ex7_p1": ex7_p1,
            "ex7_loocv": float(ex7_loocv), "ex8_loocv": ex8_loocv.tolist(), "ex8_pvalues": list(ex8_pvalues),
            "ex9": [ex9_mu, ex9_se, float(ex9_se_boot), float(np.median(medv)), float(ex9_se_median),
                    float(ex9_q10), float(ex9_se_q10), *ex9_ci_t]})
os.makedirs(os.path.join(HERE, "cache"), exist_ok=True)
with open(os.path.join(HERE, "cache", "ch05_lab_py.json"), "w") as f:
    json.dump(KEY, f, indent=1, default=float)
