Michael's Wiki

Naive Bayes Assumption

The Naive Bayes assumption in classification is that data observations are independent of each other when conditioned on their class.

Naive Bayes Model

(see lecture notes http://www.ics.uci.edu/~smyth/courses/cs277/public_slides/text_classification.pdf)

Training a Naive Bayes Classification Algorithm

For each class
For each feature
P ( x_j = 1 | c_k ) = n_{jk} / n_k
end
P( c_k ) = n_k / N
end

Complexity is linear in T, where T is the total number of word tokens: $O(T+kd)$.

Smoothing

Smoothing is very important to account for zero-counts in training data. A beta prior is common here. Without smoothing, the classifier can learn zero-probabilities for certain features. This rules out the possibility of that feature being associated with a class in the future.

Naive Bayes Bernoulli

…

History

Naive bayes was widely used in early spam email classifiers.

* See Paul Graham's ''A Plan for Spam''