Skip to content
Ahmed Haroon
← Machine Learning

Generative Classification

Discriminative vs. Generative Models

There are two main ways to approach a classification problem.

A discriminative model learns to predict the class directly from the input. In probabilistic terms, it models:

p(y∣x) p(y \mid x)

A generative model takes a different approach. It learns how the input is distributed within each class by modelling:

p(x∣y) p(x \mid y)

along with the class probabilities:

p(y) p(y)
Two panels on the same two-class data: on the left a straight discriminative decision boundary splits the points; on the right generative Gaussian density contours are fitted to each class

A discriminative model focuses on separating the classes directly, while a generative model first models what the data from each class looks like.

Once we know p(x∣y)p(x \mid y) and p(y)p(y), Bayes' rule lets us compute the quantity we actually need for classification: p(y∣x)p(y \mid x).

arg⁡max⁡yp(y∣x)=arg⁡max⁡yp(x∣y)p(y)p(x) \arg \max_y p(y \mid x) = \arg \max_y \frac{p(x \mid y)p(y)}{p(x)} =arg⁡max⁡yp(x∣y)p(y) = \arg \max_y p(x \mid y)p(y)

The denominator p(x)p(x) is the same for every class, so it does not affect which class has the largest posterior. We therefore only need to compare p(x∣y)p(y)p(x \mid y)p(y).

Gaussian Discriminant Analysis

Gaussian Discriminant Analysis (GDA) makes this generative approach concrete by assuming that the inputs from each class follow a Gaussian distribution.

For binary classification, let:

y∈{0,1},x∈Rd y \in \{0,1\}, \qquad x \in \mathbb{R}^d

We model the class prior using a parameter ϕ\phi:

p(y)=ϕy(1−ϕ)1−y p(y) = \phi^y(1-\phi)^{1-y}

Each class has its own mean:

μ0,μ1 \mu_0, \qquad \mu_1

but both classes share the same covariance matrix Σ\Sigma.

Therefore:

x∣y=0∼N(μ0,Σ) x \mid y=0 \sim \mathcal{N}(\mu_0,\Sigma) x∣y=1∼N(μ1,Σ) x \mid y=1 \sim \mathcal{N}(\mu_1,\Sigma)

The corresponding densities are:

p(x∣y=0)=1(2π)d/2∣Σ∣1/2exp⁡(−12(x−μ0)TΣ−1(x−μ0)) p(x \mid y = 0) = \frac{1}{(2 \pi)^{d/2} |\Sigma|^{1/2}} \exp \left( -\frac{1}{2} (x-\mu_0)^T \Sigma^{-1} (x-\mu_0) \right) p(x∣y=1)=1(2π)d/2∣Σ∣1/2exp⁡(−12(x−μ1)TΣ−1(x−μ1)) p(x \mid y = 1) = \frac{1}{(2 \pi)^{d/2} |\Sigma|^{1/2}} \exp \left( -\frac{1}{2} (x-\mu_1)^T \Sigma^{-1} (x-\mu_1) \right)

GDA therefore has four quantities to learn from the training data:

ϕ,μ0,μ1,Σ \phi, \qquad \mu_0, \qquad \mu_1, \qquad \Sigma

Maximum-Likelihood Estimation

We estimate them by maximizing the likelihood of the observed training data.

The log-likelihood is:

ℓ(ϕ,μ0,μ1,Σ)=log⁡∏i=1np(x(i),y(i);ϕ,μ0,μ1,Σ) \ell(\phi,\mu_0,\mu_1,\Sigma) = \log \prod_{i=1}^n p\left( x^{(i)},y^{(i)}; \phi,\mu_0,\mu_1,\Sigma \right)

Maximizing this log-likelihood gives:

