Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 218 / 4

LDA assumes $Y\in \{1,\dots ,L\}$ with prior probabilities ${\pi }_l>0$ andwhere the class means may differ but the nonsingular covariance matrix is common. Bayes' rule chooses the class maximizing $\log {\pi }_l+\log f_l(x)$. Cancelling terms common to every class gives the discriminantThe boundary between classes $l$ and $m$ is ${\delta }_l(x)={\delta }_m(x)$, an affine hyperplane with normal ${\Sigma }^{-1}({\mu }_l-{\mu }_m)$. Hence the Bayes rule $\arg {\max }_l{\delta }_l(x)$ is a linear classifier.

The fitted LDA rule replaces ${\pi }_l,{\mu }_l,\Sigma$ by class proportions, class sample means, and the pooled within-class covariance, then maximizes the resulting ${\hat{\delta }}_l(x)$. Means and covariances have unbounded sensitivity, so a gross outlier can substantially move every LDA boundary. A soft-margin linear support vector machine uses hinge loss; observations beyond the correctly classified margin cease contributing, though mislabeled or extreme points can still matter according to the penalty $C$. Thus the SVM is generally more robust to well-classified extremes, while neither method is automatically robust to adversarial outliers.

When $p>n$, the pooled within-class covariance has rank at most $n-L<p$, so it is singular and ordinary LDA is not defined. For every $\lambda >0$,is positive definite because $v^T{\hat{\Sigma }}_{\lambda }v\ge \lambda \Vert v{\Vert }^2>0$. Replacing the covariance by this matrix gives well-defined regularized LDA. Choose $\lambda$ for predictive performance by cross-validation.

Let $k$ be a positive-definite kernel with feature map $\Phi$ into a reproducing-kernel Hilbert space. Perform regularized LDA on $\Phi (x)$, replacing the within-class covariance operator $C$ by $C+\lambda I$ with $\lambda >0$, which is invertible. The representer property expresses all required inner products and discriminants through the Gram matrix $K_{ij}=k(x_i,x_j)$ and vectors $k(x_i,x)$. This is Kernel LDA. For a nonlinear kernel such as the Gaussian radial-basis kernel, its affine boundaries in feature space pull back to nonlinear boundaries in the original input space.