SLP3 Ch8 — Sequence Labeling for Parts of Speech, HMM and Viterbi — NLP Book Notes

// the one-minute version

Chapter 8 explains sequence labeling for parts of speech, hmm and viterbi as a practical model-building toolkit: represent language numerically, estimate useful quantities from text, make simplifying assumptions explicit, and evaluate on held-out data rather than on memory of the training corpus.

Treat this page as a long plain-English companion to Jurafsky and Martin, Speech and Language Processing, 3rd edition, Chapter 8. It expands the why behind each formula, the engineering choices hidden behind clean notation, and the gotchas that usually cause wrong answers or fragile implementations.

representationturn language into numberstokens, counts, vectors, states

estimationlearn from datacounts, objectives, gradients

evaluationtest honestlyheld-out data, metrics, error analysis

01 Sequence labeling as structured prediction

Sequence labeling as structured prediction is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Sequence labeling as structured prediction sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

Read the math as compressed prose. A conditional probability says what information is known. A \(\frac{\text{count}}{\text{normalizer}}\) says which events are being compared. A \(\sum\) accumulates alternatives, evidence, or loss terms. A \(\log\) changes products into stable additive scores. This habit prevents symbol shock: instead of staring at a formula, translate every part into the modeling decision it represents.

For exams and projects, connect sequence labeling as structured prediction to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

02 Parts of speech and penn treebank tagsets

Parts of speech and penn treebank tagsets is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Parts of speech and penn treebank tagsets sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect parts of speech and Penn Treebank tagsets to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

03 Why tagging is ambiguous

formula\[\hat{t}_{1:n}=\arg\max_{t_{1:n}}\prod_{i=1}^{n}P(w_i\mid t_i)P(t_i\mid t_{i-1}),\quad v_i(t)=P(w_i\mid t)\max_{u}v_{i-1}(u)P(t\mid u),\quad P(w_{1:n})=\sum_{t_{1:n}}P(w_{1:n},t_{1:n}).\]

Why tagging is ambiguous is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Why tagging is ambiguous sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect why tagging is ambiguous to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

04 Hmm hidden states and observed words

think of it likeThe model is a map, not the territory. It leaves out detail so that routes can be planned, compared, and explained.

Hmm hidden states and observed words is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Hmm hidden states and observed words sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect HMM hidden states and observed words to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

05 Transition matrix a and emission matrix b

Transition matrix a and emission matrix b is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Transition matrix a and emission matrix b sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect transition matrix A and emission matrix B to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

RepresentationWhat object is used: tokens, counts, vectors, states, or scores?

EstimationWhich corpus evidence changes the numbers?

FailureWhere do sparsity, ambiguity, bias, or domain shift appear?

06 The two hmm assumptions

watch outNever compare scores unless tokenization, vocabulary, train-test split, and evaluation metric are the same.

The two hmm assumptions is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. The two hmm assumptions sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect the two HMM assumptions to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

07 Estimating probabilities from tagged corpora

Estimating probabilities from tagged corpora is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Estimating probabilities from tagged corpora sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect estimating probabilities from tagged corpora to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

08 Decoding as an argmax problem

The chapter turns language evidence into a score or structured decision.

Decoding as an argmax problem is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Decoding as an argmax problem sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect decoding as an argmax problem to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

09 Viterbi dynamic programming recurrence

Viterbi dynamic programming recurrence is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Viterbi dynamic programming recurrence sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect Viterbi dynamic programming recurrence to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

RepresentationWhat object is used: tokens, counts, vectors, states, or scores?

EstimationWhich corpus evidence changes the numbers?

FailureWhere do sparsity, ambiguity, bias, or domain shift appear?

10 Backpointers and a small trellis intuition

the catchClassroom formulas look clean because preprocessing, smoothing, optimization, and error analysis have been hidden. Real NLP lives in those details.

Backpointers and a small trellis intuition is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Backpointers and a small trellis intuition sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect backpointers and a small trellis intuition to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

11 Forward algorithm sums over paths

