The Jackknife: Motivation

The bootstrap resamples with replacement and uses Monte Carlo. The jackknife leaves out one observation at a time, deterministically. It estimates bias and variance, it measures the influence of each observation, and those influence values are what BCa needs for its acceleration.

Historical Context (Quenouille, 1949; Tukey, 1958). Originally developed for bias reduction, later extended to variance estimation.

• Bootstrap: resamples with replacement (stochastic, \(B\) replications)
• Jackknife: leaves out one observation at a time (deterministic, exactly \(n\) calculations)

Advantages over the bootstrap. Deterministic (same result every time), computationally simpler, and theoretical analysis is often easier.

Notation and Bias Estimation

Notation.

• Original estimate: \(\hat{\theta}\), computed from \(X_1, \ldots, X_n\)
• Leave-one-out estimate: \(\hat{\theta}_{(-i)}\), the same estimate computed without \(X_i\)
• Leave-one-out mean: \(\hat{\theta}_{(\cdot)} = \frac{1}{n}\sum_{i=1}^n \hat{\theta}_{(-i)}\)

Jackknife bias estimate.

\[\widehat{\text{Bias}}_{jack} = (n-1)(\hat{\theta}_{(\cdot)} - \hat{\theta})\]

Bias-corrected estimate.

\[\tilde{\theta}_{jack} = \hat{\theta} - \widehat{\text{Bias}}_{jack} = n\hat{\theta} - (n-1)\hat{\theta}_{(\cdot)}\]

Why the Factor \(n - 1\): the \(\bar X^2\) Example

Consider \(\hat{\theta} = \bar{X}^2\) estimating \(\theta = \mu^2\). Since \(\E[\bar{X}^2] = \mu^2 + \sigma^2/n\), the bias is \(\sigma^2/n\).

Each leave-one-out mean satisfies \(\bar{X}_{(-i)} = \bar{X} - \frac{X_i - \bar{X}}{n - 1}\), so \(\bar{X}_{(-i)}^2 = \bar{X}^2 - \frac{2\bar{X}(X_i - \bar{X})}{n-1} + \frac{(X_i - \bar{X})^2}{(n-1)^2}\). Averaging over \(i = 1, \ldots, n\): the middle term vanishes because \(\sum_i (X_i - \bar{X}) = 0\), and the last term averages to \(S^2/(n(n-1))\) where \(S^2 = \frac{1}{n-1}\sum_i (X_i - \bar{X})^2\), so

\[\hat{\theta}_{(\cdot)} = \frac{1}{n}\sum_{i=1}^n \bar{X}_{(-i)}^2 = \bar{X}^2 + \frac{S^2}{n(n-1)}.\]

Thus \(\widehat{\text{Bias}}_{jack} = (n-1)\bigl(\hat\theta_{(\cdot)} - \hat\theta\bigr) = S^2/n\), and the corrected estimate \(\bar{X}^2 - S^2/n\) is exactly unbiased for \(\mu^2\).

where \(\mu = \E_F X_1\); \(\sigma^2 = \Var_F X_1\); \(\bar X_{(-i)}\): the sample mean without \(X_i\).

Pseudo-Values and Variance Estimation

Pseudo-values. \(\tilde{\theta}_i = n\hat{\theta} - (n-1)\hat{\theta}_{(-i)}\). These can be treated as approximately independent observations; their mean \(\bar{\tilde\theta}\) is the bias-corrected estimate \(\tilde\theta_{jack}\).

Direct formula.

\[\widehat{\Var}_{jack}(\hat{\theta}) = \frac{n-1}{n} \sum_{i=1}^n (\hat{\theta}_{(-i)} - \hat{\theta}_{(\cdot)})^2\]

Via pseudo-values.

\[\widehat{\Var}_{jack}(\hat{\theta}) = \frac{1}{n(n-1)} \sum_{i=1}^n (\tilde{\theta}_i - \bar{\tilde{\theta}})^2\]

where \(\hat\theta_{(-i)}\): the estimate without \(X_i\); \(\hat\theta_{(\cdot)}\): the mean of the \(\hat\theta_{(-i)}\).

The Jackknife Theorem

Theorem. If \(\E[\hat{\theta}] = \theta + a/n + b/n^2 + O(n^{-3})\) and \(\Var(\hat{\theta}) = \sigma^2/n + O(n^{-2})\), then the jackknife removes the \(O(n^{-1})\) bias term, and \(\E[\widehat{\Var}_{jack}(\hat{\theta})] = \Var(\hat{\theta}) + O(n^{-2})\).