ϕ=1n∑i=1n1{y(i)=1} \phi = \frac{1}{n} \sum_{i=1}^n 1\left\{y^{(i)}=1\right\} μ0=∑i=1n1{y(i)=0}x(i)∑i=1n1{y(i)=0} \mu_0 = \frac{ \sum_{i=1}^n 1\left\{y^{(i)}=0\right\}x^{(i)} }{ \sum_{i=1}^n 1\left\{y^{(i)}=0\right\} } μ1=∑i=1n1{y(i)=1}x(i)∑i=1n1{y(i)=1} \mu_1 = \frac{ \sum_{i=1}^n 1\left\{y^{(i)}=1\right\}x^{(i)} }{ \sum_{i=1}^n 1\left\{y^{(i)}=1\right\} } Σ=1n∑i=1n(x(i)−μy(i))(x(i)−μy(i))T \Sigma = \frac{1}{n} \sum_{i=1}^n \left( x^{(i)}-\mu_{y^{(i)}} \right) \left( x^{(i)}-\mu_{y^{(i)}} \right)^T

These estimates have a simple interpretation.

ϕ\phi is the fraction of training examples that belong to class 11.

μ0\mu_0 is the average input among class-00 examples, while μ1\mu_1 is the average input among class-11 examples.

Σ\Sigma measures how the features vary around their class means, pooling information from both classes.

Once these parameters are fitted, prediction is straightforward. For a new input xx, we compare:

p(x∣y=0)p(y=0) p(x \mid y=0)p(y=0)

and

p(x∣y=1)p(y=1) p(x \mid y=1)p(y=1)

and choose whichever is larger.

Because both classes use the same covariance matrix, the quadratic terms cancel when we compare their log probabilities. This is why the resulting decision boundary is linear.

The formulas above assume that both classes appear in the training set and that the pooled covariance matrix is nonsingular. If the covariance is singular, a common practical approach is to regularize it, for example by replacing Σ\Sigma with:

Σ+λI \Sigma + \lambda I

for some λ>0\lambda > 0.

See derivation

We start with the log-likelihood:

ℓ(ϕ,μ0,μ1,Σ)=log⁡∏i=1np(x(i),y(i);ϕ,μ0,μ1,Σ) \ell(\phi,\mu_0,\mu_1,\Sigma) = \log \prod_{i=1}^n p\left( x^{(i)},y^{(i)}; \phi,\mu_0,\mu_1,\Sigma \right)
=log⁡∏i=1np(x(i)∣y(i);μy(i),Σ)p(y(i);ϕ) = \log \prod_{i=1}^n p(x^{(i)}\mid y^{(i)};\mu_{y^{(i)}},\Sigma) p(y^{(i)};\phi)

Taking the log of the product gives:

=∑i=1n[y(i)log⁡p(x(i)∣y(i)=1;μ1,Σ)+(1−y(i))log⁡p(x(i)∣y(i)=0;μ0,Σ) = \sum_{i=1}^n \left[ y^{(i)} \log p(x^{(i)}\mid y^{(i)}=1;\mu_1,\Sigma) + (1-y^{(i)}) \log p(x^{(i)}\mid y^{(i)}=0;\mu_0,\Sigma) \right. +y(i)log⁡ϕ+(1−y(i))log⁡(1−ϕ)] \left. + y^{(i)}\log\phi + (1-y^{(i)})\log(1-\phi) \right]

First, take the derivative with respect to ϕ\phi:

∇ϕℓ=∑i=1n(y(i)ϕ−1−y(i)1−ϕ) \nabla_\phi \ell = \sum_{i=1}^n \left( \frac{y^{(i)}}{\phi} - \frac{1-y^{(i)}}{1-\phi} \right)
=∑i=1ny(i)−ϕϕ(1−ϕ) = \sum_{i=1}^n \frac{y^{(i)}-\phi}{\phi(1-\phi)}

Setting the derivative equal to 00 gives:

∑i=1n(y(i)−ϕ)=0 \sum_{i=1}^n \left( y^{(i)}-\phi \right) = 0

Therefore:

ϕ=1n∑i=1ny(i) \phi = \frac{1}{n} \sum_{i=1}^n y^{(i)} ϕ=1n∑i=1n1{y(i)=1} \phi = \frac{1}{n} \sum_{i=1}^n 1\left\{y^{(i)}=1\right\}

Now take the derivative with respect to μ0\mu_0. Only the class-00 Gaussian terms depend on μ0\mu_0:

