Final Recap: Parsing, Contextual Embeddings, Word Sense, Retrieval Augmented Generation and Text Summarization

This is the final post-midterm recap for Natural Language Processing, tying together the second half of the course. The session revisits evaluation (ROUGE), structure (constituency and dependency parsing with PCFG, CKY, arc-eager and Chu-Liu Edmonds), representation (contextual embeddings and self-attention), knowledge (WSD, WordNet, ontologies and knowledge graphs), grounding (RAG with token, chunk, and latency budgets), and distillation (text summarization with TF-IDF, LexRank, and MMR). The goal is not new theory but synthesis: procedures you can apply with given rules, tables, and formulas in an open-book exam, and patterns you will meet in industry RAG and summarization projects.

How to use these notes: for each of the eight technical sections (16.1–16.8) the spine gives hook, intuition with analogy, formal definitions with every symbol named, fully worked examples with numbers and checks, scope and pitfalls, visual description, and bridge to the next section. Exam boxes highlight mark allocation and question types; Q&A boxes preserve the professor's corrections. Work through the worked examples with a pen, then practice the sample paper CNF/CKY question and one ROUGE/MMR/RAG numerical without looking.

16.1 ROUGE — Recall-Oriented Evaluation for Summarization

16.1.1 Definition, Role and Intuition

A ROUGE score — Recall-Oriented Understudy for Gisting Evaluation — measures how much overlap exists between a system-generated summary and one or more human reference summaries. The name tells you the bias: it is recall-oriented, so it asks what fraction of the reference content was covered, not what fraction of the machine output was correct. It is the standard evaluation used for every summarization approach, whether extractive, abstractive, single-document or multi-document, rule-based, statistical, or neural. Irrespective of the method that builds the summary, the same ROUGE measure checks quality.

The intuition is direct: count words or word sequences that are common between the reference and the generated text, then normalize. When words match exactly as strings, they count. Ordering matters more when longer continuous sequences are checked. A human reference is needed as the gold benchmark; quality is judged by similarity to that benchmark. A toy example might use only one sentence, while real evaluations use many sentences, but the measure itself does not change. Because human references differ from person to person, using three references instead of one gives a fairer denominator — the system gets credit if it matches any of the trusted human phrasings.

Real-world placement: this is the score used across industry for all summarization systems, in the same way BLEU is used for machine translation. In this course ROUGE is the examinable metric for summarization evaluation, while BLEU and BERTScore will be studied in the follow-up NLP applications course. For deployment, teams report ROUGE-2 and ROUGE-3 because they balance word choice and word order, and they set a threshold such as 0.35 or 0.43 to decide whether a summary is good enough to ship.

16.1.2 Mathematical Formulation

The verbal description in the session was: count the number of words that are common across the reference summary and the generated summary, divide by the total $n$-grams in the reference set. The reconciled formula for ROUGE-N is

$$\text{ROUGE-N}=\frac{{\sum }_{S\in \{\text{ReferenceSummaries}\}}{\sum }_{{\text{gram}}_n\in S}{\text{Count}}_{\text{match}}({\text{gram}}_n)}{{\sum }_{S\in \{\text{ReferenceSummaries}\}}{\sum }_{{\text{gram}}_n\in S}\text{Count}({\text{gram}}_n)}$$

where ${\text{gram}}_n$ is an $n$-gram, a continuous sequence of $n$ words, ${\text{Count}}_{\text{match}}$ is the number of $n$-grams co-occurring in the candidate summary and the reference, $\text{Count}$ is the total number of $n$-grams in the references, and the outer sum aggregates over all available human references.

Normalization is essential. Without it, a long reference would automatically score higher. With normalization, the score is a proportion in $[0,1]$, often reported as a percentage, and a threshold can be set: only if the score exceeds the threshold is the system summary judged good.

An important counting relation was stated verbally as: if you have 11 words you have 10 bigrams; bigrams are $N-1$. More generally, derived from the sliding window argument:

$$\text{num\_bigrams}=N-1$$

$$\text{num\_trigrams}=N-2$$

$$\text{num\_n-grams}=N-n+1$$

This holds because a sliding window of size $n$ can start at positions $1$ through $N-n+1$. A reference with $N=11$ and $n=2$ yields $10$ windows; with $n=3$ yields $9$. The denominator for ROUGE-N therefore changes with $n$: for ROUGE-2 use $N-1$, for ROUGE-3 use $N-2$.

Reconciled against standard definition (Lin 2004): the form above is the recall version. Some toolkits also report ROUGE precision and F-measure, but the lecture and the exam use the recall form shown here. Texts often write the same idea as overlapping $n$-grams over reference $n$-grams; notation $N-n+1$ matches the companion document on summarization evaluation.

In the session, ROUGE-1 was described as simply counting overlapping single words, ROUGE-2 as checking two words at a time, ROUGE-3 as checking three words at a time. That progression shows how ordering sensitivity grows with $n$.

16.1.3 Worked Example — ROUGE-2 with Three References

The final step after scoring is thresholding: decide a minimum ROUGE score required to declare the system summary good. The threshold is chosen per application — for example, $0.40$ — and higher $n$ typically yields lower absolute scores because longer exact matches are rarer. A system scoring $0.43$ under a $0.40$ threshold would pass; under $0.50$ it would fail.

16.1.4 ROUGE-1, ROUGE-3 and Generalization

ROUGE-1 is simple word overlap ignoring order:

$$\text{ROUGE-1}=\frac{\text{number of overlapping words}}{\text{total words in references}}$$

