31. Generative Models for Classification#
As we have already discussed, discriminative models aim to find a direct mapping from inputs to predicted labels. Probabilistic discriminative models, in particular, do so by directly modeling the conditional probability distribution
This is for instance the case of a logistic regressor.
Generative models are another class of algorithms which do not explicitly model the conditional probability. Instead, they model the probability of the predictors independently for each class:
and then use the Bayes’ theorem to obtain the conditional probability and make predictions.
Differently from discriminative models, generative models make assumptions on the distribution of the data (e.g., data is often assumed to be Guassian) and hence are often less general than discriminative models. However, they can be advantageous when the training data is scarce. Also, while discriminative models such as the logistic regressor are unstable when data is linearly separable, generative approaches do not suffer from this limitation.
Generative models are so called because, by modeling the distribution of the data, they provide a complete data model which may also be used to generate new data following the joint probability distribution
even if they are mainly used to perform classification in this context.
31.1. Maximum A Posteriori (MAP) Classification Principle#
Let us consider the conditional probability:
Rather than trying to estimate the probability \(P(c|\mathbf{x})\) directly, generative models rely on Bayes’ theorem:
As seen in the case of probabilistic discriminative methods (e.g., logistic regressor), we can define our classification algorithm as follows:
We note that, if we are not interested in computing the actual probabilities $\(P(c|\mathbf{x})\)\(, but we only want to assign \)\mathbf{x}\( to the most likely class, we can drop the evidence \)P(X)\(, which is independent of class \)c$. Indeed we note that:
Which leads to:
This approach is known as Maximum A Posteriori (MAP) classification as we aim to maximize the posterior probability.
In order to implement this principle, we need to compute the following three quantities:
The likelihood \(P(X|C)\);
The prior \(P(C)\);
We will now see how to compute each of these quantities.
31.1.1. The Prior \(P(C)\)#
\(P(C)\): this is the prior probability of a given class. If observing a class \(c\) is not very common, then \(P(c)\) will be small. We can use different approaches to estimate \(P(c)\):
We can estimate \(P(c)\) by considering the number of examples in the dataset. For instance, if our dataset contains \(800\) non-spam e-mails and \(200\) spam e-mails, we can assume that \(P(0) = 0.2\) and \(P(1) = 0.8\).
Alternatively, we could study what is the proportion of examples in each class in the real world. In the case of spam detection, we could ask a large sample of people how many e-mails they receive in average and how many spam e-mails they receive. These numbers can be used to define the prior probability.
Another common choice, when we don’t have enough information on the phenomenon is to assume that all classes are equally probable, in which case \(P(C) = \frac{1}{m}\), where \(m\) is the number of classes.
There are many ways to define the prior probability. However, it should be considered that this quantity should be interpreted in Bayesian terms. This means that, by specifying a prior probability, we are introducing our degree of belief on what classes are more or less likely in the system.
31.1.2. The Likelihood \(P(X|C)\)#
While estimating the prior is easy and estimating the evidence is not necessary for classification purposes (it would be indeed necessary if we were to compute probabilities), computing the likelihood term is less straightforward.
If we have \(M\) different classes, a general approach to estimate the likelihood consists in group all observations belonging to a given class \(C=c\) (let’s call \(X_{c}\) the random variable of the examples belonging to this group) and estimate the probability \(P\left( X_{c} \right)\).
If we repeat this process for every possible value of \(C\), we have concretely estimated \(P(X|C)\) as:
To estimate \(P(X_{c})\) we will generally need to make a few assumptions. Depending on such assumptions, we obtain different generative models.
31.2. Joint Probability MAP Classification#
We will now see a simple application of the MAP principle which makes use of the direct estimation of the probability \(P(X|C)\) in the case of discrete features. In particular, we will consider an example with two discrete features, so that we have to estimate \(P(X_1,X_2|C)\).
Let’s say we want to classify emails as Spam or Ham (Not Spam) based on the presence of the following words:
Offer (F1): Yes/No
Free (F2): Yes/No
Each of these can be considered a binary feature which can either be present or not. Hence both Offer and Free have two possible values “Yes” and “No”.
31.2.1. Step 1: Prior Probabilities#
Let’s start by computing prior probabilities. Counting the number of e-mails in the database, we find the following picture.
Class |
Prior Probability ( P(C) ) |
|---|---|
Spam |
\( P(\text{Spam}) = 0.6 \) |
Ham |
\( P(\text{Ham}) = 0.4 \) |
31.2.2. Step 2: Contingency Tables#
We now want to estimate the probabilities \(P(X_1,X_2|C)\). One way to do it is to estimate the two following joint probabilities:
\(P(Offer,Free|Spam)\)
\(P(Offer,Free|Ham)\)
We will estimate each of them with a contingency table.
Spam Class Contingency Table
Let’s say we obtain the following “spam” contingency table:
Free (F2) |
Yes |
No |
Total |
|---|---|---|---|
Offer (F1) Yes |
30 |
10 |
40 |
Offer (F1) No |
20 |
10 |
30 |
Total |
50 |
20 |
70 |
This is obtained by looking at co-occurrences of features for elements in the “spam class”.
Ham Class Contingency Table
Similarly, we obtain the “ham” contingency table:
Free (F2) |
Yes |
No |
Total |
|---|---|---|---|
Offer (F1) Yes |
5 |
15 |
20 |
Offer (F1) No |
10 |
30 |
40 |
Total |
15 |
45 |
60 |
31.2.3. Step 3: Normalize Counts to Obtain Joint Probabilities#
We can now normalize counts to obtain joint probabilities:
Normalized Probabilities for Spam Class
Free (F2) |
Yes |
No |
Total |
|---|---|---|---|
Offer (F1) Yes |
\( \frac{30}{70} = 0.429 \) |
\( \frac{10}{70} = 0.143 \) |
0.571 |
Offer (F1) No |
\( \frac{20}{70} = 0.286 \) |
\( \frac{10}{70} = 0.143 \) |
0.429 |
Total |
0.714 |
0.286 |
1 |
Normalized Probabilities for Ham Class
Free (F2) |
Yes |
No |
Total |
|---|---|---|---|
Offer (F1) Yes |
\( \frac{5}{60} = 0.083 \) |
\( \frac{15}{60} = 0.250 \) |
0.333 |
Offer (F1) No |
\( \frac{10}{60} = 0.167 \) |
\( \frac{30}{60} = 0.500 \) |
0.667 |
Total |
0.250 |
0.750 |
1 |
We now have all we need to implement an MAP classifier.
31.2.4. Step 4: Inference for a New Email Observation#
Let’s see how to classify an email with the following characteristics:
Offer = Yes
Free = Yes
Applying the MAP rule, we obtain:
For Spam:
For Ham:
We note that:
Hence, we can classify the example as Spam.
While this is not required in MAP classification, in this case, it is also easy to compute the actual probabilities:
31.3. Linear Discriminant Analysis (LDA)#
Linear Discriminant Analysis (LDA) is a generative approach with a discriminative interpretation that brings to a formulation similar to Fisher’s Linear Discriminant (FLD), but making additional assumptions on the data, notably that examples within a class are normally distributed and that they share the same covariance matrix across classes. These assumption are made because LDA is an essence a generative algorithm which needs to perform density estimation. As FLD, also LDA is closely related to PCA in that it finds a linear transformation of the data which better explains it (in the case of LDA the aim is to discriminate the different classes).
31.3.1. Linear Discriminant Analysis for D=1#
We will start by considering the case in which the data is uni-dimensional, hence \(D=1\). Recall that, since LDA is a generative algorithm, our goal is to estimate the terms:
for all classes \(k=1,\ldots,K\).
LDA makes the assumption that the observations will distribute in a Guassian way within each class. Hence, in the one-dimensional case, we will assume that:
where \(\mu_k\) and \(\sigma_k^2\) are the mean and variance of the observations in class \(k\).
LDA further assumes that data in each class have the same variance:
Using Bayes’ theorem, we can estimate the posterior probability as follows:
Where we let
and
By the MAP principle, we will assign \(x\) the class \(k\) maximizing the posterior probability \(P(C_k|x)\):
31.3.1.1. LDA and Mahalanobis Distance#
Since the logarithm is a monotonic function, maximizing \(P(C_k|x)\) is equivalent to maximizing \(\log P(C_k|x)\). Taking the logarithm of \(P(C_k|x)\), we obtain:
Where \(Cst.\) is a constant term arising from the normalization constant of the Gaussian distribution and from the denominator, which is considered a constant as it is independent of \(k\).
The quantity
is known as the squared Mahalanobis distance. The Mahalanobis distance is defined as follows:
The Mahalanobis distance measures the distance between a point \(x\) and a Gaussian distribution with mean \(\mu\) and standard deviation \(\sigma\).
Indeed, we can see it as the number of standard deviations between \(x\) and \(\mu\). By normalizing by the standard deviation, the Mahalanobis distance allows to measure the distance between Gaussian distributions of different parameters, as illustrated in the figure below:
We can see how, even if the green dot is closer to the orange’s population mean, its distance from the blue population is smaller as this distribution is more dispersed.
This is coherent with the fact that the probability value of the green point under the blue population is larger than the probability value of the same point under the orange population.
Consider the case of uniform priors \(\pi_k = \frac{1}{K}, \forall k\). In this case, we can see LDA as classifying each point by assigning it to the class with the closest distribution in terms of Mahalanobis distance.
31.3.1.2. Linear Discriminant Analysis and Discriminant Function#
The reasoning above suggests that LDA acts as a discriminant function assigning observations to one class or another based on the computation of some scores based on the Mahalanobis distance.
We can see that LDA naturally defines a linear discriminant function, hence the words “linear” and “discriminant” in LDA. We can re-arrange the term \(\log P(C_k|x)\) as follows:
with
Where we set \(\delta_k(x)=\log P(C_k|x)\) as a shorthand notation.
From the expression above, it is clear that LDA defines a linear discriminant \(\delta_k\), hence LDA can be considered both a generative algorithm (explicitly modeling probabilities \(P(X_c)\)) and a discriminative one (explicitly modeling a decision boundary).
For instance, if \(K=2\) (two classes) and \(\pi_1=\pi_2\) (uniform priors), then the decision boundary is given by:
Note that this point would effectively act as a threshold (hence a decision boundary) to classify elements. This is also the point in which the two Guassian distribution intersect, as shown in the figure below:
When the priors are not uniform, the decision boundary will not be exactly at the intersection of the two Gaussian distributions, as shown in the figures below:
31.3.1.3. Optimization#
In practice, we can fit the LDA classifier to the data by estimating its parameters as follows:
where \(N_K\) is the number of observations in class \(C_k\), and \(N\) is the total number of elements. In practice, the first expression computes the means within each class and the second expression can be seen as a weighted average of the variances within each class.
The priors are estimated based on the number of elements in each class:
31.3.2. Linear Discriminant Analysis for D>1#
Let us now consider the general case in which \(D>1\). We will assume that our input observations are realizations of a random variable \(X=(X_1,X_2, \ldots, X_D)\) following a multivariate Gaussian distribution.
We will follow the same principle consider for the uni-dimensional case and model the likelihood terms \(P(X_c)\) with multivariate Gaussian distributions. Recall that the D-dimensional multivariate Gaussian is defined as follows:
Where \(\mathbf{\mu}\) is a D-dimensional vector indicating the mean, and \(\mathbf{\Sigma}\) is the \(D \times D\) covariance matrix.
In the multivariate case (\(D>1\)) LDA assumes that observations in class \(k\) follow a D-dimensional Gaussian distribution with mean \(\mathbf{\mu}_k\) and covariance matrix \(\mathbf{\Sigma}\). As in the previous case, we will assume that all classes have the same covariance matrix \(\mathbf{\Sigma}\), while means can be distinct. Hence, we will model:
We can estimate the posterior probability as follows:
31.3.2.1. Multidimensional Mahalanobis Distance#
Taking the logarithm of the posterior, we obtain:
This is the multivariate version of the expression seen in the unidimensional case (\(D=1\)). Note that the expression
is the generalization to multiple dimensions of the squared Mahalanobis distance. The Mahalanobis distance is indeed defined as follows in the multidimensional case:
In this case, the Mahalanobis distance estimates the distance between a multidimensional point \(\mathbf{x}\) and a multivariate Gaussian distribution. To do so, we need to take into account the covariance matrix of each distribution, which defines how the data vary along the different directions.
The plot below shows an example:
We can again see LDA as classifying \(\mathbf{x}\) with the class with the closest Gaussian distribution in terms of Mahalanobis distance.
31.3.2.2. Linear Discriminant Function#
Also in this case, LDA allows to define a multi-class linear discriminant function:
where:
We can see \(\delta_k\) as a linear function of \(\mathbf{x}\). Note that the decision boundary will be made of all points \(\mathbf{x}\) such that
We will not see the mathematical formulation in details, but it is easy to see that will be linear functions as well. The following figure shows Gaussian fits and decision boundary for a simple example:
The parameters of the LDA classifier will be fit to the data with the following formulas:
31.3.3. LDA for Dimensionality Reduction#
Linear Discriminant Analysis can also be used for dimensionality reduction, similar to Fisher’s Linear Discriminant. We will not see the mathematical details, but LDA arrives at a similar solution as FLD with some technical differences. It is useful to know that libraries such as scikit-learn often implement both versions of LDA (classification and dimensionality reduction). More information can be found here: https://scikit-learn.org/stable/modules/lda_qda.html#mathematical-formulation-of-lda-dimensionality-reduction
31.4. Quadratic Discriminant Analysis (QDA)#
Quadratic Discriminant Analysis has formulation similar to the one of Linear Discriminant Analysis, but it removes the assumption that covariance matrices in the different classes should be the same, which was formulated as:
In this sense, LDA can be seen as a specific case of QDA.
We will not see the mathematical details, but, dropping this constraint makes the decision boundary between classes a quadratic function, rather than a linear one, hence the term “quadratic” in QDA.
The figure below compares LDA and QDA for classes with different covariance matrices:
31.5. Naïve Bayes Classifier#
Let us consider the problem of classifying e-mail messages as spam or non-spam, with the e-mails represented with bag of words (a representation which counts the number of occurrences of each word given a vocabulary), with vocabulary size equal to 20000 words. In this example, we will consider \(X = \lbrack X_{1},\ldots,X_{n}\rbrack\) (e.g., \(n = 20000)\) as a multi-dimensional random variable containing the features and \(C\) as the random variable representing the class.
If we want to apply the MAP rule, we obtain:
When the dimensionality of the input data is very high, modeling \(P(X|C)\) directly as seen before is very challenging.
For instance, if we wanted to fit a 20000-D Gaussian, we would have to compute \(Cov(X)\). This would be a matrix of dimension \(20000 \times 20000\), which would require about 1.5GB in single precision!
31.5.1. Naïve Assumption#
We have seen that probabilities can be factorized using the product rule. Hence, we could obtain:
However, this is not a very helpful factorization as the terms \(P(X_{i}|X_{1},\ldots,X_{i - 1},C)\) are conditioned also on other features, which makes them not easy to model.
We can make the naïve assumption that the input features are conditionally independent given the class. That is, if the examples are represented by the multimodal random variable \(X = \lbrack X_{1},\ldots,X_{n}\rbrack\) (features) and \(C\) (class):
If \(X_{i}\) and \(X_{j}\) are word counts, then we are saying that if I take all non-spam e-mails, then the number of occurrences of a given word does not influence the number of occurrences of another word. This is obviously not true in general! For instance, there can be legitimate e-mails of different topics. If the e-mail is about a vacation, the words ‘trip’, ‘flight’, ‘luggage’ will appear often. Instead, if the e-mail is about work, the words ‘meeting’, ‘report’, ‘time’, will appear more often. This means that, within the same category (non-spam e-mails), the number of occurrences of a word (e.g., ‘trip’) may be related to the number of occurrences of another words (e.g., ‘flight’), which breaks the assumption of conditional independence. This is why this assumption is called naïve assumption. With this in mind, it should be considered that, despite such naïve assumption, the Naïve Bayes Classifier works surprisingly well in many contexts.
We know that:
Hence, we discover that, under the assumption of conditional independence:
So, we can re-write the MAP classification rule as:
The single \(P(X_{1}|C)\) terms are now easy to model, since \(X_{1}\) is mono-dimensional. In practice, depending on the considered problem, we can model these terms in different ways. Two common approaches, depending on the data, are to use a Gaussian distribution or a Multinomial distribution.
When we use Gaussian distributions to model the \(P(X_{i}|C)\) terms, the classification method is called “Gaussian Naïve Bayes). Similarly, if we consider a multinomial distribution, the classification method is called “Multinomial Naïve Bayes”.
31.5.2. Gaussian Naïve Bayes#
Let us consider again our sex classification example based on height and weight. We will consider \(X = \lbrack H,W\rbrack\), which are random variables representing heights and weights of subjects. If we assume that the data is approximately Gaussian, the probabilities \(P(H|C)\) and \(P(W|C)\) can be modeled with univariate (1D) Gaussian distributions. This is done by first obtaining four samples:
\(H_{1}\): the heights of subjects when \(C = 1\);
\(W_{1}\): the weights of subjects when \(C = 1;\)
\(H_{0}\): the heights of subjects when \(C = 0\);
\(W_{0}\): the weights of subjects when \(C = 0.\)
We hence model each sample as a 1D Gaussian distribution by computing a mean and a variance value from each of these samples to obtain four Gaussian distributions:
\(P\left( H = h \middle| C = 0 \right) = N(x;\mu_{1},\sigma_{1})\);
\(P\left( W = w \middle| C = 0 \right) = N(x;\mu_{2},\sigma_{2})\);
\(P\left( H = h \middle| C = 1 \right) = N(x;\mu_{3},\sigma_{3})\);
\(P\left( W = w \middle| C = 1 \right) = N(x;\mu_{4},\sigma_{4})\);
After this, we can apply the classification rule:
The example \((h,w)\) is classified as class 1 if
\(P\left( h \middle| C = 1 \right)P\left( w \middle| C = 1 \right)P(C = 1) > P\left( h \middle| C = 0 \right)P\left( w \middle| C = 0 \right)P(C = 0)\);
The example \((h,w)\) is classified as class 0 otherwise.
We can exemplify this process as follows:
31.5.3. Naive Bayes and QDA#
We will not see it in details, but it can be shown that a Gaussian Naive Bayes classifier is equivalent to a Quadratic Discriminant Analysis classifier with diagonal covariance matrices. By forcing the covariance matrices to have zeros on all off-diagonal elements, we are assuming that variables are conditionally independent with respect to classes (hence independent within each class).
The figure below compares a Quadratic Discriminant Analysis classifier with a Gaussian Naive Bayes on the same data:
As we can see, in both cases, decision boundaries are non-linear. This happens because we did not constrain all covariance matrices to be the equal.
Differently from QDA, in Gaussian Naive Bayes, the fitted Gaussians are aligned to the axes, which is due to the naive assumption. This brings some differences in the decision boundary between class 1 and class 2 in the specific example above.
31.6. References#
Naïve Bayes Classifier: https://en.wikipedia.org/wiki/Naive_Bayes_classifier;
https://scikit-learn.org/stable/modules/lda_qda.html#lda-qda
Section 4.4 of [1]
[1] James, Gareth Gareth Michael. An introduction to statistical learning: with applications in Python, 2023.https://www.statlearning.com