Naive Bayes & N-Grams

Two text classifiers built from scratch — a naive Bayes bag-of-words model and a set of n-gram language models — that learn word statistics from a corpus and label unseen documents by them. Both estimate probabilities by counting, and both smooth those counts so an unseen word does not zero out a whole document.

Naive Bayes picks the most probable class. For a document $d$ and classes $c$, the classifier returns the maximum a posteriori class. Dropping the shared denominator and assuming words are conditionally independent given the class,

where $P(c)$ is the class prior and $P(w_i\mid c)$ is the likelihood of word $w_i$ under class $c$. The product hides a modeling choice: the bag-of-words representation treats a document as its multiset of word counts with position discarded, so $P(d\mid c)={\prod }_{i}P(w_i\mid c)$ scores each token as an independent draw from the class's word distribution. That independence is wrong — words in text are correlated — but it keeps estimation to simple counts and still classifies well. Products of many small probabilities underflow, so the implementation works in log space, where the product becomes a sum: $\log P(c)+{\sum }_i\log P(w_i\mid c)$, and the $\mathrm{argmax}$ is unchanged.

Smoothing handles unseen words. A word absent from a class in training gives $P(w\mid c)=0$ and annihilates the product. Add-$k$ (Laplace) smoothing shifts every count up by $k$:

with $V$ the vocabulary. The numerator keeps an unseen word from zeroing the whole product, and the matching term in the denominator keeps the row summing to one, so smoothing rescues the estimate without breaking it into an improper distribution. Small $k$ trusts the counts; large $k$ pulls every word toward uniform.

For tasks like sentiment, whether a word appears matters more than how many times. Boolean (binary) naive Bayes clips each document's counts to presence or absence, $\min (\mathrm{count}(w,d),1)$, before estimating and scoring, so a review repeating great ten times cannot swamp the decision on its own. On short texts this variant often edges out the count-based model.

The classifier comes together as four counting steps:

• Tokenize. Split each document into words and reduce it to its bag of counts.
• Estimate the prior. Set $P(c)$ from the fraction of training documents in each class.
• Estimate the likelihoods. Compute each $P(w\mid c)$ as an add-$k$ smoothed count ratio over the class's text.
• Score. Sum $\log P(c)+{\sum }_i\log P(w_i\mid c)$ for every class and return the $\mathrm{argmax}$.

N-grams model the next word. The n-gram side estimates the probability of a sequence with the chain rule under a Markov assumption — each word depends only on the previous $n-1$:

Each conditional is a smoothed count ratio, exactly as above but keyed on the preceding context. Larger $n$ captures more context but fragments the counts, so unigram, bigram, and trigram models trade coverage against sharpness. Used as a classifier, the model trained on each class scores a test document, and the class whose model assigns higher probability wins.

You can read the full report.