ROUGE-2 captures ordering better than ROUGE-1; ROUGE-3 and ROUGE-4 capture even more ordering, but scores drop quickly. In practice ROUGE-2 and ROUGE-3 are the common choices because ROUGE-1 ignores order too much and gives high scores even when sentences are shuffled, while ROUGE-2 and higher capture that continuous 2, 3, or 4 words retain order information. The session emphasized that ROUGE-1 will still give a high result even if word order differs, so industry typically reports ROUGE-2 and ROUGE-3 as the balanced view.

Computation for any order follows the same template:

$$\text{ROUGE-N numerator}=\text{common }n\text{-grams}$$

$$\text{ROUGE-N denominator}=\sum (N-n+1)\text{ across references}$$

For a second worked illustration with tiny numbers (self-check): if a reference has $N=5$ words "a b c d e", bigrams are "a b", "b c", "c d", "d e" — four bigrams $=5-1$. Trigrams are "a b c", "b c d", "c d e" — three $=5-2$. If candidate is "a b d e", common bigrams are "a b" and "d e" $=2$, so ROUGE-2 $=2/4=0.50$.

Visual intuition: imagine a bar chart where the x-axis is $n$ (1, 2, 3, 4) and y-axis is ROUGE score for the same candidate against the same references. The bars fall as $n$ grows: ROUGE-1 is highest, ROUGE-4 is lowest, forming a decreasing staircase. The steepness shows how much word order matters in that dataset. Landmark: if ROUGE-1 is $0.70$ but ROUGE-2 is $0.35$, the candidate gets words right but order wrong. Takeaway: report at least two points on this curve to see both coverage and ordering.

Comparison — ROUGE versus BLEU versus BERTScore:

One-line guide: for summarization prefer ROUGE (recall); for translation prefer BLEU (precision); when paraphrase tolerance matters add BERTScore.

16.1.5 Student Questions and Answers

16.1.6 Industry and Pedagogical Notes

Real-world: ROUGE is the standard recall-oriented measure applied across industry for summarization benchmarks. Every extractive, abstractive, single-document or multi-document system is judged with the same ROUGE logic. BERTScore and related embedding-based scores complement ROUGE when paraphrase tolerance is needed; there the word vectors are compared instead of literal strings, so "leaf" and "leafy vegetable" are close in vector space. Modern LLM and AI model evaluation also uses larger toolkits like RAG evaluation harnesses, which include many task-specific measures for conversational AI and question answering; those advanced evaluations are slated for the next semester.

A caution retained from the session: ROUGE counts string overlap, so morphological variants and hyphenated forms count as mismatches unless explicitly normalized in preprocessing. For the exam, always write your tokenization and normalization assumptions, show bigram lists, and state the threshold decision.

16.2 Constituency Parsing — Ambiguity, Grammar and Strategies

16.2.1 Why Parsing Matters and the Ambiguity Problem

Ambiguity — the property that the same surface string maps to many meanings — is the central reason parsing exists. The surface words are fixed, but the relations among them are not. Even with modern transformers that learn relations implicitly, ambiguity remains because natural language permits the same words to attach at different places in a tree.

A vivid example retained from the session: the sentence involving "I saw the man on the hill with a telescope in Texas" was said to have 132 interpretations. The count is not a guess: each prepositional phrase "on the hill", "with a telescope", "in Texas" can attach to the verb "saw", to the noun "man", or to the noun "hill", and those choices multiply. Parsing means deciding, based on the relation among words, which interpretation holds. Was the telescope used to see the man? Was the speaker in Texas? Was the man on the hill? Was the speaker on the hill? Different attachment points produce different meanings. Parsing makes syntactic relations explicit so downstream tasks can ground meaning correctly.

Real-world placement: parsing supports automatic grammar correction, relation extraction, conversational AI, information extraction, and semantic search. Today many systems capture relations implicitly via transformers and self-attention, but earlier explicit parsing is more explainable and still used when you need to enforce grammatical rules, such as correcting a student's essay or ensuring machine translation respects target-language grammar. Both views teach the same core: relations among words must be resolved before meaning is reliable. Modern pipelines often combine both — explicit parse features for safety, attention for coverage.

16.2.2 Grammar, Part-of-Speech and Parse Tree

A parser needs two inputs, and the exam will give you both, so you do not need to memorize them:

1. A set of context-free grammar (CFG) rules. A typical top rule is $S\to NPVP$, where $S$ is sentence, $NP$ is noun phrase, $VP$ is verb phrase. Further rules expand phrases: $NP\to \text{Article Adjective Noun}$ and many others such as $NP\to \text{Article Noun}$, $VP\to \text{Verb NP}$, $VP\to \text{Aux Verb NP}$. Do not memorize rules; they will be provided in the exam and you apply them.
2. The part-of-speech (POS) tag of each word in the sentence — for example, Article, Adjective, Noun, Verb, Auxiliary. The tag restricts which rules can fire.

Given a sentence and the rules, a parse tree depicts relations among words as a hierarchy whose leaves are words and whose internal nodes are phrase labels. Two broad families exist: phrase-structure (constituency) parsing, which groups words into phrases (NP, VP, PP), and dependency parsing (covered in 16.4), which directly connects words with headed arcs.

Example of rule use: for "The large can", the rule $NP\to \text{Article Adjective Noun}$ licenses grouping those three words as one NP if tags are Article, Adjective, Noun respectively. If "can" is instead tagged Aux, that rule cannot fire, so a different analysis is needed. That is how POS tags prune analyses.

16.2.3 Top-Down, Bottom-Up and Chart Parsing

Why chart helps: without it, the article "the" occurring twice causes the same $NP\to \text{Article}\dots$ analysis to be redone. With a chart, after "the" at position 0-1 is recognized as Article, that fact is stored once and reused. The dot notation $A\to \alpha \bullet \beta$ means $\alpha$ already matched, $\beta$ still needed. This is the same idea as memoization in dynamic programming.

