Understanding Naive Bayes Classifier From Scratch

Naive Bayes classifier belongs to a family of probabilistic classifiers that are built upon the Bayes theorem. In naive Bayes classifiers, the number of model parameters increases linearly with the number of features. Moreover, it’s trained by evaluating a closed-form expression, i.e., a mathematical expression that can be evaluated using finite steps and has one definite solution. This means that naive Bayes classifiers train in linear time compared to the quadratic or cubic time of other iterative approximation based approaches. These two factors make naive Bayes classifiers highly scalable. In this article, we’ll go through the Bayes theorem, ‘make some assumptions’ and then implement a naive Bayes classifier from scratch. 

Bayes Theorem

Bayes theorem is one of the most important formulas in all probability. It’s an essential tool for scientific discovery and for creating AI systems; it has also been used to find century-old treasures. It is formulated as

But what does that mean? Let’s understand it with the help of a puzzle taken from Kahneman and Tversky’s Experiments:

“Steve is very shy and withdrawn, invariably helpful but with very little interest in people or in the world of reality. A meek and tidy soul, he has a need for order and structure and a passion for detail.” 

Given the above description, do you think Steve is more likely to be a librarian or a farmer? The majority of people immediately conclude that Steve must be a librarian since he fits their idea of a librarian. However, as we see the whole picture, we see that there are twenty times as many farmers as librarians (in the United States). Most people aren’t aware of this statistic and hence can’t make an accurate prediction, and that’s okay. Also, that’s beside the point of this article. However, if you want to learn why we act irrationally and make assumptions like this, I wholeheartedly recommend reading Kahneman’s Thinking Fast and Slow. 

Back to Bayes theorem, to model this puzzle more accurately, let’s start by creating create a representative sample of 420 people, 20 librarians and 400 farmers. And let’s say your intuition is that roughly 50% of librarians would fit that description, and 10% of farmers would. So the probability of a random person fitting this description being a librarian becomes 0.2 (10/50). So even if you think a librarian is five times as likely as a farmer to fit this description, that’s not enough to overcome the fact that there are way more farmers.

This new evidence doesn’t necessarily overrule your past belief but rather updates it. And this is precisely what the Bayes theorem models.  The first relevant number is the probability that your beliefs hold true before considering the new evidence. Using the ratio of farmers to librarians in the general population, this came out to be 1/5 in our example. This is known as the prior P(H). In addition to this, we need to consider the proportion of librarians that fit this description; the probability we would see the evidence given that the hypothesis is true, P(E|H).  In the context of the Bayes theorem, this value is called the ‘likelihood’. This represents a limited view of your initial hypothesis. 

Similarly, we need to consider how much of the farmer’s side of the sample space make up the evidence; the probability of seeing the evidence given that your beliefs don’t hold true P(E|H’). Using these notations, the accurate probability of your beliefs being right given the evidence, P(H|E), also called the posterior probability, can be formulated as:

Where N is the sample size. In our example, this expression evaluates to 1/5. The sample size gets cancelled out; this gives us:

This gets further simplified to:

This is the original Bayes theorem that we started with. I hope this illustrated the core point of the Bayes theorem representing a changing belief system, not just a bunch of independent probabilities. 

Assumptions Made by Naive Bayes Classifiers

The naive Bayes classifier is called ‘naive’ because it makes the assumption that all features are independent of each other. Another assumption that it makes is that the values of the features are normally (Gaussian) distributed. Using these assumptions, the original Bayes theorem is modified and transformed into a simpler form that is relevant for solving learning problems. We start with

where, 

And because the features are considered independent, we can breakdown P(X|y) 

For classification tasks, we want to select the class with the highest probability, so we choose y, which is 

And P(X) is common to all classes and will not change their final ranks; hence it can be excluded from the equation.

A lot of these probabilities will be small numbers; multiplying them can cause overflow problems, so we apply the log function. 

And that’s the equation naive Bayes classifiers use to make predictions, now let’s implement one.

Implementing a Naive Bayes Classifier from Scratch

Create a function that calculates the prior probability, P(H), mean and variance of each class. The mean and variance are later used to calculate the likelihood, P(E|H), using the Gaussian distribution. 

 import numpy as np
 class GaussianNaiveBayes:
     def fit(self, X, y):
         n_samples, n_features = X.shape
         self._classes = np.unique(y)
         n_classes = len(self._classes)
         self._mean = np.zeros((n_classes, n_features), dtype=np.float64)
         self._var = np.zeros((n_classes, n_features), dtype=np.float64)
         self._priors =  np.zeros(n_classes, dtype=np.float64)

         # calculating the mean, variance and prior P(H) for each class
         for i, c in enumerate(self._classes):
             X_for_class_c = X[y==c]
             self._mean[i, :] = X_for_class_c.mean(axis=0)
             self._var[i, :] = X_for_class_c.var(axis=0)
             self._priors[i] = X_for_class_c.shape[0] / float(n_samples) 

Write a function for calculating the likelihood, P(E|H), of data X given the mean and variance

     def _calculate_likelihood(self, class_idx, x):
         mean = self._mean[class_idx]
         var = self._var[class_idx]
         num = np.exp(- (x-mean)**2 / (2 * var))
         denom = np.sqrt(2 * np.pi * var)
         return num / denom 

And finally, write the methods for making classifications by calculating the posterior probability, P(H|E), of the classes 

     def predict(self, X):
         y_pred = [self._classify_sample(x) for x in X]
         return np.array(y_pred)

     def _classify_sample(self, x):
         posteriors = []
         # calculating posterior probability for each class
         for i, c in enumerate(self._classes):
             prior = np.log(self._priors[i])
             posterior = np.sum(np.log(self._calculate_likelihood(i, x)))
             posterior = prior + posterior
             posteriors.append(posterior)
         # return the class with highest posterior probability
         return self._classes[np.argmax(posteriors)] 

Now let’s test our naive Bayes classifier and compare it with scikit-learn’s implementation. 

 from sklearn.model_selection import train_test_split
 from sklearn.metrics import accuracy_score
 from sklearn import datasets
 import time

 X, y = datasets.make_classification(n_samples=1000, n_features=20, n_classes=2, random_state=42)
 X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=42)

 start = time.perf_counter()
 nb = GaussianNaiveBayes()
 nb.fit(X_train, y_train)
 predictions = nb.predict(X_test)
 end = time.perf_counter()
 print(f"NumPy Naive Bayes accuracy: {accuracy_score(y_test, predictions)}")
 print(f'Finished in {round(end-start, 3)} second(s)')  

 NumPy Naive Bayes accuracy: 0.796
 Finished in 0.013 second(s) 

 from sklearn.naive_bayes import GaussianNB
 start = time.perf_counter()
 sk_nb = GaussianNB()
 sk_nb.fit(X_train, y_train).predict(X_test)
 sk_predictions = sk_nb.predict(X_test)
 end = time.perf_counter()
 print(f"scikit-learn Naive Bayes accuracy: {accuracy_score(y_test, sk_predictions)}")
 print(f'Finished in {round(end-start, 3)} second(s)')  

 scikit-learn Naive Bayes accuracy: 0.96
 Finished in 0.009 second(s) 

You can find the above implementation in a Colab notebook here.

What to see naive Bayes classifiers in action check out these articles:

• Hands-On Guide to Predict Fake News Using Logistic Regression, SVM and Naive Bayes Methods
• Step By Step Guide To Reviews Classification Using SVC, Naive Bayes & Random Forest