∇μ0ℓ=∇μ0∑i=1n(1−y(i))[−12(x(i)−μ0)TΣ−1(x(i)−μ0)] \nabla_{\mu_0}\ell = \nabla_{\mu_0} \sum_{i=1}^n (1-y^{(i)}) \left[ -\frac{1}{2} (x^{(i)}-\mu_0)^T \Sigma^{-1} (x^{(i)}-\mu_0) \right]
=∑i=1n(1−y(i))Σ−1(x(i)−μ0) = \sum_{i=1}^n (1-y^{(i)}) \Sigma^{-1} \left( x^{(i)}-\mu_0 \right)

Setting this equal to 00 gives:

∑i=1n(1−y(i))Σ−1(x(i)−μ0)=0 \sum_{i=1}^n (1-y^{(i)}) \Sigma^{-1} \left( x^{(i)}-\mu_0 \right) = 0
∑i=1n(1−y(i))x(i)=[∑i=1n(1−y(i))]μ0 \sum_{i=1}^n (1-y^{(i)}) x^{(i)} = \left[ \sum_{i=1}^n (1-y^{(i)}) \right]\mu_0

Therefore:

μ0=∑i=1n(1−y(i))x(i)∑i=1n(1−y(i)) \mu_0 = \frac{ \sum_{i=1}^n (1-y^{(i)})x^{(i)} }{ \sum_{i=1}^n (1-y^{(i)}) } μ0=∑i=1n1{y(i)=0}x(i)∑i=1n1{y(i)=0} \mu_0 = \frac{ \sum_{i=1}^n 1\left\{y^{(i)}=0\right\}x^{(i)} }{ \sum_{i=1}^n 1\left\{y^{(i)}=0\right\} }

Similarly:

μ1=∑i=1n1{y(i)=1}x(i)∑i=1n1{y(i)=1} \mu_1 = \frac{ \sum_{i=1}^n 1\left\{y^{(i)}=1\right\}x^{(i)} }{ \sum_{i=1}^n 1\left\{y^{(i)}=1\right\} }

Finally, take the derivative with respect to Σ\Sigma.

For an invertible matrix AA:

∇Alog⁡∣A∣=A−T \nabla_A \log |A| = A^{-T}

and

∇A(xTA−1x)=−A−TxxTA−T \nabla_A \left( x^T A^{-1}x \right) = -A^{-T}xx^TA^{-T}

When AA is symmetric:

A−T=A−1 A^{-T}=A^{-1}

For one Gaussian term, the parts that depend on Σ\Sigma are:

−12log⁡∣Σ∣−12(x−μ)TΣ−1(x−μ) -\frac{1}{2}\log|\Sigma| - \frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu)

Differentiating gives:

−12Σ−1+12Σ−1(x−μ)(x−μ)TΣ−1 -\frac{1}{2}\Sigma^{-1} + \frac{1}{2} \Sigma^{-1} (x-\mu)(x-\mu)^T \Sigma^{-1}

Applying this to every training example:

∇Σℓ=12∑i=1n[−Σ−1+Σ−1(x(i)−μy(i))(x(i)−μy(i))TΣ−1] \nabla_\Sigma \ell = \frac{1}{2} \sum_{i=1}^n \left[ -\Sigma^{-1} + \Sigma^{-1} \left( x^{(i)}-\mu_{y^{(i)}} \right) \left( x^{(i)}-\mu_{y^{(i)}} \right)^T \Sigma^{-1} \right]

Setting this equal to 00 gives:

∑i=1n[−Σ−1+Σ−1(x(i)−μy(i))(x(i)−μy(i))TΣ−1]=0 \sum_{i=1}^n \left[ -\Sigma^{-1} + \Sigma^{-1} \left( x^{(i)}-\mu_{y^{(i)}} \right) \left( x^{(i)}-\mu_{y^{(i)}} \right)^T \Sigma^{-1} \right] = 0
nΣ−1=Σ−1[∑i=1n(x(i)−μy(i))(x(i)−μy(i))T]Σ−1 n\Sigma^{-1} = \Sigma^{-1} \left[ \sum_{i=1}^n \left( x^{(i)}-\mu_{y^{(i)}} \right) \left( x^{(i)}-\mu_{y^{(i)}} \right)^T \right] \Sigma^{-1}

