NLP Fundamentals

Words with higher dot product to the center word get higher probability. u_a and u_c both have dot product 1, so they share the highest probability. u_d has dot product -1, so it gets the lowest probability (0.047). This is exactly what we want: the model says "a" and "c" are likely context words for center word "c".

The denominator ∑_w∈V exp(u_w · v_c) requires computing the dot product of v_c with every context vector u_w in the vocabulary. For V = 50,000, that's 50,000 dot products per training pair. With billions of training pairs, this is prohibitively expensive. This is the softmax bottleneck — and it's exactly why negative sampling was invented.

Positive term: σ(u_o · v_c) = σ(2.0). Negative terms use σ(-u_k · v_c):

The key subtlety: negative samples use σ(-u_k · v_c), which encourages high sigmoid output when the dot product is negative (i.e., the words are dissimilar). With just k=2 negatives instead of V=50,000 terms in the softmax denominator, training is orders of magnitude faster.

First compute E[u_w] (first component only):

The gradient is negative in the first component, meaning the update will increase v_c in that direction — pushing v_c toward the observed context word u_a. The gradient literally says: "move the center vector closer to the word you actually observed."

This is why negative sampling made Word2Vec practical. The original paper (Mikolov et al., 2013) reported that k=5-20 negative samples works well for small datasets, while k=2-5 suffices for very large corpora. The quality barely degrades because most words in the vocabulary are irrelevant to any given center word — you only need a small sample of negatives to approximate the full gradient.

Line 4 is the bug. For negative samples, we want σ(-u_k · v_c), not σ(u_k · v_c). The correct line should be: loss -= Math.log(sigmoid(-dot(negVecs[k], vc)));

Without the negation, the loss encourages high similarity with negative samples instead of discouraging it. The model would learn to make all words similar — the exact opposite of what we want.

Each SHIFT moves the front word from the buffer onto the top of the stack. The stack grows from left to right — the rightmost element is the "top."

LEFT-ARC: the top of stack (cat) becomes the parent of the second-on-stack (The). The second-on-stack (The) is removed. The arc is cat → The (parent → child), labeled "det" for determiner.

Think of LEFT-ARC as: "the word below me on the stack depends on me." The arrow points from parent to child: cat → The. This correctly says "The" is a determiner of "cat."

Every word must be shifted once (6 shifts) and every word must be attached to exactly one parent (6 arcs, one for each word including ROOT attachment). This gives exactly 2n transitions. A neural parser with a scoring network that runs in O(1) per transition thus parses in O(n) total time — linear in sentence length.

Correct order: SHIFT "The" → SHIFT "cat" → LEFT-ARC(det) → SHIFT "sat" → LEFT-ARC(nsubj) → RIGHT-ARC(root)

The final tree: ROOT → sat, sat → cat (nsubj), cat → The (det). This correctly captures that "sat" is the main verb, "cat" is the subject, and "The" modifies "cat."

Shift-reduce: O(n) = 80 steps. Graph-based (Eisner/MST): O(n²) or O(n³) = 1,600 or 64,000 steps. Shift-reduce wins on speed, but graph-based can find the globally optimal tree while shift-reduce makes greedy local decisions. In practice, beam search (keeping top-k candidates at each step) helps shift-reduce approach global optimality while staying fast.

Alternative computation via the product formula: (0.1 × 0.3 × 0.5 × 0.2 × 0.4)^-1/5 = (0.0012)^-0.2 = (1/0.0012)^0.2 = 833.3^0.2 ≈ 3.84. Both methods give the same answer. The model is about as confused as picking from ~4 equally likely options.

This is the most common conversion you'll do in practice. Training loss of 2.8 → perplexity of ~16.4. For reference: GPT-2 achieved ~29.4 perplexity on WikiText-103, GPT-3 improved to ~20.5, and current frontier models are in the 5-10 range on similar benchmarks.

Lower perplexity = better model. Model B (PP=15.3) assigns higher probability to the test text than Model A (PP=22.1). Concretely: at each word position, Model B is as uncertain as choosing from ~15 options, while Model A is as uncertain as choosing from ~22 options. Model B has a tighter, more accurate distribution over next words.