Visual intuition: picture a grid where rows are span lengths and columns are word boundaries 0 to $n$. Cell $(i,j)$ holds constituents covering words $i$ to $j$. Bottom row holds words, next row holds $NP$ over "The large can", top cell $(0,n)$ should hold $S$ if the sentence is grammatical. Complexity grows as $O(n^3)$ for CKY (later). Takeaway: parsing fills the triangle from short spans upward; the chart is that triangle.

16.2.4 Worked Example — Bottom-Up Chart Parsing

The same bottom-up flow applies generally: start at words, propose only rules whose first needed symbol matches the current tag, extend dotted items, complete constituents when dots reach the end, and propagate completions upward. Show a small table in the exam with columns Step, Span, Dotted Rule, Action.

16.2.5 Student Questions and Answers — Chart Memory

A useful cross-link retained for later: stack, buffer, and arcs in dependency parsing (16.4) have analogous bookkeeping roles to the chart in constituency parsing: they keep state that allows reuse or transition. The difference is that chart stores completed constituents by span, while stack/buffer store incremental dependency state.

16.3 Statistical Parsing, PCFG, CKY and Parser Evaluation

16.3.1 Statistical Parsing and PCFG Intuition

When multiple parse trees satisfy the same CFG, ambiguity remains unresolved by rules alone. Statistical or probabilistic parsing resolves this by attaching probability values to each grammar rule. The domain matters: if building a parser for the medical domain, probabilities are estimated from a corpus of medical documents; a news corpus gives different numbers. That is the teaching moment about domain specificity — the same rule $NP\to \text{Noun Noun}$ may be common in medical records but rare in poetry. [Teaching moment 16.3.moment.1 — medical domain probabilities, corpus domain specificity]

Probabilistic Context-Free Grammar (PCFG) is exactly the same as earlier CFG but with a probability on each rule. Formally, $G=(N,\Sigma ,P,S)$ where each $A\to \alpha \in P$ carries $P(A\to \alpha )$ with ${\sum }_{\alpha }P(A\to \alpha )=1$ for each left-hand side $A$. These probabilities are counts from training data that is labeled with part-of-speech and phrasing; once a treebank is annotated, counting makes probability estimation straightforward for a machine: $P(A\to \alpha )=\text{Count}(A\to \alpha )/\text{Count}(A)$.

Two additional items stressed: this needs labeled training data (a treebank), and evaluation uses a gold-standard benchmark dataset separate from training.

Real-world placement: PCFG probabilities are domain-specific. A parser trained on Wall Street Journal text may perform poorly on medical notes because rule frequencies change. Retraining on in-domain counts is often required before deployment.

16.3.2 Mathematical Formulation

16.3.3 CKY Parsing and Chomsky Normal Form (CNF)

CKY (Cocke-Kasami-Younger) parsing is a bottom-up chart parsing algorithm specialized for PCFG but with a restriction on rule form. It runs in $O(n^3|P|)$ for sentence length $n$, using dynamic programming over spans. The core requirement for CNF is that every rule's right-hand side must have exactly one terminal or exactly two non-terminals:

$$A\to w\text{(where }w\text{ is a terminal word)}$$

$$A\to BC\text{(where }B,C\text{ are non-terminals like NP, VP, AdjP)}$$

Concrete CNF conversion example retained for exam: $VP\to \text{Verb NP PP}$ (three symbols) becomes $VP\to \text{Verb X}$, $X\to NPPP$ with $X$ a new non-terminal. That two-step replacement is applied wherever a rule has length $>2$.

CKY table intuition: cell $[i,j]$ stores non-terminals that derive substring $i$..$j$. Base cells $[i,i]$ filled by $A\to w_i$ where $w_i$ is word $i$. Then for span length $2$ to $n$, combine splits $k$ between $i$ and $j$: if $B\in [i,k]$ and $C\in [k+1,j]$ and $A\to BC\in P$, add $A$ to $[i,j]$ with probability $P(A\to BC)\times P(B\text{ in }[i,k])\times P(C\text{ in }[k+1,j])$. The max-probability parse is recovered by back-pointers.

Visual: imagine a triangular table with words along the diagonal. You fill bottom row with POS tags, then grow upward: two bottom cells combine to form a cell above. Landmark is top cell $[0,n-1]$ — if it contains $S$, sentence is grammatical and its stored probability is $P(S)$. Takeaway: CKY is chart parsing turned into a filled triangle with max-probability bookkeeping.

Exam note: you may be asked to convert rules to CNF first, then apply CKY to get the parse probability and the tree. Apply probability values at every point where a rule is applied and show the table or arcs.

16.3.4 Evaluation of Parsers — Labelled Precision, Recall and F-Score

Any parser system must be evaluated against a gold standard dataset that contains benchmark parses (the treebank test split). The standard measures are precision and recall, adapted to constituents because a constituent is correct only when both its label (e.g., NP, VP) and its span positions match the gold. Positions matter: even if the rule label is the same, differing positions means not identical — an NP covering words 0-2 is different from an NP covering 1-3.

16.4 Dependency Parsing

16.4.1 Foundations — Heads, Roots, Nodes and Rules

While phrase-structure parsing groups words into phrases, dependency parsing finds direct relations between words. That is its focus: each word chooses one head it depends on, and the set of choices forms a tree.

Key terms:

• Root word: the most important word in the sentence, typically the main verb. Each phrase also has a head/root: a noun phrase has noun as its head, a verb phrase has verb as head.
• Words are treated as nodes (vertices), relations as directed edges (arcs) labeled with relation types such as nsubj, dobj, det, or similar short forms.
• Edge labels are short forms indicating the relation type; you do not need to memorize them — if named relations are asked in arc-eager parsing, those names will be provided.

