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:
- Quadratic discriminant analysis (QDA)
- Linear discriminant analysis (LDA), and its connection to Fisher discriminant analysis (FDA)
- 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}^*\):
- 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\).
- 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*}\]
- 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.
- For \(k = 1, \ldots, K\), compute \[ d_k(\mathbf{x}^*) = \|\tilde{\mathbf{x}}^* - \tilde{\mu}_k\|^2 - 2\log \hat{\pi}_k. \]
- 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.