where \(a\), \(b\), \(\sigma^2\): constants that do not depend on \(n\).

Essentially, the jackknife variance works whenever the statistic is smooth enough for a Taylor expansion in \(1/n\).

The Empirical Influence Function

Empirical influence function. The change in \(\hat\theta\) when \(X_i\) is removed, scaled by \(n - 1\):

\[\widehat{\text{IF}}_i = (n-1)(\hat{\theta} - \hat{\theta}_{(-i)})\]

where \(\hat\theta_{(-i)}\): the estimate without \(X_i\). It is positive when \(X_i\) pulls the estimate up.

The pseudo-value is \(\tilde\theta_i = \hat\theta + \widehat{\text{IF}}_i\).

Connection to jackknife variance. \(\widehat{\Var}_{jack}(\hat{\theta}) = \frac{1}{n(n-1)} \sum_{i=1}^n (\widehat{\text{IF}}_i - \overline{\text{IF}})^2\), where \(\overline{\text{IF}} = -\widehat{\text{Bias}}_{jack}\). When the influence values sum to zero (linear statistics), this simplifies to \(\frac{1}{n(n-1)} \sum_i \widehat{\text{IF}}_i^2\).

Influence on the Law-School Correlation

The law-school data: \(n = 15\) schools, \(\hat\theta = 0.776\). School 1 has the largest influence value, \(\widehat{\text{IF}} = -1.63\). Deleting it moves the correlation to \(0.893\). Jackknife SE: \(0.143\), jackknife bias: \(-0.0065\).

Leave-One-Out in Regression

In a linear model \(y_i = \mathbf{x}_i^\top\boldsymbol\beta + \varepsilon_i\) with least-squares estimate \(\hat{\boldsymbol\beta}\), one fit gives all \(n\) leave-one-out fits:

