Naive Bayes

Before translating a page, checking spelling or showing search results, a program has to understand what language the text is in. The simplest method that works is to count. Take 1500 sentences in each of fourteen languages and remember how many times each combination of three consecutive letters, a trigram, occurred in each language. To identify the language of a new text, multiply the frequencies of its trigrams in each language and choose the language where the product is largest. This is naive Bayes. Write something yourself or take an example.

The example is a Belarusian phrase, and the nearest rival is Russian. The highlighting shows who votes for whom. «лі» at the end of a word, «пад» and «і·п» are for Belarusian: such combinations hardly ever occur in Russian sentences. The ending «-ему» pulls towards Russian, but such evidence is scarcer and weaker. Russian is 38.6 behind; this is a difference of logarithms, and as a ratio Russian’s odds are e^38.6 ≈ 6·10¹⁶ times smaller. On 2800 test sentences the model has not seen, it gets 2780 right, that is, 99.29%. The “where it errs” button shows the remaining twenty: almost all are short phrases, most often Ukrainian ones taken for Russian.

The idea

We need the probability that text x is written in language L. Bayes’ formula turns it into something that can be estimated from data:

The denominator is the same for all languages and need not be computed when comparing. P(L) is the prior probability of the language: we have 1500 sentences per language, and it is the same for all. What remains is P(x | L), the probability of seeing exactly this text if it is in language L. It cannot be estimated from data: this phrase is most likely not in the training set. So a naive assumption is made: a text is a sequence of trigrams, and given the language each is chosen independently of its neighbours. Then

and each P(g | L) is estimated by counting: how many times trigram g occurred in texts of language L, divided by the number of all their trigrams. A repeated trigram enters the product as many times as it occurs in the text; such a model is called multinomial.

Naive Bayes chooses the class with the greatest probability by Bayes’ formula and makes one simplification: given the class, the features are considered independent. Then the probability of a text is the product of the probabilities of its features, and each of them is given by counting over the training examples. Training is counting, and the answer is a sum of logarithms.

The assumption is certainly false: neighbouring trigrams share two letters of three, and «вже» in a text can be followed only by a trigram starting with «же», not by any at all. Why a model with such an assumption gets 99% of languages right is worked out below. First, two places where the formula breaks if programmed literally.

Zero and smoothing

A trigram that did not occur in a language’s training data gets probability 0 and zeroes the whole product. One rare word, name or typo is enough for the language to be excluded, however much evidence there is for it. And if every language has such a trigram, there is no answer at all.

The cure is Laplace smoothing: α is added to every counter, as if every trigram of the vocabulary had been seen α more times,

where c_L(g) is how many times the language saw the trigram, N_L how many trigrams its texts have in all, and V how many distinct trigrams there are in the whole training set, 25,155. The denominator grows exactly enough for the probabilities still to sum to one. An unfamiliar trigram now costs a lot, but a finite amount.

Without smoothing 928 sentences of 2800, a third, get zero for all fourteen languages, and only 1856 are right. With any α > 0 from 2755 to 2780 are right: 2773 at α = 0.001, 2780 at α = 1, 2755 at α = 10. What matters is that there is an addition; how large it is hardly matters, as long as it does not start drowning out the counters themselves.

The rule of adding one was devised by Laplace for a problem he himself considered more of an exercise: what is the probability that the sun will rise tomorrow, if it has risen on each of n days? His answer is (n + 1)/(n + 2): as if one sunrise and one non-sunrise had been added to the observations. In his “Philosophical Essay on Probabilities” of 1814 he took five thousand years, 1,826,213 days, and got odds of 1,826,214 to one.

Logarithms instead of a product

The second trouble is the product itself. The average trigram of a Russian text has a probability of the order of 10^−3.4, and the product loses more than three decimal orders on every letter. The smallest positive double is about 4.9·10⁻³²⁴. The lower chart of the scene shows what happens: at the 97th trigram the product becomes exactly zero, and from then on all languages are equal. A hundred letters is one or two sentences.

A logarithm turns the product into a sum, and the sum of logarithms loses only seven or eight units per letter. The probability of 6276 characters of Russian test sentences is 10^−21,386, and this number is calmly stored as −49,243.8. Languages can be compared directly by the sums: the logarithm is increasing, and a larger sum means a larger probability.

6276 characters of Russian: the product of probabilities is 0 from trigram 97 on; the sum of logarithms is -49243.8, that is 10^-21386.3

Code

Training is a dictionary of counters for each language. The answer is, for each language, the sum of log(c + α) − log(N_L + αV) over the trigrams of the text, plus the logarithm of the prior probability. The texts in the file are already cleaned, lowercase letters and spaces instead of everything else, so Python and Go cut the same characters into trigrams. In Go the text is cut by runes, not bytes: a Cyrillic letter takes two bytes in UTF-8.

«ти вже попоїла»: ukr -109.06, bul -125.70, rus -126.55
«ты уже поела»: rus -90.57, bel -106.20, ukr -110.49
«мы не забылі»: bel -86.50, rus -93.95, kaz -107.58

The Ukrainian and Russian phrases saying the same thing (“you have already eaten”) differ in the letters «и» and «ы», «ї», the words «вже» and «уже», and each leads its nearest rival by more than fifteen units of logarithm. The Belarusian «мы не забылі» (“we have not forgotten”) consists almost entirely of trigrams common in Russian too, and it is given away by its last letters «лі»: a lead of 7.45, which is still odds of about 1700 times.

