Naive Bayes for Text

A Naive Bayes classifier is a probabilistic model that assigns a document to the class $c$ maximizing the posterior probability $P(c \mid d)$, where $d$ is the document. By Bayes' rule,

Since $P(d)$ is the same for every candidate class, classification only requires comparing $P(d \mid c)\,P(c)$ across classes — the denominator can be dropped entirely. $P(c)$ is the prior, the overall frequency of class $c$ in the training data. $P(d \mid c)$ is the likelihood, the probability the model assigns to generating exactly this document under class $c$. The likelihood term is where the "naive" assumption enters. Representing $d$ as a bag-of-words sequence of tokens $w_1, w_2, \dots, w_n$, the model assumes each word's occurrence is conditionally independent of every other word, given the class:

This is false in general — "not" and "good" are strongly correlated in sentiment text — but it converts an intractable joint distribution over exponentially many word combinations into $|V|$ (vocabulary size) independent one-dimensional distributions, each estimable from simple word counts. The full decision rule, called the Maximum A Posteriori (MAP) class, is:

Two design choices complete the model. First, the multinomial event model treats a document as a sequence of word draws from a per-class die with $|V|$ faces, so word frequency matters — a word appearing three times contributes three factors. This is the standard choice for text and the one developed below. An alternative, the Bernoulli event model, only asks whether each vocabulary word is present or absent, ignoring repeat counts; it tends to work better on very short documents. Second, because every $P(w_i \mid c)$ is a fraction less than one, the product over a long document underflows floating-point precision, which is why real implementations always work in log-space, turning the product into a sum of log-probabilities.

Training estimates two sets of parameters from labeled data: class priors and word likelihoods. For each class $c$, the prior is the fraction of training documents labeled $c$:

For each word $w$ and class $c$, the likelihood is estimated by counting how often $w$ occurs across all documents labeled $c$, relative to the total word count in class $c$:

This raw maximum-likelihood estimate has a fatal flaw: if a word never appears in class $c$'s training documents, $\hat{P}(w \mid c) = 0$, and because the model multiplies probabilities, a single zero factor forces the entire class likelihood to zero — no matter how strongly every other word favors $c$. Laplace (add-one) smoothing fixes this by pretending every vocabulary word was seen one extra time in every class:

The $+|V|$ in the denominator is required so the smoothed probabilities still sum to one over the vocabulary — adding 1 to every one of the $|V|$ numerators must be balanced by adding $|V|$ to the shared denominator. At test time, an unseen document is tokenized, out-of-vocabulary words are dropped (the model has no parameters for them), and the remaining words are scored against every class using log-probabilities, and the arg-max class is returned. ``` // ---------- TRAINING ---------- function TRAIN_NAIVE_BAYES(documents, labels, classes): V := set of all distinct words seen in documents // vocabulary N_total := number of documents for each class c in classes: N_c := number of documents with label c logprior[c] := log(N_c / N_total) // concatenate all class-c documents into one "mega-document" text_c := concatenation of documents where label == c for each word w in V: count[w][c] := number of occurrences of w in text_c total_c := sum over w in V of count[w][c] for each word w in V: // Laplace smoothing: +1 numerator, +|V| denominator loglikelihood[w][c] := log( (count[w][c] + 1) / (total_c + |V|) ) return logprior, loglikelihood, V // ---------- INFERENCE ---------- function PREDICT(doc, classes, logprior, loglikelihood, V): best_class := null best_score := -infinity for each class c in classes: score := logprior[c] for each word w in TOKENIZE(doc): if w in V: // ignore out-of-vocabulary words score := score + loglikelihood[w][c] // else: skip — no evidence for or against any class if score > best_score: best_score := score best_class := c return best_class ``` Note the invariant maintained by training: after smoothing, $\sum_{w \in V} \hat{P}(w \mid c) = 1$ for every class $c$, since

This guarantees each class's likelihood model is a genuine probability distribution over the vocabulary, not merely a scoring heuristic.

Training time is $O(D \cdot L)$, where $D$ is the number of training documents and $L$ is the average document length, since each word token requires a single increment to a count table; the smoothing pass afterward touches every (word, class) pair once, adding $O(|V| \cdot |C|)$. Total training time is $O(D L + |V||C|)$, linear in the size of the corpus — no iterative optimization, no gradient descent, no convergence loop. This is a major practical advantage over discriminative alternatives like logistic regression, which require multiple passes over the data to converge.