Rules that a final dependency graph must satisfy to be a well-formed tree (an arborescence rooted at an imaginary ROOT):

• No island nodes: every word must be connected to at least one other node — no isolated word left floating.
• Every word has a single head (single incoming edge). A word cannot have two bosses.
• The root is an imaginary word, not an actual token; every real word may have an incoming edge from ROOT, but ROOT has no incoming edge, and typically exactly one word (the main verb) is a child of ROOT.
• No cycles: following head arrows must eventually reach ROOT without looping.
• Projectivity is often assumed for arc-eager but not for graph-based — the lecture notes that graph-based can handle non-projective cases.

Naming of relations need not be memorized; CKY can be used for dependency but is complex and not popular, so exam will give labels if needed.

Real-world placement: dependency parsing is more widely used in industry for relation-centric tasks than constituency, though constituency remains foundational and better suited to grammar-check systems like Grammarly or to machine translation where the grammar of the target language must be followed exactly. The choice depends on application: dependency helps capture meaning via word relations ("who did what to whom"); constituency helps enforce phrasal grammar ("is the noun phrase well-formed?"). Many modern systems learn dependencies implicitly via transformers but still expose explicit dependency APIs where explainability matters.

Visual: draw words in a line, with ROOT above the verb. Arcs are arrows from head to dependent curving above the line. A valid tree has every word with one incoming arrow, no word isolated, and all arrows eventually trace back to ROOT. A cycle would be two words pointing at each other — a loop above the line that must be broken.

16.4.2 Deterministic Arc-Eager Parsing — Stack, Buffer and Arcs

For the exam, expect a table with columns Step, Stack, Buffer, Arcs, Transition. Initial state is Stack [], Buffer [w1...wn], Arcs {}. Terminate when Buffer empty and Stack contains only ROOT or is empty depending on variant.

16.4.3 Walkthrough — Arc-Eager Steps

Student exchange during walkthrough confirmed: after shift, the stack gains the first buffer word and the buffer loses it; after left-arc the dependent leaves the stack and arcs grow; after right-arc the dependent is pushed but the head remains — these are the invariants to keep.

16.4.4 From Transitions to a Classifier — Feature Learning

Creating the gold transition sequence alone does not make a parser. The purpose is to create training data for a multi-class classifier where each configuration's features predict the gold transition.

Features: part-of-speech tags, word forms, stack/buffer top items, and rule-like contextual clues. A configuration's feature vector encodes, for example, is-stack-empty, POS of stack top, POS of buffer front. Any machine learning or neural classifier, including feedforward networks or transformers used as classifiers, can be trained on these features.

Feature learning boils down to learning weights for each feature. At test time, the input features are multiplied by learned weights to decide which transition to predict — exactly like a 4-way logistic classifier over {SHIFT, LEFT-ARC, RIGHT-ARC, REDUCE}.

A misconception corrected in class: weight update does not mean executing the wrong predicted arc; it means adjusting numbers so that future argmax will favor the oracle. The benchmark transition drives the state progression during training — keep those two roles separate.

16.4.5 Graph-Based Dependency — Chu-Liu Edmonds

16.4.6 Learning Edge Weights

Exam note: expect problems on graph-based parsing for one of: tree construction with given edge weights, or edge-weight calculation from features with $w^{\top }f$, or one iteration of weight recomputation. Show work in tables where required, and always state feature definitions as given.

16.5 Contextual Word Embedding and Attention

16.5.1 Motivation — From RNN to Attention

Early sequence models progressed from RNN to LSTM to encoder-decoder. The encoder converts input into a hidden representation; the decoder generates output token by token. A known limitation is vanishing or diminishing gradients: during back-propagation through many time steps, gradients shrink toward zero, so early-layer weights move close to zero and key features are effectively ignored. That means some words in the sentence are ignored when deciding an output such as translation — the model "forgets" the beginning by the time it reaches the end.

Attention was introduced to capture relations among input words explicitly without relying solely on recurrent compression. Rather than compressing the whole sentence into one vector, attention computes vector similarity between words and uses those similarities to decide importance for each position.

Normalization idea: similarity scores must be turned into proportions that sum to one, so the model can select among options in a calibrated way. Softmax does that: it exponentiates scores and normalizes to a probability distribution. If there are 10 options, normalizing ensures probabilities add to one and the most relevant option can be chosen. The same idea applies when deciding how much one word pays attention to others — the attention weights ${\alpha }_{i,j}$ sum to 1 across $j$ for each $i$. [Teaching moment 16.5.moment.1 — softmax normalizes similarities to probabilities summing to one]

Real-world consequence of vanishing gradients: in a long clinical note, the diagnosis at the start may be lost by the end of an RNN. Attention fixes this by letting the last word attend directly to the first, with path length 1 instead of $n$ steps.

Visual: picture a $n\times n$ matrix where row $i$ is the query word and column $j$ is the key word; cell brightness is ${\alpha }_{i,j}$. Row sums are 1. For "I ate mango", row for "mango" may shine brightly on "ate" (verb-object) and on itself, dimly on "I". Takeaway: attention matrix shows which words each word listens to.

16.5.2 Self-Attention vs Cross-Attention

Why this split matters: if you are only embedding a sentence to obtain vectors for classification or search, you need self-attention alone. If you are translating, you need cross-attention to align source and target. The test will ask you to state which is used when and why contextual embedding excludes cross-attention.

16.5.3 Mathematical Formulation — Query, Key, Value

16.5.4 Multi-Head Attention

