Generative & Instance-Based Classifiers
Classifying by modeling P(x|y) instead of P(y|x) directly — plus k-NN.
On this page
Every model in Module 4 shared one design decision: model P(y|x) — the label given the features — directly, and never bother modeling the features themselves. That's the discriminative approach, and it's extremely effective, but it's not the only way to build a classifier. This module covers the other half of the classification story: generative models, which instead learn P(x|y) — what the data for each class actually looks like — and a class prior P(y), then combine them with Bayes' theorem to get a decision rule. It also covers the simplest classifier of all, k-Nearest Neighbors, which sidesteps modeling either distribution and instead just asks "what are the labels of the points closest to me?" — and it closes with a rigorous comparison of the generative and discriminative philosophies themselves.
This is a genuine change of lens, not just a new set of formulas. Logistic regression (section 2.4.1) answers "given these features, what's the probability of each class?" directly and only that. Naive Bayes and Gaussian Discriminant Analysis answer a different question first — "if I were this class, what data would I expect to see?" — and get the classification decision as a byproduct of comparing those class-conditional stories. That byproduct turns out to buy real things discriminative models don't get for free: the ability to generate synthetic data, robustness with very little training data, and — as the last lesson proves rigorously — a genuinely different asymptotic error profile as sample size grows.
Every generative classifier in this module is the same application of Bayes' rule:
Naive Bayes and Gaussian Discriminant Analysis differ only in what they assume about the class-conditional density P(x|y=k): Naive Bayes assumes the features are conditionally independent given the class (letting it multiply simple 1-D distributions together); GDA assumes each class's features follow a multivariate Gaussian, and LDA vs. QDA is just the question of whether every class shares one covariance matrix or gets its own. Once P(x|y) and P(y) are estimated (almost always by plain MLE — section 2.1.6), predicting a label is just picking the k that maximizes this posterior. k-NN never estimates a density at all — it approximates P(y|x) non-parametrically from the neighborhood directly — which is exactly why the module's last lesson needs to treat it as a bridge case when comparing generative and discriminative philosophies.
- 2.5.1 Naive Bayes — Bayes' theorem, the conditional-independence assumption that makes it tractable, MLE parameter estimates for Gaussian / Multinomial / Bernoulli feature types, Laplace smoothing, and why everything is computed in log-space.
- 2.5.2 Gaussian Discriminant Analysis — LDA / QDA — modeling each class as a multivariate Gaussian, and the single modeling choice (shared vs. per-class covariance) that decides whether the decision boundary is linear or quadratic.
- 2.5.3 k-Nearest Neighbors (k-NN) — a classifier with no training phase and no density estimate at all: distance metrics, majority vote, the Cover-Hart bound, and the curse of dimensionality.
- 2.5.4 Generative vs. Discriminative Models — the precise mathematical distinction between modeling
P(x,y)and modelingP(y|x), and Ng & Jordan's classic asymptotic result on when each one wins.
- Assuming "generative" means "worse" — generative models are frequently the right choice with limited data, when missing features need to be handled naturally, or when you actually need
P(x)itself (e.g. novelty/outlier detection, a preview of Module 17). - Treating Naive Bayes' independence assumption or GDA's Gaussian assumption as something that needs to be exactly true to be useful — both are frequently "wrong but useful": the resulting decision boundary can still be excellent even when the generative story itself is a simplification, precisely because classification only needs the boundary to be right, not the density estimate.
Going deeper
Logistic regression (2.4.1) and Gaussian Discriminant Analysis with shared covariance are a particularly illuminating pair to compare: GDA's modeling assumptions, once plugged into Bayes' rule, produce a posterior P(y|x) of exactly the sigmoid/softmax form logistic regression assumes directly — meaning logistic regression's hypothesis class is a strict superset of GDA's. GDA makes a stronger assumption (Gaussian class-conditionals) and therefore, when that assumption holds, is strictly more data-efficient; logistic regression makes a weaker assumption and is therefore more robust when it doesn't. Section 2.5.4 makes this exact trade-off rigorous.
Start with 2.5.1, Naive Bayes — it's the cleanest possible illustration of the generative recipe (assume a simple class-conditional density, fit it with MLE, combine with Bayes' rule), and every later lesson in this module either relaxes one of its assumptions (GDA drops feature independence but keeps the Gaussian family), abandons density estimation altogether (k-NN), or steps back to compare the whole approach against Module 4's discriminative one (2.5.4).