Why the naive assumption works

Take two languages, A and B, and look at the difference of their logarithms. Each trigram g of the text adds log P(g | A) − log P(g | B), as many times as it occurs.

This is the same form as logistic regression: a weighted sum of features and a threshold. The difference is where the weights come from. Logistic regression fits them all together so as to predict the classes correctly, and thereby takes into account that features are related. Naive Bayes computes each weight separately, from frequencies in one class and in the other, as if the other features did not exist. If features duplicate each other, it counts the same evidence several times.

For choosing the class this rarely matters: the sign of the sum decides, and double counting of evidence inflates the sum but seldom changes its sign. Pedro Domingos and Michael Pazzani analysed this rigorously in 1997: naive Bayes chooses the best class in a far wider range of problems than those where the features really are independent. But the probabilities it names are wrong: too confident.

When the model is 99.99% sure or more, as it is for 2618 sentences of 2800, it is always right. But among those where it says “from 90 to 99%”, 96.6% on average, only 79.5% of answers are right. We know the reason: neighbouring trigrams share two letters, and each letter votes almost three times. Divide the logarithms by two, as if there were half as much independent evidence; move T. The confidence in the same bin becomes 96.3% and the accuracy 99.1%: the correction is crude, and now the model is even more modest than it should be. But not a single answer changed: all sums were divided by the same number, and the order of languages is the same.

T = 1: confidence   texts  said     right
  0.0000-0.9000     36   73.931%   69.44%
  0.9000-0.9900     39   96.557%   79.49%
  0.9900-0.9990     47   99.649%   97.87%
  0.9990-0.9999     60   99.960%  100.00%
  0.9999-1.0000   2618  100.000%  100.00%

Hence a practical rule. If only the answer is needed, which language, spam or not, naive Bayes is good and cheap. If the probability itself is needed, for example to decide what to do with a message that is spam with probability 95%, its probabilities cannot be trusted: in 2005 Niculescu-Mizil and Caruana showed on eight problems that it pushes probabilities towards 0 and 1. Then its output is calibrated separately, or logistic regression is used. Andrew Ng and Michael Jordan compared this pair in 2001, both theoretically and on data: naive Bayes reaches its accuracy limit faster and wins when examples are few, while logistic regression on large data usually arrives at a smaller error.

What it costs

Training is one pass over the texts: O(N) for N characters, one dictionary operation per trigram. The memory is one counter for each “language, trigram” pair that occurred at least once; this is noticeably less than 25,155 × 14, because most trigrams occur in few languages. An answer for a text of m characters is L·m dictionary lookups and logarithms for L languages; the logarithms can be computed in advance and stored instead of the counters. The time grows linearly with the length of the text:

From the fact that the model is counters follows a property most other methods lack: it can be trained and untrained one example at a time. A user marked a message as spam: add its words to the spam counters; made a mistake and undid it: subtract them. No recomputation, no pass over old data. This is how mail filters that adapt to one person’s messages work; the article’s second problem is about this. The only subtlety is V, the number of distinct features in the vocabulary: it changes when a feature appears for the first time or disappears entirely, and it has to be maintained too.

Where it works

The best-known story of naive Bayes is spam. In 1998 Mehran Sahami, Susan Dumais, David Heckerman and Eric Horvitz described a Bayesian filter for junk mail based on the words of a message. The approach became widely known after Paul Graham’s 2002 essay “A Plan for Spam”: by his account, on his own mail a slightly refined Bayesian filter let through fewer than 5 spam messages out of 1000 and sent not a single wanted one to spam. Strictly speaking, Graham combined word probabilities in his own way, and there was debate about how Bayesian his method was; but after the essay filters appeared that followed it directly, such as SpamBayes.

Spammers responded by attacking the very adding up of evidence: they began appending words common in normal mail to their messages. Daniel Lowd and Christopher Meek measured in 2005 what this costs: without access to the filter, adding at most 150 such words is enough for half the spam the filter used to stop to get through, and if messages can be tested against the filter itself, 30 suffice. This holds for both naive Bayes and logistic regression: both models add up evidence linearly. Frequent retraining helps: a filter that learns from fresh messages also learns the spammers’ new “good” words.

Identifying language by character n-grams is the second classic task. Shuyo Nakatani’s language-detection library of 2010 is naive Bayes over combinations of one to three letters; according to the author’s slides, it distinguished 49 languages with accuracy above 99%. And scikit-learn has MultinomialNB, exactly the model in the listing, with smoothing α = 1 by default; it is often taken first to see how much can be squeezed out of texts at all, before turning to more complex models.

History

Thomas Bayes’ work, where the formula for inverse probability appeared, was found among his papers after his death by Richard Price and published in 1763; Laplace gave it its general form in 1774. The first to try classifying texts by Bayes’ formula was apparently Melvin Maron: in 1961 his program assigned abstracts of papers on computing to 32 categories by the clue words that occurred in them. Two years later Frederick Mosteller and David Wallace applied a Bayesian approach to a dispute over authorship: twelve of the Federalist papers of 1787–1788 had been attributed both to Alexander Hamilton and to James Madison. Mosteller and Wallace looked not at topics but at function words that a writer chooses without thinking, upon, whilst and others, and concluded that all twelve papers were written by Madison.

Problems

The first problem is a complete language identifier: counting, smoothing and logarithms, without which a long text cannot be recognised. In the second, examples come and go on the fly, and recomputing everything from scratch takes too long.