Five questions for today

1. 1Words as dataHow does a message become numbers?
2. 2Count, then flipHow do you classify by counting?
3. 3Model each classWhat if you modeled what each class looks like?
4. 4Generating languageWhat does it take to write the next word?
5. 5In codeWhat does Naive Bayes look like in fifteen lines?

Three real datasets: 5,574 text messages people actually received, the Palmer penguins from the data lecture, and a whole book, Gibran's The Prophet.

Spam vs Not Spam

A classifier reads the words and decides. But a message is not a number, so what is \(x\)?

5,574 real text messagesThe SMS Spam Collection, labelled by hand

Data: Almeida, Gómez Hidalgo and Yamakami, Contributions to the study of SMS spam filtering, DocEng 2011, via the UCI repository (CC BY 4.0). Messages shown are drawn at random.

Language: One-Hot Word Representation

Bag of Words

Drop the order. Ask only: is this word present? Define \( x_j = 1 \) or \( x_j = 0 \).

Each email is now a row of zeros and ones, and a label \(y\): the same table shape we have used since week one.

What Are the Relevant Probabilities?

The Naive Assumption

We want the probability of a whole message, not one word:

There are \(2^n\) possible messages, so we can never count them all. Assume the words are conditionally independent given the label:

It is wrong: "prize" and "win" travel together. It is also enough, which is the useful kind of wrong.

Bayes Rule Turns It Around

We can count \( P(x \mid y) \). What we want is \( P(y \mid x) \).

For a Given Dataset

\( \{ (x^{(i)}, y^{(i)}) \}_{i=1}^{M} \), estimate each piece by counting.

That is the whole training procedure: count, divide, store. No gradient descent anywhere.

Naming the parameters: \(\phi\)Every probability the model needs is one number to learn

Finding \(\phi\): maximum likelihood is countingWhy the formulas on "For a Given Dataset" are the best possible values

Every word casts a voteType a message. The filter is trained on 4,459 real ones.

Where the vote comes fromFrom Bayes' rule to a sum of bars, on the message "Congratulations! You won a prize, call now to claim"

The word it never sawCounting gives zero, and zero ruins a product

Two ways to generate an emailTwo event models: two stories of how a message gets written

Neither is best at everything: the Bernoulli model never flags a friend, and lets more spam through. Which mistake is worse is a decision, not a statistic (see the logistic regression lecture).

Bernoulli or multinomial, in detailThe same messages, two different random experiments

Rule of thumb: presence is the signal in short texts, frequency in long documents, which is why the multinomial is the usual default for text. In these messages 1,964 of 4,459 repeat some word, and the multinomial catches more spam (the table on the last slide).

Generative and Discriminative

A Gaussian in two dimensionsShape it: two spreads and a correlation

Gaussian discriminant analysis, on penguinsAdelie and Chinstrap, by their bills (the data lecture's penguins)

one shared \(\Sigma\)one \(\Sigma\) per species show logistic regressionGenerate 24 penguins

Bill length: along the top ridge. Bill depth: its height. Adelie is \(y = 0\), Chinstrap \(y = 1\); no Gentoo today. Artwork by @allison_horst.

\( y \sim \text{Bernoulli}(\phi) \)
\( x \mid y = 0 \sim \mathcal{N}(\mu_0, \Sigma) \)
\( x \mid y = 1 \sim \mathcal{N}(\mu_1, \Sigma) \)

Fitting is counting again: \(\phi\) is the share of Chinstraps, \(\mu_k\) the average bill of each species, \(\Sigma\) the spread around those averages.

Hidden inside GDA: a logistic regression

Apply Bayes rule to the GDA model and simplify. With a shared \(\Sigma\), the quadratic terms cancel:

A stronger assumption learns faster...while it holds

Auto-Regressive Language Models

Same counting idea, one step further: predict the next word.

The context is too long to count, so an n-gram model truncates it:

An n-gram model of The ProphetKahlil Gibran, 1923: 13,000 words, learned by counting

Text: The Prophet, Project Gutenberg eBook 58585, public domain.

Large Language Models

• An LLM is also a probabilistic model for \( P(x_1, \dots, x_n) \)
• It approximates \( P(x_i \mid x_{i-k}, \dots, x_{i-1}) \), which is \(V^k\) dimensional, instead of counting it, where \(V\) is the size of the dictionary
• The embedding replaces the one-hot vector: \( x \in \mathbb{R}^d \) instead of a \(V\)-dimensional spike

Naive Bayes from scratchPress Run: real Python, on the 5,574 messages

import numpy as np, pandas as pd, re
from collections import Counter

sms = pd.read_csv('sms_spam.csv')
words = lambda s: re.findall(r"[a-z0-9']+", s.lower())
test = sms.index % 5 == 0                      # every fifth message is held out
train = sms[~test]

counts = {c: Counter(w for s in train.text[train.label == c] for w in words(s)) for c in ('spam', 'ham')}
vocab = set(counts['spam']) | set(counts['ham'])
total = {c: sum(counts[c].values()) for c in counts}
prior = {c: np.log((train.label == c).mean()) for c in counts}

def log_p(msg, c, alpha=1):                    # count, divide, store: that was training
    return prior[c] + sum(np.log((counts[c][w] + alpha) / (total[c] + alpha * len(vocab))) for w in words(msg) if w in vocab)

guess = [max(('spam', 'ham'), key=lambda c: log_p(m, c)) for m in sms.text[test]]
print('held-out accuracy:', np.mean(np.array(guess) == sms.label[test].values).round(4))
print('most spammy words:', sorted(vocab, key=lambda w: (counts['spam'][w] + 1) / (counts['ham'][w] + 1))[-8:])
print(log_p('Free entry! Text WIN to claim', 'spam') > log_p('Free entry! Text WIN to claim', 'ham'))
    

You should get 0.9848, the multinomial row of the table, and a spam list ending in 'won', 'prize', 'claim'. Try alpha=0 in log_p, and a message with a word only one class has seen.

Summary

What to take away

1. A discriminative model learns \(P(y \mid x)\). A generative one learns \(P(x \mid y)\) and \(P(y)\), then flips them with Bayes rule, and can draw new examples.
2. Naive Bayes trains by counting. Its assumption is false, words travel together, and it still catches 144 of 156 spam messages it never saw.
3. Zero counts are not impossibilities: Laplace smoothing adds imaginary sightings so one unseen word cannot decide everything.
4. GDA models each class as a Gaussian cloud; with a shared \(\Sigma\) its posterior is exactly a logistic regression. It learns faster from little data, and breaks when the clouds are not Gaussian.
5. An n-gram model writes by counting what came next. More context makes it fluent, then makes it copy: overfitting, in words.