Implementing the Naive Bayes Classifier from Scratch in C++

Welcome to our exploration tour of the Naive Bayes Classifier! This robust classification algorithm is renowned for its simplicity and effectiveness. We will implement it from scratch in C++, allowing you to leverage its sheer power without the need for any prebuilt libraries. Let's get started!

Let's do a quick recall of probability theory.

$P(A)$ usually denotes the likelihood of a certain event A occurring. $P(A|B)$, on the other hand, indicates the probability of event A taking place, assuming event B has already happened.

For instance, let's imagine there's a bag housing three marbles - one red and two blue. Denote A as the event where a red marble is picked, and B when a blue one is drawn. The probability of A, $P(A)$, is 1/3 in this case.

Now, let's consider a scenario where a blue marble has been already drawn from the bag. This leaves us with one red and one blue marble in the bag. The probability of drawing a red marble (event A), given that a blue marble has already been extracted (event B), is denoted by $P(A|B)$. In this case, $P(A|B)$ would be 1/2, highlighting a higher likelihood of drawing a red marble following the initial removal of a blue one.

The Naive Bayes algorithms rely on the Bayes' theorem. Let's recall it quickly. This theorem calculates the probability of an event based on prior knowledge of potentially related events. It is represented mathematically as:

$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$

Where $P(A|B)$ is the posterior probability of class ($A$) given predictor ($B$). It's what we are trying to calculate. $P(B|A)$ is the likelihood, which is the probability of the predictor given a class. $P(B)$ is the marginal probability of predictor, and $P(A)$ is the prior probability of the class. This formula forms the backbone of the Naive Bayes classifier.

The term 'naive' refers to the assumption that all variables in a dataset are independent of each other, which may not always be the case in real-life data. Nonetheless, it still offers robust performance and can be easily implemented.

In the context of machine learning, the Naive Bayes Classifier uses the Bayes theorem to compute the posterior probability of a class given a set of features and then classifies the outcome based on the highest posterior probability.

Assuming a binary class variable $Y$ (binary means it can be equal to either 0 or 1) and features $X_1, X_2, ..., X_n$, our task is to compute the posterior probability $P(Y=1 | X_1=x_1, X_2=x_2,...,X_n=x_n)$. By shedding the denominator from Bayes' theorem (since it doesn't depend on $Y$ and is constant for all classes), we are left with the task of maximizing the probability of $Y$ and $X$ happening together $P(Y, X) = P(X|Y)P(Y)$, which forms the basis for Naive Bayes classification.