Gaussian Discriminant Analysis (GDA)

A generative learning algorithm that models class-conditional distributions as multivariate Gaussians.

Key Assumptions

1. Class-conditional distributions are multivariate Gaussian: $P(x|y) \sim \mathcal{N}(\mu_y, \Sigma)$
2. Shared covariance matrix: Both classes use the same $\Sigma$ (Quadratic Discriminant Analysis (QDA) uses different $\Sigma_y$ per class)
3. Covariance matrix properties: $\Sigma$ must be symmetric and positive semi-definite (PSD):
   • Symmetric: $\Sigma = \Sigma^T$
   • PSD: $\mathbf{z}^T\Sigma\mathbf{z} \geq 0$ for all $\mathbf{z}$, or equivalently, all eigenvalues $\lambda_i \geq 0$
   • For GDA to work properly, $\Sigma$ should be positive definite (PD) (invertible)

Model

For binary classification $y \in \{0, 1\}$:

$$\begin{align} y &\sim \text{Bernoulli}(\phi) \\ x|y=0 &\sim \mathcal{N}(\mu_0, \Sigma) \\ x|y=1 &\sim \mathcal{N}(\mu_1, \Sigma) \end{align}$$

Parameters: $\phi, \mu_0, \mu_1, \Sigma$

Maximum Likelihood Estimates

$$\begin{align} \phi &= \frac{1}{m} \sum_{i=1}^{m} \mathbb{1}\{y^{(i)}=1\} \\ \mu_0 &= \frac{\sum_{i=1}^{m} \mathbb{1}\{y^{(i)}=0\} x^{(i)}}{\sum_{i=1}^{m} \mathbb{1}\{y^{(i)}=0\}} \\ \mu_1 &= \frac{\sum_{i=1}^{m} \mathbb{1}\{y^{(i)}=1\} x^{(i)}}{\sum_{i=1}^{m} \mathbb{1}\{y^{(i)}=1\}} \\ \Sigma &= \frac{1}{m} \sum_{i=1}^{m} (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T \end{align}$$

Decision Boundary

GDA produces a linear decision boundary (when $\Sigma_0 = \Sigma_1$).

The decision boundary is given by:

$$(\mu_1 - \mu_0)^T \Sigma^{-1} x = \frac{1}{2}(\mu_1^T \Sigma^{-1} \mu_1 - \mu_0^T \Sigma^{-1} \mu_0) + \log\frac{1-\phi}{\phi}$$

This is linear in $x$ (affine function), making it the same form as logistic regression.

GDA vs Logistic Regression

Aspect	GDA	Logistic Regression (LR)
Type	Generative	Discriminative
Assumptions	Strong (Gaussian distributions)	Weak (only needs linear decision boundary)
Data Efficiency	More efficient when assumptions hold	Needs more data
Robustness	Sensitive to assumption violations	More robust to distribution violations
Decision Boundary	Linear (with shared $\Sigma$)	Linear
Parameter Estimation	MLE of $P(x\|y)$ and $P(y)$	MLE of $P(y\|x)$ directly
When to Use	Data truly Gaussian, small dataset	Large dataset, unknown distributions

Key Insight: GDA and LR produce the same linear decision boundary, but they estimate parameters differently:

• GDA: Models $P(x|y)$ and $P(y)$ → derives $P(y|x)$ via Bayes' rule
• LR: Directly models $P(y|x)$ parametrically

Generalization and Reduction

Generalization: GDA is a special case that can be generalized:

• QDA (Quadratic Discriminant Analysis): Different $\Sigma_y$ per class → produces quadratic boundaries
• Naive Bayes: Independence assumption → $\Sigma$ is diagonal
• General exponential family: Replace Gaussian with other distributions (see GLM)

Reduction to Special Cases:

• If features are independent: $\Sigma$ becomes diagonal
• If classes are balanced and means are equal: reduces to random guessing
• If $\Sigma$ is identity matrix: decision boundary depends only on Euclidean distance to means

Why Covariance Must Be PSD

The covariance matrix $\Sigma$ must be PSD because:

1. Variance is always non-negative: For any vector $\mathbf{z}$, $\text{Var}(\mathbf{z}^T x) = \mathbf{z}^T \Sigma \mathbf{z} \geq 0$
2. Inverse exists: For GDA, we need $\Sigma^{-1}$, so $\Sigma$ must be positive definite (PD) (strictly PSD)
3. Physical interpretation: Covariance captures how features co-vary; negative variance is meaningless

Ensuring PSD: The MLE formula $\Sigma = \frac{1}{m} \sum_{i=1}^{m} (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T$ automatically produces a PSD matrix because it's a sum of outer products $(x - \mu)(x - \mu)^T$, which are PSD.