Lecture 4: Inference — Greedy and Search

Roles

Model vs inference

• Model assigns scores to (input, output) — full sequences, spans, labels.
• Inference searches for high-scoring output (not always global argmax).
• Learning adjusts model so intended outputs score high.

RecallIn one sentence: what does inference optimize if the model is fixed?

Exact

Exhaustive search

• Enumerate all candidates → argmax (small output spaces, e.g. some assignments).
• POS: \(|T|^n\) tag sequences — e.g. \(17^4\sim 8.3\times 10^4\); \(17^{20}\) intractable.
• Exact but rarely scales.

RecallWhy is exhaustive tagging OK for 4 words but not 20 (order of magnitude)?

Approximate

Greedy & decoding variants

• Greedy: best tag/token one step at a time · \(O(n|T|)\) vs \(|T|^n\).
• May disagree with global argmax (e.g. POS “Fruit flies…” example).
• Generation variants: top-1 argmax; random sample; top-k; top-p nucleus; contrastive (penalise repetition).

RecallTop-p vs top-k in one phrase each.

Prune

Beam search

• Keep top-\(K\) partial hypotheses; extend; prune · complexity ∝ length × \(K\) × branching.
• Top-\(K\) maintenance: naive / heap / quickselect.
• Variable length: organise beams by length or steps; normalise scores (e.g. avg log-prob per word).

RecallWhat does beam width \(K\) trade off?

Heuristics

Graph search

• Partial outputs as graph paths.
• Use estimate of future score to guide extension (A*-like, but maximise score not shortest path).

Structure

Sequence tagging

• Independent per-token predictions → BIO violations.
• Greedy errors early are irreversible.
• Tractable chain models: Viterbi for best joint tag sequence under local scores.

RecallWhy can greedy tagging break BIO constraints?

Structure

Dependency parsing

• Dependencies: directed arcs from head to dependent word; parse = tree over the sentence.
• "I saw the person on the hill with a telescope" → multiple valid parses (PP attachment ambiguity).
• Arc model: parse score = sum of individual arc scores; inference must produce a tree (no crossing arcs, single root).
• Search algorithms exploit tree structure for tractable exact inference.

RecallWhat constraint must a dependency parse satisfy that general graphs do not?

Discourse

Coreference resolution

• Identify all mentions in a text that refer to the same real-world entity (e.g. "Victoria Chen", "she", "the CEO").
• Search space: \(|w|^2\) possible mention pairs × all possible clusterings.
• Simplify: (1) detect and filter mentions, (2) link each mention to its best antecedent, (3) transitive closure → entity clusters.
• Entity linking / Wikification: link mentions to external knowledge base entries.

RecallThree steps to simplify coreference search.

Lab

Workshop 4

• chapters/chapter4/Materials/Workshop4/ — char RNN, language of surname · names.txt, workshop4.ipynb.

Quick practice