Generative Learning Algorithms Quiz

Introduction to Machine Learning - AI 305

• The lecture covers generative learning algorithms
• These algorithms model p(y|x; θ) - the conditional distribution of y given x
• Logistic regression is an example
• A classification problem that distinguishes between elephants (y=1) and dogs (y=0) based on features is discussed.
• Algorithms (like logistic regression or perceptron) find a decision boundary (a straight line) to separate elephants and dogs.

Agenda

• Linear Discriminant Analysis
• Quadratic Discriminant Analysis
• Naïve Bayes

Generative Learning Algorithms

• Algorithms that learn p(x|y) and p(y) directly are called generative
• These algorithms model the distribution of x for each class separately: p(x|y=0) and p(x|y=1)
• If y = 0, p(x|y = 0) models distributions of dog features
• If y = 1, p(x|y = 1) models distributions of elephant features

Bayes Theorem for Classification

• Thomas Bayes developed a subfield of statistical and probabilistic modelling
• Bayes theorem: $p(Y=k|X=x) = \frac{p(X=x|Y=k)p(Y=k)}{p(X=x)} $
• Rewritten for discriminant analysis: $p(Y=k|X=x) = \frac{f_k(x) \pi_k}{\sum_{l=1}^K f_l(x)\pi_l}$
• $f_k(x)$ is the density of x in class k
• $\pi_k$ is the prior marginal probability for class k
• $p(Y = k|X = x)$ is the posterior probability that x belongs to the kth class

Bayes Theorem for Classification - Continued

• Estimating $\pi_k$ is straightforward using training data
• Estimating $f_k(x)$ requires assumptions
• Simplifying assumptions are needed to estimate $f_k(x)$

Classify to the Highest Density

• Classifying a new point is based on which density is higher
• If priors are different, they are considered when comparing $p(x|y)p(y)$
• Decision boundaries shift differently according to prior probabilities

Why Discriminant Analysis?

• In well-separated classes, logistic regression parameter estimates are unstable
• Linear Discriminant Analysis avoids instability
• LDA is more stable than logistic regression when $n$ is small and predictors $X$ approximately normal in each class
• Also useful with more than two response classes to provide low-dimensional views of data.

Linear Discriminant Analysis when p = 1

• To estimate $f_k(x)$ when p = 1 (one predictor)
• Assumption: $f_k(x)$ is normal/Gaussian
• $f_k(x) = \frac{1}{\sqrt{2\pi\sigma_k}} exp(-\frac{1}{2\sigma_k^2}(x - \mu_k)^2)$
• $\mu_k$: mean in class k
• $\sigma_k$: variance in class k (for simplicity, assumed equal)

Discriminant Functions

• To classify a new value of X, find the class with the highest discriminant score.
• $ δ_k(x) = \frac{(x - \mu_k)^2}{2\sigma^2} + log(\pi_k)$
•  $δ_k(x)$ is a linear function of x
• If there are two classes and prior probabilities are equal, the decision boundary is $x = \frac{\mu_1 + \mu_2}{2}$

Example with µ1 = −1.5, µ2 = 1.5, π1 = π2 = 0.5, and σ^2 = 1

• Show examples of different densities in different scenarios

Estimating the parameters

• $\pi_k = \frac{n_k}{n}$, where $n_k$ = observations in class k
• $\mu_k = \frac{1}{n_k} \sum_{i:y_i =k} x_i$
• $\sigma^2 = \frac{1}{n - K} \sum_{k=1}^K \sum_{i:y_i = k} (x_i - \mu_k)^2$

LDA - Continued

• Assumes observations within each class follow a normal distribution with a common variance and class-specific mean

Linear Discriminant Analysis when p > 1

• Extends LDA to multiple predictors
• Assumes each predictor follows a multivariate Gaussian distribution
• Multivariate Gaussian has class-specific mean vectors and a common covariance matrix

Linear Discriminant Analysis when p > 1 - Continued

• Formally, multivariate Gaussian density: $f(x) = \frac{1}{(2\pi)^{p/2} |\Sigma|^{1/2}} exp(-\frac{1}{2}(x - \mu)^T\Sigma^{-1}(x - \mu))$
• Discriminant function $δ_k(x) = \frac{1}{2} x^T \Sigma^{-1} \mu_k - \frac{1}{2} \mu_k^T \Sigma^{-1} \mu_k + log(\pi_k)$

Example

• Show examples of applying LDA to real data

Quadratic Discriminant Analysis

• When class covariance matrices are different, QDA is used
• QDA’s discriminant function is quadratic in $x$.

LDA and QDA in two scenarios

• Show examples of applying LDA and QDA in scenarios with different correlations or variables

Naïve Bayes

• Features are assumed independent in each class in Naive Bayes
• $f_k(x) = \prod_{j=1}^p f_{kj}(x_j)$

Naïve Bayes - Continued

• $f_{kj}(x_j)$ is probability distribution of feature j in class k
• Useful when p is large, or when LDA breaks down

Gaussian Naïve Bayes

• $δ_k(x) = log(\pi_k) + \sum_{j=1}^p log(f_{kj}(x_j))$
• If x is qualitative, use probability mass function of feature values instead of normal distribution

LDA on Credit Data

• Example of applying LDA to credit data
• Issues with training error vs test error are discussed

Types of Errors

• False positive rate and false negative rate are defined
• Error rates can be changed by changing the threshold

Varying the threshold

• The effects of changing threshold on error rates are discussed
• Equal Error Rate (EER) is identified as point where False Positive and False Negative rates are equal.

ROC Curve

• ROC plot displays true positive rate vs false positive rate
• AUC (Area Under Curve) is calculated to summarize performance; Higher is better.

Logistic Regression versus LDA

• Both can be shown as log function, but parameters estimated differently
• Logistic regression uses conditional likelihood (discriminative) , while LDA uses full likelihood (generative)

Summary

• Summary of when to use each classification method (Logistic Regression, LDA, QDA, Naive Bayes) based on data characteristics