Multiplying on both sides by Σ\Sigma gives:

Σ=1n∑i=1n(x(i)−μy(i))(x(i)−μy(i))T \Sigma = \frac{1}{n} \sum_{i=1}^n \left( x^{(i)}-\mu_{y^{(i)}} \right) \left( x^{(i)}-\mu_{y^{(i)}} \right)^T

Naive Bayes

GDA models the entire feature vector xx jointly using a multivariate Gaussian. This means it has to model how the features vary together.

Naive Bayes takes a simpler approach: it assumes that the features are conditionally independent once we know the class.

For binary features, this gives Bernoulli Naive Bayes.

We assume:

x∈{0,1}d x \in \{0,1\}^d

and:

p(x1,…,xd∣y)=∏j=1dp(xj∣y) p(x_1,\ldots,x_d\mid y) = \prod_{j=1}^d p(x_j\mid y)

In words, once we know the class yy, the value of one feature does not affect the probability of another feature.

This assumption is usually not exactly true, which is why the model is called "naive." However, it makes the model very simple to estimate.

For each feature jj, we need two probabilities:

ϕj∣y=1=p(xj=1∣y=1) \phi_{j\mid y=1} = p(x_j=1\mid y=1)

and:

ϕj∣y=0=p(xj=1∣y=0) \phi_{j\mid y=0} = p(x_j=1\mid y=0)

We also use:

ϕy=p(y=1) \phi_y = p(y=1)

for the class prior.

For binary classification:

y∈{0,1} y\in\{0,1\}

Because of the conditional-independence assumption, the probability of an entire feature vector factors into a product of simple probabilities.

The log-likelihood is:

ℓ(ϕy,ϕj∣y=0,ϕj∣y=1)=log⁡∏i=1np(x(i),y(i);ϕy,ϕj∣y=0,ϕj∣y=1) \ell( \phi_y, \phi_{j\mid y=0}, \phi_{j\mid y=1} ) = \log \prod_{i=1}^n p\left( x^{(i)},y^{(i)}; \phi_y, \phi_{j\mid y=0}, \phi_{j\mid y=1} \right)

Using the Naive Bayes factorization:

=log⁡∏i=1n(∏j=1dp(xj(i)∣y(i)))p(y(i)) = \log \prod_{i=1}^n \left( \prod_{j=1}^d p( x_j^{(i)} \mid y^{(i)} ) \right) p(y^{(i)})

Maximizing the log-likelihood gives:

ϕj∣y=1=∑i=1n1{xj(i)=1∧y(i)=1}∑i=1n1{y(i)=1} \phi_{j\mid y=1} = \frac{ \sum_{i=1}^{n} 1\left\{ x_j^{(i)}=1 \land y^{(i)}=1 \right\} }{ \sum_{i=1}^{n} 1\left\{ y^{(i)}=1 \right\} } ϕj∣y=0=∑i=1n1{xj(i)=1∧y(i)=0}∑i=1n1{y(i)=0} \phi_{j\mid y=0} = \frac{ \sum_{i=1}^{n} 1\left\{ x_j^{(i)}=1 \land y^{(i)}=0 \right\} }{ \sum_{i=1}^{n} 1\left\{ y^{(i)}=0 \right\} } ϕy=1n∑i=1n1{y(i)=1} \phi_y = \frac{1}{n} \sum_{i=1}^{n} 1\left\{ y^{(i)}=1 \right\}

Again, these estimates are just empirical frequencies.

For example,

ϕj∣y=1 \phi_{j\mid y=1}

is the fraction of class-11 training examples for which feature jj is also 11.

Similarly,

ϕj∣y=0 \phi_{j\mid y=0}

is the fraction of class-00 training examples for which feature jj is 11.

Prediction

To classify a new input xx, we compare the posterior probability of each class.

Using Bayes' rule:

p(y=1∣x)=p(x∣y=1)p(y=1)p(x) p(y=1\mid x) = \frac{ p(x\mid y=1)p(y=1) }{ p(x) }

Because of the conditional-independence assumption:

p(x∣y=1)=∏j=1dp(xj∣y=1) p(x\mid y=1) = \prod_{j=1}^{d} p(x_j\mid y=1)