The above describes single-head attention. Multi-head attention uses multiple separate sets of $W_Q,W_K,W_V$ matrices — that is, multiple attention heads, often $h=8$ or $12$. Each head can focus on a different linguistic aspect: one head might focus on part-of-speech patterns, another on phrase structure, another on dependency relations such as subject-verb. The example mentioned in class from a university study showed each attention head capturing a different type of relation when visualized — one head's $\alpha$ matrix lit up noun-modifier pairs, another lit up verb-object.

Combining heads yields richer representation than a single head. Conceptually, if you have $h$ heads, you get $h$ different $z_i^{(h)}\in {\mathbb{R}}^{d_v}$ and they are concatenated then projected:

$$z_i=\text{Concat}(z_i^{(1)},\dots ,z_i^{(h)})W_O$$

where $W_O\in {\mathbb{R}}^{h{d}_v\times d}$ mixes heads back to dimension $d$. The benefit is specialization: different heads learn different $W_Q,W_K,W_V$ so they attend to different patterns, and the concat lets the model combine those views.

Why not just one bigger head? Multiple heads with smaller $d_k$ allow diverse representations without blowing up computation, and each head can learn a distinct similarity metric rather than averaging into one.

16.5.5 Positional Encoding and Masking

Independent of attention scores, word order matters: "I eat mango" is not the same as "mango eat I" — attention alone is permutation-invariant (swapping words permutes rows but not values), so order must be injected. Positional encoding captures that order. Instead of relying on recurrence, a fixed or learned positional signal $P{E}_i\in {\mathbb{R}}^d$ is added to the word vector:

$$x_i^{\prime }=x_i+P{E}_i$$

Sometimes written as:

$${\text{input}}_i={\text{embedding}}_i+{\text{positional\_encoding}}_i$$

The method for computing $PE$ (for example sine and cosine functions of position and dimension: $P{E}_{(pos,2k)}=\sin (pos/10000^{2k/d})$, $P{E}_{(pos,2k+1)}=\cos (pos/10000^{2k/d})$) need not be memorized; only the fact that it is added to the original contextual embedding to retain order information is important. Values from the positional encoding are summed with the attention-derived vectors elementwise before feeding to the encoder block.

Future masking: in self-attention for generation (decoder), only current and previous words are visible; future words are masked by setting their scores to $-\infty$ before softmax so $\alpha$ becomes 0 for future positions. This prevents cheating by looking ahead. This detail was noted as for understanding only; the exam's mathematical question will focus on self-attention contextual embedding steps described above, not on masking details inside full transformers.

Encoder block also contains residual connections ($z_i+x_i$) and layer normalization and feed-forward sublayers that produce probabilistic values, but those are not exam-critical beyond recognizing their presence: they stabilize training and add non-linearity after attention.

Visual: picture a stack of encoder blocks: input at bottom → add PE → self-attention (with $Q{K}^{\top }/\sqrt{d_k}$ and softmax) → add & norm → feed-forward → output at top. Each block refines $z_i$; stacking 6 or 12 blocks builds deep contextualization.

16.5.6 Significance

The biggest advantage of contextual embedding over static embeddings (such as GloVe, Skip-Gram, CBOW studied pre-midterm) is that the same surface word receives different vectors depending on context words, because attention weights $\alpha$ change with surrounding words. Static embeddings give one vector per word type irrespective of context: the word "bank" gets one point in space. Contextual gives every occurrence its own point — "river bank" and "bank account" are far apart in space despite sharing a string.

A concrete consequence: a classifier that uses static vectors must struggle with polysemy, while one that uses $z_i$ can separate senses linearly because context has already disambiguated. That is why contextual vectors remain the standard even in modern agentic AI scenarios where inputs are converted to vectors via contextual embedding before tool use.

Real-world: transformers and their attention mechanism dominate current NLP, and vector similarity with normalization via softmax is a recurring technique in industry systems at web scale — from search ranking to retrieval-augmented generation. The same scaled-dot product appears in rerankers and dense retrievers.

16.6 Word Sense Disambiguation, WordNet and Knowledge Graphs

16.6.1 What Word Sense Covers

Word sense is the exact meaning intended for a polysemous word in context (for example "bank" as river bank versus financial institution, or "bass" as fish versus musical instrument). Word Sense Disambiguation (WSD) is the task of choosing the correct sense for each occurrence in running text; the system must output a sense identifier rather than just a POS tag.

WordNet is a manually created lexical graph that records relations among words: hypernymy (more general — "canine" is hypernym of "dog"), hyponymy (more specific — "dog" is hyponym of "animal"), synonymy (words sharing a synset), meronymy (part-of), and others. WordNet groups word forms into synsets (sets of synonyms) and links synsets via these relations, forming a navigable graph of meaning. These relations support disambiguation as features — if candidate sense shares hypernyms with surrounding words, it gains evidence.

Why WordNet still matters in the neural era: even with contextual embeddings, WordNet provides curated, interpretable links that are useful for low-resource domains and for building ontologies where you need explicit relation names, not just vector closeness. It also supplies glosses for the Lesk algorithm next.

Visual: imagine WordNet as a subway map. Synsets are stations, hypernym links are north-bound lines toward generality, hyponym links go south toward specificity. "Bass" appears at two stations on different lines; context words "fish" and "guitar" light up nearby stations. The brighter path picks the correct station.

16.6.2 Supervised Learning and Lesk

Lesk algorithm: a simple yet powerful unsupervised method that requires no labeled training data, only WordNet glosses. It uses word overlap between the test sentence and the dictionary gloss (definition plus example sentences) for each sense. Count how many words overlap; the sense with highest overlap wins. Variants exist, but core Lesk is count intersection.

Comparison — supervised versus Lesk:

One-line guide: if you have labeled examples for that word, train Naive Bayes; if not, run Lesk and consider vector-extended Lesk for paraphrase tolerance.

16.6.3 Semantic Web, Ontology and Knowledge Graphs

