The full Natural Language Processing mid-semester (regular) paper, every question worked end-to-end — TF-IDF, neural language models, skip-gram, interpolation/back-off, and Viterbi POS tagging. Questions are boxed; solutions are collapsible. The makeup-exam study guide at the end lists the same concepts to revise.
Q1 — Levels of analysis & TF-IDF 1 + 2 + 2 marks
(a) A search engine can’t tell if “bank” means a financial institution or a river bank. Which level of language analysis is required, and why? (b) For D1 = “machine learning improves prediction accuracy” and D2 = “prediction models use machine learning techniques” (lowercase, no stopword removal/lemmatization): (1) compute TF and DF for all terms; (2) compute the TF-IDF vector for each document. Use \(TF = \tfrac{\text{count}}{\text{length}}\).
Show worked solution
(a) Semantic analysis (word-sense disambiguation / lexical semantics). Tokenization and syntax can’t resolve which sense of “bank” is meant — only meaning in context can, so we need the semantic level.
(b1) TF and DF. D1 length = 5, D2 length = 6, \(N=2\) documents.
| Term | TF in D1 | TF in D2 | DF | IDF = log₁₀(N/DF) |
|---|---|---|---|---|
| machine | 1/5 = 0.20 | 1/6 = 0.167 | 2 | log(2/2) = 0 |
| learning | 0.20 | 0.167 | 2 | 0 |
| prediction | 0.20 | 0.167 | 2 | 0 |
| improves | 0.20 | 0 | 1 | log(2) = 0.301 |
| accuracy | 0.20 | 0 | 1 | 0.301 |
| models | 0 | 0.167 | 1 | 0.301 |
| use | 0 | 0.167 | 1 | 0.301 |
| techniques | 0 | 0.167 | 1 | 0.301 |
(b2) TF-IDF = TF × IDF. Terms appearing in both documents have IDF = 0, so they contribute 0:
D2: models = use = techniques = 0.167×0.301 = 0.0502 each; machine = learning = prediction = 0.
Takeaway: IDF zeroes out terms shared by all documents — only the distinctive words (improves/accuracy for D1, models/use/techniques for D2) carry weight.
Q2 — Neural LM vs bigram; Chain-of-Thought 3 + 2 marks
(a) A smart email-typing assistant: design a Neural Language Model and justify why it beats a simple bigram model. (b) A tutoring LLM solves: “A train travels 240 km in 4 hours. What is its average speed?” Why is Chain-of-Thought prompting useful here?
Show worked solution
(a) Neural LM design. Words → embedding layer (dense vectors) → context encoder (an LSTM or Transformer over the typed prefix) → softmax over the vocabulary giving \(P(w_t \mid w_{1..t-1})\); train by next-word prediction (cross-entropy). Why better than a bigram:
- A bigram uses only the previous one word, suffers severe data sparsity, and assigns zero to unseen pairs.
- The neural model’s embeddings generalize to semantically similar words, captures long-range context, and predicts well on unseen word combinations → far lower perplexity, much better typing suggestions.
(b) Chain-of-Thought. CoT makes the model emit intermediate steps (“distance 240 km, time 4 h, speed = 240 ÷ 4 = 60 km/h”) instead of guessing the answer directly. For multi-step arithmetic/word problems this decomposes the problem, reduces calculation errors, and makes the reasoning checkable/interpretable, improving accuracy.
Q3 — Skip-gram forward pass 1 + 2 + 2 marks
Sentence “We love NLP”, skip-gram, window size 1, \(V=\{We, love, NLP\}\), embedding dim 2.
\(W=\begin{bmatrix}0.2&0.4\\0.5&0.1\\0.3&0.6\end{bmatrix}\) (input→hidden), \(W'=\begin{bmatrix}0.1&0.3&0.2\\0.4&0.2&0.5\end{bmatrix}\) (hidden→output). Centre word = “love”.
(a) List all centre–context training pairs. (b) Hidden representation for “love”. (c) Output scores before softmax.
Show worked solution
(a) Training pairs (window = 1, skip-gram = centre → each context word):
For centre “love”: (love, We) and (love, NLP).
(b) Hidden layer. One-hot(love) × W = the “love” row of W:
(c) Output scores \(u = h\,W'\):
\(u_{love} = 0.5(0.3) + 0.1(0.2) = 0.15 + 0.02 = \) 0.17
\(u_{NLP} = 0.5(0.2) + 0.1(0.5) = 0.10 + 0.05 = \) 0.15
Scores (before softmax): \([We, love, NLP] = [0.09,\ 0.17,\ 0.15]\). (Softmax would then turn these into probabilities.)
Q4 — Linear interpolation & back-off 1 + 2 + 2 marks
Estimates for “food”: P(food)=0.05; P(food|thai)=0.40; P(food|indian)=0.30; P(food|priced thai)=0.60; P(food|priced indian)=0 (unseen). Combine with interpolation weights \(\lambda_1=0.1\) (uni), \(\lambda_2=0.3\) (bi), \(\lambda_3=0.6\) (tri). (a) Interpolated P after “priced thai”. (b) Interpolated P after “priced indian” and what interpolation achieved. (c) What would simple back-off give for P(food|priced indian)?
Show worked solution
(a) “priced thai”:
(b) “priced indian” (trigram = 0):
Interpolation gave a non-zero estimate despite the unseen trigram, by mixing in the lower-order (unigram + bigram) models — i.e. it smooths away the zero.
(c) Simple back-off. The trigram is unseen, so back-off drops to the highest available lower order — the bigram \(P(food\mid indian)\) = 0.30 (times a back-off weight α ≈ 1). Unlike interpolation, back-off uses only the bigram, not a blend.
Q5 — Viterbi POS tagging 6 marks
Using the Viterbi algorithm, find the most probable POS-tag sequence for “the small cat chases mouse”, given the transition, emission, and initial probabilities (tags DT, JJ, NN, VB). Show each step.
Show worked solution
Initial: DT 0.70, JJ 0.10, NN 0.10, VB 0.10. Emissions used directly. We track \(\delta_t(\text{tag})\) and back-pointers.
t1 “the” (\(\delta = \text{init}\times\text{emit(the)}\)): DT = 0.70×0.90 = 0.63; JJ = 0.10×0.10 = 0.01; NN = 0; VB = 0.
t2 “small”: JJ = max(DT→JJ 0.63×0.70 = 0.441)×0.80(emit) = 0.3528 ←DT; NN = (DT→NN 0.63×0.20 = 0.126)×0.20 = 0.0252 ←DT; DT, VB = 0.
t3 “cat”: NN = max(JJ→NN 0.3528×0.80 = 0.28224)×0.70 = 0.19757 ←JJ; JJ = (JJ→JJ 0.3528×0.10)×0.10 = 0.003528 ←JJ; VB = (JJ→VB 0.3528×0.10)×0.10 = 0.003528 ←JJ.
t4 “chases”: VB = max(NN→VB 0.19757×0.70 = 0.138297)×0.90 = 0.12447 ←NN; NN = (NN→NN 0.19757×0.20)×0.10 = 0.003951 ←NN.
t5 “mouse”: NN = max(VB→NN 0.12447×0.80 = 0.099576)×0.80 = 0.07966 ←VB; VB = (VB→VB 0.12447×0.10)×0.20 = 0.002489 ←VB.
Best final = NN (0.07966). Back-track the pointers: NN←VB←NN←JJ←DT.
Linguistically sensible: determiner, adjective, noun, verb, noun.
Q6 — HMM vs Neural POS tagger: experiment design 4 marks
An e-commerce chatbot uses POS tagging before intent detection. Design an experimental study comparing a Statistical (HMM) tagger and a Neural (Bi-LSTM/Transformer) tagger: (1) dataset, (2) evaluation metrics, (3) how to compare, (4) expected advantages of the neural tagger.
Show worked solution
1. Dataset. A POS-annotated corpus (e.g. Penn Treebank / Universal Dependencies) plus a domain set of labelled chatbot queries (short, imperative “show me…”, “track my order”). Split into train/validation/test (e.g. 70/15/15) with the same split for both taggers.
2. Metrics. Per-token accuracy; precision/recall/F1 per tag (esp. noun/verb/adjective used by intent detection); confusion matrix; and OOV (unknown-word) accuracy. Optionally downstream intent-classification accuracy.
3. Comparison. Train both on identical data, evaluate on the same held-out test set, report metrics, and run a significance test (e.g. McNemar’s) on the difference; also compare on short/noisy queries and OOV words, and note training/inference cost.
4. Expected advantages of the neural tagger. Handles OOV / rare words via subword/character embeddings; uses bidirectional long context (vs HMM’s local Markov assumption); resolves ambiguity better; no strong independence assumptions → higher accuracy on informal chatbot text (at the cost of more data and compute).
Makeup exam — what to study study guide
The makeup paper tests the same concepts with new sentences/numbers. Drill the methods below.
| Concept (revise this) | Tested in | What to be able to do |
|---|---|---|
| Levels of language analysis | Q1a | Match an ambiguity (lexical/syntactic/semantic/pragmatic) to the right analysis level. |
| TF, DF, IDF, TF-IDF | Q1b | Compute TF/DF/IDF and TF-IDF vectors by hand; explain why shared terms get IDF 0. |
| Neural LMs vs n-grams; prompting | Q2 | Design an embedding→encoder→softmax LM; justify over bigram; explain Chain-of-Thought / zero-shot prompting. |
| Word embeddings (skip-gram / CBOW) | Q3 | List training pairs; compute hidden vector and pre-softmax scores from weight matrices. |
| Smoothing: interpolation & back-off | Q4 | Compute linear-interpolation probabilities; contrast interpolation vs back-off on unseen n-grams. |
| HMM POS tagging / Viterbi | Q5 | Run Viterbi with δ-tables and back-pointers; recover the best tag sequence. |
| Statistical vs neural taggers; evaluation | Q6 | Design a comparison study: dataset, metrics (accuracy/F1/OOV), method, neural advantages. |