7.1 Discriminant Analysis

Discriminant analysis builds a classifier by modeling how the features are distributed within each class, then applying Bayes’ theorem to recover \(P(Y = k \mid X = x)\). The three standard variants differ mainly in how they model \(X \mid Y = k\), and therefore in the shape of the resulting boundary:

  1. Quadratic discriminant analysis (QDA)
  2. Linear discriminant analysis (LDA), and its connection to Fisher discriminant analysis (FDA)
  3. Naive Bayes

All three start from the factorization \(P(x, y) = P(x \mid y)\, P(y)\). We estimate

  • \(f_k(x) = P(X = x \mid Y = k)\), the class-conditional density of the features, and
  • \(\pi_k = P(Y = k)\), the class prior,

and then flip the conditioning.

Bayes’ theorem for classification

\[\begin{align*} P(Y = k \mid X = x) &= \frac{P(X = x \mid Y = k)\, P(Y = k)}{P(X = x)} = \frac{\pi_k \, f_k(x)}{P(X = x)} \propto \pi_k \, f_k(x). \end{align*}\]

  • \(f_k(x)\): class-conditional density of \(X \mid Y = k\)
  • \(\pi_k = P(Y = k)\): prior probability of class \(k\)

The Bayes classifier therefore has the equivalent form \[ f(x) = \arg\max_k \; \pi_k f_k(x) = \arg\max_k \bigl[\log \pi_k + \log f_k(x)\bigr]. \] To implement it we only need estimates of \(\pi_k\) and \(f_k\).

7.1.1 Quadratic Discriminant Analysis

Assume that, given \(Y = k\), the feature vector is multivariate normal, \(\mathbf{x} \sim N_p(\mu_k, \Sigma_k)\), with class-specific mean \(\mu_k\) and class-specific covariance \(\Sigma_k\). The density is \[ f_k(\mathbf{x}) = (2\pi)^{-p/2} \, |\Sigma_k|^{-1/2} \exp\Bigl\{ -\tfrac12 (\mathbf{x} - \mu_k)^\top \Sigma_k^{-1} (\mathbf{x} - \mu_k) \Bigr\}. \] The quadratic form in the exponent is \[ (\mathbf{x} - \mu_k)^\top \Sigma_k^{-1} (\mathbf{x} - \mu_k) = \sum_{j=1}^{p} \sum_{\ell=1}^{p} \theta_{k,j\ell}\, (x_j - \mu_{k,j})(x_\ell - \mu_{k,\ell}), \] where \(\theta_{k,j\ell}\) are the entries of \(\Sigma_k^{-1}\). Dropping terms that do not depend on \(k\), \[ P(Y = k \mid \mathbf{x}) \propto \pi_k f_k(\mathbf{x}) \propto e^{-d_k(\mathbf{x})/2}, \] where \[\begin{align*} d_k(\mathbf{x}) &= (\mathbf{x} - \mu_k)^\top \Sigma_k^{-1} (\mathbf{x} - \mu_k) + \log|\Sigma_k| - 2\log \pi_k. \end{align*}\] The first term is the Mahalanobis distance from \(\mathbf{x}\) to \(\mu_k\). We assign \(\mathbf{x}\) to the class with the smallest \(d_k(\mathbf{x})\). Because \(d_k\) is a quadratic function of \(\mathbf{x}\), the decision boundaries are quadratic, which is why the method is called quadratic discriminant analysis (QDA).

In practice we replace the unknown parameters by sample estimates:

  • Prior and mean: \[ \hat{\pi}_k = \frac{n_k}{n}, \qquad \hat{\mu}_k = \frac{1}{n_k} \sum_{i: y_i = k} \mathbf{x}_i, \qquad k = 1, \ldots, K. \]
  • Class covariance: \[ \hat{\Sigma}_k = \frac{1}{n_k - 1} \sum_{i: y_i = k} (\mathbf{x}_i - \hat{\mu}_k)(\mathbf{x}_i - \hat{\mu}_k)^\top. \]

Remark. If \(\hat{\Sigma}_k\) is singular (common when \(p\) is large relative to \(n_k\)), replace \(\hat{\Sigma}_k^{-1}\) by \((\hat{\Sigma}_k + \eta I_p)^{-1}\) for a small \(\eta > 0\), or use a generalized inverse. This is a simple form of regularization.

7.1.2 Linear Discriminant Analysis

Now assume a common covariance, \(\Sigma_k = \Sigma\) for all \(k\). Then \[ d_k(\mathbf{x}) = (\mathbf{x} - \mu_k)^\top \Sigma^{-1} (\mathbf{x} - \mu_k) + \log|\Sigma| - 2\log \pi_k. \] Expanding the quadratic form, \[ (\mathbf{x} - \mu_k)^\top \Sigma^{-1} (\mathbf{x} - \mu_k) = \mathbf{x}^\top \Sigma^{-1} \mathbf{x} - 2\mathbf{x}^\top \Sigma^{-1} \mu_k + \mu_k^\top \Sigma^{-1} \mu_k. \] The term \(\mathbf{x}^\top \Sigma^{-1} \mathbf{x}\) does not depend on \(k\), nor does \(\log|\Sigma|\). What remains is a linear function of \(\mathbf{x}\), so the decision boundaries are hyperplanes. This is linear discriminant analysis (LDA).

The shared covariance is estimated by the pooled sample covariance \[ \hat{\Sigma} = \frac{1}{n - K} \sum_{k=1}^{K} \sum_{i: y_i = k} (\mathbf{x}_i - \hat{\mu}_k)(\mathbf{x}_i - \hat{\mu}_k)^\top. \]