Connections made in class:

• Knowledge graphs are used far beyond one retrieval method: Google's knowledge graph powers web search, enriching queries with entities without exposing user data. Agent frameworks access web APIs and search results internally via similar graph-backed knowledge — the agent's tool call is routed through an entity graph.

• In modern agent AI, ontologies and knowledge graphs help ground agents and prevent undesired autonomous actions, contributing to safe behavior even on the path toward more general intelligence. Example: an agent asked to "book the cheapest flight" can be constrained by an ontology that defines allowed airlines, budget limits, and booking rules, so it cannot book outside policy. This is why ontology remains relevant despite neural dominance — it supplies hard guardrails where vectors supply soft similarity.

• Graph-based retrieval (Graph RAG, covered in 16.7) stores data as a graph rather than plain vectors, suitable for domains like medical and finance where relations must be precise (drug-interacts-with-disease). Normal (naive) RAG stores vectors, Graph RAG stores nodes and edges.

Six marks can be expected on word sense disambiguation plus semantic web ontology together, asked as conceptual or application-oriented questions based on algorithms (Lesk, Naive Bayes) or knowledge graph construction. No heavy math beyond the small Naive Bayes or Lesk table.

16.7 Retrieval Augmented Generation (RAG)

16.7.1 Architecture and Motivation

Retrieval Augmented Generation (RAG) is a semantic search plus generation pattern present in roughly 90 to 95 percent of industry projects today, so understanding it deeply matters beyond the exam.

The same idea applies in federated contexts where each organization keeps its own corpus private and RAG retrieval is scoped locally — no cross-org data leakage.

Visual: draw a swim lane with three boxes: Corpus → Vector Store (offline indexing), Query → Embed → Search → Top-K chunks, then Prompt = System + Query + Chunks → LLM → Grounded answer with citations. Arrows show 500 pages in, 5 pages out, then answer out. Landmark: the narrow waist after retrieval is where cost and quality are traded.

16.7.2 Token Cost, Budget and Chunking

Definitions: a chunk is a contiguous group of words/section into which every document is broken before embedding (for example 512 or 600 tokens). Retrieval returns chunks, not whole documents. Selection uses a threshold cutoff or top-K highest similarity scores; top-K is deterministic count, threshold is quality-driven.

16.7.3 Latency and Reranking

Retrieval is not free. The user waits while embedding, search, reranking, and generation happen sequentially.

Real-world placement: chunk-level similarity threshold, top-K selection, and reranking are design choices balancing quality versus cost and time. Many production RAG systems set adaptive $K$ per query: high similarity → smaller K, low similarity → larger K, always bounded by token budget.

16.7.4 Variants, Tools and Exam Focus

Exam note: mathematical problems on RAG may ask token budget with given numbers ($L_{\max },T_{\text{system}},T_{\text{query}},C$), chunk overlap/stride calculation ($C-O$, $D/\text{stride}$), latency allowance and whether reranking fits ($T_{\max }-\text{others}$), purpose and calculation of similarity threshold/top-K, or a combination of all these. No mathematical problem on multimodal or agentic RAG; only conceptual understanding ("what is multimodal RAG, when to use") is expected. Any simple combination of token, chunk, and latency numbers can be given — show formulas and floor/ceiling choices explicitly.

16.8 Text Summarization

16.8.1 Types and When Each Suits

Text summarization reduces a longer text to a shorter version that retains key information while respecting length and coherence.

Approaches for extractive content selection:

• IR-based: steps are content selection (which sentences are most important), information ordering (in what order to present them for coherence), and sentence realization (polishing). Example IR-weighting: weight words by TF-IDF and give a sentence the sum of its words' TF-IDF weights (normalize by length to avoid long-sentence bias); sentences with maximum aggregated TF-IDF may be most important and should appear in the summary. Detailed TF-IDF example was shown and should be reviewed — compute term frequency times inverse document frequency per word, sum per sentence, rank.

• Graph-based (LexRank style): represent sentences as nodes, connect by vector similarity (or embedding cosine) above a threshold, find sentences that are maximally connected/central — the most central nodes have high LexRank scores and are likely summary-worthy. It is the graph analogue of PageRank on sentences, alternative to TF-IDF when you trust inter-sentence similarity over word frequency.

• Neural: feed the text into autoencoders or transformers (encoder-decoder) which generate the summary directly; worry about encoder length limits and decoder hallucination. No mathematical problem on neural summarization was indicated for this course, but understanding the pipeline is required: encode long text, decode short summary, train on article-summary pairs, evaluate with ROUGE.

Visual: for IR, imagine a bar chart where x-axis is sentences and y-axis is summed TF-IDF — the top five bars are selected. For graph, imagine sentences as dots with lines thicker for higher similarity — the densest cluster center is selected. For neural, imagine an hourglass: wide encoder, narrow bottleneck, wide decoder. Takeaway: different signals (frequency, centrality, learned) pick sentences differently.

Comparison — extractive versus abstractive versus graph:

One-line guide: need audit trail → extractive; need consensus → LexRank; need fluency → abstractive with RAG grounding.

16.8.2 Redundancy Control — MMR

When a summary is limited to, say, five sentences, selecting the five individually most important sentences can produce redundant information — they may all say the same thing in slightly different words, wasting budget. Redundancy must be removed while relevance is retained. The tool for this is Maximal Marginal Relevance (MMR), used after ranking for content selection.

Additional notes retained:

• Information ordering after content selection also matters; the selected sentences must be ordered coherently (for example chronologically or by narrative flow), not just by MMR score order. Query-focused multi-document summarization combines selection and ordering steps across many source documents, plus redundancy removal across documents.