\[\hat{\boldsymbol\beta}_{(-i)} = \hat{\boldsymbol\beta} - \frac{(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{x}_i\, e_i}{1 - h_{ii}}, \qquad y_i - \mathbf{x}_i^\top\hat{\boldsymbol\beta}_{(-i)} = \frac{e_i}{1 - h_{ii}}\]

where \(\mathbf{X}\): the \(n \times p\) design matrix, rows \(\mathbf{x}_i^\top\); \(\hat{\boldsymbol\beta}_{(-i)}\): the estimate without observation \(i\); \(e_i = y_i - \mathbf{x}_i^\top\hat{\boldsymbol\beta}\): the residual; \(h_{ii} = \mathbf{x}_i^\top(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{x}_i\): the leverage.

Essentially, an observation moves the fit when its residual is large and its leverage is high.

The Jackknife in Applied Regression

where \(\hat{\mathbf{y}}_{(-i)} = \mathbf{X}\hat{\boldsymbol\beta}_{(-i)}\); \(\hat\sigma^2\): the residual variance estimate; \(p\): the number of coefficients.

The empirical influence value of observation \(i\) is \((n-1)\) times its DFBETA. The jackknife variance is HC3 with the leave-one-out estimates centered at their mean, times \((n-1)/n\).

The Law-School Regression

GPA regressed on LSAT for the \(n = 15\) schools. The slope is \(0.452\) GPA points per 100 LSAT points.

School 1 has the largest Cook’s distance, \(0.36\): residual \(0.41\), leverage \(0.09\). Without it the slope is \(0.497\).

School 11 moves the slope most: residual \(-0.21\), leverage \(0.18\). Without it the slope is \(0.508\).

Failure for the Median

• The jackknife variance is inconsistent for the median.
• \(n = 2m\): delete an observation of rank at most \(m\) and the median is \(X_{(m+1)}\); delete any other and it is \(X_{(m)}\). Two values only (\(n\) odd: three).
• So \(\widehat{\text{SE}}_{jack} = \sqrt{n-1}\,(X_{(m+1)} - X_{(m)})/2\): one spacing, and a single spacing never settles as \(n\) grows.
• Delete-\(d\) jackknife. Leave out \(d\) at a time, \(\binom{n}{d}\) subsets. Consistent for quantiles when \(\sqrt{n}/d \to 0\) and \(n - d \to \infty\) (Shao and Wu, 1989); costly for \(d > 1\).

where \(X_{(k)}\): the \(k\)th smallest observation.

Leave-One-Out Medians Take Two Values

• Left: one \(\Exp(1)\) sample, \(n = 20\). The 20 leave-one-out medians take 2 values: red when the deleted observation has rank at most 10, blue otherwise.
• Right: \(2000\) such samples, jackknife SE over true SE. For the mean the ratio stays near \(1\) (SD \(0.29\)); for the median it scatters (SD \(0.99\)).
• In the limit the median’s ratio is \(\Exp(1)\): mean \(1\), standard deviation \(1\) (Efron, 1982). It never settles.

Jackknife as a Linear Approximation to the Bootstrap

• A smooth statistic is close to an average of one term per observation: its linear approximation.
• Result (Efron, 1982). The jackknife variance is, up to the factor \(n/(n-1)\), the bootstrap variance of that linear approximation (Efron and Tibshirani, 1993, Ch. 20).
• The jackknife captures the linear term; the bootstrap captures all terms.

The Jackknife Works for Smooth Statistics

• Deterministic, exactly \(n\) refits, estimates both bias and variance.
• Works for smooth statistics (a Taylor expansion in \(1/n\) must exist); fails for the median.
• The empirical influence values say how much each observation matters, and they feed BCa.
• In regression one fit gives every leave-one-out fit: DFBETA, Cook’s distance, and HC3 are jackknife quantities.

Bias Correction: \(\hat z_0\)

• Recall the percentile interval? First-order accurate, no correction for bias or skewness.
• BCa corrects both, and the jackknife supplies one of the two corrections.

\[\hat{z}_0 = \Phi^{-1}\!\left(\frac{\#\{\hat\theta^{*(b)} < \hat\theta\}}{B}\right)\]

where \(\Phi^{-1}\): the standard normal quantile function; \(\hat\theta^{*(b)}\): the estimate on resample \(b\), \(b = 1, \ldots, B\).

• \(\hat z_0\): the normal quantile of the proportion of bootstrap estimates below \(\hat\theta\).
• \(\hat z_0 = 0\) when \(\hat\theta\) sits at the median of its bootstrap distribution; otherwise it measures the median bias on the normal scale.

Acceleration: \(\hat a\) from the Jackknife

\[\hat{a} = \frac{\sum_{i=1}^n (\hat{\theta}_{(\cdot)} - \hat{\theta}_{(-i)})^3}{6\left[\sum_{i=1}^n (\hat{\theta}_{(\cdot)} - \hat{\theta}_{(-i)})^2\right]^{3/2}}\]

where \(\hat\theta_{(-i)}\): the estimate without \(X_i\); \(\hat\theta_{(\cdot)}\): the mean of the \(n\) leave-one-out estimates; \(\widehat{\text{IF}}_i = (n-1)(\hat\theta - \hat\theta_{(-i)})\).

• \(\hat a\) is the skewness of the influence values \(\widehat{\text{IF}}_i\) divided by \(6\sqrt{n}\).
• It measures how fast the standard error of \(\hat\theta\) changes with \(\theta\).
• A skewed sampling distribution makes the percentile method’s symmetric cuts wrong; \(\hat a\) moves them.

The BCa Formula

Adjusted percentiles. For a \(1-\alpha\) interval, define

\[\alpha_1 = \Phi\!\left(\hat{z}_0 + \frac{\hat{z}_0 + z_{\alpha/2}}{1 - \hat{a}(\hat{z}_0 + z_{\alpha/2})}\right), \qquad \alpha_2 = \Phi\!\left(\hat{z}_0 + \frac{\hat{z}_0 + z_{1-\alpha/2}}{1 - \hat{a}(\hat{z}_0 + z_{1-\alpha/2})}\right)\]

where \(\Phi\) is the standard normal CDF and \(z_\alpha = \Phi^{-1}(\alpha)\).

The interval.

\[\text{CI}_{\text{BCa}} = \left[\hat\theta^*_{(\alpha_1)},\; \hat\theta^*_{(\alpha_2)}\right]\]

where \(\hat\theta^*_{(\alpha)}\) is the \(\alpha\)-quantile of \(\{\hat\theta^{*(1)}, \ldots, \hat\theta^{*(B)}\}\).

BCa on the Law-School Data

• Histogram: \(B = 5000\) bootstrap correlations. Dark line \(\hat\theta\); dashed blue the percentile cuts at 2.5% and 97.5%; red the BCa cuts.
• Corrections \(\hat z_0 = -0.130\), \(\hat a = -0.076\) move the cuts to \(\alpha_1 = 0.004\) and \(\alpha_2 = 0.930\): both left, toward the long tail.
• Percentile interval (0.460, 0.963); BCa interval (0.299, 0.940).

Coverage for the Law-School Correlation

• Samples of \(n = 15\) drawn from the 82 schools (\(\theta = 0.760\)), \(1000\) samples, \(B = 1000\), nominal 95%; Monte Carlo SE about \(0.009\).
• Nothing reaches 95% at \(n = 15\), Fisher’s \(z\) included.
• The percentile interval misses on one side: \(7.7\%\) of its intervals sit entirely above \(\theta\), against 2.5% nominal. BCa pushes left and cuts that to \(5.5\%\).
• BCa is the best bootstrap interval here and still short of nominal.

where Fisher’s \(z\): \(\tanh\bigl(\operatorname{artanh}\hat\theta \pm z_{0.975}/\sqrt{n-3}\bigr)\), the normal-theory interval for a correlation.

What BCa Guarantees

• Theorem (Efron, 1987). Under regularity conditions, BCa intervals are second-order accurate: one-sided coverage error \(O(n^{-1})\).
• They respect monotone transformations and adapt to bias and skewness automatically.
• Cost. \(B\) bootstrap samples plus \(n\) leave-one-out fits for \(\hat a\): \(B + n\) operations.

When to Use BCa

• Avoid for very small samples (\(n < 20\)) and non-smooth statistics.
• Median with \(n\) even: the two leave-one-out values are symmetric about their mean, so \(\hat a = 0\) exactly (this week’s lab).
• The law-school data sit below the threshold at \(n = 15\); the four intervals disagree there.
• Alternatives. Bootstrap-\(t\) for better one-sided coverage; percentile for simplicity.

BCa Corrects the Percentile Interval

• BCa fixes two defects of the percentile interval: median bias (\(\hat z_0\)) and skewness (\(\hat a\)).
• \(\hat a\) comes from the jackknife influence values: the jackknife does double duty, variance and BCa.
• With \(\hat z_0 = \hat a = 0\) BCa is the percentile interval; the correction matters when the sampling distribution is skewed or the estimator is biased.

The Prediction Error Problem

• Leaving one observation out also estimates prediction error: same operation, new purpose.
• Training error: \(\frac{1}{n}\sum_{i=1}^n L(y_i, \hat{f}(x_i))\). Optimistic: the model saw these data.
• True prediction error: \(\E_{(X,Y)}[L(Y, \hat{f}(X))]\). Unknown: it needs data the model has not seen.

where \(\hat f\): a model trained on the data \(\mathcal{D}_n = \{(x_i, y_i)\}_{i=1}^n\); \(L\): the loss function; \((X, Y)\): a new observation, independent of \(\mathcal{D}_n\).

What Cross-Validation Estimates

For squared error loss at a fixed \(x\):

\[\E\bigl[(Y - \hat{f}(x))^2 \mid X = x\bigr] = \sigma^2 + \text{Bias}^2(\hat{f}(x)) + \Var(\hat{f}(x))\]

where \(f(x) = \E[Y \mid X = x]\): the true regression function; \(\E\) and \(\Var\) of \(\hat f(x)\): over training samples.

• \(\sigma^2 = \Var(Y \mid X = x)\), the irreducible error: noise in \(Y\) at that \(x\). No model removes it.
• \(\text{Bias}^2(\hat{f}(x)) = (\E[\hat{f}(x)] - f(x))^2\), the bias: how far the average fit sits from the truth. The price of a model family too simple for \(f\).
• \(\Var(\hat{f}(x)) = \E[(\hat{f}(x) - \E[\hat{f}(x)])^2]\), the variance: how much the fit moves from one training set to the next. The price of flexibility.
• A more flexible model trades bias for variance. A new observation pays the sum.
• CV estimates that sum, averaged over \(x\), for a model trained on \(n(1 - 1/k)\) observations: pessimistic for the model trained on all \(n\), less so as \(k\) grows.

The Hat-Matrix Shortcut for Linear Models

• Recall the deleted residual \(e_i/(1 - h_{ii})\) from the jackknife in regression? LOOCV for a linear model is its mean square.

\[\widehat{\text{Err}}_{LOO} = \frac{1}{n}\sum_{i=1}^n \left(\frac{y_i - \hat{y}_i}{1 - h_{ii}}\right)^2\]

where \(\hat{\mathbf{y}} = \mathbf{H}\mathbf{y}\) with \(\mathbf{H} = \mathbf{X}(\mathbf{X}^\top\mathbf{X})^{-1}\mathbf{X}^\top\) the hat matrix; \(\mathbf{X}\): the \(n \times p\) design matrix; \(\mathbf{y}\): the responses; \(\hat y_i\): the fitted value from the full fit; \(h_{ii}\): the \(i\)th diagonal entry of \(\mathbf{H}\).

• Removing observation \(i\) inflates its residual by exactly \(1/(1 - h_{ii})\).
• No refitting: one model fit gives all \(n\) leave-one-out errors.

One Fit in Place of \(n\)

• Seconds per LOOCV computation against \(n\) on log scales: red the \(n\) refits, blue one fit plus the leverages.
• The two give the same number: largest difference over the five \(n\) is \(4.4 \times 10^{-16}\).
• At \(n = 1600\) the refits take about \(836\) times as long, and the gap widens with \(n\).

GCV and the Connection to AIC

• Generalized cross-validation (GCV). Replace each \(h_{ii}\) by its average \(\text{tr}(\mathbf{H})/n = p/n\):

\[\widehat{\text{Err}}_{GCV} = \frac{1}{n}\sum_{i=1}^n \left(\frac{y_i - \hat{y}_i}{1 - p/n}\right)^2 = \frac{\text{RSS}/n}{(1 - p/n)^2}\]

where \(p\): the number of fitted coefficients, intercept included; \(\text{RSS} = \sum_{i=1}^n (y_i - \hat y_i)^2\); \(\mathbf{H}\): the hat matrix.

• Connection to AIC. For linear models with Gaussian errors, \(\text{AIC} \approx n \log \widehat{\text{Err}}_{GCV} + \text{constant}\).
• The link: \(\log \text{GCV} = \log(\text{RSS}/n) - 2\log(1 - p/n) \approx \log(\text{RSS}/n) + 2p/n\); times \(n\) this is \(n\log(\text{RSS}/n) + 2p\), AIC up to a constant.

The Polynomial-Degree Problem

• Simulated data: \(n = 100\) points with \(x \sim \Uniform(0, 1)\) and \(y = \sin(2\pi x) + \varepsilon\), \(\varepsilon \sim \Normal(0, 0.3^2)\).
• Candidates: one model per degree \(d = 1, \ldots, 12\), fitted by least squares:

\[\mathcal{M}_d: \quad y_i = \beta_0 + \beta_1 x_i + \beta_2 x_i^2 + \cdots + \beta_d x_i^d + \varepsilon_i, \qquad \hat f_d(x) = \sum_{j=0}^{d} \hat\beta_j x^j\]

where \(d\): the degree of the polynomial; \(\hat\beta_0, \ldots, \hat\beta_d\): the least-squares estimates, \(p = d + 1\) coefficients; \(\hat f_d\): the fitted curve for degree \(d\).

• The question: which degree predicts a new \(y\) best?
• Why simulated: the truth is a smooth curve that is no polynomial, so no degree is “right” and training error cannot decide.
• Method: \(10\)-fold CV for each degree, with a standard error from the \(10\) fold errors; report \(d_{\min}\), the degree with the smallest CV error, and \(d_{1\mathrm{SE}}\), the smallest degree within one SE of it (the one-SE rule).

Choosing a Polynomial Degree

• Mean squared error against degree: blue the \(10\)-fold CV error with \(\pm 1\) SE bars, orange the training error; dashed lines mark \(d_{\min}\) and \(d_{1\mathrm{SE}}\).
• CV error is smallest at degree \(4\); the one-SE rule selects degree \(3\).
• Training error keeps falling and would choose degree \(12\).

where \(d_{\min}\): the degree with the smallest CV error; \(d_{1\mathrm{SE}}\): the smallest degree whose CV error is within one SE of that minimum.

Nested Cross-Validation

• Nested CV separates model selection from model evaluation.
• Inner loop: choose the model (hyperparameters) by CV on the training part of each outer fold.
• Outer loop: assess the chosen model on the held-out outer fold.
• Without nesting, the data that chose the model also evaluate it, and the estimate is optimistic.

Punchlines, and What Comes Next

• The jackknife is the bootstrap’s deterministic, linear cousin: \(n\) leave-one-out calculations, no random numbers, and it removes the \(O(n^{-1})\) bias term of a smooth statistic.
• The jackknife’s influence values feed directly into BCa, which corrects both bias and skewness of the percentile interval and is the recommended bootstrap interval for smooth statistics.
• Cross-validation repurposes the same leave-one-out idea for prediction: training error is optimistic, and CV estimates the error on data the model has not seen, at the cost of variance.
• The hat-matrix shortcut turns LOOCV for linear models from \(n\) fits into one.

When \(F\) is unknown, the sample is all we have. Resampling from it, with replacement, without one observation, or in folds, gives standard errors, bias corrections, intervals, and an estimate of prediction error. Each method perturbs the data and watches what the statistic does.