Generative and Discriminative Models

A discriminative model learns P(y | x) or the decision boundary directly. A generative model learns how each class produces its data, P(x | y), together with P(y), and classifies with Bayes' rule. For binary feature vectors a full generative model needs 2ᵈ parameters per class, which is hopeless; an independence assumption brings it down to d.

Every classifier so far has looked directly for a boundary. There is a second way to build a classifier, one that tells a story about where each class's data comes from, much as Gaussian mixtures did for clustering. The two approaches have names, and the difference between them runs through the rest of the course.

Two ways to model a classification problem

Think of the data as pairs $(x, y)$ drawn from some joint distribution $P(x, y)$ . That distribution can be factorised in two ways:

P(x, y) = P(y \mid x)\, P(x) = P(x \mid y)\, P(y) .

A discriminative model learns $P(y \mid x)$ directly, or just a boundary that separates the classes. It does not care how the features themselves are distributed. kNN, decision trees, logistic regression and support vector machines are discriminative.
A generative model learns $P(x \mid y)$ , what typical data from each class looks like, and the class proportions $P(y)$ . It can then classify by Bayes' rule:

P(y \mid x) = \frac{P(x \mid y)\,P(y)}{\sum_{y'} P(x \mid y')\,P(y')} ,

predicting the class with the larger posterior. Because it models the features too, a generative model could in principle generate new examples of each class, hence the name.

An analogy: to tell Hindi text from Tamil text, a discriminative learner looks for whatever cues separate them (the script, a few common words). A generative learner learns to write a little of each language, then asks which language's model would more plausibly have produced the text in front of it.

A generative story for spam

Represent an email by which words it contains. Fix a vocabulary of $d$ words; the feature vector $x \in \{0, 1\}^d$ has $x_j = 1$ if word $j$ appears. The label $y$ is 1 for spam and 0 for genuine mail.

The generative story:

Choose the class. Spam with probability $p$ , so $P(y = 1) = p$ .
Generate the words given the class, from a distribution $P(x \mid y)$ specific to that class: spam is more likely to contain "winner" and "lottery", genuine mail "meeting" and "invoice".

The parameter $p$ is easy to estimate: the fraction of training emails that are spam (its maximum likelihood estimate, as for the coin in Module 5).

The problem: too many parameters

What about $P(x \mid y)$ ? A binary vector of length $d$ has $2^d$ possible values. Describing an arbitrary distribution over all of them needs $2^d - 1$ probabilities per class.

With a vocabulary of just 30 words, that is over a billion parameters per class. With a realistic vocabulary of tens of thousands of words, the number is beyond astronomical, and no amount of email could estimate it: almost every possible combination of words would appear zero times in the training data, so its estimated probability would be zero. A fully general generative model is hopeless, not because the idea is wrong but because it has far too many parameters for any finite data.

The way out: an assumption

The only escape is to assume structure in $P(x \mid y)$ that cuts the number of parameters down. The boldest useful assumption is that within each class, the features are independent of one another:

P(x \mid y) = \prod_{j=1}^{d} P(x_j \mid y) .

Each factor is a coin flip: the probability that word $j$ appears in an email of class $y$ . That is one parameter per word per class, $2d$ in all (plus $p$ ), instead of $2(2^d - 1)$ . With 30 words, 61 numbers instead of about two billion.

The assumption is clearly false in detail: "lottery" and "winner" tend to appear together, and so do "meeting" and "agenda". It is called naive for that reason. Yet the resulting classifier, naive Bayes, works remarkably well for text and many other problems, because classification only needs to get the larger posterior right, not the exact probabilities. The next chapter builds it in full.

Left panel labelled discriminative: two classes of points with a single boundary line between them. Right panel labelled generative: the same points with an oval density contour around each class, and a boundary drawn where the two densities, weighted by class proportions, are equal — Discriminative models learn the boundary directly. Generative models learn a density for each class and put the boundary where the weighted densities are equal.

Which approach is better?

Neither always wins.

Generative models use more assumptions. When those assumptions are roughly right they need less data and train very fast (often just by counting). They handle missing features naturally (just leave the factor out) and can detect inputs that look like neither class.
Discriminative models spend all their effort on the boundary, which is what classification needs. With enough data they usually achieve lower error, because they are not hurt by a wrong model of $P(x)$ .

A classic study (Ng and Jordan, 2002) compared naive Bayes with its discriminative counterpart, logistic regression: naive Bayes reaches its best error with fewer examples, but logistic regression usually reaches a lower error once there is plenty of data.

Try it yourself

Machine Learning Lab: naive Bayes vs logistic →

The same data, a generative classifier and a discriminative one. Change the spread of one class and see whose boundary bends, and whose accuracy holds up.

EasyGenerative modelsNaive Bayes

How many parameters does a fully general model of P(x | y) need for 20 binary features and 2 classes, and how many under the naive Bayes assumption?

EasyGenerative models

Classify each as generative or discriminative: Gaussian mixture classifier, logistic regression, k-nearest neighbours, naive Bayes, decision tree.

MediumGenerative modelsMissing data