Naive Bayes

Classifying by counting words.

On this page

1 Sorting posts by counting words 2 Documents are bags of words 3 Bayes rule, then the naive part 4 Fitting is counting, scoring is a sum 5 Scoring one real post, word by word 6 Naive Bayes in practice 7 When naive Bayes misleads 8 Finding clumps when nothing is labeled 9 References

1 Sorting posts by counting words

To sort 15,076 training posts from 20 newsgroups (topic forums on Usenet, an early internet discussion network) without reading them, count: a post about "openwindows" and "motif" goes to the pile that uses those words most. That is naive Bayes, Bayes rule from Probability and Bayes Rule applied to a document as a bag of words. Fitting is one counting pass over the training posts; after that, scoring a new post is one pass over its words.

Figure 1. From counting words to a prediction, with what each step buys.

2 Documents are bags of words

A post loses its word order and becomes one row of counts, a column per vocabulary word. The 20 Newsgroups corpus (Lang 1995) gives 15,076 training posts, one row each, over the 10,000 most common words.

Figure 2. One sentence becomes a row of 10,000 counts, and almost all of them are 0.

3 Bayes rule, then the naive part

Score each topic, or class, by how common it is times the chance of every word in the post, then pick the highest score.

A class scores high when it is common and its posts use the document’s words often. c is a class. d is a document.

P(c | d) ∝ P(c)

· Π_w P(w | c)

The left side is the answer, how likely class c is given document d. The prior P(c) is how common the class is before any word is read. The bar reads "given", so P(w | c) is the chance of word w in class c, and the big Π multiplies it over every word w in the document: the likelihood. A word the class uses often multiplies its score by a large factor and a word it rarely uses by a tiny one, so every word moves every class. The ∝ sign reads "is proportional to": the missing factor, the chance of the document itself, is the same for every class, so the ranking is right. The product is the naive part: it treats words as independent once the class is known, which is false ("san" and "francisco" travel together) and works anyway.

My naive Bayes notebook (in my Machine-Learning-Concepts repo on GitHub) fits this model on the 15,076 training posts. There posts in comp.windows.x, the newsgroup for the X Window System (the graphics system of Unix workstations), are 0.0513 of the training set, so its prior is 0.0513.

Each word chance is a count share; unsmoothed, it is the maximum likelihood estimate (see Maximum Likelihood and EM). Laplace smoothing adds a little to every count.

A word's likelihood in a class is its smoothed share of the class's words.

P(w | c) = count(w, c) + αN_c + α·V

count(w, c) is how many times word w appears in class c’s training posts. N_c is the class’s total word count. α is the smoothing constant, added to every word’s count. Without the α terms the fraction is the plain share, the maximum likelihood estimate. V is the vocabulary size, 10,000 here. Adding α to each of V counts adds α times V to the total, so the shares still add to 1. A word the class never used now gets a small share instead of 0, and a bigger α pulls every word toward the same share.

Figure 3. 1One zero count zeroes the score. 2Adding α = 0.1 (purple) fixes it.

Multiplying a thousand word chances of 1e-4 underflows: the product prints 0.0, while the sum of logs stays usable.

import numpy as np
word_probs = np.full(1000, 1e-4)
product = np.prod(word_probs)
log_sum = np.log(word_probs).sum()
print(product, log_sum)  # 0.0 and about -9210.34

Each class is scored in log space, where the product of word chances becomes a sum that cannot underflow.

score(c) = log P(c)

+ Σ_w n_w·log P(w | c)

n_w is how many times word w appears in the document. Σ adds over the vocabulary, and words not in the document have n_w = 0, so they drop out. Each appearance adds the word’s log chance once, so a word said twice counts twice. Log keeps the order of the scores, so the class with the largest score wins, the same winner as the product.

4 Fitting is counting, scoring is a sum

This snippet fits naive Bayes on four toy posts by counting words per class, then scores a new post with the log score card in Section 3.