Remark. If \(\hat{\Sigma}\) is singular, use \((\hat{\Sigma} + \eta I_p)^{-1}\) or a generalized inverse. For example, if the SVD is \(\hat{\Sigma} = U \operatorname{diag}(d_1, \ldots, d_r, 0, \ldots, 0) U^\top\), invert only the positive singular values: \[ \hat{\Sigma}^{+} = U \operatorname{diag}(d_1^{-1}, \ldots, d_r^{-1}, 0, \ldots, 0) U^\top. \]

7.1.3 Reduced-Rank LDA

As a further simplification, take \(\Sigma = I_p\). The LDA discriminant reduces to \[ d_k(\mathbf{x}) = \|\mathbf{x} - \mu_k\|^2 - 2\log \pi_k. \] Only the squared Euclidean distance from \(\mathbf{x}\) to the class center \(\mu_k\) depends on the features.

This distance can be computed in a subspace of dimension at most \(K-1\). In that sense, LDA is a dimension-reduction method: it automatically collapses \(p\) coordinates to \(K-1\) coordinates without changing the classification rule (under \(\Sigma = I_p\)).

Without loss of generality, translate the data so that the grand mean \(\bar{\mu}\) is at the origin. The \(K\) class means then lie in a subspace \(\mathcal{A}\) of dimension at most \(K-1\). Decompose any \(\mathbf{x} \in \mathbb{R}^p\) as \[ \mathbf{x} = \mathbf{x}_1 + \mathbf{x}_2, \qquad \mathbf{x}_1 \in \mathcal{A}, \quad \mathbf{x}_2 \in \mathcal{A}^\perp. \] In matrix form, if \(B = (\mu_1, \ldots, \mu_{K-1})\) and \(H = B(B^\top B)^{-1} B^\top\) is the orthogonal projector onto \(\mathcal{A}\), then \(\mathbf{x}_1 = H\mathbf{x}\) and \(\mathbf{x}_2 = \mathbf{x} - \mathbf{x}_1\). Orthogonality gives \[ \|\mathbf{x}\|^2 = \|\mathbf{x}_1\|^2 + \|\mathbf{x}_2\|^2, \] and, because each \(\mu_k\) already lies in \(\mathcal{A}\), \[ \|\mathbf{x} - \mu_k\|^2 = \|\mathbf{x}_1 - \mu_k\|^2 + \|\mathbf{x}_2\|^2. \] The residual length \(\|\mathbf{x}_2\|^2\) does not depend on \(k\), so \[ d_k(\mathbf{x}) = \|\mathbf{x}_1 - \mu_k\|^2 - 2\log \pi_k + \text{constant}. \] Classification using the original \(\mathbf{x}\) is identical to classification using only its projection \(\mathbf{x}_1\) onto the class-mean subspace.

When \(\Sigma \ne I_p\), first whiten the features. If \(\Sigma = U D^2 U^\top\) is an SVD, set \[ \Sigma^{-1/2} := U D^{-1} U^\top, \qquad \tilde{\mathbf{x}} = \Sigma^{-1/2} \mathbf{x}. \] Then \(\operatorname{Cov}(\tilde{\mathbf{x}}) = I_p\): \[\begin{align*} \operatorname{Cov}(\tilde{\mathbf{x}}) &= \Sigma^{-1/2}\, \Sigma\, (\Sigma^{-1/2})^\top = U D^{-1} U^\top \, U D^2 U^\top \, U D^{-1} U^\top = I_p. \end{align*}\] (The one-dimensional analogue is dividing a scalar by its standard deviation.) After whitening, apply the \(\Sigma = I_p\) argument to \(\tilde{\mathbf{x}}\) and the whitened means \(\tilde{\mu}_k = \Sigma^{-1/2} \mu_k\).

Remark. \(\Sigma^{-1/2}\) is symmetric and satisfies \(\Sigma^{-1/2}\Sigma^{-1/2} = \Sigma^{-1}\).

Summary of reduced-rank LDA

Training. From \(\{(x_i, y_i)\}_{i=1}^{n}\), compute \((\hat{\pi}_k, \hat{\mu}_k)_{k=1}^{K}\) and \(\hat{\Sigma}\).

Prediction at a test point \(\mathbf{x}^*\):

  1. Compute a square-root inverse \(A = \hat{\Sigma}^{-1/2}\) from the SVD \(\hat{\Sigma} = U D^2 U^\top\), \(A = U D^{-1} U^\top\).
  2. Form the whitened, centered class means and the projector onto their span: \[\begin{align*} B &= \bigl[A(\hat{\mu}_1 - \bar{\hat{\mu}}),\; \ldots,\; A(\hat{\mu}_{K-1} - \bar{\hat{\mu}})\bigr], \\ H &= B(B^\top B)^{-1} B^\top. \end{align*}\]
  3. Project the whitened test point: \(\tilde{\mathbf{x}}^* = H A \mathbf{x}^*\). Let \(\tilde{\mu}_k = H A \hat{\mu}_k\) be the corresponding projected means.
  4. For \(k = 1, \ldots, K\), compute \[ d_k(\mathbf{x}^*) = \|\tilde{\mathbf{x}}^* - \tilde{\mu}_k\|^2 - 2\log \hat{\pi}_k. \]
  5. Predict \(\arg\min_k d_k(\mathbf{x}^*)\).

When \(p \ge K\), LDA therefore lives in a \((K-1)\)-dimensional subspace (a single line, in the binary case). The same subspace appears in Fisher discriminant analysis (FDA), derived from a different criterion.

Risk of overfitting

Each of the \(K-1\) directions is a linear combination of the original \(p\) coordinates, with weights estimated from the training sample. If \(p\) is large, those weights can lock onto noise and produce excellent training separation that does not reproduce on test data.