Caveat: perplexity must be compared on the same test set with the same vocabulary. A model with vocabulary size 1000 will naturally have lower perplexity than one with vocabulary 50000 on the same text, simply because it has fewer choices.

javascript
function perplexity(probs) {
  const N = probs.length;
  let sumLogP = 0;
  for (let i = 0; i < N; i++) {
    sumLogP += Math.log(probs[i]);
  }
  return Math.exp(-sumLogP / N);
}

The uniform model has perplexity exactly equal to the vocabulary size. This is the worst-case baseline — any model that learns anything about language should beat this. For V=50,000, the model is maximally confused, picking randomly from all 50,000 words at each position. A perplexity of 15 means the model has reduced its effective choices from 50,000 to 15 — a 3,333× improvement.

h₃ gets the highest attention weight (~49%) because it has the largest dot product with the decoder state. This makes sense: h₃=[1,1] is the most aligned with s=[0.5,0.8] — it's the source word the decoder "wants" to look at most.

The context vector is a weighted average of the encoder states. Since h₃ has the highest weight, c is pulled strongly toward h₃=[1,1]. This vector summarizes "what the decoder should know about the input" for generating the current output word.

Bahdanau uses a tanh nonlinearity, so it can capture non-linear relationships between query and key. But this prevents efficient batching — you can't compute all scores with a single matrix multiply. Luong's dot product can be computed as S × H^T, a single GEMM call that GPUs love. This is why transformers chose scaled dot-product attention: QK^T/√d_k is just Luong attention with a scaling factor to prevent softmax saturation.

"chat" is the French word for "cat," so it should receive the highest attention weight when generating "cat." This is exactly what attention was designed for: it learns to align source and target words. In French-to-English translation, attention handles word reordering naturally — "Le chat noir" becomes "The black cat" by attending to the right word at each step, regardless of position differences between the languages.

Without scaling, dot products grow proportionally to d_k (expected magnitude ≈ √d_k for random vectors). Large dot products push softmax into saturated regions where gradients vanish. Dividing by √d_k keeps the variance at 1, regardless of dimension. The original "Attention Is All You Need" paper (Vaswani et al., 2017) explains this in Section 3.2.1.

BPE always merges the most frequent pair. (a,b) appears 8 times — more than any other pair. After merging, the new token "ab" replaces all occurrences of "a b" in the corpus. The vocabulary becomes {a, b, c, d, _, ab} with 6 tokens.

Each merge creates exactly one new token (the concatenation of the merged pair) without removing the original characters. So the vocabulary grows by exactly 1 per merge. This is how you choose your target vocabulary size: set k = desired_V - initial_chars. LLaMA's 32K vocabulary used approximately 32,000 - 256 = 31,744 merges.

Count pair frequencies across all words (weighted by word frequency):

BPE's key advantage is that it cannot produce [UNK]. Any string can be decomposed into known subwords — in the worst case, into individual bytes. The model can still compose meaning from pieces: "Chat" (conversation), "GPT" (common in AI context), "4" (number), "o" (suffix). Word-level models are helpless with OOV words, making them brittle against new terminology, typos, and morphological variation.

52M parameters saved just in the embedding table! For GPT-2 Small (124M total), this is ~42% of the entire model. Smaller vocabulary also speeds up the output softmax layer. The tradeoff: BPE sequences are ~20-30% longer than word-level (e.g., "unforgettable" = 1 word-token vs 3 BPE tokens), increasing compute per sentence.

Only 77 out of 512 positions generate a loss signal — that's 15% efficiency. CLM generates loss at all 512 positions, making it 6.7x more data-efficient per sequence. This is one reason GPT-style models eventually overtook BERT: they extract more learning from each training example.

CLM gets 6.7x more training signal from the same data. This is misleading though — MLM predictions see bidirectional context, which is arguably a richer learning signal per prediction. The field has debated this tradeoff extensively. Chinchilla (Hoffmann et al., 2022) showed that for CLM, optimal training uses roughly 20 tokens per parameter. For a 7B model, that's ~140B tokens.

