Leave-One-Out Error for Linear Discriminant Analysis

Why Leave-One-Out LDA Needs a Refit

A training observation is not an independent test case for the classifier fitted using that same observation: it helped determine the class means and pooled covariance used to classify it. Leave-one-out (LOO) assessment addresses this by deleting each observation in turn, fitting the classification rule to the remaining data, and predicting the deleted observation. For linear discriminant analysis (LDA), the refits have enough algebraic structure that some calculations can be updated exactly rather than repeated from scratch.

The key qualification is that an algebraic shortcut is exact only if it reproduces the entire specified training procedure. Updating the class means while leaving the covariance unchanged, for example, is not the same as refitting ordinary LDA. The pooled covariance, its degrees-of-freedom denominator, and any estimated class priors may also change.

The LDA Fit and Its Deletion Updates

Write \(n_h=\#\{i:g_i=h\}\), and suppose initially that every class has at least two observations. The class mean and within-class scatter for class \(h\) are $$ \bar x_h=\frac{1}{n_h}\sum_{i:g_i=h}x_i,\qquad W_h=\sum_{i:g_i=h}(x_i-\bar x_h)(x_i-\bar x_h)^\mathsf T. $$ The pooled within-class scatter is \(W=\sum_{h=1}^K W_h\). We use the usual pooled covariance estimate \(S=W/(n-K)\), assuming \(n>K\). For a positive-definite \(S\), the LDA score for class \(h\), with prior probability \(\pi_h>0\), is $$ \delta_h(x)=x^\mathsf T S^{-1}\bar x_h-\frac{1}{2}\bar x_h^\mathsf T S^{-1}\bar x_h+\log\pi_h. $$ The assigned class maximizes this score, with a fixed deterministic rule for ties.

Consider deleting \(x_i\) from its class \(h=g_i\), and put \(d=x_i-\bar x_h\). The other class means do not change. The deleted class mean does:

The corresponding scatter update is a rank-one downdate. The recentering step matters: after removing \(x_i\), the remaining observations are not generally centered at the old mean.

To prove the scatter identity, let \(r_j=x_j-\bar x_h\) for observations \(j\) in class \(h\). The residuals sum to zero, so the residuals of the remaining \(n_h-1\) observations sum to \(-d\). Their scatter about the old mean is \(W_h-dd^\mathsf T\). Recentring at their new mean subtracts the outer product of their residual sum divided by their number:

Only class \(h\) changes, giving the stated update for \(W\). After deletion there are \(n-1\) observations and still \(K\) represented classes, so the pooled covariance denominator is \((n-1)-K=n-K-1\), not \(n-K\). This proves the result. \(\square\)

When the Inverse Shortcut Is Exact

For many observations, directly inverting each refitted covariance can be wasteful. The Sherman–Morrison identity gives the inverse of a rank-one update. In this setting it is an exact computational shortcut, not an approximation, when its invertibility conditions hold.

For a direct verification, set \(u=W^{-1}d\), \(q=d^\mathsf T W^{-1}d\), and \(c=\alpha/(1-\alpha q)\). Multiplying the proposed inverse by \(W-\alpha dd^\mathsf T\) gives $$ (W-\alpha dd^\mathsf T)(W^{-1}+c uu^\mathsf T) =I+(c-\alpha-\alpha cq)du^\mathsf T. $$ Since \(c(1-\alpha q)=\alpha\), the coefficient \(c-\alpha-\alpha cq\) is zero. The product is therefore \(I\), proving the inverse formula. The pooled covariance relation follows by inverting \(S_{-i}=W_{-i}/(n-K-1)\). \(\square\)

To reproduce the LOO prediction, insert \(\bar x_{h,-i}\) for the deleted class mean, leave the other means unchanged, use \(S_{-i}^{-1}\) in every score, and use the priors prescribed by the fitting procedure. For fixed externally specified priors, the \(\pi_h\) values remain fixed. If priors are estimated as the training class proportions, they must be updated too: after deletion, they are \((n_h-1)/(n-1)\) for class \(h\) and \(n_g/(n-1)\) for each \(g\ne h\). In either case, the shortcut matches refitting only when every changed ingredient is accounted for.

When Shortcuts Fail—and Why LOO Matters

The update formulas give computational savings, but do not remove the conditions required by the classifier. If \(W\) or \(W_{-i}\) is singular, the ordinary inverse-based LDA score is not defined. The Sherman–Morrison denominator then cannot be used as if it were a valid inverse. One must instead apply the specified alternative fitting rule, such as a stated regularization method, and ensure its deletion update matches that rule. Deleting an observation from a class of size one removes that class entirely; the formulas above do not apply, and the intended prediction problem needs an explicit convention for that case.

A further pitfall is to update means but keep the full-sample covariance, or to update \(W\) but retain the old denominator \(n-K\). Both produce a different classifier from the ordinary refit. Likewise, if priors are estimated from class counts, leaving them at their full-sample values changes the procedure. A valid shortcut must reproduce all these choices, as well as any data-dependent preprocessing or fitting decisions that are part of the classifier.

LOO error estimates the performance of the specified training procedure when trained on \(n-1\) observations, using each observation once as a held-out case. Its value is not the apparent training error, and it is not a guarantee of the risk for a model trained on all \(n\) observations. The held-out predictions also share much of their training data, so the individual error indicators are dependent. These are properties of the assessment, not reasons to alter the refitting calculation. The earlier material on classification risk distinguishes such empirical error estimates from the underlying risk being estimated.