Naive Bayes classifier

• 1. Introduction

  ›

  The naive Bayes classifier looks at a fruit that is red, round, and about 10 cm across, and decides that it is an apple. It reaches that verdict by treating every clue as separate evidence. Color, roundness, and size are weighed one at a time, as though knowing a fruit is round told you nothing about how big it is. Real fruit does not behave that way, and the people who use this method know it. Why would anyone build a classifier on a premise they know to be false? What does it do well in spite of that flaw? And what happens when someone sets out to fool it on purpose?

  1333

• 2. The Naive Assumption

  ›

  Statisticians sometimes call the method simple Bayes, and sometimes, less kindly, idiot's Bayes. The name points at one assumption. Once the class is known, each feature is treated as conditionally independent of every other feature. Every variable offers its own information about the class, and none of it is shared with the rest. Statisticians admit this is highly unrealistic, and that is exactly what makes the classifier naive. It also places naive Bayes among the simplest Bayesian network models.

  Bayes' theorem supplies the machinery for everything else. The model assigns a probability to each of K possible classes, given a vector describing n features of the item. Storing those probabilities in tables becomes infeasible when n is large, or when a feature can take many values. So the formula is rewritten. Bayes' theorem turns it into a fraction, and only the numerator matters, because the bottom of the fraction does not depend on the class.

  The chain rule, which unpacks a joint probability into repeated conditional probabilities, is where the shortcut pays off. Under the independence assumption, that long chain collapses into a plain product with one term per feature. Each term depends only on the class. The final distribution over classes is proportional to the class prior multiplied by that product, with the evidence acting as a constant scaling factor.

  Working with log-probabilities, measured in units called nats, brings two benefits. They have a natural reading in information theory, and they avoid arithmetic underflow. To turn the model into a classifier, one common choice is the maximum a posteriori rule, or MAP. It picks the most probable hypothesis so as to minimize the chance of misclassification. The prior for each class can assume equiprobable classes, or it can be estimated from the proportions seen in the training set.

  1236

• 3. Wrong But Useful

  ›

  In 2004, an analysis of the Bayesian classification problem found sound theoretical reasons for the odd success of naive Bayes. A broad comparison in 2006 was less flattering. It showed that boosted trees and random forests outperform Bayes classification. Logistic regressions generally do better as well, especially at quantifying uncertainty, where naive Bayes often produces wildly overconfident probabilities.

  One parameter per feature is all the model needs to learn. Maximum-likelihood training reduces to a closed-form expression, which amounts to counting observations in each group. Most other models require expensive iterative approximation instead. The method also needs only a small amount of training data to estimate its parameters.

  The curse of dimensionality normally demands data sets that grow exponentially with the number of features. Naive Bayes sidesteps much of that burden. Because the features are decoupled, each class-conditional distribution can be estimated on its own as a one-dimensional distribution.

  The MAP rule explains why poor probabilities do not always mean poor answers. The classifier chooses the right class whenever that class is rated more probable than any other. It does not matter whether the estimate is slightly off or grossly inaccurate. The overall classifier can therefore shrug off serious flaws in its underlying probability model.

  The name also misleads on one point. Despite Bayes' theorem in its decision rule, naive Bayes is not necessarily a Bayesian method. It can be fit with either Bayesian or frequentist techniques, and maximum likelihood is common in practice.

  4153313

• 4. Three Event Models

  ›

  Before a naive Bayes classifier can estimate anything, someone must choose a distribution for each feature. These choices are called event models, and they produce quite different classifiers.

  The Gaussian model suits continuous measurements. The data is first split by class, and then the mean and the Bessel corrected variance are computed for each class. A new observation is plugged into the normal distribution built from those two numbers. Another route is binning, which turns continuous values into Bernoulli features. Some literature calls this mandatory, but it is not, because discretizing can throw away discriminative information.

  John and Langley introduced kernel density estimation to handle features whose distributions are far from normal. Their method can boost the accuracy of the classifier considerably.

  The bag of words assumption underlies the multinomial model, the usual choice for classifying documents. Each document becomes a histogram that counts how many times each word occurred. Expressed in log space, the multinomial classifier is a linear classifier. Logs also help with rounding error, which creeps in when many small values are multiplied together.

  Laplace smoothing sets a pseudocount of one, and Lidstone smoothing covers the general case. The need for it is simple. If a word and a class never appear together in training, the estimate is zero, and that zero wipes out every other probability in the product. A small pseudocount keeps any probability from being exactly zero.

  Rennie and colleagues studied problems with the multinomial assumption in document classification. They suggested tf-idf weights instead of raw term frequencies, plus document length normalization. With those changes, naive Bayes became competitive with support vector machines.

  The Bernoulli model records only whether each vocabulary term is present or absent, using independent Boolean variables. It is especially popular for short texts, and it explicitly models the absence of terms. It is not the same as a multinomial classifier with counts truncated to one, though the two are often confused.

  781396

