NLP Models: N-grams to Transformers

Language Models

A language model (LM) assigns probabilities to sequences of words. Formally, it estimates:

$P(w_1, w_2, \ldots, w_n) = \prod_{i=1}^{n} P(w_i | w_1, \ldots, w_{i-1})$

Language models underpin all of NLP: they power text generation, scoring candidate translations, ASR decoding, and are the foundation of modern LLMs.

N-gram Language Models

N-gram models approximate the full history with a Markov assumption of order $n$:

$P(w_i | w_1 \ldots w_{i-1}) \approx P(w_i | w_{i-n+1} \ldots w_{i-1})$

Bigram model ($n=2$): $P(\text{the cat sat}) = P(\text{the}) \cdot P(\text{cat}|\text{the}) \cdot P(\text{sat}|\text{cat})$

Probabilities are estimated by Maximum Likelihood Estimation:

$P(w_i | w_{i-1}) = \frac{\text{count}(w_{i-1}, w_i)}{\text{count}(w_{i-1})}$

Smoothing handles zero-count n-grams:

• Laplace (add-1): add 1 to all counts
• Kneser-Ney: redistributes probability mass based on continuation counts — strongest classical smoother

Limitations of n-grams:

• Cannot capture long-range dependencies (fixed window)
• No generalization: "dog" and "canine" are unrelated
• Vocabulary explosion: $|V|^n$ possible n-grams
• Perplexity (evaluation): $PP(W) = P(w_1 \ldots w_N)^{-1/N}$ — lower is better

RNNs and LSTMs

Vanilla RNN

$h_t = \tanh(W_h h_{t-1} + W_x x_t + b_h)$ $y_t = \text{softmax}(W_y h_t + b_y)$

Vanishing gradient problem: during backpropagation through time (BPTT), gradients are multiplied by $W_h$ at every time step. If $\|W_h\| < 1$, gradients vanish exponentially. If $\|W_h\| > 1$, they explode. This makes learning long-range dependencies very difficult.

Long Short-Term Memory (LSTM)

LSTM (Hochreiter & Schmidhuber, 1997) addresses vanishing gradients with gates that control information flow:

$\text{Forget gate: } f_t = \sigma(W_f [h_{t-1}, x_t] + b_f)$ $\text{Input gate: } i_t = \sigma(W_i [h_{t-1}, x_t] + b_i)$ $\text{Cell gate: } \tilde{c}_t = \tanh(W_c [h_{t-1}, x_t] + b_c)$ $\text{Cell state: } c_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t$ $\text{Output gate: } o_t = \sigma(W_o [h_{t-1}, x_t] + b_o)$ $\text{Hidden state: } h_t = o_t \odot \tanh(c_t)$

The cell state $c_t$ acts as a conveyor belt — information flows unchanged unless the forget gate suppresses it, solving the vanishing gradient problem for long sequences.

GRU (Gated Recurrent Unit): simplified LSTM with only reset and update gates; fewer parameters, similar performance.

Bidirectional RNN

Standard RNNs only use left context. BiRNNs process sequences in both directions:

$\overrightarrow{h}_t = \text{RNN}(x_t, \overrightarrow{h}_{t-1}) \qquad \overleftarrow{h}_t = \text{RNN}(x_t, \overleftarrow{h}_{t+1})$ $h_t = [\overrightarrow{h}_t ; \overleftarrow{h}_t]$

BiLSTMs are the backbone of pre-Transformer NLP: BiLSTM-CRF for NER, BiLSTM for text classification, seq2seq with attention for MT.

RNN Limitations

Despite LSTMs, RNNs have fundamental limitations:

• No parallelism: must process tokens sequentially → slow training on long sequences
• Limited context: effectively ~100–200 tokens of useful context even with LSTMs
• Fixed-size representation bottleneck in seq2seq (partially solved by attention)

These limitations motivated the Transformer.

The Transformer Architecture

The Transformer (Vaswani et al., 2017) processes sequences entirely through attention — no recurrence:

Scaled Dot-Product Attention

$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d_k}}\right) V$

• $Q$ (queries), $K$ (keys), $V$ (values): linear projections of input
• $\sqrt{d_k}$ scaling: prevents dot products from growing large (saturating softmax)
• Output: weighted sum of values, where weights reflect query-key similarity

Multi-Head Attention

Multiple attention heads allow the model to jointly attend to different representation subspaces:

$\text{MultiHead}(Q,K,V) = \text{Concat}(\text{head}_1, \ldots, \text{head}_h) W^O$ $\text{head}_i = \text{Attention}(Q W_i^Q, K W_i^K, V W_i^V)$

Each head can capture different relationships: one head might learn syntactic dependencies, another semantic similarity.

Positional Encoding

Since attention has no notion of order, position is injected via sinusoidal encodings added to token embeddings:

$PE(pos, 2i) = \sin\left(\frac{pos}{10000^{2i/d}}\right) \qquad PE(pos, 2i+1) = \cos\left(\frac{pos}{10000^{2i/d}}\right)$