• Evaluation of summaries uses ROUGE, as covered in 16.1; neural summaries are evaluated the same way — ROUGE-N with $12/28\approx 0.43$ pattern and threshold. So the pipeline is: select via TF-IDF/LexRank/MMR → order → evaluate via ROUGE.

Exam note: text summarization was recently covered, so less time was spent in this recap, but standard question types include: conceptual differences (extractive versus abstractive, generic versus query — state which fits a scenario), IR-based steps with TF-IDF calculation, LexRank graph example description, and MMR calculation with $\lambda =0.5$ balance. Neural techniques require only conceptual preparation (describe encoder-decoder and length limits). Also expect a potential evaluation problem as noted for ROUGE.

Exam Guidance Summary

This session served as the final post-midterm recap; pre-midterm quick review was deferred due to time but slides and videos remain available for that portion. All guidance below is carried through from the earlier draft and supplemented with procedure tips.

Structure and marks

• End-semester examination is weighted 40 marks. Pre-midterm content contributes 10 marks; post-midterm contributes 30 marks.
• Paper is open-book. Do not memorize grammar rules, relation names, or long derivations; those will be provided. Instead ensure understanding of procedures so you can apply given rules, POS tags, feature tables, and edge-weight tables.

Breakdown by module — what to expect and how to answer

• Module 2 — vector semantics and language models: 5 marks. Expect mathematical problems on TF-IDF (compute term frequency times inverse document frequency, sum per sentence) or conceptual questions on vector semantics and word embeddings (contrast static GloVe/Skip-Gram with contextual); also a problem on n-gram language models (count, smoothing, perplexity) or an application-oriented question on neural language models.

• POS tagging via Hidden Markov Model: 5 marks. Expect a problem either with Viterbi (trellis with emission and transition probabilities) or without Viterbi (HMM tagging by max probability).

• Parsing (constituency / statistical / dependency together): 6 marks. Expect a small problem or application-oriented question such as building a parse tree via bottom-up chart (show spans, e.g., $NP\to \text{Article Adjective Noun}$), or comparison of why one parsing strategy suits a given application (constituency for grammar check, dependency for relations). Rules and POS tags will be given; you decide phrase boundaries.

• Statistical parsing and PCFG plus CKY and evaluation: integrated with parsing. PCFG six marks style: compute $P(T)=\prod P(r)$ and $P(S)=\sum P(T)$, with domain-specific probabilities. CKY/CYK: expect CNF conversion ($A\to w$ or $A\to BC$, binarizing longer rules with new non-terminals) before CKY; sample paper includes a CNF+CKY question — practice it. Parser evaluation may ask Labelled Precision, Recall, $F_1$ with label+span matching.

• Dependency parsing: part of parsing marks. Expect Arc-eager transition table (stack, buffer, arcs; operations SHIFT, LEFT-ARC, RIGHT-ARC, REDUCE) or Chu-Liu Edmonds graph maximum spanning tree problem using given edge weights (greedy max incoming — keep 30, keep 20 — and cycle contraction with WJS 40 versus 29, 31 versus 30). Also possible: feature weights one iteration with 12 dimensions (C0 C1 C2) showing shift versus left-arc 6 and 4.5, and update $w_{\text{new}}=w_{\text{old}}+f_{\text{oracle}}-f_{\text{predicted}}$. Also edge score $w^{\top }f(i,j)$ where Root→John score 12 will be given as feature table.

• Contextual word embedding and Attention: 6 marks. Mostly a mathematical problem on self-attention: compute $Q_i=x_i{W}_Q,K_i=x_i{W}_K,V_i=x_i{W}_V$, scaled score $Q_i{K}_j^{\top }/\sqrt{d_k}$, softmax ${\alpha }_{i,j}$, weighted sum $z_i=\sum {\alpha }_{i,j}{V}_j$ for three words I/ate/mango style example; plus conceptual comparison of self-attention versus cross-attention and positional encoding $x_i^{\prime }=x_i+P{E}_i$. Residual and layer norm are not core.

• Word sense disambiguation + semantic web ontology: 6 marks together. Expect conceptual or application-oriented questions based on algorithms (Lesk overlap $|\text{Gloss}(s)\cap C|$ or Naive Bayes $P(s)\prod P(c\mid s)$ for bass fish versus music) or knowledge graph / RDF / OWL construction (triples subject-predicate-object, class axioms) and component description. No heavy math beyond small tables.

• Retrieval Augmented Generation: can include mathematical problems or concepts. Be ready for token budget $T_{\text{retrieved}}=L_{\max }-T_{\text{system}}-T_{\text{query}}$ and max chunks $\lfloor 7672/512\rfloor =14$ (floor not ceiling), chunk overlap/stride $600-120=480$ and chunks $18200/480\approx 38$, latency $T_{\text{total}}=T_{\text{embed}}+T_{\text{retrieval}}+T_{\text{rerank}}+T_{\text{generation}}$ and check against 2500 ms threshold to decide if reranking fits, plus threshold/top-K reasoning. Tool and challenge awareness is enough for the non-numerical part.

• Text summarization: can include mathematical or application questions. Expect ROUGE evaluation (ROUGE-2 $12/28\approx 0.43$ with denominator $N-n+1$, ROUGE-1 word overlap, ROUGE-3 $N-2$, threshold), or MMR with $\lambda =0.5$ balance $\lambda \text{Sim}(D_i,Q)-(1-\lambda )\max \text{Sim}(D_i,D_j)$, or TF-IDF / LexRank conceptual and scoring steps. Neural summarization is conceptual only. Text summarization evaluation, MMR, and related concepts are all fair game; MMR lambda 0.5 relevance versus redundancy is specifically noted. Evaluation also covers overall weight: pre-mid 10 marks include TF-IDF, n-gram language model, neural LM 5 marks plus HMM POS Viterbi 5 marks — review those slides too. Overall 40 marks, 30 post-mid weightage, open book show tables and assumptions — the recurring instruction is to show work and state assumptions.