• 5. Close Relatives

  ›

  Multinomial logistic regression is the natural partner of naive Bayes when the inputs are discrete. The two form a generative-discriminative pair. Naive Bayes fits a probability model by optimizing the joint likelihood. Logistic regression fits the same model by optimizing the conditional likelihood.

  The link shows up in the binary case, where the decision rule says to predict one class if its odds exceed those of the other. Written in log space, that rule yields the log-odds, or logit, which is the quantity a logistic regression predicts. Both discrete event models are linear, so naive Bayes can be reparametrised as a linear function. Applying the logistic function gives probabilities, and the softmax function does the job when there are more than two classes.

  Ng and Jordan found a twist in the rivalry. Discriminative classifiers have lower asymptotic error than generative ones. Yet in some practical cases naive Bayes beats logistic regression, because it reaches its asymptotic error faster.

  Labels are not required for every example. Given labeled samples L and unlabeled samples U, a semi-supervised version starts by training a classifier on L alone. It then loops until convergence. Each pass predicts class probabilities for all examples in U, then retrains the model on those probabilities rather than on hard labels. Convergence is judged by improvement in the model likelihood.

  The loop is an instance of the expectation-maximization algorithm, known as EM. The prediction step is the E-step, and the retraining is the M-step. The method is justified by assuming the data come from a mixture model whose components are exactly the classes of the problem.

  17141112

• 6. A Worked Example

  ›

  Eight people make up the training set in a textbook demonstration of naive Bayes, four men and four women. Each is described by height, weight, and foot size. The task is to guess whether a new person is male or female. The three measurements are treated as independent, though they are not independent in reality.

  Fitting a Gaussian distribution to each group gives the model its numbers. The men average 5.855 feet in height, 176.25 lbs in weight, and a foot size of 11.25 inches. The women average 5.4175 feet, 132.5 lbs, and a foot size of 7.5 inches. The example assumes equiprobable classes, so each prior is 0.5.

  The test sample stands 6 feet tall, weighs 130 lbs, and has a foot size of 8 inches. Its height sits near the men's average. Its weight and foot size sit close to the women's averages. Which pull wins is decided by comparing the two posteriors. The evidence term is the same for both, so it scales them equally and can be ignored. The female numerator comes out larger, and the sample is classified as female.

  One detail in the arithmetic can look alarming. Some of the values come out greater than 1. That is fine, because height is continuous, so the figure is a probability density rather than a probability.

  61112

• 7. Inside A Spam Filter

  ›

  Sahami and his co-authors published the first scholarly paper applying naive Bayes to spam filtering in 1998. Bayesian algorithms had been used for email filtering as early as 1996. Several programs appeared in 1998 to address the growing problem of unwanted email, although Bayesian filters did not become popular until later.

  The approach rests on bag-of-words features. The filter correlates tokens, usually words, with spam and non-spam messages. It then uses Bayes' theorem to estimate the probability that a new email is spam. With two classes, spam and not spam, the ratio of the two posteriors reduces to a series of likelihood ratios. Taking logarithms and applying a sigmoid curve converts that ratio back into a probability.

  The technique is a baseline defense that can tailor itself to the needs of each user. It tends to give low false positive rates, which users generally find acceptable. Many modern mail clients include Bayesian filtering. Server-side filters such as DSPAM, Rspamd, SpamAssassin, SpamBayes, Bogofilter, and ASSP use it too, and sometimes it is built into mail server software.

  CRM114 is often cited as a Bayesian filter, yet it is not meant to use one in production. It includes a "unigram" feature only for reference.

  A word that never appeared during training leaves both numerator and denominator at zero. The software can simply discard such words. Words seen only a few times are a subtler problem, since their evidence should not be trusted blindly. Some programs treat the spam-or-ham status of messages containing a word like "replica" as a random variable with a beta distribution. They then use a corrected probability in place of the raw one.

  Neutral words such as "the", "a", "some", or "is" can be ignored as stop words. Some filters also skip every word whose spamicity is near 0.5, since such words add little to the decision. One method keeps only the ten words in a message with the greatest absolute value of |0.5 - pI|. Products differ on whether they count repeated words in one message.

  Some products read sequences of words rather than isolated ones. With a context window of four words, they score "Viagra is good for" as a unit instead of scoring "Viagra", "is", "good", and "for" separately. This gives more sensitivity to context and removes Bayesian noise better, at the cost of a bigger database.

  192892021

• 8. Spammers Strike Back

  ›

  Bayesian poisoning is the name for a spammer's counterattack on filters that rely on Bayesian methods. The spammer sends emails padded with large amounts of legitimate text gathered from news or literary sources. Random innocuous words that are not normally linked to spam are mixed in. The aim is to lower the spam score of the message so it slips past the filter. Paul Graham's scheme resists this, because it uses only the most significant probabilities, so padding barely affects detection.

  Words that are common in spam can also be disguised. "Viagra" becomes "Viaagra" or "V!agra". A human reader can still make out the altered word, but the filter meets each variant more rarely, which hinders its learning. As a general rule this trick does not work well, because the filter ends up recognizing the derived words just like the normal ones.

  Another tactic replaces text with pictures, either included directly or linked from elsewhere. The sensitive words are drawn inside an image, which a filter usually cannot analyze. The tactic has costs. Many mail clients block linked pictures for security reasons, so a spammer who links to remote images may reach fewer targets. A picture also takes more bytes than the equivalent text, so the spammer needs more bandwidth. Some filters become more suspicious of messages that are mostly graphics.

  Google's Gmail answers by running optical character recognition on every mid to large size image. That lets the system read the hidden words inside the picture and score them like any other text.

  28292725