A second diagram for the same chapter: evidence is weighted, normalized, and interpreted.

Forward algorithm sums over paths is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Forward algorithm sums over paths sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect forward algorithm sums over paths to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

12 Memms and discriminative tagging

Memms and discriminative tagging is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Memms and discriminative tagging sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect MEMMs and discriminative tagging to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

13 Bidirectionality and modern bi-lstm-crf

Bidirectionality and modern bi lstm crf is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. Bidirectionality and modern bi lstm crf sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect bidirectionality and modern Bi LSTM CRF to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

14 How to revise sequence labeling

How to revise sequence labeling is one of the working ideas in Sequence Labeling for Parts of Speech, HMM and Viterbi. In plain English, it tells us what evidence the model is allowed to use and what it must predict. The important move is not the notation by itself; the important move is turning a messy language phenomenon into an object that can be counted, weighted, optimized, decoded, or compared. Once that object exists, the rest of the chapter asks how reliable it is, how it fails, and how to evaluate it honestly.

The reason this matters is the recurring NLP trade-off between rich context and reliable statistics. If the representation keeps every detail, the model sees too many rare cases and cannot generalize. If it throws away too much, it becomes stable but shallow. How to revise sequence labeling sits somewhere between those extremes. It keeps enough structure to be useful, but it imposes a simplifying assumption so the computation can finish on real corpora rather than imaginary perfect data.

For exams and projects, connect how to revise sequence labeling to errors. Ask what happens with unseen words, rare contexts, ambiguous examples, noisy labels, biased text, and domain shift. Ask whether the evaluation is intrinsic, like perplexity or similarity, or extrinsic, like task accuracy. Ask which choices are learned from data and which were manually chosen. These questions turn the chapter from a list of definitions into a debugging checklist.

15 References and extra reads

The primary reference is Daniel Jurafsky and James H. Martin, Speech and Language Processing, 3rd edition online draft, Chapter 8. These notes follow the chapter vocabulary while expanding the intuition, assumptions, equations, examples, caveats, and revision strategy.

Extra reads after SLP3: information retrieval notes for vector spaces, smoothing tutorials for language models, neural network optimization introductions, and sequence labeling resources on HMMs, CRFs, and Bi-LSTM-CRF decoders.

FAQ Quick questions students usually ask

Should I memorize every formula?

Memorize the core shape, but focus on what is conditioned, normalized, summed, maximized, or logged.

Why does preprocessing matter?

Because changing tokens, vocabulary, casing, or unknown-word handling changes the event space the model sees.

How should two models be compared?

Use the same data split, preprocessing, metric, and error analysis protocol.

How does this connect to modern NLP?

The architecture may change, but probability, representation, context, evaluation, and bias remain central.

!! Exam traps, implementation gotchas, and debugging smells

common catches & gotchas

Do not confuse the model with language itself — Sequence Labeling for Parts of Speech, HMM and Viterbi is an approximation.
Held-out evaluation matters — tuning on the test set contaminates it.
Rare and unknown events matter — sparse evidence causes many failures.
Domain shift is real — text genres do not share one distribution.
Metrics hide errors — inspect examples.
Math is compressed prose — read every \(\sum\), \(\log\), and \(\frac{}{}\) aloud.

++ Takeaways and chapter cheatsheet

Start from the task and the representation.
Name the assumption that makes the computation tractable.
Know which quantities are learned and which are chosen.
Use log probabilities, normalization, and held-out data carefully.
Connect formulas to sparsity, ambiguity, overfitting, bias, and domain mismatch.

// chapter cheatsheetconcept quick-ref

core formulas

fraction\(\frac{\text{count}}{\text{normalizer}}\) turns evidence into probabilities or weights.

sum\(\sum\) accumulates losses, evidence, alternatives, or normalizers.

log\(\log\) turns products into stable additive scores.

revision loop

defineState the input, output, and modeled quantity.

estimateExplain what the corpus contributes.

evaluateUse held-out data and inspect errors.

SLP3 Chapter 8 — Sequence Labeling for Parts of Speech, HMM and Viterbi.