Training space is $O(|V| \cdot |C|)$ to store the likelihood table, plus $O(|C|)$ for priors — the model size depends only on vocabulary and class count, not on the number of training documents, so it does not grow as more data arrives (only the counts inside the table become more accurate).

Inference time per document is $O(L' \cdot |C|)$, where $L'$ is the length of the test document, since the algorithm performs one table lookup and addition per word per class. This is a single linear pass with no search, making Naive Bayes attractive for high-throughput filtering systems.

Correctness argument. The MAP decision rule is provably Bayes-optimal — it minimizes expected classification error — if the model's assumed joint distribution $P(c)\prod_i P(w_i \mid c)$ equals the true data-generating distribution $P(c, w_1, \dots, w_n)$. The independence assumption is the model's only approximation; everything else (Bayes' rule, arg-max decision) is exact probability theory. The practical claim is weaker but still meaningful: even when features are correlated, the arg-max decision can remain correct as long as the ranking of classes by score is preserved, because classification only needs the correct class to have the highest score, not an accurate probability value. This explains empirically why Naive Bayes performs far better as a classifier than its probability estimates would suggest — the miscalibration from ignoring correlation often biases all classes' scores in a similar direction, leaving the relative ranking intact.

Honest tradeoffs. Correlated features that consistently co-occur get double-counted — if "not" and "good" always appear together in negative reviews, the model effectively counts that evidence twice, overconfidently favoring whichever class that pair supports. Naive Bayes also produces poorly calibrated probability estimates (often extremely close to 0 or 1) even when its class decisions are accurate, so its raw probability outputs should not be trusted as confidence scores without recalibration. On large datasets with abundant training examples, discriminative classifiers that model $P(c \mid d)$ directly (e.g., logistic regression, or later, neural classifiers) typically overtake Naive Bayes in accuracy, because they can adjust for feature correlations that Naive Bayes cannot represent. Naive Bayes's advantage is sharpest precisely when training data is scarce, since it needs only simple counts and never overfits the way a high-parameter discriminative model can.

Consider a two-class sentiment task with a tiny training set (following the standard textbook-style illustration used to sanity-check implementations):

Vocabulary $V$ (unique words across all documents, 20 words); class counts: $N_- = 3$, $N_+ = 2$, $N_{\text{total}} = 5$.

Priors:

Suppose the negative-class mega-document has 14 word tokens and the positive-class mega-document has 9 word tokens (small numbers chosen for hand-tracing). With $|V| = 20$:

Now classify the test sentence "predictable with no fun". Suppose "with" never appeared in training (out-of-vocabulary, so it is dropped), and the remaining words have these smoothed counts:

Score for negative class (log base 10, for readability):

Score for positive class:

Since $-4.216 > -4.483$, the model predicts negative. This is sensible: "predictable" and "no" are strong negative-class signals present in training, and even though "fun" leans positive, it alone cannot outweigh two negative-leaning words plus the negative class's higher prior. Notice also that "with," an out-of-vocabulary word, contributed nothing to either score — the model simply has no opinion about words it never saw during training, which is a deliberate and correct behavior, not a bug.

The probabilistic engine behind Naive Bayes is Bayes' theorem itself, but its application to automated text categorization crystallized during the growth of statistical NLP and information retrieval in the late twentieth century, when researchers needed fast, trainable classifiers for exploding volumes of digital text — email, newswire, and web documents.

Naive Bayes remains embedded in production systems where speed, interpretability, and low data requirements outweigh the accuracy gains of heavier models. Early and many current email spam filters use Naive Bayes variants because the classifier retrains instantly as users flag new spam, needing no gradient-based fine-tuning. Sentiment analysis baselines in industry and academic benchmarks routinely report Naive Bayes accuracy first, since any more complex model must justify its added cost by beating this cheap reference point — a core habit taught alongside Text Classification Fundamentals. Language identification systems (detecting whether a string of text is English, French, or Japanese) often use character-level or word-level Naive Bayes because the independence assumption is nearly harmless when the discriminating signal is simple character or n-gram frequency. Document-routing systems in customer-support platforms, and simple content-moderation triage layers, use Naive Bayes as a fast first-pass filter before escalating uncertain cases to slower, more accurate models. Pedagogically, Naive Bayes is the cleanest bridge from the Bag-of-Words Model representation to fully generative sequence models: the next conceptual step, Hidden Markov Models, keeps the same "independent emissions given a hidden variable" structure but adds a Markov chain over the hidden states themselves, turning a single hidden class into a sequence of hidden states that evolve over time.

Ask the tutor: How would the decision rule and training procedure change if we wanted to use a Bernoulli event model instead of the multinomial one?