The core issue is pretrain-finetune mismatch. During fine-tuning, the model never sees [MASK] tokens — all inputs are real words. If the model only learned to predict from [MASK] tokens, it would struggle with real inputs. The 10% "keep original" and 10% "random token" ensure the model also learns to predict from non-[MASK] positions, reducing the distribution shift at fine-tuning time. The BERT paper (Devlin et al., 2019) discusses this in Section 3.1.

Line 5 is the bug. All selected positions are replaced with [MASK], ignoring the 80/10/10 split. The correct implementation should: 80% of the time use [MASK], 10% use a random token, and 10% keep the original. Without this split, the model overfits to the [MASK] token distribution and suffers from pretrain-finetune mismatch. The fix:

javascript
const r = Math.random();
if (r < 0.8) tokens[i] = MASK_TOKEN;
else if (r < 0.9) tokens[i] = randomToken();
// else: keep original (10%)

If position t can see position t+1, then when predicting w_t+1, the model already has w_t+1 in its context — it just copies the answer instead of learning to predict. The causal mask enforces the autoregressive property: each prediction only uses past tokens. This is also what makes CLM naturally suited for generation: at inference time, the model generates one token at a time, always conditioning only on previous tokens, which exactly matches training.

1.76 GB fits easily on any modern GPU. But for a 7B model: 7 × 10⁹ × 16 = 112 GB — that's more than a single A100 80GB. This is why PEFT methods like LoRA are essential for large models. They reduce the 16 bytes/param down to ~2 bytes/param for frozen weights + 16 bytes/param for just the tiny adapter.

Only 0.54% of parameters are trainable! The other 99.46% are frozen, requiring only 2 bytes/param (for inference). LoRA memory: frozen weights (110M × 2 = 220 MB) + trainable weights+optimizer (0.59M × 16 = 9.4 MB) = ~230 MB total. Compare to 1.76 GB for full fine-tuning.

Even fewer than LoRA! But prefix tuning has a downside: the k virtual tokens consume positions in the sequence length budget. With k=20 and max sequence 512, you effectively lose 20 positions (3.9%). For long-context tasks, this matters. LoRA doesn't consume any sequence positions.

Correct order: Full (110M) > LoRA (0.59M) > Prefix (0.37M) > Head only (0.0015M = 768 × 2 for binary classification).

Performance generally follows the same order, but with diminishing returns: LoRA with 0.5% of parameters typically reaches 95-99% of full fine-tuning quality. The linear head alone can work for simple tasks where the pretrained representations already capture what you need.

javascript
function loraForward(x, W, A, B) {
  const dOut = W.length, dIn = x.length, r = A.length;
  // Compute Wx
  const Wx = Array(dOut).fill(0);
  for (let i = 0; i < dOut; i++)
    for (let j = 0; j < dIn; j++)
      Wx[i] += W[i][j] * x[j];
  // Compute Ax (r-dim)
  const Ax = Array(r).fill(0);
  for (let i = 0; i < r; i++)
    for (let j = 0; j < dIn; j++)
      Ax[i] += A[i][j] * x[j];
  // Compute BAx (dOut-dim)
  const BAx = Array(dOut).fill(0);
  for (let i = 0; i < dOut; i++)
    for (let j = 0; j < r; j++)
      BAx[i] += B[i][j] * Ax[j];
  // y = Wx + BAx
  return Wx.map((v, i) => v + BAx[i]);
}

LoRA uses ~12.5% of the memory of full fine-tuning — making it feasible to fine-tune a 7B model on a single 24GB GPU (14 GB for weights + a few GB for activations). Full fine-tuning would need at least 2x A100 80GB just for the optimizer states.

Naive precision: All 6 words in the hypothesis are "the", and "the" appears in the reference. So naive precision = 6/6 = 1.0. This is clearly wrong — the hypothesis is terrible!

Clipped precision: "the" appears 2 times in the reference, so we clip the match count to 2:

Clipping prevents gaming by repeating high-frequency words. BLEU always uses clipped counts. This is why BLEU is called "modified n-gram precision" — the modification is this clipping step.

The hypothesis correctly captures 3 of 4 bigrams but misses (cat,sat) because "sat" was omitted. The missing word "sat" breaks one bigram pair. Higher-order n-grams are more sensitive to word order and fluency — BLEU-4 (the standard) uses up to 4-grams.

