Foundations of Machine Learning and NLP
Overview of Language Models: From N-grams to Neural LMs
This lesson explains the evolution of language models from simple n-gram models to modern neural approaches, providing the foundational reasoning behind how they predict text. Understanding these concepts is crucial because they form the backbone of how large language models (LLMs) process and generate human-like language, enabling you to debug, optimize, or even build your own. You’ll reach for this knowledge when designing tokenization strategies, evaluating model performance, or innovating beyond existing architectures.
What is a Language Model?
A language model is a system that assigns probabilities to sequences of words or tokens, enabling it to predict the likelihood of a given sequence appearing in natural language. The core idea is to capture the statistical patterns of language—how words tend to follow one another—so the model can generate or complete text in a way that mimics human writing. For example, if you’ve seen the phrase 'the cat sat on the' many times, a language model will assign a high probability to the next word being 'mat' because of its frequency in similar contexts. This probabilistic approach is why language models work: they don’t memorize text but instead learn distributions over sequences, allowing them to generalize to unseen data. The power of this lies in its simplicity—by counting and comparing sequences, the model can make surprisingly accurate predictions without understanding meaning in the human sense. This foundational concept applies whether you’re working with a 3-gram model or a billion-parameter neural network, as both rely on the same principle of sequence probability.
# Calculate the probability of a word given its history using a simple unigram model
from collections import defaultdict
# Sample corpus: a list of sentences
corpus = [
"the cat sat on the mat",
"the dog sat on the log",
"the cat slept on the mat"
]
# Build a unigram model: count word frequencies
word_counts = defaultdict(int)
total_words = 0
for sentence in corpus:
words = sentence.split()
for word in words:
word_counts[word] += 1
total_words += 1
# Calculate probability of a word
def unigram_probability(word):
return word_counts.get(word, 0) / total_words
# Example: Probability of 'mat'
print(f"P('mat') = {unigram_probability('mat'):.4f}") # Output: P('mat') = 0.2000N-grams: Capturing Local Word Dependencies
N-gram models extend the idea of unigrams by considering sequences of *n* words, allowing them to capture local dependencies in language. For example, a bigram model (n=2) looks at pairs of words, so it can learn that 'sat on' is a common sequence while 'sat the' is rare. This is powerful because language is inherently sequential—words don’t appear randomly but follow patterns based on grammar, syntax, and semantics. The reason n-grams work is that they approximate the conditional probability of a word given its history, using the chain rule of probability: P(w1, w2, ..., wn) = P(w1) * P(w2|w1) * P(w3|w1, w2) * ... * P(wn|w1, ..., wn-1). In practice, computing this for long sequences is intractable, so n-grams simplify it by assuming a word depends only on the previous *n-1* words (the Markov assumption). This trade-off between complexity and accuracy is why n-grams were the dominant approach for decades—they’re computationally efficient and surprisingly effective for many tasks, like autocomplete or spell-checking. However, their limitation is clear: they can’t capture long-range dependencies (e.g., a word at the start of a sentence influencing one at the end) because they only look at a fixed window of context.
# Build a bigram model and calculate conditional probabilities
from collections import defaultdict
corpus = [
"the cat sat on the mat",
"the dog sat on the log",
"the cat slept on the mat"
]
# Count bigrams and their preceding words
bigram_counts = defaultdict(lambda: defaultdict(int))
preceding_word_counts = defaultdict(int)
for sentence in corpus:
words = sentence.split()
for i in range(1, len(words)):
prev_word, current_word = words[i-1], words[i]
bigram_counts[prev_word][current_word] += 1
preceding_word_counts[prev_word] += 1
# Calculate P(current_word | prev_word)
def bigram_probability(prev_word, current_word):
return bigram_counts[prev_word].get(current_word, 0) / preceding_word_counts[prev_word]
# Example: P('mat' | 'on')
print(f"P('mat' | 'on') = {bigram_probability('on', 'mat'):.4f}") # Output: P('mat' | 'on') = 0.6667Smoothing: Handling Unseen N-grams
A critical challenge with n-gram models is their inability to handle sequences they’ve never seen before (zero-frequency problem). For example, if your training data never contains the bigram 'sat under', the model will assign it a probability of zero, which is unrealistic—language is creative, and new word combinations appear all the time. Smoothing techniques address this by redistributing probability mass from seen n-grams to unseen ones, ensuring no sequence gets a zero probability. The simplest method is *add-one smoothing* (Laplace smoothing), which adds 1 to every count, effectively pretending every possible n-gram appeared once more than it did. While this prevents zero probabilities, it’s overly aggressive and distorts the true distribution. A more refined approach is *Kneser-Ney smoothing*, which considers how often a word appears in novel contexts (e.g., 'under' might be rare after 'sat', but it’s common after other verbs). The reasoning behind smoothing is that language models must generalize beyond their training data, and smoothing provides a principled way to do this without overfitting. Without it, n-gram models would fail catastrophically on real-world text, where unseen sequences are inevitable. This concept carries over to neural models, where techniques like dropout or regularization serve a similar purpose.
# Implement add-one smoothing for a bigram model
from collections import defaultdict
corpus = [
"the cat sat on the mat",
"the dog sat on the log"
]
# Vocabulary: all unique words in the corpus
vocab = set()
for sentence in corpus:
vocab.update(sentence.split())
vocab_size = len(vocab)
# Count bigrams and preceding words with add-one smoothing
bigram_counts = defaultdict(lambda: defaultdict(int))
preceding_word_counts = defaultdict(int)
for sentence in corpus:
words = sentence.split()
for i in range(1, len(words)):
prev_word, current_word = words[i-1], words[i]
bigram_counts[prev_word][current_word] += 1
preceding_word_counts[prev_word] += 1
# Add-one smoothing: add 1 to every possible bigram
for prev_word in preceding_word_counts:
for word in vocab:
bigram_counts[prev_word][word] += 1
preceding_word_counts[prev_word] += vocab_size
# Calculate smoothed P(current_word | prev_word)
def smoothed_bigram_probability(prev_word, current_word):
return bigram_counts[prev_word][current_word] / preceding_word_counts[prev_word]
# Example: P('under' | 'sat') (unseen in corpus)
print(f"P('under' | 'sat') = {smoothed_bigram_probability('sat', 'under'):.4f}") # Output: P('under' | 'sat') = 0.0714Limitations of N-grams and the Need for Neural Models
Despite their utility, n-gram models have fundamental limitations that make them impractical for modern applications. First, they suffer from the *curse of dimensionality*: as *n* increases, the number of possible n-grams grows exponentially, requiring massive amounts of data to estimate probabilities accurately. For example, a 5-gram model over a vocabulary of 50,000 words would need to store 50,000^5 possible sequences—an astronomical number. Second, n-grams can’t capture long-range dependencies because they only consider a fixed window of context. In a sentence like 'The cat, which was black and fluffy, sat on the mat,' the relationship between 'cat' and 'sat' spans multiple words, but a bigram model would miss it entirely. Third, n-grams treat words as discrete symbols, ignoring semantic relationships (e.g., 'dog' and 'canine' are unrelated in an n-gram model, even though they mean the same thing). Neural language models address these issues by representing words as continuous vectors (embeddings) and using architectures like RNNs or Transformers to model dependencies across arbitrary distances. The key insight is that neural models learn *distributed representations*—words with similar meanings have similar vectors, and the model can generalize to unseen sequences by interpolating between known ones. This shift from counting to learning representations is what enables modern LLMs to achieve human-like fluency.
# Demonstrate the curse of dimensionality: count possible n-grams for a given vocabulary
import math
def count_possible_ngrams(vocab_size, n):
return vocab_size ** n
vocab_size = 50000 # Typical vocabulary size for a language model
# Calculate possible n-grams for n=1 to n=5
for n in range(1, 6):
possible_ngrams = count_possible_ngrams(vocab_size, n)
print(f"n={n}: {possible_ngrams:,} possible {n}-grams")
# Output:
# n=1: 50,000 possible 1-grams
# n=2: 2,500,000,000 possible 2-grams
# n=3: 125,000,000,000,000 possible 3-grams
# ... (exponential growth)Neural Language Models: Learning Distributed Representations
Neural language models (NLMs) revolutionized the field by replacing discrete n-gram counts with continuous, learned representations. The core idea is to map words to dense vectors (embeddings) in a high-dimensional space, where words with similar meanings are close to each other. For example, the vectors for 'dog' and 'canine' might be nearby, while 'dog' and 'pizza' are far apart. This is achieved by training the model to predict the next word in a sequence, adjusting the embeddings to minimize prediction error. The power of this approach lies in its ability to generalize: if the model learns that 'dog' and 'canine' appear in similar contexts, it can infer their semantic relationship even if it’s never seen them together explicitly. Architectures like RNNs (Recurrent Neural Networks) or Transformers then use these embeddings to model dependencies across the entire sequence, not just a fixed window. For instance, an RNN processes words one by one, maintaining a hidden state that acts as a memory of previous words, allowing it to capture long-range dependencies. The reason this works is that the model learns to compress the vast space of possible word sequences into a compact, continuous representation, enabling it to make predictions based on patterns it has never seen before. This is why modern LLMs can generate coherent paragraphs or answer questions about topics they weren’t explicitly trained on—they’ve learned the underlying structure of language, not just memorized sequences.
# Train a simple neural language model (word embeddings + softmax) using PyTorch
import torch
import torch.nn as nn
import torch.optim as optim
# Toy corpus: list of sentences
corpus = [
"the cat sat on the mat",
"the dog sat on the log",
"the cat slept on the mat"
]
# Build vocabulary and word-to-index mapping
words = set()
for sentence in corpus:
words.update(sentence.split())
vocab = {word: idx for idx, word in enumerate(sorted(words))}
vocab_size = len(vocab)
# Convert sentences to sequences of indices
sequences = []
for sentence in corpus:
seq = [vocab[word] for word in sentence.split()]
sequences.append(seq)
# Simple neural language model: embedding + linear layer
class NeuralLM(nn.Module):
def __init__(self, vocab_size, embedding_dim):
super().__init__()
self.embedding = nn.Embedding(vocab_size, embedding_dim)
self.linear = nn.Linear(embedding_dim, vocab_size)
def forward(self, x):
embeds = self.embedding(x)
return self.linear(embeds)
# Initialize model, loss, and optimizer
model = NeuralLM(vocab_size, embedding_dim=8)
criterion = nn.CrossEntropyLoss()
optimizer = optim.SGD(model.parameters(), lr=0.01)
# Train the model to predict the next word
for epoch in range(100):
total_loss = 0
for seq in sequences:
for i in range(len(seq) - 1):
input_word = torch.tensor([seq[i]], dtype=torch.long)
target_word = torch.tensor([seq[i+1]], dtype=torch.long)
optimizer.zero_grad()
output = model(input_word)
loss = criterion(output, target_word)
loss.backward()
optimizer.step()
total_loss += loss.item()
if epoch % 20 == 0:
print(f"Epoch {epoch}, Loss: {total_loss:.4f}")
# Example: Get embedding for 'cat'
cat_embedding = model.embedding(torch.tensor([vocab['cat']]))
print(f"Embedding for 'cat': {cat_embedding.detach().numpy()}")Key points
- Language models assign probabilities to sequences of words by learning statistical patterns from data, enabling them to predict or generate text.
- N-gram models approximate the probability of a word given its history by assuming it depends only on the previous n-1 words, making them computationally efficient but limited in context.
- Smoothing techniques like add-one or Kneser-Ney smoothing prevent n-gram models from assigning zero probabilities to unseen sequences, ensuring generalization to real-world text.
- The curse of dimensionality makes n-gram models impractical for large vocabularies or long sequences, as the number of possible n-grams grows exponentially with n.
- Neural language models overcome n-gram limitations by learning continuous word representations (embeddings) that capture semantic relationships and generalize to unseen sequences.
- Architectures like RNNs or Transformers use embeddings to model dependencies across arbitrary distances, enabling them to capture long-range context in language.
- The shift from counting (n-grams) to learning representations (neural models) is what enables modern LLMs to achieve human-like fluency and coherence.
- Understanding the trade-offs between n-grams and neural models helps you design better tokenization strategies, evaluate model performance, and innovate beyond existing architectures.
Common mistakes
- Mistake: Assuming n-gram models can capture long-range dependencies as effectively as neural language models. Why it's wrong: N-gram models rely on fixed-size windows of previous words, limiting their ability to model context beyond a few tokens. Fix: Use neural language models (e.g., RNNs, Transformers) that can learn dependencies across entire sequences through embeddings and attention mechanisms.
- Mistake: Ignoring smoothing techniques when training n-gram models on small datasets. Why it's wrong: Without smoothing (e.g., Laplace, Kneser-Ney), unseen n-grams in the training data will have zero probability, leading to poor generalization. Fix: Apply smoothing to assign non-zero probabilities to unseen n-grams and improve model robustness.
- Mistake: Treating language model training as a one-time task without iterative refinement. Why it's wrong: Language models often require multiple training cycles to adjust hyperparameters (e.g., learning rate, batch size) and improve performance. Fix: Use validation sets to monitor progress and fine-tune the model iteratively.
- Mistake: Overlooking the importance of tokenization in neural language models. Why it's wrong: Poor tokenization (e.g., splitting words arbitrarily) can break semantic meaning and hurt model performance. Fix: Use subword tokenization methods like Byte Pair Encoding (BPE) or WordPiece to handle rare words and morphological variations effectively.
- Mistake: Assuming larger models always perform better without considering computational constraints. Why it's wrong: While larger models may have higher capacity, they require more data, compute, and time to train, which may not be feasible for custom LLM projects. Fix: Start with smaller models and scale up only if necessary, balancing performance with resource limitations.
Interview questions
What is an n-gram language model, and why is it a foundational concept when creating your own LLM?
An n-gram language model is a probabilistic model that predicts the next word in a sequence based on the previous n-1 words. It's foundational because it introduces the core idea of modeling language as a sequence of tokens with conditional probabilities. For example, in a bigram model (n=2), the probability of 'dog' following 'the' is estimated from how often 'the dog' appears in training data. While simple, n-grams teach us about data sparsity and the need for smoothing techniques like Laplace or Kneser-Ney, which are crucial when building more complex models. They also demonstrate why larger context windows matter, setting the stage for neural approaches that can handle longer dependencies.
How would you implement a basic trigram model in code when creating your own LLM, and what limitations would you immediately notice?
Here's a Python implementation of a trigram model using maximum likelihood estimation: ```python from collections import defaultdict import math def train_trigram(corpus): counts = defaultdict(lambda: defaultdict(int)) context_counts = defaultdict(int) for i in range(len(corpus)-2): w1, w2, w3 = corpus[i], corpus[i+1], corpus[i+2] counts[(w1, w2)][w3] += 1 context_counts[(w1, w2)] += 1 return counts, context_counts def probability(counts, context_counts, context, word): return counts[context].get(word, 0) / context_counts.get(context, 1) ``` The immediate limitations you'd notice are: 1) Data sparsity - most trigrams never appear in training, 2) Fixed context window - can't handle long-range dependencies, 3) No semantic understanding - just memorizes patterns, and 4) Exploding vocabulary size - the model grows exponentially with n. These limitations motivate the transition to neural models that can generalize better and handle variable-length contexts.
Why did neural language models replace n-gram approaches when creating modern LLMs, and what key advantage do they offer?
Neural language models replaced n-gram approaches because they solve three fundamental problems: 1) They generalize to unseen sequences through distributed representations, 2) They handle variable-length contexts via recurrent or attention mechanisms, and 3) They capture semantic relationships through learned embeddings. The key advantage is their ability to learn continuous representations of words and contexts. For example, in an RNN-based LLM, the hidden state compresses all previous context into a fixed-size vector, allowing the model to make predictions based on arbitrarily long histories. This is impossible with n-grams, which suffer from the curse of dimensionality. Neural models also enable transfer learning - you can pre-train on large corpora and fine-tune for specific tasks, which is how modern LLMs achieve their versatility.
Compare feedforward neural language models with recurrent neural language models when creating your own LLM. What tradeoffs do you consider?
Feedforward neural language models process fixed-size windows of text, similar to n-grams but with learned representations. They're simple to implement and parallelizable, but limited by their fixed context window. For example: ```python # Feedforward model with window size 3 input = [w1_emb, w2_emb, w3_emb] # concatenated embeddings output = softmax(dense_layer(input)) ``` Recurrent models like RNNs or LSTMs process sequences step-by-step, maintaining a hidden state that theoretically captures all previous context. They handle variable-length input but suffer from vanishing gradients and are harder to parallelize. The tradeoffs are: 1) Context - RNNs win for long-range dependencies, 2) Training - feedforward models train faster, 3) Memory - RNNs require sequential processing, and 4) Implementation - feedforward models are simpler. Modern LLMs often combine both approaches, using feedforward layers within transformer architectures that use attention to get the best of both worlds.
Explain how attention mechanisms improved language models when creating your own LLM, with a focus on the self-attention implementation details.
Attention mechanisms revolutionized language models by allowing each token to dynamically focus on all other tokens in the sequence, solving the fixed-context problem of both n-grams and RNNs. In self-attention, we compute three vectors for each token: query (Q), key (K), and value (V). The attention scores are calculated as: ```python # scaled dot-product attention scores = softmax(Q @ K.T / sqrt(d_k)) @ V ``` This means each word's representation becomes a weighted sum of all words' values, where the weights depend on how well the query matches each key. The key improvements are: 1) Parallel processing - all tokens are processed simultaneously, 2) Variable context - attention weights adapt to each input, 3) Long-range dependencies - direct connections between distant tokens, and 4) Interpretability - attention weights show what the model focuses on. For example, in the sentence 'The cat sat on the mat', the word 'sat' might attend strongly to both 'cat' and 'mat', capturing their relationship regardless of distance.
When creating your own LLM from scratch, how would you design the training process to handle the challenges of neural language modeling? Walk through the key components and their purposes.
Designing the training process requires addressing several challenges: 1) **Data Preparation**: Start with a large, clean corpus and tokenize it using subword algorithms like BPE or SentencePiece to handle rare words. This gives you a vocabulary of ~30-50k tokens. 2) **Model Architecture**: Use a transformer with multiple layers (e.g., 12-24) of self-attention and feedforward networks. The key hyperparameters are embedding dimension (e.g., 768), number of attention heads (e.g., 12), and layer count. 3) **Training Objective**: Implement masked language modeling (MLM) where you randomly mask 15% of tokens and train the model to predict them. This forces the model to learn bidirectional context. 4) **Optimization**: Use AdamW optimizer with weight decay and learning rate scheduling (e.g., linear warmup then cosine decay). The learning rate should peak around 5e-5 for a 100M parameter model. 5) **Regularization**: Apply dropout (e.g., 0.1) and layer normalization to prevent overfitting. 6) **Distributed Training**: Use mixed-precision training (FP16) and data parallelism across multiple GPUs/TPUs to handle the computational load. 7) **Evaluation**: Monitor both training loss and validation metrics like perplexity. For example, a well-trained model might achieve perplexity < 20 on English text. The entire process might take weeks on high-end hardware, which is why most practitioners fine-tune existing models rather than training from scratch.
Check yourself
1. Why do n-gram language models struggle with capturing long-range dependencies in text?
- A.They rely on fixed-size windows of previous words, limiting context to a few tokens.
- B.They use neural networks to learn dependencies across entire sequences.
- C.They require smoothing techniques to handle long sequences effectively.
- D.They are designed to memorize entire documents rather than generalize.
Show answer
A. They rely on fixed-size windows of previous words, limiting context to a few tokens.
The correct answer is that n-gram models rely on fixed-size windows, which restricts their ability to model context beyond a few tokens. The other options are incorrect because: (1) Neural networks, not n-grams, learn dependencies across entire sequences. (2) Smoothing helps with unseen n-grams but doesn't address long-range dependencies. (3) N-gram models generalize from training data, not memorize documents.
2. What is the primary purpose of smoothing techniques in n-gram language models?
- A.To assign non-zero probabilities to unseen n-grams and improve generalization.
- B.To increase the model's vocabulary size for better performance.
- C.To reduce the computational cost of training the model.
- D.To enable the model to capture long-range dependencies in text.
Show answer
A. To assign non-zero probabilities to unseen n-grams and improve generalization.
The correct answer is that smoothing assigns non-zero probabilities to unseen n-grams, improving generalization. The other options are incorrect because: (1) Smoothing doesn't increase vocabulary size. (2) It doesn't reduce computational cost. (3) It doesn't address long-range dependencies, which are a limitation of n-gram models.
3. How does subword tokenization (e.g., BPE) benefit neural language models compared to word-level tokenization?
- A.It handles rare words and morphological variations by breaking words into subword units.
- B.It reduces the model's vocabulary size to improve training speed.
- C.It eliminates the need for embeddings, simplifying the model architecture.
- D.It allows the model to memorize all possible word forms in the training data.
Show answer
A. It handles rare words and morphological variations by breaking words into subword units.
The correct answer is that subword tokenization handles rare words and morphological variations by breaking words into subword units. The other options are incorrect because: (1) Subword tokenization typically increases vocabulary size. (2) Embeddings are still required for subword units. (3) Neural models generalize, not memorize, word forms.
4. Why might a developer choose a smaller neural language model over a larger one for a custom LLM project?
- A.Smaller models require fewer resources (data, compute, time) and may suffice for the task.
- B.Smaller models always outperform larger models in generalization.
- C.Smaller models can capture long-range dependencies more effectively.
- D.Smaller models eliminate the need for tokenization and embeddings.
Show answer
A. Smaller models require fewer resources (data, compute, time) and may suffice for the task.
The correct answer is that smaller models require fewer resources and may suffice for the task. The other options are incorrect because: (1) Larger models often generalize better with sufficient data. (2) Both small and large models can capture long-range dependencies, but larger ones do it better. (3) Tokenization and embeddings are still needed regardless of model size.
5. What is a key advantage of neural language models (e.g., RNNs, Transformers) over traditional n-gram models?
- A.They can learn dependencies across entire sequences through embeddings and attention mechanisms.
- B.They rely on fixed-size windows of previous words, making them simpler to train.
- C.They require no tokenization or preprocessing of the input text.
- D.They guarantee zero probability for unseen sequences, improving accuracy.
Show answer
A. They can learn dependencies across entire sequences through embeddings and attention mechanisms.
The correct answer is that neural language models learn dependencies across entire sequences using embeddings and attention. The other options are incorrect because: (1) Fixed-size windows are a limitation of n-gram models, not an advantage of neural models. (2) Neural models still require tokenization. (3) Neural models assign non-zero probabilities to unseen sequences through generalization.