Difference Between Generative And Discriminative Classifiers
Difference Between Generative And Discriminative Classifiers

Using the examples of Naive Bayes, MaxEnt (Logistic Regression), HMM, and CRF

Photo by Tianyi Ma on Unsplash

There are a few types of classical supervised machine learning algorithms: Naive Bayes, MaxEnt (also called Logistic Regression), Decision Trees, Hidden Markov Models (HMMs), Support Vector Machines, Conditional Random Fields (CRFs), Neural Networks, and some others. The top n list may differ depending on the field they are used in.

Most of those types have a few sub-types based on the kinds of tasks they are designed for and implementation approaches they leverage, for example, Bernoulli Naive Bayes, linear-chain CRFs, etc.

Models built using four of those main algorithms — Naive Bayes, MaxEnt, HMMs, and CRFs — can be split into two groupings, generative and discriminative (also called conditional). Let’s see how they differ and how they correspond to each other.

Naive Bayes

Naive Bayes is one of the most basic algorithms. It produces a generative model and this model captures the joint probability p(y, x) — so having y, you can generate a random vector of x.

It makes a couple of simplifying assumptions, hence it’s “naive”. The most important one is that all input variables are conditionally independent of one another. It also assumes that the position of the variable doesn’t matter.

So, based on Bayes’ theorem, we’ll model posterior as follows:

Naive Bayes

p(x) — the probability of the feature vector across the dataset — is going to be the same for either class. So for practical reasons, we can drop it and assume that:

Naive Bayes

In any case, p(x) is extremely difficult to model, especially for named entity recognition (NER) tasks with proper names, because x will most probably never occur in the training set.

At the same time, p(y, x) = p(y) p(x|y), thus it models the joint probability.

Using the chain rule, the previous formula can be re-written as:

Naive Bayes

Naive Bayes is easy to implement and is known to perform well for certain tasks, including text classification, and may be preferred under certain conditions, for instance when the training data is scarce. However, it’s not very robust. One of the issues is, for example, “double counting” — such a model doesn’t take into account how often certain words co-occur together in the same class, for example, ‘CEO’ and ‘sales’ in ‘Business’.

2. MaxEnt

The MaxEnt algorithm models the conditional probability distribution directly from the data and allows to address some of the issues with Naive Bayes. Such a model learns to discriminate one class over the other based on the input.

It learns to do so by computing the weights Θ for each feature for each class. However, in practice, instead of learning different weight vectors for every class, one can build a common set of weights for all classes and use feature functions that activate the weights if the feature is present in the instance, and return 0 otherwise.

Thus, one way to describe such a model is:

MaxEnt

Where Z(x) is a normalization constant.

The weights are effectively the posteriors that are learned by iteratively computing the deltas between the empirical and expected counts of the feature occurrences using a set learning rate as a step until the deltas are as close to 0 as possible. This would mean that the best weight values have been achieved.

There is no closed-form, unlike Naive Bayes, so the tricky part is in fact-finding the best weights and deciding when to stop. Training a MaxEnt model is also a lot more involving compared to Naive Bayes because you need to compute p(y|x) for each feature.

Logistic Regression is used to solve an extensive range of problems. If you’re interested in more details, there is a really good paper by Andrew Ng and Michael Jordan comparing the motivation and performance for Naive Bayes and MaxEnt.

3. Hidden Markov Models

Both Naive Bayes and MaxEnt cope well with predicting a single class variable. However, some tasks involve sequence modeling. The two classical algorithms that can solve such problems are Hidden Markov Models (HMM) and Conditional Random Fields (CRF).

The HMM algorithm also produces a generative model, similar to Naive Bayes. However, it alleviates the independence assumption of Naive Bayes - it models the linear sequence and captures the information about the previous label. Therefore, it can be described as:

Hidden Markov Models

In practice, it’s also comparable to Naive Bayes in that it normally uses very few features. Otherwise, an inference can quickly become intractable.

HMM also makes a few simplifying assumptions, for instance, that being in a particular state t only depends on the previous state t-1. Also, it assumes that the conditional distribution over the next state given current state doesn’t change over time (the stationary assumption).

HMM is often used for tasks like part-of-speech tagging in natural language processing or analyzing RNA secondary structures in computational biology.

4. Conditional Random Fields

The CRF model is a discriminative one, similar to MaxEnt, but also captures the sequence and the information about the previous states (labels), similar to HMM. It can be described as:

Conditional Random Fields

CRFs were designed to address issues with generative models not allowing to introduce non-independent features, for example, capitalization and affixation in natural language data.

Since CRFs capture more of these richer features, they handle better such tasks like sentence segmentation and named entity recognition.
['Anna Astori']
['Machine Learning', 'Women In Tech', 'Artificial Intelligence', 'Data Science', 'Technology']