Modern LLMs use Rotary Position Embeddings (RoPE) or ALiBi for better length generalization.

Transformer Block

Each block applies:

1. Multi-Head Self-Attention (with residual connection + LayerNorm)
2. Position-wise Feed-Forward Network (2-layer MLP, with residual + LayerNorm)

$\text{FFN}(x) = \max(0, xW_1 + b_1)W_2 + b_2$

Encoder vs Decoder vs Encoder-Decoder

Architecture	Example Models	Used For
Encoder-only	BERT, RoBERTa, DeBERTa	Classification, NER, QA, embeddings
Decoder-only	GPT, LLaMA, Mistral	Text generation, completion, chat
Encoder-Decoder	T5, BART, mBART	Translation, summarization, seq2seq

Encoder: bidirectional attention (each token sees all others) Decoder: causal (masked) attention (each token only sees past tokens) + cross-attention to encoder

Pre-training and Fine-tuning

Pre-training Objectives

Model	Pre-training Task	Key Feature
BERT	Masked LM (MLM) + NSP	Bidirectional context
RoBERTa	MLM (no NSP)	Larger batches, more data
GPT	Causal LM (predict next token)	Autoregressive generation
GPT-3/4	Causal LM at scale	Few-shot in-context learning
T5	Span masking + text-to-text	Unified text-to-text format
BART	Denoising (mask, delete, shuffle)	Encoder-decoder, good for generation
XLNet	Permuted LM	Overcomes BERT's [MASK] discrepancy

BERT Pre-training

Masked Language Model (MLM): randomly mask 15% of tokens; predict them:

• 80% of the time replace with [MASK]
• 10% replace with a random word
• 10% keep unchanged

This prevents the model from simply copying the input and forces it to use context.

Next Sentence Prediction (NSP): classify if sentence B follows sentence A (50% positive, 50% random). Removed in RoBERTa as it was found to hurt downstream performance.

Fine-tuning Strategies

Full fine-tuning: update all parameters on downstream task. Most flexible but expensive.

Parameter-Efficient Fine-Tuning (PEFT):

• LoRA (Low-Rank Adaptation): inject trainable low-rank matrices $\Delta W = BA$ into attention layers; only ~0.1–1% of parameters trained
• Adapter layers: insert small trainable MLP modules between frozen transformer layers
• Prefix tuning: prepend trainable "soft prompts" to the input; freeze all model parameters
• Prompt tuning: similar to prefix tuning but only at the embedding layer

In-context learning (ICL): provide examples in the prompt (few-shot); no gradient updates. GPT-3 showed this works surprisingly well at scale.

Scaling Laws

Kaplan et al. (2020) showed that model loss follows a power law with compute, data, and parameters:

$L \propto N^{-\alpha} \quad L \propto D^{-\beta} \quad L \propto C^{-\gamma}$

Chinchilla scaling (Hoffmann et al., 2022): for optimal performance, scale data and parameters equally — a 70B model needs ~1.4 trillion tokens for compute-optimal training.

# ─── 1. N-gram Language Model ────────────────────────────────
from collections import defaultdict, Counter
import numpy as np
import math

class NgramLM:
    def __init__(self, n=2, alpha=0.1):
        self.n = n
        self.alpha = alpha  # Laplace smoothing
        self.counts = defaultdict(Counter)
        self.vocab = set()

    def train(self, sentences):
        for sent in sentences:
            tokens = ["<s>"] * (self.n - 1) + sent.split() + ["</s>"]
            for i in range(self.n - 1, len(tokens)):
                context = tuple(tokens[i - self.n + 1:i])
                word = tokens[i]
                self.counts[context][word] += 1
                self.vocab.add(word)

    def prob(self, word, context):
        ctx = tuple(context[-(self.n-1):]) if self.n > 1 else ()
        count_ctx = sum(self.counts[ctx].values())
        count_word = self.counts[ctx][word]
        return (count_word + self.alpha) / (count_ctx + self.alpha * len(self.vocab))

    def perplexity(self, sentences):
        log_prob = 0
        N = 0
        for sent in sentences:
            tokens = ["<s>"] * (self.n - 1) + sent.split() + ["</s>"]
            for i in range(self.n - 1, len(tokens)):
                context = tokens[i - self.n + 1:i]
                word = tokens[i]
                log_prob += math.log(self.prob(word, context) + 1e-10)
                N += 1
        return math.exp(-log_prob / N)

corpus = [
    "the cat sat on the mat",
    "the dog sat on the floor",
    "the cat ate the fish",
    "the dog chased the cat",
    "natural language processing is fascinating",
]
test = ["the cat sat on the floor", "the dog ate the fish"]

for n in [1, 2, 3]:
    lm = NgramLM(n=n)
    lm.train(corpus)
    print(f"{n}-gram LM perplexity: {lm.perplexity(test):.2f}")

# ─── 2. LSTM Language Model (PyTorch) ────────────────────────
import torch
import torch.nn as nn