import numpy as np
alpha = 0.1
# rows are posts; columns count "port", "motif", "puck"
counts = np.array([[2, 1, 0], [1, 2, 0], [0, 0, 3], [0, 1, 2]])
classes = np.array([0, 0, 1, 1])
ids = np.unique(classes)
log_prior = np.log([np.mean(classes == c) for c in ids])
count_wc = np.array([counts[classes == c].sum(0) for c in ids])
smooth = count_wc + alpha
log_pwc = np.log(smooth / smooth.sum(1, keepdims=True))
doc = np.array([1, 1, 0])
score = log_prior + doc @ log_pwc.T
print(ids[score.argmax()])  # 0, windows.x

1Builds four toy posts as word-count rows, like the row in Figure 2, with their class labels.
2Takes the log prior log P(c), eq card in Section 3, line 1.
3Adds α to each count and divides, the smoothing eq card in Section 3.
4Scores the new post and picks the top class, the score eq card in Section 3, lines 1 and 2.

5 Scoring one real post, word by word

Test post 20 in my notebook is held out from training. It asks how to port programs written for OS/2, an old IBM operating system, to the X Window System, using OpenWindows or Motif, two X toolkits. The notebook puts it in comp.windows.x, its real newsgroup.

smoothing α 0.10

Figure 4. "port" lifts comp.windows.x to 0.38, "motif" to 0.91. Scored with 61 toy posts written for this page, not the notebook’s training split.

6 Naive Bayes in practice

A scikit-learn pipeline turns text into counts and fits MultinomialNB; fit runs once on the training posts, predict scores each new post.

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
from sklearn.pipeline import make_pipeline
train_docs = [
    "port the motif applications to x",
    "openwindows emulator for sun workstations",
    "the goalie stopped the puck",
    "power play goal in the third period",
]
train_labels = ["comp.windows.x", "comp.windows.x", "rec.sport.hockey", "rec.sport.hockey"]
model = make_pipeline(CountVectorizer(), MultinomialNB(alpha=0.1))
model.fit(train_docs, train_labels)
print(model.predict(["need help to port motif code"]))

1Lists four toy training posts and their labels.
2Builds the pipeline, where CountVectorizer makes the count rows of Figure 2, and MultinomialNB holds α.
3Counts words per class in one pass, the smoothing eq card in Section 3.
4Scores a new post with the score eq card in Section 3 and prints the top class.

CountVectorizer learns the vocabulary from training posts only. Naive Bayes needs raw word counts, so the pipeline has no scaler.

step	when, on what, and its cost
`fit`	Once, one counting pass over the training posts, linear in their length.
`predict`	Per new post, one score per class, one term per word of the post.
state	Log priors (`class_log_prior_`) and log word chances per class (`feature_log_prob_`).

setting	raise it, lower it	default
`alpha`, `α` in the smoothing card	Up pulls every word toward share 1/`V`; huge `α` leaves only the prior deciding. Down follows raw counts; `α` = 0 lets one unseen word zero a class.	1.0 (my notebook: 0.1)
`fit_prior`, `P`(`c`) in the score card	True learns class shares; False makes all priors equal.	True

Defaults from the MultinomialNB docs; cost from Manning, Raghavan and Schütze (2008). Gotchas are in Section 7.

7 When naive Bayes misleads

Words that travel together, like "san" and "francisco", count as separate evidence, so probabilities come out too close to 0 or 1. Trust the ranking more than the numbers.
Words outside the vocabulary are ignored, so a post made of rare words carries little evidence and the prior decides.

8 Finding clumps when nothing is labeled

With no labels at all, k-means finds the clumps, each point joining its nearest center.

9 References

Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 13.2. Cambridge University Press. (training and testing cost)
Lang, K. (1995). NewsWeeder: Learning to filter netnews. Proceedings of the Twelfth International Conference on Machine Learning. (the 20 Newsgroups corpus used throughout this page)
Anushiravani, R. Machine-Learning-Concepts (GitHub), naive Bayes notebook. (the run on 15,076 training posts, its vocabulary, prior and α, and test post 20)