Therefore:

p(y=1∣x)=(∏j=1dp(xj∣y=1))p(y=1)(∏j=1dp(xj∣y=1))p(y=1)+(∏j=1dp(xj∣y=0))p(y=0) p(y=1\mid x) = \frac{ \left( \prod_{j=1}^{d} p(x_j\mid y=1) \right) p(y=1) }{ \left( \prod_{j=1}^{d} p(x_j\mid y=1) \right) p(y=1) + \left( \prod_{j=1}^{d} p(x_j\mid y=0) \right) p(y=0) }

For classification alone, we do not actually need to calculate the denominator. It is the same for both classes.

We can simply compare:

p(x∣y=1)p(y=1) p(x\mid y=1)p(y=1)

and

p(x∣y=0)p(y=0) p(x\mid y=0)p(y=0)

and choose whichever is larger.

Laplace Smoothing

There is one important problem with estimating the probabilities using raw counts.

Suppose feature jj never appears among the class-11 training examples. Then:

p(xj=1∣y=1)=0 p(x_j=1\mid y=1)=0

Naive Bayes multiplies the feature probabilities together, so this single zero can make the probability of the entire input under class 11 equal to zero.

Laplace smoothing avoids this by pretending that we have seen each possible binary outcome once before observing the training data.

We therefore add one pseudocount to each outcome:

ϕj∣y=1=1+∑i=1n1{xj(i)=1∧y(i)=1}2+∑i=1n1{y(i)=1} \phi_{j\mid y=1} = \frac{ 1+ \sum_{i=1}^{n} 1\left\{ x_j^{(i)}=1 \land y^{(i)}=1 \right\} }{ 2+ \sum_{i=1}^{n} 1\left\{ y^{(i)}=1 \right\} } ϕj∣y=0=1+∑i=1n1{xj(i)=1∧y(i)=0}2+∑i=1n1{y(i)=0} \phi_{j\mid y=0} = \frac{ 1+ \sum_{i=1}^{n} 1\left\{ x_j^{(i)}=1 \land y^{(i)}=0 \right\} }{ 2+ \sum_{i=1}^{n} 1\left\{ y^{(i)}=0 \right\} }

The class prior remains:

ϕy=1n∑i=1n1{y(i)=1} \phi_y = \frac{1}{n} \sum_{i=1}^{n} 1\left\{ y^{(i)}=1 \right\}

The added pseudocounts prevent a feature probability from becoming exactly 00 or 11 merely because one outcome was absent from the training sample.

See derivation

The log-likelihood is:

ℓ(ϕy,ϕj∣y=0,ϕj∣y=1)=log⁡∏i=1n(∏j=1dp(xj(i)∣y(i)))p(y(i)) \ell( \phi_y, \phi_{j\mid y=0}, \phi_{j\mid y=1} ) = \log \prod_{i=1}^n \left( \prod_{j=1}^d p( x_j^{(i)} \mid y^{(i)} ) \right) p(y^{(i)})

For binary features and labels, this becomes:

=∑i=1n[∑j=1d(xj(i)y(i)log⁡ϕj∣y=1 = \sum_{i=1}^n \left[ \sum_{j=1}^d \left( x_j^{(i)}y^{(i)} \log\phi_{j\mid y=1} \right. \right. +(1−xj(i))y(i)log⁡(1−ϕj∣y=1) + (1-x_j^{(i)})y^{(i)} \log(1-\phi_{j\mid y=1}) +xj(i)(1−y(i))log⁡ϕj∣y=0 + x_j^{(i)}(1-y^{(i)}) \log\phi_{j\mid y=0} +(1−xj(i))(1−y(i))log⁡(1−ϕj∣y=0)) \left. + (1-x_j^{(i)})(1-y^{(i)}) \log(1-\phi_{j\mid y=0}) \right) +y(i)log⁡ϕy+(1−y(i))log⁡(1−ϕy)] \left. + y^{(i)}\log\phi_y + (1-y^{(i)})\log(1-\phi_y) \right]

First, take the derivative with respect to ϕy\phi_y:

