Naive Bayes
In probability theory, the conditional probability of an event B is the probability that the event will occur, given the knowledge that an event A has already occurred. is the notation for the conditional probability of event B, given event A.
If events A and B are not independent, then the probability of the intersection of A and B (the probability that both events occur) is defined by
. That is to say, by this definition, we can derive the conditional probability
is as follows: (assumes the probability of event A occur
is greater than 0)
For the probability of the intersection of three events A, B, and C, we can follow the definition above and express as .
According to the conditional probability definition, Bayes theorem describes the probability of an event, based on prior knowledge of conditions that might be related to the event. Bayes theorem is stated mathematically as follows:
where A and B are events and is greater than 0.
-
is the conditional probability as above: the probability of event B occurs, given event A has already occurred.
-
is the probability of event A occurs, given event B has already occurred.
-
and
are the marginal probabilities of event A and event B.
The theorem is based on stating the probability of event A is the sum of the conditional probabilities of event A given that event B has or has not occurred, which can be expressed as follows:
If event A and event B are independent, then:
Therefore, the Bayes theorem can also be written as the following equation:
Naive Bayes classifier is a probabilistic classifier based on applying Bayes' Theorem of conditional probabilities with strong independence (naive) assumptions between each feature.
Naive Bayes is a technique for constructing classifiers: models that assign class labels to problem instances, represented as vectors of feature values, where the class labels are drawn from some finite set. It is a family of algorithms based on the principle of Bayes Theorem: all naive Bayes classifiers assume that the value of a particular feature is independent of the value of any other feature, given the class variable.
Naive Bayes classifiers can be trained very efficiently in a supervised learning setting. In many practical applications, parameter estimation for naive Bayes models uses the method of maximum likelihood. That is to say, one can work with the naive Bayes model without accepting Bayesian probability or using any Bayesian methods. Despite the naive design and oversimplified assumptions, naive Bayes classifiers have worked quite well in many complex real-world situations. An advantage of naive Bayes is that it only requires a small number of training data to estimate the parameters necessary for classification.
Based on Bayes theorem, the conditional probabilities of class , given the data
can be written as follows:
where:
-
: the data matrix,
matrix
(
instances, each with
dimensions (features), each belongs to one of
possible classes (levels)
-
:
, an instance in the data
-
: the label vector,
vector
-
: label for level
However, in practice, it is intractable to deal with joint probabilities, especially when the dimensionality of the data is extremely high. (That is to say,
is greatly large.)
Hence, "naive" Bayes assumes that each word conditionally independent of the others, given the label . Therefore, the conditional probabilities of each word, given the label
, will not be affected by other words:
. Then the original problem above will be:
where:
-
(
-
-
: value for feature
,
-
-
Since the denominator is the same across all documents, we can effectively ignore it as a constant, thereby giving us a decision: We can compute the probability for each label , then perform the classification and return the label with the highest probability as our prediction, which is obtaining
as follows:
In the document classification, we are curious about: "What is the probability of the document class, given the document itself?" If we are using individual word counts as features, then consider a document as a single instance with
features, where
is the number of unique words across all the vocabulary. Conditional independence in naive Bayes imposes the bag-of-words model, where word order does not matter, only word frequency.
Then, the word probabilities can be computed with simple term frequencies. Specifically, the probability of a particular word given a label ,
, is the frequency that word appears in documents of label
divided by the total frequency that word appears in all documents.
For example, to obtain the class of label with largest probabilities, we will have to calculate the following two probabilities for each label:
-
The conditional probability of word i, given label k, is the same as the word count of word i in label k divided by the total word count in label k.
-
The prior probability of label k is the same as the number of documents in label k divided by the total numbers of documents in the whole training set.
Since many probabilities are multiplied, this can result in a floating point underflow. It is therefore better to perform the computation by adding logarithms transformation to the probabilities. The multiplication of the probabilities will become the summation of log-probabilities. The class with the highest log probability score is still the most probable.
Notice that if there is a word j in training data but not in testing data, the count of the word j will be 0, and the conditional probability of the word j, given label k, will be 0. Based on the equation above, the product of all probability will be 0. Since we can not always include all the words both in the training data and testing data, the problem of word count 0 will be solved by Laplace Smoothing.
The conditional independence assumption of naive Bayes is so critical: it substantially reduces the number of required estimated parameters. It works well in practice, however, it has some important drawbacks to be aware of:
-
Not Conditionally Independent
In practice, replicates are common in the data, which are clearly dependent entities, but naive Bayes will treat them as independent to each other, given the class label.
-
Continuous Attributes
In most data, including document classification, are not boolean. Rather, they are continuous. We can fairly modify Naive Bayes to Gaussian Naive Bayes, where attributes are i.i.d. Gaussian, but then we assume our data are Gaussian, which may not be true in practice.
-
Observed data in testing but not training
In document classification, the parameters in training the naive Bayes classifier consists of word counting. However, when a word
are in a testing set but not in training set, the corresponding probability
will be 0 by default. The problem is, computing
for a document with a single probabilty of 0 will result in a 0 for entire statement.
Laplace Smoothing is also called additive smoothing or Lidstone smoothing (but it's different as Laplacian smoothing), which is a technique used to smooth categorical data.
In Naive Bayes document classifier, Laplace smoothing is used to fix the problem of zero word count. For those words in the training data but not in the testing data, Laplace smoothing can solve the problem of 0 conditional probability as follows:
Therefore, when the word count is zero, the nominator will be 1 instead of 0, then the conditional probability will not be 0 either. V in the denominator is the distinct words number of the whole training data. We implemented Laplace smoothing to all the conditional probabilities in our Naive Bayes classifier.
[1] Conditional Porbability - Yale University, Department of Statistics