ROUGE-L F1 = 0.75. The score is penalized because "killed" vs "kill" is an exact token mismatch. Some ROUGE variants use stemming to handle this (both stem to "kill"), which would give LCS=4 and perfect F1=1.0. This shows why metric choice matters — stemming, tokenization, and case sensitivity all affect the final score.

F1 = 0.33, which seems harsh — the model got the year right but also extracted extra tokens ("built in"). In SQuAD evaluation, exact match (EM) would be 0 (not an exact match) but F1 captures partial credit. A predicted answer of just "1889" would get Precision=1.0, Recall=1/3, F1=0.5 — still penalized for missing "1887 to." The ideal answer is the exact span "1887 to 1889."

javascript
function bleu1(hypothesis, reference) {
  // Count words in reference
  const refCount = {};
  for (const w of reference)
    refCount[w] = (refCount[w] || 0) + 1;
  // Count clipped matches
  const hypCount = {};
  let clippedMatches = 0;
  for (const w of hypothesis) {
    hypCount[w] = (hypCount[w] || 0) + 1;
  }
  for (const w in hypCount) {
    clippedMatches += Math.min(hypCount[w], refCount[w] || 0);
  }
  return hypothesis.length > 0 ? clippedMatches / hypothesis.length : 0;
}

The brevity penalty halves the BLEU score! This prevents a strategy of generating short, confident outputs. Without BP, a model could output a single highly-probable word and achieve perfect precision. BP kicks in whenever the hypothesis is shorter than the reference (c < r). When c ≥ r, BP = 1 (no penalty).

Always use the tokenizer that matches your pretrained model. BERT's WordPiece and RoBERTa's BPE handle OOV words, model numbers, and most emoji. Training a custom tokenizer on 10K examples would be vastly inferior to the pretrained tokenizer trained on billions of words. Character-level would work but makes sequences 4-5x longer, increasing compute. Word-level would choke on model numbers and rare product names.

With 10K examples, BERT-base or RoBERTa-base is the sweet spot. Training from scratch requires millions of examples. A 70B model with LoRA would work but is overkill — the marginal improvement over BERT-base on binary sentiment is minimal, while compute cost is 10-50x higher. Bag-of-words actually works reasonably (85-88%) but BERT easily reaches 93-95% with fine-tuning, and the compute cost is minimal ($1-5 on a single GPU for a few hours).

2,534 TFLOPs. An A100 delivers ~312 TFLOPS (BF16 with tensor cores). At 50% utilization: 2,534 / (312 × 0.5) = ~16 seconds of A100 time. This is why BERT fine-tuning is so cheap — even on consumer GPUs (RTX 3090 at 71 TFLOPS), it takes under 2 minutes. The $200 budget is wildly more than needed.

~2.5 GB fits on any GPU made in the last 5 years (even a 4GB GTX 1050 would work with smaller batch size). This is why BERT fine-tuning democratized NLP — you don't need expensive hardware. The real cost is not compute but data labeling: 10,000 labeled examples at $0.10/label = $1,000, far more than the $5 of GPU time.

Correct order: Split data → Tokenize → Load pretrained model → Fine-tune → Evaluate

You must split before tokenizing to prevent data leakage. The model is loaded after tokenization because you need the tokenizer to prepare inputs. Fine-tuning uses the validation set for early stopping. Final evaluation on the test set happens only once — if you tune hyperparameters based on test performance, you're overfitting to the test set.

Under $1 total! With the $200 budget, you could run 1,500 experiments. In practice, you'd spend more on the minimum billing increment (most cloud providers charge per-minute or per-second with a minimum). The real lesson: BERT-base fine-tuning on small datasets is essentially free. The engineering time to set up the pipeline (a few hours of your salary) vastly exceeds the compute cost.

Line 5 is the bug. The code evaluates on the same tokenized data used for training — there's no train/test split! The model memorized the training examples and the 99.8% accuracy is meaningless. The fix: split data into train/val/test before training, train on train, use val for early stopping, and evaluate on test only once at the end. Without this split, you have no idea how the model performs on unseen data.