• Overall exam advice — open book strategy: Refer to Jurafsky and Martin (especially parsing chapters — statistical parsing, PCFG, CKY) and to the shared watermark slides on the e-learn portal. Use recordings for stepwise algorithm demonstrations. For printing, minimize pages: include only slides with formulas or details that are hard to recall; smaller printouts are faster to search during the exam and save cost and paper. Show work in tables (for example chart parsing steps, stack-buffer-arc tables, CKY triangular tables); this makes grading easier and helps secure partial marks. Write all assumptions in full where interpretation is needed (tokenization for ROUGE hyphen handling, span convention for precision/recall, span numbering for parsing). Practice sample paper questions: there is a question on CNF conversion and CYK in the sample. Difficulty calibration: word sense disambiguation and ontology were described as comparatively simple if concepts are understood — an opportunity to secure marks — so do not leave them to last.

Key Industry Applications

• ROUGE as deployment gate: ROUGE provides the universal recall-based benchmark for summarization systems before deployment. Teams set a threshold (for example ROUGE-2 $>0.35$) to decide whether an extractive or abstractive summary is good enough, mirroring the lecture's $12/28\approx 0.43$ example and threshold decision.

• Parser benchmarking: Labelled precision, recall and $F_1$ with label-plus-span matching (exact label and span must match) are standard for parser benchmarking against gold treebank data. A candidate constituent $(NP,0,2)$ does not match $(NP,0,3)$ — that strictness is used in industry evaluation harnesses.

• Constituency versus dependency in production: Constituency parsing underpins grammar-check tools (Grammarly-style) and machine translation where target phrase grammar must be enforced; dependency parsing underpins relation extraction, information extraction, and conversational AI (who did what to whom). Modern pipelines often use dependency relations implicitly via transformers and attention, while still relying on graph-based dependency or neural dependency models in production where explicit relations are needed for explainability.

• Domain-specific PCFG: PCFG domain-specific rule probabilities illustrate why parsers trained on one domain (for example medical) may not transfer without retraining — Wall Street Journal probabilities differ from clinical notes. Retraining on in-domain treebank counts is standard before deploying a parser in a new domain.

• CKY with CNF as textbook standard: CKY with CNF ($A\to w$ or $A\to BC$) is the tabular algorithm taught in textbooks such as Jurafsky and Martin and mirrors bottom-up chart parsing used in statistical parsing pipelines where binarized rules via new non-terminals are introduced first.

• MaltParser-style learning to parse: MaltParser-style arc-eager deterministic parsing illustrates how oracle transitions over stack/buffer/arcs become training data for classifier-based parsers, a pattern reused across ML and neural implementations where features (C0 C1 C2, 12 dimensions) and weights are learned (shift 6 versus left-arc 4.5 after perceptron update $w_{\text{new}}=w_{\text{old}}+f_{\text{oracle}}-f_{\text{predicted}}$) and applied at test time.

• Chu-Liu Edmonds as workhorse: Chu-Liu Edmonds maximum spanning tree (arborescence) is the workhorse for graph-based dependency parsing in production, greedily keeping max incoming (for example 30 for Mary, 20 for saw) and contracting cycles (WJS 40 versus 29, 31 versus 30) when greedy creates a loop, then expanding — exactly the steps practiced for the exam.

• Contextual embeddings as LLM substrate: Contextual word embeddings with self-attention ($Q_i=x_i{W}_Q,K_i=x_i{W}_K,V_i=x_i{W}_V$, scaled dot $Q{K}^{\top }/\sqrt{d_k}$, softmax to $\alpha$, weighted sum $z_i=\sum \alpha V$) are the input representation for today's LLMs and agentic AI, replacing static embeddings like GloVe and Skip-Gram where a single word type had one vector. The same scaled-dot product is used in dense retrievers and rerankers.

• WordNet and Lesk in practice: WordNet as a manually built lexical graph enables sense features via hypernymy/hyponymy; simple Lesk-style overlap ($|\text{Gloss}(s)\cap C|$) still competes with heavier methods for many disambiguation tasks where data is scarce, while supervised classifiers treat each sense as a class (Naive Bayes over bass fish versus music). Both patterns appear in entity linking and search query disambiguation.

• Knowledge graphs for grounding and safety: Knowledge graphs (for example Google Knowledge Graph) support web search and agent tooling (agent web-search tool calls). Ontology languages RDF (triples subject-predicate-object) and OWL (classes, restrictions, reasoning) encode domain facts for safe grounding of agents, relevant even on the path toward more general intelligence, where grounding prevents undesired autonomous actions. Ontology design (entities, classes, relations) is the first step before graph construction.

• RAG at scale: RAG architectures dominate current deployments (around nine in ten projects, 90-95% ). Variants in use include naive vector RAG (flat store), Graph RAG for medical/finance where graph traversal matters, multimodal RAG for multi-format data (text plus tables/images), and agentic RAG for orchestrated multi-step workflows. Practical cost and latency engineering tasks are token-budget ($L_{\max }-T_{\text{system}}-T_{\text{query}}$ and $\lfloor 7672/512\rfloor =14$), chunk-overlap with stride ($600-120=480$, $18200/480\approx 38$ chunks), and latency-budget ($T_{\text{embed}}+T_{\text{retrieval}}+T_{\text{rerank}}+T_{\text{generation}}<2500$ ms) calculations. Embedding-based BERTScore mirrors ROUGE logic but on vectors, improving tolerance to paraphrase where leaf versus leafy mismatch is no longer a failure.