Introduction to Machine Learning
Generative Learning
and Language
From counting words to predicting the next one
Spam vs Not Spam
not spam
"Hey, are we still meeting at 4? I pushed the notes to the repo, take a look before then."
spam
"CONGRATULATIONS! You have WON a free entry to our weekly prize. Text WIN to claim your money now!"
A classifier reads the words and decides. But a
message is not a number, so what is \(x\)?
Language: One-Hot Word Representation
A dictionary
Fix a vocabulary. Each word becomes a vector of zeros with a single 1 in its own slot.
A sentence
Becomes a matrix: one one-hot column per word, in order.
\( x_1, x_2, \dots, x_n \)
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?
\( P(x_j \mid y) \)
Ask of every word
\( P(\text{free} = 1 \mid \text{spam}) = ? \)
\( P(\text{free} = 1 \mid \text{not spam}) = ? \)
counted from the six emails above
The Naive Assumption
We want the probability of a whole message, not one word:
\( P(x_1, x_2, \dots, x_n \mid y) \)
There are \(2^n\) possible messages, so we can never count them all.
Assume the words are conditionally independent given the label:
Naive Bayes assumption
\( \displaystyle P(x_1, \dots, x_n \mid y) = \prod_{j=1}^{n} P(x_j \mid y) \)
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) \).
\( \displaystyle P(y \mid x_1, \dots, x_n)
= \frac{P(x_1, \dots, x_n \mid y)\, P(y)}{P(x_1, \dots, x_n)} \)
Prior
\( P(y) \): how common spam is before reading a single word.
Evidence
\( P(x) \) is the same for both labels, so for a decision it cancels.
For a Given Dataset
\( \{ (x^{(i)}, y^{(i)}) \}_{i=1}^{M} \), estimate each piece by counting.
\( \displaystyle P(y = 1) = \frac{\sum_{i=1}^{M} \mathbb{1}[y^{(i)} = 1]}{M} \)
\( \displaystyle P(x_j = 1 \mid y = 1)
= \frac{\sum_{i=1}^{M} \mathbb{1}[x_j^{(i)} = 1 \wedge y^{(i)} = 1]}
{\sum_{i=1}^{M} \mathbb{1}[y^{(i)} = 1]} \)
That is the whole training procedure: count, divide,
store. No gradient descent anywhere.
Generative and Discriminative
Discriminative
Learns \( P(y \mid x) \) directly: draw the boundary.
logistic regression
Generative
Learns \( P(x \mid y) \) and \( P(y) \), then applies Bayes rule: model what each class
looks like, and you can generate new examples from it.
naive Bayes, Gaussian discriminant analysis
Also worth knowing
Gaussian discriminant analysis makes the same move with continuous
features: assume each class is a Gaussian cloud, fit its mean and covariance, then use Bayes rule.
With shared covariance, the boundary it draws is exactly a straight line.
Auto-Regressive Language Models
Same counting idea, one step further: predict the next word.
\( \displaystyle P(x_1, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_1, \dots, x_{i-1}) \)
The context is too long to count, so an n-gram
model truncates it:
\( P(x_i \mid x_1, \dots, x_{i-1}) \approx P(x_i \mid x_{i-k}, \dots, x_{i-1}) \)
\( P(\text{apple} \mid \text{I ate an}) = \dfrac{\text{Count}(\text{I ate an apple})}{\text{Count}(\text{I ate an})} \)
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
\( x_1, \dots, x_{100} \)
\( \longrightarrow \)
big function
\( \xrightarrow{\;\text{softmax}\;} \)
\( p(x_{101} \mid x_1, \dots, x_{100}) \)
Summary
Words to numbers
one-hot per word, then a bag of words
drops the order and keeps presence
Naive Bayes
\( P(x \mid y) = \prod_j P(x_j \mid y) \)
wrong but useful, and trained by counting
Bayes rule
\( P(y \mid x) \propto P(x \mid y) P(y) \)
turns what we can count into what we want
The through line
an n-gram counts the next word;
an LLM approximates the same probability