∇ϕyℓ=∑i=1n(y(i)ϕy−1−y(i)1−ϕy) \nabla_{\phi_y}\ell = \sum_{i=1}^n \left( \frac{y^{(i)}}{\phi_y} - \frac{1-y^{(i)}}{1-\phi_y} \right)
=∑i=1ny(i)−ϕyϕy(1−ϕy) = \sum_{i=1}^n \frac{y^{(i)}-\phi_y} {\phi_y(1-\phi_y)}

Setting this equal to 00 gives:

∑i=1n(y(i)−ϕy)=0 \sum_{i=1}^n \left( y^{(i)}-\phi_y \right) = 0

Therefore:

ϕy=1n∑i=1ny(i) \phi_y = \frac{1}{n} \sum_{i=1}^n y^{(i)} ϕy=1n∑i=1n1{y(i)=1} \phi_y = \frac{1}{n} \sum_{i=1}^n 1\left\{ y^{(i)}=1 \right\}

Now take the derivative with respect to ϕk∣y=1\phi_{k\mid y=1}:

∇ϕk∣y=1ℓ=∑i=1n[xk(i)y(i)ϕk∣y=1−(1−xk(i))y(i)1−ϕk∣y=1] \nabla_{\phi_{k\mid y=1}}\ell = \sum_{i=1}^n \left[ \frac{ x_k^{(i)}y^{(i)} }{ \phi_{k\mid y=1} } - \frac{ (1-x_k^{(i)})y^{(i)} }{ 1-\phi_{k\mid y=1} } \right]
=∑i=1ny(i)xk(i)−ϕk∣y=1ϕk∣y=1(1−ϕk∣y=1) = \sum_{i=1}^n y^{(i)} \frac{ x_k^{(i)} - \phi_{k\mid y=1} }{ \phi_{k\mid y=1} \left( 1-\phi_{k\mid y=1} \right) }

Setting this equal to 00 gives:

∑i=1ny(i)(xk(i)−ϕk∣y=1)=0 \sum_{i=1}^n y^{(i)} \left( x_k^{(i)} - \phi_{k\mid y=1} \right) = 0

Therefore:

∑i=1ny(i)xk(i)=ϕk∣y=1∑i=1ny(i) \sum_{i=1}^n y^{(i)}x_k^{(i)} = \phi_{k\mid y=1} \sum_{i=1}^n y^{(i)}

and so:

ϕk∣y=1=∑i=1ny(i)xk(i)∑i=1ny(i) \phi_{k\mid y=1} = \frac{ \sum_{i=1}^n y^{(i)}x_k^{(i)} }{ \sum_{i=1}^n y^{(i)} }
ϕk∣y=1=∑i=1n1{xk(i)=1∧y(i)=1}∑i=1n1{y(i)=1} \phi_{k\mid y=1} = \frac{ \sum_{i=1}^n 1\left\{ x_k^{(i)}=1 \land y^{(i)}=1 \right\} }{ \sum_{i=1}^n 1\left\{ y^{(i)}=1 \right\} }

Similarly, taking the derivative with respect to ϕk∣y=0\phi_{k\mid y=0} gives:

ϕk∣y=0=∑i=1n(1−y(i))xk(i)∑i=1n(1−y(i)) \phi_{k\mid y=0} = \frac{ \sum_{i=1}^n (1-y^{(i)})x_k^{(i)} }{ \sum_{i=1}^n (1-y^{(i)}) }
ϕk∣y=0=∑i=1n1{xk(i)=1∧y(i)=0}∑i=1n1{y(i)=0} \phi_{k\mid y=0} = \frac{ \sum_{i=1}^n 1\left\{ x_k^{(i)}=1 \land y^{(i)}=0 \right\} }{ \sum_{i=1}^n 1\left\{ y^{(i)}=0 \right\} }

GDA and Naive Bayes are both generative classifiers. They model p(x∣y)p(x\mid y) and p(y)p(y), then use Bayes' rule to classify new examples.

The main difference is how they model p(x∣y)p(x\mid y).

GDA models the features jointly using a multivariate Gaussian.

Naive Bayes instead simplifies the distribution by assuming that the features are conditionally independent given the class.