Anisotropic QDA vs LDA

Agenda:

1. Anisotropic QDA
2. Anisotropic LDA
3. Isotropic QDA (already learned) (spherical) ${\sigma }_c^{2}I$
4. Isotropic LDA (spherical) ${\sigma }^{2}I$

Maximum Likelihood Estimation for Anisotropic Gaussians

Given training points $X_1,\dots X_n$ and classes $y_1\dots y_n$, we need to find the best-fit Gaussians.

Let $n_c$ be the number of training points in class C.

Quadratic Discriminant Analysis (QDA)

1. Covariance Matrix: The best estimate covariance matrix (conditional covariance of points in class C) , $\widehat{{\Sigma }_c}$ is: $${\hat{\Sigma }}_c=\frac{1}{n_c}\sum _{i:y_i\in C}(X_i-{\hat{\mu }}_c)(X_i-{\hat{\mu }}_c{)}^T$$
2. Discriminant Function: $$Q_c(x)=-\frac{1}{2}(x-{\mu }_c{)}^T{\Sigma }^{-1}(x-{\mu }_c)-\frac{1}{2}\ln |{\Sigma }_c|+\ln {\pi }_c$$
3. Decision Boundary: $Q_C(x)-Q_D(x)=0$
4. Posterior Probability (for two class): $P(Y=C|X=x)=s(Q_C(x)-Q_D(x))=\frac{1}{1-e^{Q_D(x)-Q_C(x)}}$
5. Visualization:

Two-Class QDA

Multi-Class QDA

---

Linearly Discriminant Analysis (LDA)

1. Covariance Matrix: For LDA, we want pool-covariance within-class matrix $\hat{\Sigma }$. **Note: This is a weighted sum with prior probabilities. **That means:

$$\hat{\Sigma }=\frac{1}{n}\sum _c\sum _{i:y_i=c}(X_i-{\hat{\mu }}_c)(X_i-{\hat{\mu }}_c{)}^T$$ $$\hat{\Sigma }=\sum _c\frac{n_c}{n}.\frac{1}{n_c}\sum _{i:y_i=c}(X_i-{\hat{\mu }}_c)(X_i-{\hat{\mu }}_c{)}^T$$

Note that $\frac{n_c}{n}$ is the same as prior probability of class C. And the rest of the terms is covariance of class C.

2. Discriminant Function: $Q_c(x)={\mu }_c^T{\Sigma }^{-1}x-\frac{{\mu }_c^T{\Sigma }^{-1}{\mu }_c}{2}+\ln {\pi }_c$

3. Decision Boundary $Q_C(x)-Q_D(x)=0$

   $$Q_c(x)-Q_D(x)=\underset{w^{T}x=w.x}{\underbrace{({\mu }_c-{\mu }_D{)}^T{\Sigma }^{-1}x}}-\underset{\alpha }{\underbrace{\frac{{\mu }_c{\Sigma }^{-1}{\mu }_c-{\mu }_D^T{\Sigma }^{-1}{\mu }_D}{2}+\ln {\pi }_C-\ln {\pi }_D}}$$

4. Posterior Probability (for two class): $P(Y=C|X=x)=s(w^{T}x+\alpha )=s(Q_C(x)-Q_D(x))=\frac{1}{1+e^{Q_D(x)-Q_C(x)}}$

5. Visualization:

Two-Class LDA

Multi-Class Real World Data LDA

---

GDA vs LDA

For Two-classes Classification:

1. LDA has d+1 parameters (w, $\alpha$).
2. QDA has $\frac{d(d+3)}{2}+1$ parameters.
3. LDA is more likely to underfit (small number of parameters).
4. QDA is more likely to overfit (the danger is much bigger wiith larger dimensions d) as the parameters grow with squared of the dimensions.

Cautions:

• that QDA or LDA on data doesn’t find the True Baye’s Classifier. In fact, it is not possible to get a true Baye’s Classifier since we do not know the true parameters / distribution of real world data. Most of the time, if not all the time, we use the estimated distributions from finite data. Moreover, real-world data might not fit the Gaussian perfectly.
• Changing Prior Probabilities or Loss Functions is the same as adding constants (actually ln(constants)) to our discriminant functions. Thus, in a two-class classifiers, changing these values would be the same as simply changing isovalue.
• Posterior Probability gives us some sort of confidence levels.
• Decision boundaries are drawn at different probability thresholds (e.g 10%, 50%, 90%) to indicate how confident we need to be before making a classification decision. 50% for 0-1 loss functions.
• Setting the decision boundary at probability p is the same as setting asymmetric loss values for false positives and false negatives. (Similarly, the prior probability follows the same rule).
• LDA can result in non-linear decision boundaries if we introduce new features or transformations.

Cite

LDA & QDA are the best method in practice for many applications. In the STATLOG project, either LDA or QDA were among the top three classifiers for 10 out of 22 datasets. But it’s not because all those datasets are Gaussian. LDA & QDA work well when the data can only support simple decision boundaries such as linear or quadratic, because Gaussian models provide stable estimates.

Decorrelating the Design Matrix