Naive Bayes classifier

From Wikipedia, the free encyclopedia
  (Redirected from Naive bayes)
Jump to: navigation, search



Training naive Bayes can be done by evaluating an approximation algorithm in closed form in linear time, rather than by expensive iterative approximation.




Despite their naive design and apparently oversimplified assumptions, naive Bayes classifiers have worked quite well in many complex real-world situations. In 2004, an analysis of the Bayesian classification problem showed that there are sound theoretical reasons for the apparently implausible efficacy of naive Bayes classifiers.[2] Still, a comprehensive comparison with other classification algorithms in 2006 showed that Bayes classification is outperformed by other approaches, such as boosted trees or random forests.[3]


Probabilistic model[edit]

Abstractly, the probability model for a classifier is a conditional model

p(C \vert F_1,\dots,F_n)\,

over a dependent class variable C with a small number of outcomes or classes, conditional on several feature variables F_1 through F_n. The problem is that if the number of features n is large or if a feature can take on a large number of values, then basing such a model on probability tables is infeasible. We therefore reformulate the model to make it more tractable.

Using Bayes' theorem, this can be written

p(C \vert F_1,\dots,F_n) = \frac{p(C) \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)}. \,

In plain English, using Bayesian Probability terminology, the above equation can be written as



p(C, F_1, \dots, F_n)\,


p(C, F_1, \dots, F_n) & = p(C) \ p(F_1,\dots,F_n\vert C) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3) \\
                      & = p(C) \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ \dots p(F_n\vert C, F_1, F_2, F_3,\dots,F_{n-1})

Now the "naive" conditional independence assumptions come into play: assume that each feature F_i is conditionally independent of every other feature F_j for j\neq i given the category C. This means that

 p(F_i \vert C, F_j) = p(F_i \vert C)\,,
p(F_i \vert C, F_j,F_k) = p(F_i \vert C)\,,
p(F_i \vert C, F_j,F_k,F_l) = p(F_i \vert C)\,,


p(C \vert F_1, \dots, F_n) & \varpropto p(C, F_1, \dots, F_n) \\
                           & \varpropto p(C) \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots \\
                           & \varpropto p(C) \prod_{i=1}^n p(F_i \vert C)\,.


p(C \vert F_1,\dots,F_n) = \frac{1}{Z}  p(C) \prod_{i=1}^n p(F_i \vert C)

where the evidence Z = p(F_1, \dots, F_n) is a scaling factor dependent only on F_1,\dots,F_n, that is, a constant if the values of the feature variables are known.

Constructing a classifier from the probability model[edit]


\mathrm{classify}(f_1,\dots,f_n) = \underset{c}{\operatorname{argmax}} \ p(C=c) \displaystyle\prod_{i=1}^n p(F_i=f_i\vert C=c).

Parameter estimation and event models[edit]

All model parameters (i.e., class priors and feature probability distributions) can be approximated with relative frequencies from the training set. These are maximum likelihood estimates of the probabilities. A class' prior may be calculated by assuming equiprobable classes (i.e., priors = 1 / (number of classes)), or by calculating an estimate for the class probability from the training set (i.e., (prior for a given class) = (number of samples in the class) / (total number of samples)). To estimate the parameters for a feature's distribution, one must assume a distribution or generate nonparametric models for the features from the training set.[4]


Gaussian naive Bayes[edit]



Another common technique for handling continuous values is to use binning to discretize the feature values, to obtain a new set of Bernoulli-distributed features. In general, the distribution method is a better choice if there is a small amount of training data, or if the precise distribution of the data is known. The discretization method tends to do better if there is a large amount of training data because it will learn to fit the distribution of the data. Since naive Bayes is typically used when a large amount of data is available (as more computationally expensive models can generally achieve better accuracy), the discretization method is generally preferred over the distribution method.

Multinomial naive Bayes[edit]

With a multinomial event model, samples (feature vectors) represent the frequencies with which certain events have been generated by a multinomial (p_1, \dots, p_n) where p_i is the probability that event i occurs (or k such multinomials in the multiclass case). This is the event model typically used for document classification; the feature values are then term frequencies, generated by a multinomial that produces some number of words (see bag of words assumption). The likelihood of observing a feature vector (histogram) F is given by

p(F|C) = \frac{(\sum_i F_i)!}{\prod_i F_i !} \prod_i {p_i}^{F_i}

The multinomial naive Bayes classifier becomes a linear classifier when expressed in log-space:[1]

\log p(C|F) & = \log \left( p(C) \prod_{i=1}^n p(F_i \vert C) \right) \\
            & = \log p(C) + \sum_{i=1}^n \log p(F_i \vert C)          \\
            & = b + \mathbf{w}_C^\mathsf{T} \mathbf{F}

where b = \log p(C) and w_{Ci} = \log p(F_i \vert C).



Bernoulli naive Bayes[edit]

In the multivariate Bernoulli event model, features are independent booleans (binary variables) describing inputs. This model is also popular for document classification tasks,[5] where binary term occurrence features are used rather than term frequencies. If F_i is a boolean expressing the occurrence or absence of the i'th term from the vocabulary, then the likelihood of a document given a class C is given by[5]

p(F_1, \dots, F_n \vert C) = \prod_{i=1}^n \left[ F_i\, p(w_i \vert C) + (1 - F_i)(1 - p(w_i \vert C)) \right]

where p(w_i \vert C) is the probability of class C generating the term w_i. This event model is especially popular for classifying short texts. It has the benefit of explicitly modelling the absence of terms. Note that a naive Bayes classifier with a Bernoulli event model is not the same as a multinomial NB classifier with frequency counts truncated to one.




Sex classification[edit]



Example training set below.

male 6 180 12
male 5.92 (5'11") 190 11
male 5.58 (5'7") 170 12
male 5.92 (5'11") 165 10
female 5 100 6
female 5.5 (5'6") 150 8
female 5.42 (5'5") 130 7
female 5.75 (5'9") 150 9

The classifier created from the training set using a Gaussian distribution assumption would be (given variances are sample variances):





sample 6 130 8



For the classification as female the posterior is given by


The evidence (also termed normalizing constant) may be calculated:




P(male) = 0.5





P(\mbox{female}) = 0.5






Document classification[edit]


p(w_i \vert C)\,





Now by definition










Using the Bayesian result above, we can write:


Dividing one by the other gives:


Which can be re-factored as:



Taking the logarithm of all these ratios, we have:




See also[edit]


  1. ^ a b c Rennie, J.; Shih, L.; Teevan, J.; Karger, D. (2003). "Tackling the poor assumptions of Naive Bayes classifiers". ICML. 
  2. ^ Zhang, Harry. "The Optimality of Naive Bayes". FLAIRS2004 conference. 
  3. ^ Caruana, R.; Niculescu-Mizil, A. (2006). "An empirical comparison of supervised learning algorithms". Proceedings of the 23rd international conference on Machine learning. CiteSeerX: 
  4. ^ John, George H.; Langley, Pat (1995). "Estimating Continuous Distributions in Bayesian Classifiers". Proc. Eleventh Conf. on Uncertainty in Artificial Intelligence. Morgan Kaufmann. pp. 338–345. 
  5. ^ a b c McCallum, Andrew; Nigam, Kamal (1998). "A comparison of event models for Naive Bayes text classification". AAAI-98 workshop on learning for text categorization 752. 
  6. ^ Metsis, Vangelis; Androutsopoulos, Ion; Paliouras, Georgios (2006). "Spam filtering with Naive Bayes—which Naive Bayes?". Third conference on email and anti-spam (CEAS) 17. 

Further reading[edit]

External links[edit]