class LSTMLanguageModel(nn.Module):
    def __init__(self, vocab_size, embed_dim=128, hidden_dim=256, num_layers=2, dropout=0.3):
        super().__init__()
        self.embedding = nn.Embedding(vocab_size, embed_dim)
        self.lstm = nn.LSTM(embed_dim, hidden_dim, num_layers,
                            dropout=dropout, batch_first=True)
        self.dropout = nn.Dropout(dropout)
        self.fc = nn.Linear(hidden_dim, vocab_size)

    def forward(self, x, hidden=None):
        emb = self.dropout(self.embedding(x))     # (batch, seq, embed_dim)
        out, hidden = self.lstm(emb, hidden)       # (batch, seq, hidden_dim)
        logits = self.fc(self.dropout(out))        # (batch, seq, vocab_size)
        return logits, hidden

    def generate(self, start_token, max_len=50, temperature=1.0, top_k=40):
        self.eval()
        tokens = [start_token]
        hidden = None
        with torch.no_grad():
            for _ in range(max_len):
                x = torch.tensor([[tokens[-1]]])
                logits, hidden = self.forward(x, hidden)
                logits = logits[0, -1, :] / temperature
                if top_k > 0:
                    values, _ = torch.topk(logits, top_k)
                    logits[logits < values[-1]] = -float('inf')
                probs = torch.softmax(logits, dim=-1)
                next_token = torch.multinomial(probs, 1).item()
                tokens.append(next_token)
                if next_token == 1:  # </s> token
                    break
        return tokens

# Usage (pseudocode — needs tokenizer and data loader):
# vocab_size = len(tokenizer)
# model = LSTMLanguageModel(vocab_size)
# optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
# criterion = nn.CrossEntropyLoss(ignore_index=pad_token_id)

# ─── 3. BERT Fine-tuning with HuggingFace Trainer ─────────────
from transformers import (AutoTokenizer, AutoModelForSequenceClassification,
                          TrainingArguments, Trainer)
from datasets import load_dataset
import numpy as np
from sklearn.metrics import accuracy_score, f1_score

# Load dataset (SST-2 sentiment)
dataset = load_dataset("glue", "sst2")
tokenizer = AutoTokenizer.from_pretrained("distilbert-base-uncased")

def tokenize_fn(batch):
    return tokenizer(batch["sentence"], truncation=True,
                     padding="max_length", max_length=128)

tokenized = dataset.map(tokenize_fn, batched=True)

model = AutoModelForSequenceClassification.from_pretrained(
    "distilbert-base-uncased", num_labels=2)

def compute_metrics(eval_pred):
    logits, labels = eval_pred
    preds = np.argmax(logits, axis=-1)
    return {
        "accuracy": accuracy_score(labels, preds),
        "f1": f1_score(labels, preds),
    }

args = TrainingArguments(
    output_dir="./sst2-distilbert",
    num_train_epochs=3,
    per_device_train_batch_size=32,
    per_device_eval_batch_size=64,
    evaluation_strategy="epoch",
    save_strategy="epoch",
    load_best_model_at_end=True,
    metric_for_best_model="accuracy",
    learning_rate=2e-5,
    weight_decay=0.01,
    warmup_ratio=0.1,
)
trainer = Trainer(
    model=model,
    args=args,
    train_dataset=tokenized["train"],
    eval_dataset=tokenized["validation"],
    compute_metrics=compute_metrics,
)
# trainer.train()  # uncomment to train (~93% accuracy expected)

# ─── 4. LoRA Fine-tuning ─────────────────────────────────────
# pip install peft
from peft import get_peft_model, LoraConfig, TaskType

lora_config = LoraConfig(
    task_type=TaskType.SEQ_CLS,
    r=8,                    # rank
    lora_alpha=16,          # scaling
    lora_dropout=0.1,
    target_modules=["q_lin", "k_lin"],  # DistilBERT attention projections
)
lora_model = get_peft_model(model, lora_config)
lora_model.print_trainable_parameters()
# trainable params: ~295k (0.35%) vs 67M total — 99.65% frozen

Summary

Model Family	Architecture	Pre-training	Best Use Cases
N-gram LM	Count-based	MLE + smoothing	Baseline, fast, interpretable
LSTM	RNN with gates	LM from scratch	Sequential labeling (with BiLSTM)
BERT	Transformer encoder	MLM + NSP	Classification, NER, QA, embeddings
RoBERTa	Transformer encoder	MLM (bigger)	Best encoder baseline
GPT-3/4	Transformer decoder	Causal LM at scale	Generation, few-shot ICL
T5	Encoder-Decoder	Span masking	Translation, summarization, multitask
LLaMA	Transformer decoder	Causal LM	Open-source foundation model

Key takeaways:

• N-grams → RNNs → Transformers: each generation solved the previous model's key weakness
• Pre-training on massive text corpora then fine-tuning on small task data is the dominant paradigm
• PEFT methods (LoRA, adapters) enable efficient fine-tuning of 7B–70B models on consumer hardware
• Scaling laws predict that compute-optimal training requires equal scaling of model size and data

Next: NLP Evaluation & Deployment — metrics, benchmarks, monitoring, and productionizing NLP systems.