—

Natural Language Processing

Part-of-Speech Tagging: Viterbi, MEMM, and Neural Approaches

Published: 2026-08-13

Level: postgraduate

Audience: Postgraduate students in Natural Language Processing

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Part-of-speech tagging and WordNet — the first encounter with POS tagging in Lecture 1 (Introduction to Natural Language Processing).
Why language is hard: ambiguity — word order and lexical ambiguity from Lecture 1 (Introduction to Natural Language Processing).
The Markov assumption — the independence idea behind HMMs from Lecture 4 (CBOW, GloVe, and Statistical Language Modeling).
Sigmoid and softmax — the activation functions behind the MEMM classifier from Lecture 5 (Perplexity and Neural Language Models).
POS tagging: the problem and the Penn Treebank — the tag set and why tagging is hard from Lecture 6 (Large Language Models, Prompt Engineering, and Part-of-Speech Tagging).
Statistical POS tagging with the HMM — transition and emission tables from Lecture 6 (Large Language Models, Prompt Engineering, and Part-of-Speech Tagging).
The ice-cream example and Viterbi — the HMM decoding setup from Lecture 6 (Large Language Models, Prompt Engineering, and Part-of-Speech Tagging).
Zero-shot and few-shot prompting — the prompting ideas from Lecture 6 (Large Language Models, Prompt Engineering, and Part-of-Speech Tagging).

This session finishes the Viterbi algorithm with a couple of fully worked mathematical problems, then moves to Maximum Entropy Markov Models (MEMM), and finally walks through the modern neural and LLM-based approaches to part-of-speech tagging.

A part-of-speech (POS) tag is the grammatical category of a word — noun, verb, preposition, pronoun, and so on — and POS tagging is the task of automatically assigning one such tag to every word in a sentence. The session follows one steady climb: it starts with the classical decoding algorithm (Viterbi) that makes statistical tagging feasible, works two tagging examples end to end with real numbers, meets the discriminative MEMM, and then moves up the modern ladder — Bi-LSTM + CRF, Transformers and BERT, prompting, and finally LLM agents that call taggers as tools. Along the way, the professor's exam guidance is flagged where it appears, because a mathematical problem on Viterbi is expected on the mid-semester paper.

7.1 Viterbi Algorithm: Decoding the Best State Sequence

Hook: Jason ate 3 ice creams on Monday, 1 on Tuesday, and 3 on Wednesday. Was each day hot or cold? You never see the weather directly, yet the ice-cream counts leak just enough information to guess it — that is the hidden Markov model (HMM) game from the previous session, and Viterbi is the algorithm that plays it efficiently.

7.1.1 Why brute force fails

We begin with the hidden Markov model (HMM) ice-cream example from the previous session. In an HMM, we observe something on the surface and we want to recover the hidden sequence that produced it. Here the observation sequence is the number of ice creams that Jason ate on three consecutive days, and the state sequence we want is the weather sequence — hot or cold — for each of those days. The weather is the hidden variable: we never see it directly, but it explains how many ice creams Jason eats.

If there are two states (hot and cold) and three observations (three days of ice-cream counts), enumerating every possible state sequence costs $2^{3} = 8$ computations. That is small enough to do by hand. The trouble starts when the same idea is applied to POS tagging: the Penn Tree Bank has 45 POS tags, and those tags play the role of the states. A typical English sentence has about 8 to 10 words. Enumerating all tag sequences for one sentence then costs $4 5^{8}$ computations — an astronomically large number. So we need an optimized algorithm, and that algorithm is Viterbi.

The general pattern behind the explosion: with $N$ states and $T$ observation positions, brute force must score every one of the $N^{T}$ state sequences, and $N^{T}$ grows at an exponential rate. Doubling the sentence length squares the work; doubling the tag set multiplies the work by $2^{T}$ . Exponents are the enemy, and the whole point of Viterbi is to trade that exponential blow-up for polynomial work.

Real-world: Viterbi is not a museum piece. It is still used in a lot of POS tagging algorithms, and it is also used in agentic AI for many applications, which we will come back to later in the session.

7.1.2 Storing intermediate results: Viterbi probabilities

Viterbi is a dynamic programming algorithm: it stores intermediate results so that it never recomputes them. The stored quantity is the Viterbi probability $V_{t} (j)$ — the probability of the single best path that ends in state $j$ at position $t$ and produces the observations seen so far. The convention used on the slides is that the first subscript marks the observation position and the superscript marks the state, so $V_{1}^{j}$ (written $V_{1}^{j}$ or $V_{11}$ ) is the value for the first observation and state $j$ . Read $V_{3}^{2}$ as "the second state at the third observation": position first, state second. (Textbooks such as the Jurafsky and Martin treatment write the same cell as $viterbi [j, t]$ with the state first and time second — the order is only a bookkeeping convention, and the professor's position-first order is what the slides use.)

For the very first position there is no previous state to consider, so the value is just the initial probability multiplied by the emission probability:

$V_{1} (j) = π_{j} \cdot b_{j} (o_{1})$

where $π_{j}$ is the initial probability that the first state is $j$ (in the ice-cream problem: $P (hot) = 0.8$ and $P (cold) = 0.2$ ), and $b_{j} (o_{1})$ is the emission probability — the likelihood that the first observation $o_{1}$ was produced in state $j$ . The professor's phrasing: "the first state, the first observation, whether the weather is cold or hot, can be computed as the initial probability pi multiplied by the emission probability, what is the likelihood that Jason ate 3 ice creams given the weather was cold."

Formalize — the posterior is the prior times the likelihood. This is a direct application of Bayes' rule in words: the posterior — the probability that the first day was hot given that Jason ate three ice creams — is nothing but the prior (the initial probability) multiplied by the likelihood (the emission probability). Posterior = prior × likelihood. Strictly, Bayes' rule divides by a normalization term $P (o_{1})$ , the overall chance of seeing the observation; the professor's slide does not carry that term because it is the same constant for every candidate first state, so it cannot change which state wins and may be dropped when we only compare candidates.

7.1.3 The greedy recurrence, backpointers, and the complexity saving

The recurrence — build every later column from the stored previous column. For every position after the first, the new Viterbi value is built from the stored values of the previous position: multiply the previous Viterbi probability by the transition probability into the current state and by the emission probability of the current observation, then take the maximum over all previous states:

$V_{t} (j) = i max (V_{t - 1} (i) \cdot a_{ij} \cdot b_{j} (o_{t}))$

with the backpointer that records the winning predecessor:

$bp_{t} (j) = ar g i max (V_{t - 1} (i) \cdot a_{ij})$

Here $a_{ij}$ is the transition probability of moving from state $i$ to state $j$ (taken from training data), $b_{j} (o_{t})$ is the emission probability of observation $o_{t}$ in state $j$ (also from training data), and $V_{t - 1} (i)$ is the stored Viterbi probability from the previous position. In the general formulation with $T$ observations and $N$ states, the slide marks the initial step as $A_{0}$ : this is the transition out of the start-of-sentence marker, a special non-emitting state 0 whose transition $a_{0 j}$ is exactly the initial probability $π_{j}$ . For the first position you do not take a max, you keep all $N$ values, and the backpointer for the initial state is 0 — the same convention as the standard pseudocode, which initializes $backpointer [s, 1] \leftarrow 0$ for every first-column state $s$ .

The greediness is the heart of Viterbi. At every state you keep only the path with the maximum probability; all other paths into that state are eliminated and are never recomputed in later steps. The backpointers — one per state per position, pointing at the previous state on the best path — are stored so that at the end you can walk backwards and extract the best states in order. The professor's summary: "you are storing all the back pointers, whichever are giving the best path, so that you can extract that in the last and extract those as the best states."

The complexity argument is the payoff. Brute-force enumeration costs $N^{T}$ path computations — for the toy problem $2^{3} = 8$ . Viterbi costs $N \times T$ : for the toy problem $2 \times 3 = 6$ computations. For POS tagging, brute force costs $4 5^{8}$ while Viterbi costs $45 \times 8$ — the reduction is enormous, which is why Viterbi is "much faster and efficient." The professor described the count as "N into M," with M the number of observations (the $T$ above). One honest refinement: each stored cell takes a maximum over $N$ incoming paths, so the actual arithmetic is $O (N^{2} T)$ operations over $N \times T$ stored cells — still polynomial, and still a transformation from hopeless to cheap compared with $N^{T}$ .

7.1.4 Student questions: greedy behavior and the HMM–Viterbi distinction

Q: Are we always going to be greedy?

A: Yes, in Viterbi. In HMM we are not greedy. Greedy has its pros and cons — if we greedily select, we may miss out on certain options. If you want a highly accurate system, you should go for HMM. If you want a faster, optimized way, Viterbi gives pretty good accuracy — not very bad — and that is why it is popular.

Q: Are HMM and Viterbi two different things?

A: No. HMM and Viterbi are basically the same method — the calculation is the same, except that Viterbi is an optimization of HMM where you greedily select the maximum probability for every state. In HMM we look at all the options; in Viterbi we omit some of them because they do not satisfy the maximum-probability criteria.

Q: Is there a possibility that we can reduce some of the states whose probability is very low?

A: Right, correct — you're right. Paths with very low probability can be pruned and not considered further.

Pitfalls — what the greediness buys and costs. The greedy max at each cell is exact for decoding a single best path — that is why Viterbi finds the true best sequence, not an approximation. The trade-off the professor flags is at a different level: greedy selection within a well-specified model is safe, but any model itself makes approximations (the HMM sees only the previous tag, never the future). A path that is weak at an early step can still be part of the best overall sequence, and Viterbi handles that correctly by keeping one candidate per state rather than one candidate for the whole grid. Do not confuse "one best path per state" with "one path overall": pruning all but a single global path at step one is what genuinely loses accuracy. Also remember that zero Viterbi values kill every path through them — a single zero emission eliminates all downstream candidates that pass through that cell.

Recap + bridge. Viterbi fills a grid one column at a time: first column from initial × emission, every later cell as max over the stored previous column of Viterbi × transition × emission, with backpointers for the final walk backwards — all at $N \times T$ cells instead of $N^{T}$ sequences. Next, the ice-cream example puts real numbers through this machinery day by day.

Exam note: a mathematical problem on Viterbi or HMM is expected on the mid-semester paper, testing understanding of the concepts rather than heavy computation — the values will be small, with lots of zeros that clear most paths.

7.2 Worked Example: The Ice-Cream Weather Sequence

7.2.1 Setup and the first day

The observation sequence: Jason ate 3 ice creams on the first day, 1 ice cream on the second day, and 3 ice creams on the third day. We want to predict the weather state sequence — hot, hot, cold, or whatever combination — behind those counts. The initial probabilities say that the first day is hot with probability 0.8 and cold with probability 0.2.

The full model has three ingredients, all taken from training data in real use:

Part	Symbol	Hot (H)	Cold (C)
Initial probability	$π_{j}$	$P (H) = 0.8$	$P (C) = 0.2$
Transition (from H)	$a_{ij}$	$P (H ∣ H) = 0.7$	$P (C ∣ H) = 0.3$
Transition (from C)	$a_{ij}$	$P (H ∣ C) = 0.4$	$P (C ∣ C) = 0.6$
Emission	$b_{j} (o)$	$P (1 ∣ H) = 0.2, P (2 ∣ H) = 0.4, P (3 ∣ H) = 0.4$	$P (1 ∣ C) = 0.5, P (2 ∣ C) = 0.4, P (3 ∣ C) = 0.1$

These are the standard values for the textbook (Eisner / Jurafsky and Martin) ice-cream HMM, in which hot days make 3 ice creams likely and cold days make 1 ice cream likely.

Day 1 (observation: 3 ice creams). For each possible first state we compute the posterior — prior × likelihood:

$V_{1} (hot) = π_{hot} \cdot b_{hot} (3) = 0.8 \times 0.4 = 0.32$

$V_{1} (cold) = π_{cold} \cdot b_{cold} (3) = 0.2 \times 0.1 = 0.02$

Both values are stored as Viterbi probabilities because they are needed again and again for the later states. The emission values used here — 0.4 for three ice creams given hot, 0.1 for three ice creams given cold — are the model table values; the lecture's slide shows the same products (0.32 and 0.02) directly.

Sense-check: the day-1 posterior strongly favours hot (0.32 versus 0.02), which matches the intuition that a three-ice-cream day is a hot-day event. But the cold candidate is not discarded yet — it stays in the grid because a later sequence could still make cold the better overall start.

7.2.2 The second day: competing paths and the max

Day 2 (observation: 1 ice cream). Suppose we want the probability that day 2 is cold. We do not just multiply a transition and an emission — we must also fold in the stored day-1 values, because the complete sequence matters. There are two paths that end in "cold" on day 2:

First day hot → second day cold. Probability = stored $V_{1} (hot) = 0.32$ , times the transition from hot to cold $P (C ∣ H) = 0.3$ , times the emission of 1 ice cream given cold $P (1 ∣ C) = 0.5$ :

$0.32 \times 0.3 \times 0.5 = 0.048$

First day cold → second day cold. Probability = stored $V_{1} (cold) = 0.02$ , times the transition cold to cold $P (C ∣ C) = 0.6$ , times the same emission $P (1 ∣ C) = 0.5$ :

$0.02 \times 0.6 \times 0.5 = 0.006$

Since 0.048 > 0.006, the hot→cold path is the maximum. That path is stored and the cold→cold path is not considered when we move to the next day. The professor's intuition: "you are greedily selecting at each node the path with the maximum probability. That is the intuition behind Viterbi."

The same computation runs for the other day-2 state (hot). The candidate from the first day hot → second day hot costs $0.32 \times 0.7 \times 0.2 = 0.0448$ ; the candidate from first day cold → second day hot costs $0.02 \times 0.4 \times 0.2 = 0.0016$ . The larger of the two (0.0448) is kept and the other is dropped. With more states — suppose we had warm, very hot, or rainy weather too — we would take all the paths into each state; here there are only two states, so two paths per target state.

A note on the lecture's slide: the narration cites the fragments "0.32 multiplied by 0.2 is 0.064" for the hot→cold partial product, a competing total of 0.05, and "0.4 multiplied by 0.5 is nothing but 0.20" — these come from the slide's own table values, which differ slightly from the standard textbook tables used above. The arithmetic rule is identical: stored value × transition × emission, keep the max. On the exam, work with the probability values printed in the problem.

7.2.3 The third day: use the stored value

Day 3 (observation: 3 ice creams). For "hot on day 3" the chain is the transition $P (hot ∣ hot) = 0.7$ , multiplied by the emission $P (3 ice creams ∣ hot) = 0.4$ , multiplied by a previous Viterbi value. Which previous value?

Q: Will it be 0.32 or 0.038 at this point?

A: 0.038. That is the stored Viterbi probability for the second day — the latest stored value, not the first-day value 0.32. When you move to the next observation you use the latest stored Viterbi value, never a value from an older position. On the lecture's slide this cell is written $V_{3}^{2} = 0.038$ , labelled "second state and third observation"; with the standard table values above, the two day-2 cells come out as $V_{2} (cold) = 0.048$ and $V_{2} (hot) = 0.0448$ — the difference is again the slide's table values, not the rule. The rule is what matters: the next column reads only the previous column.

Day 3 (observation: 3 ice creams), with the stored day-2 values.

For "cold on day 3" the two candidates are:

$V_{2} (hot) \times P (C ∣ H) \times P (3 ∣ C) = 0.0448 \times 0.3 \times 0.1 = 0.001344$

$V_{2} (cold) \times P (C ∣ C) \times P (3 ∣ C) = 0.048 \times 0.6 \times 0.1 = 0.00288$

so $V_{3} (cold) = 0.00288$ , coming from the day-2 cold state.

For "hot on day 3" the two candidates are:

$V_{2} (hot) \times P (H ∣ H) \times P (3 ∣ H) = 0.0448 \times 0.7 \times 0.4 = 0.012544$

$V_{2} (cold) \times P (H ∣ C) \times P (3 ∣ H) = 0.048 \times 0.4 \times 0.4 = 0.00768$

so $V_{3} (hot) = 0.012544$ , coming from the day-2 hot state.

Final step. The best last state is hot (0.012544 > 0.00288). Walking the backpointers backwards: day-3 hot ← day-2 hot ← day-1 hot. The best weather sequence is so hot, hot, hot with probability 0.0125 (rounded).

Sense-check: 0.0125 looks tiny, but it is the probability of the single best sequence — a product of six probabilities, each below 1, so a small number is expected. Comparing sequences, not numbers alone, is the correct reading. Also note the day-2 cold state (0.048) did win its own column, yet the final path still goes through day-2 hot — Viterbi decides with the full path, not single cells.

At every state some paths are automatically eliminated, and that is the advantage of Viterbi: instead of $2^{3} = 8$ computations we do $N \times T = 2 \times 3 = 6$ stored cells. "So one of the paths' computations are reduced when we go for a Viterbi, because we are greedily selecting the one that is maximum." The same elimination is far more valuable in POS tagging, where the grid is $45$ states wide instead of 2.

Recap + bridge. The ice-cream walkthrough shows the whole Viterbi machinery in miniature: posterior = prior × likelihood on day 1, stored values feeding max-via-transition-and-emission on days 2 and 3, backpointers for the final walk, and the $N \times T$ versus $N^{T}$ saving. The same grid, with POS tags as the states and words as the observations, is exactly the next example — "I want to race."

Exam note: exam values will be simple — "a lot of 0 and lesser values" — because the aim is to test understanding of the concepts, not computational ability ("calculators are good at that"). Expect at most two to three states, with zeros clearing most paths.

Real-world: the ice-cream HMM is the standard teaching model for decoding, but the same Viterbi code that guesses weather from ice-cream counts guesses POS tags from words, phonemes from audio, and paths in speech and error-correction systems. Wherever a model has hidden states, Viterbi is the decoder of choice — which is why the professor stresses it as the exam's mathematical target.

7.3 Worked Example: POS Tagging "I want to race"

7.3.1 The problem, the tag set, and the matrices

The problem: given an English sentence or phrase, automatically produce the best POS tag sequence — $ar g max$ over all tag sequences. The machine does not know the tags: there is no dictionary storing each word's part of speech, so it must try out all possibilities, and the tag assignments are ambiguous (a word can belong to several categories). For the sentence "I want to race," the professor's answer in the walkthrough is: I = pronoun, want = verb, to = preposition, race = noun.

This toy example uses just four POS tags: PPSS (pronoun), VB (verb), TO (the preposition "to" — its own tag in the Penn Tree Bank), and NN (noun). The professor notes this example appears in the Jurafsky and Martin textbook in the appendix, so it can be studied there as well.

An HMM needs two matrices plus initial probabilities. The transition matrix $A$ gives $P (tag_{j} ∣ tag_{i})$ — the probability of moving from one POS tag to the next — and the initial probabilities give $P (tag ∣ start)$ for the first word of a sentence. The emission matrix $B$ gives $P (word ∣ tag)$ — the probability that a particular word appears given a particular POS tag, for example the probability that the word "I" appears given the tag PPSS. All of these come from training data.

The tables below are the Brown-corpus tables for this example (Jurafsky and Martin). Rows are the conditioning tag ("from"), columns the next tag ("to"):

Transition matrix $A$ (probability of moving from the row tag to the column tag):

from \ to	PPSS	VB	TO	NN
start	.067	.019	.0043	.041
PPSS	.00014	.23	.00079	.0012
VB	.0070	.0038	.035	.047
TO	0	.83	0	.00047
NN	.0045	.0040	.016	.087

Emission matrix $B$ (probability of the column word given the row tag):

tag \ word	I	want	to	race
PPSS	.37	0	0	0
VB	0	.0093	0	.00012
TO	0	0	.99	0
NN	0	.000054	0	.00057

Three entries decide the whole example in advance: "I" can only be PPSS, "to" can only be TO, and "want" and "race" are the ambiguous words.

7.3.2 The first word: reading values from the tables

For the first word "I" we compute, for each of the four states, the initial Viterbi value: transition-from-start × emission. The relevant numbers from the tables:

$V_{1} (PPSS) = P (PPSS ∣ start) \times P (I ∣ PPSS) = 0.067 \times 0.37 = 0.0248$

$V_{1} (NN) = P (NN ∣ start) \times P (I ∣ NN) = 0.19 \times 0 = 0$

The other two states also get zero because their emissions for "I" are zero: $V_{1} (VB) = 0.019 \times 0 = 0$ and $V_{1} (TO) = 0.0043 \times 0 = 0$ . "For all of these, the emission probabilities are zero, therefore we are getting the first values as zero." The zeros are convenient — a zero Viterbi value anywhere in the grid kills every path that passes through it.

Q: How is the first calculation starting? How are we picking this value from the table?

A: For the first state it is from the start: the current state is PPSS and the earlier state is start-of-sentence, so that is your transition. Multiply it by the emission — the probability that the current state is PPSS given the word observation is "I." It is not a matrix multiplication: it is just a simple scalar multiplication, transition probability multiplied by emission probability.

Q: There is an error in this diagram — you are saying 0.67 multiplied by 0.37?

A: Yes — the values shown in the diagram are incorrect; the correct ones are 0.067 multiplied by 0.37. This is taken from Jurafsky and Martin, and there seems to be a typo there. The diagram printed $0.67 \times 0.37$ ; the right entry in the transition table is 0.067, so the product is $0.067 \times 0.37 = 0.0248$ , not the printed value. (The slide's printed product 0.055 is also inconsistent with either reading — the source table value 0.067 times 0.37 is the one to use.)

7.3.3 The second word: greedy pruning and the 0.093 fix

For the second word "want" we compute, say, the probability that the tag is VB. Now the greedy selection begins: we consider all paths from the four day-1 states into VB, and since three of the four stored first-word values are zero, those candidates need not be computed at all — "since this itself is 0, you actually do not need to compute these at all." Only the path from the nonzero state has a value. During this walkthrough the professor corrected a calculation on the slide: "there is a mistake here in the calculation — it should be 0.093." That corrected 0.093 is the lecture's own table value for this cell; with the Brown-corpus tables above, the same cell works out as:

$V_{2} (VB) = i max (V_{1} (i) \cdot a_{i, VB}) \times P (want ∣ VB) = 0.0248 \times 0.23 \times 0.0093 = 0.000053$

(Only the PPSS predecessor contributes; every other path starts from a zero.) On the exam, use the probability values printed in the problem — the rule is always the same: stored value × transition × emission, keep the max. The maximum is stored as the Viterbi probability for that state, and the other candidates are not carried forward.

The remaining second-word cells die by zeros: $V_{2} (TO) = 0$ because $P (want ∣ TO) = 0$ , and $V_{2} (NN) = 0.0248 \times 0.0012 \times 0.000054 \approx 1.6 \times 1 0^{- 9}$ , which is practically zero and carries nothing forward.

Q: From "I" to "want," can you show the table again?

A: It is again transition × emission. The transition is the probability that the current POS tag is VB given the earlier POS tag was PPSS, and the emission is the probability that the word is "want" given the tag VB. Remember: transition is with respect to the states, and states are always your POS tags; emission is always with respect to the words.

7.3.4 The final stage: maximum everywhere

For the third word "to" only the TO cell survives, fed by the stored second column:

$V_{3} (TO) = V_{2} (VB) \times P (TO ∣ VB) \times P (to ∣ TO) = 0.000053 \times 0.035 \times 0.99 = 1.8 \times 1 0^{- 6}$

All other third-word cells are zero because $P (to ∣ tag) = 0$ for every tag except TO. For the last word "race" the grid narrows to two live candidates, VB and NN:

$V_{4} (VB) = V_{3} (TO) \times P (VB ∣ TO) \times P (race ∣ VB) = 1.8 \times 1 0^{- 6} \times 0.83 \times 0.00012 = 1.8 \times 1 0^{- 10}$

$V_{4} (NN) = V_{3} (TO) \times P (NN ∣ TO) \times P (race ∣ NN) = 1.8 \times 1 0^{- 6} \times 0.00047 \times 0.00057 = 4.9 \times 1 0^{- 13}$

The complete grid for "I want to race" (Brown-corpus tables). Column 1 ("I") is initial × emission: PPSS = 0.067 × 0.37 = 0.0248; VB = 0.019 × 0 = 0; TO = 0.0043 × 0 = 0; NN = 0.041 × 0 = 0. Column 2 ("want") is max over predecessors × emission: VB = 0.0248 × 0.23 × 0.0093 = 0.000053 (path PPSS → VB); NN = 0.0248 × 0.0012 × 0.000054 ≈ 1.6 × 10⁻⁹; TO and PPSS are zero. Column 3 ("to") keeps only TO = 0.000053 × 0.035 × 0.99 = 1.8 × 10⁻⁶ (path VB → TO). Column 4 ("race") keeps only the two live candidates:

race cell	path	computation	value
VB	TO → VB	1.8 × 10⁻⁶ × 0.83 × 0.00012	1.8 × 10⁻¹⁰
NN	TO → NN	1.8 × 10⁻⁶ × 0.00047 × 0.00057	4.9 × 10⁻¹³

The final column's maximum is VB (1.8 × 10⁻¹⁰). Backtracing the pointers VB ← TO ← VB ← PPSS gives the textbook solution I/PPSS want/VB to/TO race/VB with sequence probability 1.8 × 10⁻¹⁰.

Sense-check: the word-level evidence alone favours race/NN (0.00057 > 0.00012), but the transition out of TO — P(VB|TO) = 0.83 versus P(NN|TO) = 0.00047 — flips the answer. That is the whole point of decoding the sequence instead of tagging each word alone. In the lecture walkthrough the professor's stated assignment is race → noun; the lecture's own table values produce that answer, and the exam gives you the tables to decide.

Q: In the last part of the tagging problem, where exactly is the max value used in the final stage?

A: At every point the maximum is selected. Among the last states also the maximum will be selected, and so on. In your exam you can select the one which is maximum for three words, and from the second word onwards you will get to the maximum value alone.

Q: In the third state we have a one-node-to-many-node connection from one to two — and from two to three to four will we be getting only one thing?

A: No — you will get multiple candidates again at this point as well. Here also you compute the maximum and go ahead with the best path, but when you move ahead you do not look at the other eliminated values; those computations will not be done when you go to the next node. Only the max path (the bold one on the slide) is carried forward.

Running the whole grid, the maximum tag for each word ends up being: I → pronoun (PPSS), want → verb (VB), to → preposition (TO), race → noun (NN). The overall probability of the sequence is the product along the chosen path — that is the sequence probability for the tag sequence pronoun, verb, preposition, noun.

Recap + bridge. "I want to race" shows the full POS tagging grid in miniature: only PPSS survives word 1, only the PPSS→VB path feeds word 2, only TO survives word 3, and the final column's max — guided by the transition out of TO — settles "race." Greedy selection happens at every column, including the last one.

Exam note: in a Viterbi problem, show the grid/graph — "better would be to show the graph, a simple graph, not fancy" — and if the final path is asked, show the final path too. From the second word onward you select the maximum value alone, and among the final states too you select the maximum.

Real-world: this four-tag toy mirrors exactly what an HMM tagger does at production scale with the full 45-tag Penn Tree Bank set — the tables are bigger, the grid has 45 rows, and the same Viterbi sweep runs under the hood of classical taggers that still ship in NLP libraries today.

7.4 Worked Example: POS Tagging "The doctor is in"

7.4.1 Setup: five states and the initial probabilities

This example is similar to the previous one — an emission matrix and a transition matrix, with probabilities from training data — but for the phrase "the doctor is in." The phrase has four words and the grid has five states: noun, verb, determiner, preposition, and adverb. (The fifth state, adverb, was counted but not named in the narration; it matters for the last word "in," which can be an adverb.) The tables used here are the ones from the textbook treatment of this example:

Transition matrix $P (tag_{j} ∣ tag_{i})$ , rows "from," columns "to":

from \ to	Noun	Verb	Det	Prep	Adv
start	0.3	0.1	0.3	–	–
Det	0.9	0.01	–	–	–
Noun	0.2	0.4	–	0.3	–
Verb	–	–	–	0.2	0.1

Emission matrix $P (word ∣ tag)$ :

tag \ word	the	doctor	is	in
Noun	0	0.4	0.1	0
Verb	0	0.1	0.9	0
Det	0.7	0	0	0
Prep	0	0	0	1.0
Adv	0	0	0	0.1

Initial probabilities: the first word is noun with probability 0.3, verb with 0.1, determiner with 0.3. Emissions for "the": $P (the ∣ noun) = 0$ , $P (the ∣ verb) = 0$ , $P (the ∣ determiner) = 0.7$ , $P (the ∣ preposition) = 0$ . The transition table includes $P (noun ∣ determiner) = 0.9$ and the emissions include $P (doctor ∣ noun) = 0.4$ .

7.4.2 Word by word: "the" and "doctor"

Word 1, "the". Every first-word cell is initial probability × emission:

$V_{1} (noun) = 0.3 \times 0 = 0, V_{1} (verb) = 0.1 \times 0 = 0$

$V_{1} (determiner) = 0.3 \times 0.7 = 0.21, V_{1} (preposition) = 0, V_{1} (adverb) = 0$

The narration: "the given noun is 0, 0.3 multiplied by zero is going to give zero; the first word is verb is 0.1, 0 multiplied by 0.1 is again 0; determiner given the word is 'the' is 0.7, and the first word is determiner is 0.3, therefore 0.7 multiplied by 0.3 which is point twenty-one." Preposition also emits zero, so it is zero too. Only the determiner cell survives.

Word 2, "doctor." A key point from the walkthrough: the greedy selection starts after the second word, not at the first word — for the first word you must compute all the states, and only from the second word on does pruning take over. (In this example the pruning is quiet because the zeros already eliminate everything except one path.) For the candidate "doctor = noun," the chain is: emission $P (doctor ∣ noun) = 0.4$ , transition $P (noun ∣ determiner) = 0.9$ , times the stored first-word value $V_{1} (determiner) = 0.21$ :

$V_{2} (noun) = 0.21 \times 0.9 \times 0.4 = 0.0756$

The only other live candidate, "doctor = verb," comes from the same determiner start: $0.21 \times 0.01 \times 0.1 = 0.00021$ . All the other candidates into "doctor" carry a zero from the first word, so the maximum is 0.0756 — "we know that all these others are zero, therefore the maximum at this point is going to be 0.0756." This is exactly where the stored Viterbi values pay off: "you do not have to again compute all of these — these are precomputed and stored, so only look at this final value for the first step."

The two-word grid so far. Column 1 ("the") has exactly one nonzero cell: Det at 0.21. Column 2 ("doctor") keeps Noun at 0.0756 (via Det) and Verb at 0.00021 (via Det); the backpointers in both cells point to Det. Everything else is zero. Only these two rows are alive for the remaining words — the zero-kill rule has already shrunk the grid from 5 rows to 2.

Sense-check: 0.0756 = 0.21 × 0.9 × 0.4 — "the doctor" as determiner + noun is a natural noun phrase, and the large transition 0.9 (determiner → noun) plus the 0.4 emission make it win easily.

7.4.3 "is," "in," and the overall sequence probability

The same computation runs for "is" and "in," computing all candidates and taking the max at each step — at both places we compute the max, exactly like the ice-cream example.

Word 3, "is." The two live predecessors are Noun (0.0756) and Verb (0.00021). For "is = verb":

$V_{3} (verb) = max (0.0756 \times 0.4, 0.00021 \times 0.05) \times P (is ∣ verb) = 0.03024 \times 0.9 = 0.027216$

(the first candidate, from the noun, wins by far). For "is = noun":

$V_{3} (noun) = 0.0756 \times 0.2 \times P (is ∣ noun) = 0.0756 \times 0.2 \times 0.1 = 0.001512$

All other third-word cells are zero because "is" emits nothing under determiner, preposition, or adverb. So "is" gets the tag verb with 0.027216, and the backpointer points to noun.

Word 4, "in." Again two candidates, both from the verb cell 0.027216:

$V_{4} (preposition) = 0.027216 \times P (prep ∣ verb) \times P (in ∣ prep) = 0.027216 \times 0.2 \times 1.0 = 0.0054432$

$V_{4} (adverb) = 0.027216 \times P (adv ∣ verb) \times P (in ∣ adv) = 0.027216 \times 0.1 \times 0.1 = 0.00027216$

The higher one wins, so "in" gets the tag preposition with 0.0054432.

The final assignment is: the → determiner, doctor → noun, is → verb, in → preposition. The overall sequence probability is just the product along the winning path — $0.21 \times 0.9 \times 0.4 \times 0.4 \times 0.9 \times 0.2 \times 1.0 = 0.0054432$ — "this is just the multiplication of these probabilities... this is the value for this." That product is the probability of the sequence determiner, noun, verb, preposition, which is what $ar g max$ picks. In plain HMM you would compute all paths; Viterbi selects the maximum at each step, which makes the problem much easier.

Recap + bridge. "The doctor is in" runs the full grid: only determiner survives word 1 (0.21), the 0.21 × 0.9 × 0.4 chain gives doctor/noun (0.0756), "is" and "in" each keep their best single candidate, and the winning path Det → Noun → Verb → Prep carries the sequence probability 0.0054432.

Exam note: for this example, keep the grid picture in mind. If a question is asked with the graph, show the graph — a simple graph, not a fancy one. The final path matters: from the second word onward you select the maximum value alone, and among the final states too you select the maximum.

7.4.4 Reading the emission table

Q: In the emission table, the left side is always taken as the given — like doctor given noun — right?

A: Correct. In the emission matrix we always read word given the POS tag — the left side is the given one, the right side is what follows from it. So "doctor given verb" is not the emission; "verb given doctor" is what we want to find out. That posterior is nothing but the likelihood — doctor given verb, the emission — multiplied by the transition. Likelihood times transition gives you the posterior probability.

Exam note: exam problems on Viterbi will be much simpler than this five-state grid. Expect at most two to three states, with zeros and these kinds of simple calculations — the probability values are given as small numbers, and the zeros remove most paths for you. Real-world problems, by contrast, have many more states and messier values.

Real-world: this five-state grid is the skeleton of a real HMM tagger — only the table size changes. Production taggers estimate the same transition and emission counts from a large tagged corpus and run the identical sweep, which is why mastering the small grid transfers directly to working systems.

7.5 Maximum Entropy Markov Models (MEMM)

7.5.1 HMM's bidirectionality limitation

Hook: the HMM can only look left. For most sentences, left-to-right context is enough — but what happens when the disambiguating clue sits to the right of the ambiguous word? That single limitation motivates the whole move to the MEMM.

One of the issues with HMM is the bidirectionality issue. An HMM always runs left to right — and since English text is written left to right, this works effectively for most sentences. Yet sometimes the right-to-left information would help disambiguate a particular POS tag: for a tag that is unambiguous, left-to-right context works well, but for an ambiguous tag, the words to the right add value and help pin down the correct tag. Bidirectionality is simply not possible in an HMM. Most of today's POS taggers — the ones built on transformers, discussed later — use bidirectionality: attention mechanisms that look at the words before the current word as well as the words after it. HMMs remain useful in many situations, but they have this limitation.

A second, related limitation: the HMM is a generative model — it tells you how the words are produced from the tags, through the likelihood $P (word ∣ tag)$ and the transition $P (tag_{j} ∣ tag_{i})$ . It can only use these two factor types, so it cannot use arbitrary clues like "the word is capitalized" or "the word ends in -ing."

7.5.2 MEMM as a discriminative classifier

MEMM — Maximum Entropy Markov Model — applies the same Markov-model principles: we again predict the maximum-probability POS tag sequence given the observation sequence. The difference is that MEMM treats tagging as a classification problem. In HMM we compute likelihood × prior; in MEMM we go directly for the posterior:

$y^_{1.. n} = ar g y_{1}, \dots, y_{n} max P (y_{1}, \dots, y_{n} ∣ x_{1}, \dots, x_{n})$

Here $x_{i}$ is the $i$ -th word of the sentence and $y_{i}$ is its POS tag. The professor described this in words: "we are just finding directly this tag sequence given the words and the tags or earlier tags in the sentence." The Markov structure is retained inside the posterior — the standard form (Ratnaparkhi's log-linear tagger) factors it one tag at a time, exactly the same conditional used by the lecture's version:

$P (y_{1}, \dots, y_{n} ∣ x_{1}, \dots, x_{n}) = i = 1 \prod n P (y_{i} ∣ y_{i - 1}, x_{1}, \dots, x_{n})$

where each local factor is a softmax over scores:

$P (y_{i} ∣ y_{i - 1}, x) = \frac{exp ( w \cdot f ( y _{i} , y _{i - 1} , x ) )}{Z ( y _{i - 1} , x )}, Z (y_{i - 1}, x) = y^{'} \sum exp (w \cdot f (y^{'}, y_{i - 1}, x))$

The vector $w$ holds the learned feature weights, $f (y_{i}, y_{i - 1}, x)$ is the feature vector built for the candidate tag $y_{i}$ , and $Z$ is the normalization over all candidate tags at that position — the denominator that makes each factor a genuine probability.

Because it is posed as a classification problem, any classification algorithm can do the job: neural network classifiers, SVM, Naive Bayes, logistic regression. The professor stresses that logistic regression is used quite popularly in many real-world applications even today, including in agentic AI: the sigmoid function is used even there, and "softmax is nothing but a sigmoid function, kind of a sigmoid function only." (Technically, the sigmoid is the two-class special case of softmax: for two classes, softmax's two outputs $e^{a} / (e^{a} + e^{b})$ and $e^{b} / (e^{a} + e^{b})$ reduce to $σ (\cdot)$ of their difference.) The POS tags are the classes — it is a multi-class problem — so one-vs-all or any multi-class method can be applied to POS tagging.

The transition and emission information is not computed as separate factors; instead they are combined into features and fed to a machine learning model that learns feature weights from labeled training data. That combination is the whole shift: "instead of finding them individually, we are just combining them as features and treating them as a machine learning problem."

Worked example: turning feature scores into tag probabilities. Suppose the model's features give tag VB a raw score of 2.0 and tag NN a score of 0.5 for the current word.

Step 1: raise $e$ to each score: $e^{2.0} \approx 7.39$ and $e^{0.5} \approx 1.65$ . Step 2: add them: the total is $7.39 + 1.65 = 9.04$ . Step 3: divide: $P (VB) = 7.39/9.04 \approx 0.82$ and $P (NN) = 1.65/9.04 \approx 0.18$ .

Sense-check: the two probabilities sum to 1.00, as a probability distribution must. The tag with the bigger score wins, and richer features give sharper, better-informed splits.

Comparison — HMM versus MEMM:

Dimension	HMM	MEMM
Model type	Generative (models how words come from tags)	Discriminative (models the tag directly)
What it computes	Likelihood × prior, then Bayes	Direct posterior $P (y_{i} ∣ y_{i - 1}, x)$
Sources of information	Transitions + emissions only	Arbitrary features (spelling, capitalization, neighbours, ...)
Decoding	Viterbi	Viterbi (or greedy shortcut)
Known flaw	Zero counts for unseen pairs (sparsity)	Label-bias problem (fixed later by the CRF)

When to pick which: if you have rich, hand-designed clues about words, the MEMM turns them straight into accuracy; if you want a simple, fully generative story with clean probabilities, the HMM. Both decode with Viterbi.

7.5.3 Features for POS tagging

Every supervised learning algorithm needs labeled data. Ready-made, manually annotated, high-quality labeled POS data exists — the Penn Tree Bank is available, with every word labeled, and similar datasets are readily available. From a previous session we know the word "back" can be an adjective, a verb, a noun, an adverb, and more — "back" meaning a body part, "back" meaning a backside, "back the bill," and so on. To disambiguate a target word, we encode features around it:

the previous word and the word before that;
the next word;
the POS tag of the previous word;
the POS tag of the previous two words;

and we can go up to the end of the sentence for all of these. Each of these acts as a feature. The model learns the feature weights from training data, and at test time it predicts the POS tag for each word. Because the tags are produced greedily — for each word of the sentence, pick the single most probable tag — the approach mirrors the greedy selection used with Viterbi. For example, for the word JANET the model may consider three candidate tags — noun, verb, modal — and greedily selects the one with the maximum probability, repeating this for the whole sentence.

Pitfalls. Greedy per-word decoding locks in each tag before the rest of the sentence is seen, so one early mistake propagates through everything after it — decode the MEMM with Viterbi when the whole sentence matters. And features are only as good as their weights: with few training examples, a rich feature set overfits, so feature choice is a modelling decision, not a free lunch.

Q: [Question posed to the class] One advantage in MEMM is that you are looking at the next words as features. So what is the disadvantage? It is considering the next words, but is it considering the sequence?

A: It is not. MEMM does not take the actual context of the word sequence — each word's tag is chosen without a global view of the sentence. That limitation is exactly what motivates the next approach: neural sequence models.

The blind spot has a technical name: the label-bias problem. Because each local softmax normalizes over the candidate tags at its own position, the model tends to favour tags that have fewer competitors, and the global sequence quality is never scored directly. The next section's fix — a conditional random field on top of a Bi-LSTM — reintroduces exactly this global, whole-sequence view.

Recap + bridge. The MEMM trades the HMM's generative likelihood for a direct posterior over tags, feeding arbitrary hand-built features into a softmax classifier per position — at the price of a blind spot: it never scores the whole tag sequence. That global view returns with the CRF.

Exam note: there will be no mathematical problems on MEMM. Mathematical problems can be expected on HMM and Viterbi — those are the ones to practice numerically.

Real-world: the MEMM lineage survives in practice — logistic regression and its features remain popular in real-world applications, including inside agentic AI pipelines, and the feature idea lives on in every neural tagger, which simply learns the features itself instead of requiring them by hand.

7.6 Bi-LSTM + CRF for Sequence Tagging

We now move to the neural approaches. Everything from here on is a neural-network approach, and a key consequence is that you do not need to engineer features by hand: give the model labeled training data and it learns the features automatically through the hidden weights of the fully connected layers. This is the neural-network baseline for sequence tagging — not just for POS tagging, but for other NLP applications as well. Two terms matter here: the Bi-LSTM part addresses the local challenge, and the CRF part addresses the global challenge.

7.6.1 LSTM recap and the vanishing gradient

LSTM stands for long short-term memory — a sequence-learning neural network algorithm, familiar from the earlier DNN course. It has gates — including the forget gate — that decide what information to keep and what to remove, tracking the state over the sequence. GRU is a related architecture.

The gated memory, one step at a time. At each word the LSTM updates two state vectors. Let $x_{t}$ be the current word vector, $h_{t - 1}$ the previous hidden state (the running summary), and $c_{t - 1}$ the previous cell state (the notepad). Three gates — each a sigmoid $σ (z) = 1/ (1 + e^{- z})$ producing a number between 0 and 1 — decide how much of each signal flows:

Forget gate: $f_{t} = σ (W_{f} x_{t} + U_{f} h_{t - 1} + b_{f})$ — how much of the old memory to keep;
Input gate: $i_{t} = σ (W_{i} x_{t} + U_{i} h_{t - 1} + b_{i})$ — how much new content to write down;
Candidate: $g_{t} = tanh (W_{g} x_{t} + U_{g} h_{t - 1} + b_{g})$ — the proposed new content itself;
Output gate: $o_{t} = σ (W_{o} x_{t} + U_{o} h_{t - 1} + b_{o})$ — how much of the memory to reveal right now.

The update (with $⊙$ meaning entry-by-entry multiplication):

$c_{t} = f_{t} ⊙ c_{t - 1} + i_{t} ⊙ g_{t}, h_{t} = o_{t} ⊙ tanh (c_{t})$

Read $c_{t}$ aloud: "keep $f_{t}$ of the old memory, then add $i_{t}$ of the new content $g_{t}$ ."

The reason such gating exists: simple RNNs suffer from the vanishing gradient problem. If you start with an initial weight of 0.5 and repeatedly multiply by the original values when taking partial gradients, the gradient can go on diminishing; initialize too high and the gradient can instead grow exponentially large. LSTM avoids this problem — partially — by incorporating the previous state's information in addition to the current input. A practical consequence the professor flagged: an LSTM can capture roughly 7 to 8 context words, which is contextual information that MEMM and HMM could not capture.

One LSTM step, every number shown. Use single-number states so the arithmetic is easy to follow. Start with old memory $c_{t - 1} = 0.5$ , old summary $h_{t - 1} = 0.3$ , and a new word $x_{t} = 1.0$ , with the cell's learned weights given per gate.

Step 1 — forget gate: $z = 0.5 (1.0) + 0.4 (0.3) + 0.1 = 0.72$ , so $f_{t} = σ (0.72) = 0.673$ . Keep about two-thirds of the old memory. Step 2 — input gate: $z = 0.69$ , so $i_{t} = σ (0.69) = 0.666$ . Step 3 — candidate: $z = 0.76$ , so $g_{t} = tanh (0.76) = 0.641$ . Step 4 — update memory: $c_{t} = 0.673 (0.5) + 0.666 (0.641) = 0.336 + 0.427 = 0.763$ . Step 5 — output gate: $z = 0.65$ , so $o_{t} = σ (0.65) = 0.657$ . Step 6 — read out: $h_{t} = 0.657 \times tanh (0.763) = 0.657 \times 0.643 = 0.422$ .

Sense-check: the cell carried two-thirds of its old memory forward and folded in new information — no full rewrite, no forgetting everything. That is precisely the property that keeps early words alive across a long sentence.

Scope — when LSTM still struggles. The gates are learned, not set by hand, so the keep/forget behaviour comes from training data. And even with gates, an LSTM strains over very long distances — its useful context is on the order of 7 to 8 words, which is why the next step (attention) exists. For POS tagging, though, this window is enough to beat every classical tagger.

7.6.2 Why bidirectional

POS tagging is a sequence-learning problem — a sequence of words in, a sequence of tags out — so any sequence-learning algorithm (LSTM, transformers, and so on) can be used. The "bi" in Bi-LSTM means bidirectional. In "I want to race," when we produce the tag for the word "want," we do not only look at the previous word "I" — we also look at the next words "to" and "race." The bidirectional LSTM processes the sentence in both directions and captures long-range dependencies in the bidirectional context.

Intuition — the meeting-minutes notepad. An LSTM is like a person taking minutes in a long meeting: keep the decisions that still matter (high "keep" — the forget gate), jot the genuinely new points (high "write" — the input gate), and read out only the relevant lines when asked (the output gate). The Bi-LSTM runs this process twice — once left to right, once right to left — and glues the two summaries together, so every word's representation sees both sides at once.

Where the analogy breaks: the gates are numbers learned from data, not conscious choices — and even the two-sided LSTM has the 7-to-8-word context limit that a human note-taker does not.

For "bank" in "I walked to the river bank," the forward LSTM has already read "river," so it leans toward the riverbank reading (a noun); the backward LSTM reads the rest of the sentence coming the other way. Only together do the two passes pin the word down — a one-way reading would miss half the evidence. That is exactly the bidirectionality that the HMM could not offer.

7.6.3 The CRF layer: conditional random fields

But there is one thing the Bi-LSTM does not do: when it produces the tag for a word, it does not look at the tag of the previous or next word. It looks at the neighboring words, not the neighboring tags. That is handled by the CRF — the conditional random field layer. The CRF looks at the previous POS tag: if we want to know whether the current word is a noun, we can check whether the previous word is an article — if so, the next word is probably a noun. The professor's framing: "that's what human beings do, so the same intuition we are trying to encode in the CRF." The CRF finds the best sequence of labels while considering the dependencies between neighboring POS tag labels.

The scoring formula looks heavier than it is:

$P (Y ∣ X) = \frac{1}{Z ( X )} exp (i = 1 \sum N s (y_{i - 1}, y_{i}, X, i))$

Here $X$ is the input sequence (the words), $Y$ is the label sequence (the POS tags — called output labels in general, since CRF is used for other problems too), $N$ is the length of the sequence, and $s (y_{i - 1}, y_{i}, X, i)$ is a scoring function that scores the move from one state (one POS tag) to another at position $i$ . The bottom normalizes the scores across all label sequences — exactly the softmax idea: the denominator $Z (X) = \sum_{Y^{'}} exp (\sum_{i} s (y_{i - 1}^{'}, y_{i}^{'}, X, i))$ sums over every possible tag sequence, and dividing by it turns raw scores into a probability. In the Bi-LSTM + CRF recipe the per-position score splits into two learned pieces:

$s (y_{i - 1}, y_{i}, X, i) = E_{i} [y_{i}] + T [y_{i - 1} \to y_{i}]$

where the emission score $E_{i} [y_{i}]$ comes from the Bi-LSTM (how well tag $y_{i}$ fits word $i$ on its own) and the transition score $T [y_{i - 1} \to y_{i}]$ comes from a small learned table (how natural it is for tag $y_{i}$ to follow tag $y_{i - 1}$ ). The whole-sequence score — the exponent before normalization — is:

$Score (t_{1}, \dots, t_{n}) = i = 1 \sum n E_{i} [t_{i}] + i = 2 \sum n T [t_{i - 1} \to t_{i}]$

Worked example: "the plays" — greedy picks a verb, the CRF picks the noun. Two words, three candidate tags {DT, NN, VBZ}. The Bi-LSTM emission scores $E$ and the learned transition table $T$ are:

Emission $E_{i} [t]$	DT	NN	VBZ
the	5	0	-2
plays	-3	2	3

Transition $T [row \to col]$	DT	NN	VBZ
DT	-2	4	-1
NN	-1	1	3
VBZ	2	2	-3

Step 1 — what greedy does: per word, take the biggest emission. "the" → DT (5), "plays" → VBZ (3). Greedy answer: DT VBZ, score $5 + T [DT \to VBZ] + 3 = 5 - 1 + 3 = 7$ .

Step 2 — score every full path as $E_{1} [t_{1}] + T [t_{1} \to t_{2}] + E_{2} [t_{2}]$ : DT→NN gives $5 + 4 + 2 = 11$ ; DT→VBZ gives $5 - 1 + 3 = 7$ ; every other path scores 6 or less.

Step 3 — find the best: the maximum is 11 at DT NN. The reward $T [DT \to NN] = + 4$ outweighs the higher emission for VBZ — structure won.

Step 4 — turn into a probability: sum $exp (score)$ over all nine paths: $e^{11} + e^{7} + e^{6} + e^{3} + e^{2} + e^{0} + e^{- 2} + e^{- 3} + e^{- 4} \approx 61402.9 = Z$ . Then

$P (DT NN) = \frac{e ^{11}}{Z} = \frac{59874.1}{61402.9} = 0.975$

Sense-check: the CRF puts 97.5% on "the plays" as determiner-plus-noun and only about 1.8% on the greedy verb reading — the sequence-level view flipped the answer even though VBZ had the best single-word emission.

7.6.4 Combining Bi-LSTM emissions with CRF transitions

In practice the two layers divide the work: the Bi-LSTM produces the emission scores — how likely each word is to carry each tag — and the CRF produces the transition scores from one tag to the next. The sequence score combines both, and, as in Viterbi, the CRF greedily selects the best label at each step. This combination is also the workhorse for named entity recognition (NER) — identifying whether a word is a person name, a location name, a place name, and so on — and for many applications, including conversational AI systems. The accuracy is very good: around 97%, which is high enough that you do not need fancier transformer models for many tasks. The trade-off: training time is slower than for the non-recurrent models (the transformers).

Why that last percent matters: "97% per word" sounds finished, but a sentence is only fully correct if every word is correct. If each word is right with probability $a$ , an $n$ -word sentence is fully correct with probability $a^{n}$ — for $n = 20$ words, a Bi-LSTM-CRF at $a = 0.97$ gives $0.9 7^{20} = e^{- 0.6092} \approx 0.544$ , only about 54% of sentences perfect, while a transformer at $a = 0.99$ gives $0.9 9^{20} = e^{- 0.2010} \approx 0.818$ , about 82%. A tiny per-word gain compounds into a large sentence-level gain.

Real-world: POS tagging can be viewed as the same shape of problem as NER — both are sequence-labeling problems with a small fixed set of labels — which is why the Bi-LSTM + CRF recipe generalizes across them. Both tasks also sit inside conversational AI systems today.

Q: What is the difference between MEMM and this? Both are doing the same thing?

A: In MEMM we pose it as a machine learning problem with feature engineering. Here we pose it as an LSTM neural network. All of these approaches we are discussing now are neural networks — the major advantage is that you do not have to embed any features; the model learns the features automatically from the labeled training data via the hidden weights of the fully connected network.

Recap + bridge. The Bi-LSTM reads the sentence both ways and emits per-word tag scores; the CRF layer adds learned tag-to-tag transition scores and decodes the single best-scoring sequence, so the output is globally consistent instead of locally greedy — at about 97% token accuracy, with slower training than transformers.

Exam note: no mathematical problems on the CRF formula in the exam, but the intuition matters: $P (Y ∣ X)$ is almost like a conditional probability — scores up top, softmax-style normalization below.

7.7 Transformers and BERT for POS Tagging

7.7.1 Attention: the "Attention Is All You Need" breakthrough

The transformer architecture (recapped from the deep learning course, and covered in detail in a later session) introduced the attention mechanism: attention scores, key, query, and value matrices, multi-headed attention, and layer normalization. The mathematics — why we need three different vectors (key, query, value), why we cannot get away with just query and key — is scheduled for the post-mid-semester material, with mathematical problems to be solved on attention scores, multi-headed attention, self-attention, and the key-query-value matrices. What matters here: attention captures context. Self-attention and cross-attention came about because of the flaws of LSTM — LSTM's limited context window — and attention can capture any length of context; that was the best part, and the reason it proved useful across NLP, including conversational AI, question answering, machine translation, and POS tagging.

Intuition — attention is a meeting. To understand your own role in a sentence, you ask every other word: "how relevant are you to me?" You listen more to the relevant words and blend what they say into your own representation. Distance does not matter — relevance does. That is why attention has no context window: a word at position 3 can pull directly from a word at position 500 in one step, instead of sending a message through 497 intermediate states that keep fading.

In POS tagging, attention plays the role that hand-coded features played in MEMM: in MEMM we hard-coded "what was the previous word, what is the next word, what is the POS tag of the previous word"; here those signals are learned automatically as attention scores. One attention head may specialize in part-of-speech-like signals, another in something else entirely.

Real-world: research builds on research. The professor's own experience: in this research area it is not easy to find something novel — "you think of an idea and you get a paper with the results of the same idea." Self-attention came out of the flaws of LSTM, and cross-attention and self-attention together removed the context-length restriction that motivated the work.

7.7.2 BERT: the bidirectional encoder

A transformer has two stacks — one for encoding, one for decoding. BERT is the bidirectional, encoder-only part of the transformer: it is used for producing contextual word embeddings. GPT — the generative pre-trained transformer — is the decoder-only part, used for generation. In POS tagging we use the encoder side. The earlier word-embedding unit covered static word embeddings (for example, GloVe) and the frequency-based TF-IDF; the contextual word embeddings produced by BERT come after the mid-semester exam.

BERT is a pre-trained model (PTM). These are large language models trained on web-scale data for a single broad task: produce the next set of tokens given the earlier set of tokens. BERT itself has a very large number of parameters — it uses a large stack of encoder layers. The professor mentioned "16 encoders or 32 encoders" in passing; the standard BERT variants actually stack 12 transformer encoder layers (BERT-base) or 24 (BERT-large), and BERT-large uses 16 attention heads per layer — likely the source of the "16" — so treat the lecture's count as approximate. RoBERTa is an optimized version of BERT, and there are smaller variants as well. The next semester's courses cover fine-tuning, small language models, nano models, and transfer learning in detail — how small language models can be built from large language models, and the various versions of the GPT family.

Intuition — the well-read graduate. Pre-training is a general education: BERT learns grammar by solving puzzles on huge text (the masked language model trick — hide a word and predict it from both sides). Fine-tuning is a short job induction: you do not reteach the model English; you give it a one-day course on your house style — which tag goes on which word — and it is productive. The POS corpus is the one-day course.

7.7.3 Fine-tuning for POS tagging

A pre-trained model is trained to produce the next tokens; for a specific task like POS tagging we fine-tune it. The idea: the model has already learned grammar from huge amounts of text; we fine-tune it for the classification head — and POS tagging is a classification problem, as established with MEMM. We can also fine-tune with instructions — instructions related to POS tagging — so the model is in a better position to give correct tags. This is why small language models are often fine-tuned with instructions for POS tagging: better results at lower cost.

The head is a single linear layer. For each token's contextual vector $h$ it computes one raw score per tag — a logit — and softmax turns the logits into probabilities:

$logits = W h + b, P (t) = \frac{e ^{logit_{t}}}{\sum _{t^{'}} e ^{logit_{t^{'}}}}$

Here $W$ has one row of weights per tag and $b$ is the bias vector. Training the whole model for a few epochs on the tagging corpus completes the fine-tune.

Worked example: reading the tag off "plays" in "she plays well." Suppose BERT's contextual vector for "plays" is $h = [0.5, - 1.0, 2.0, 0.3]$ and the head has three tag rows (biases 0): $W_{DT} = [0.1, 0.2, - 0.5, 0.0]$ , $W_{NN} = [0.3, 0.1, 0.4, - 0.2]$ , $W_{VBZ} = [- 0.2, - 0.3, 0.9, 0.5]$ .

Step 1 — logit for DT: $0.1 (0.5) + 0.2 (- 1) + (- 0.5) (2) + 0 (0.3) = 0.05 - 0.2 - 1.0 + 0 = - 1.15$ . Step 2 — logit for NN: $0.3 (0.5) + 0.1 (- 1) + 0.4 (2) + (- 0.2) (0.3) = 0.15 - 0.1 + 0.8 - 0.06 = 0.79$ . Step 3 — logit for VBZ: $(- 0.2) (0.5) + (- 0.3) (- 1) + 0.9 (2) + 0.5 (0.3) = - 0.1 + 0.3 + 1.8 + 0.15 = 2.15$ . Step 4 — softmax: $e^{- 1.15} = 0.317$ , $e^{0.79} = 2.203$ , $e^{2.15} = 8.585$ ; sum = 11.105. So $P (DT) = 0.029$ , $P (NN) = 0.198$ , $P (VBZ) = 0.773$ .

Sense-check: the head reads off VBZ with about 77% confidence — correct for "she plays well." The pre-trained vector already encoded "verb after she"; the one-line head only had to point at it.

The key practical rule: fine-tuning does not mean retraining everything. "Typically, when you do the fine-tuning, you do not retrain all the 175 billion parameters — you freeze some of them and only train the last layer or something like that. Fine-tuning is usually done on a small set of parameters, otherwise there is no purpose — it is like retraining." Completely changing the earlier model weights would not even be useful.

Pitfalls. BERT splits rare words into sub-word pieces ("playing" becomes "play" + "##ing"); the convention is to read the tag from the first piece — forget this and words and tags drift apart, quietly wrecking accuracy. And fine-tuning every layer on a tiny corpus invites overfitting, which is exactly why freezing most layers is the standard move.

Real-world: Hugging Face hosts many open-source BERT and other model implementations, including ready-made POS tagging implementations, which can be used directly in your own code. SpaCy is also a very good library for POS tagging and ships transformer implementations for it.

7.7.4 Parallelization, auto-regressive decoders, and RAG

Transformers deliver near-perfect accuracy — close to 100% on POS tagging. They are also highly parallelizable on the encoding side: the attention layers can be computed in parallel. The decoding side is different: the decoder is auto-regressive — it takes the output of the earlier state as input to the next state — so it is not easily parallelizable. Encoders can be parallelized; decoders cannot.

Q: When we say we take the output of the previous iteration as input in the decoder — during training we know the complete sentence, but the model may predict a wrong next word. In that case, do we give the real output or the one the model predicted as the input for the next iteration?

A: Auto-regressive, yes. During training itself, when you are predicting each word, you use the training data — the loss is computed, the softmax is computed, and only the word with the maximum probability is predicted as the first word. That is what happens in GPT as well: although it looks like a sentence appears at once, the model actually produces one word at a time — that is why you see the tokens appear one by one in the output. It produces this word, gives it as input, then produces the next one, along with the previous input sequence. Because of this one-at-a-time flow it is difficult to parallelize the decoder. And because the model can hallucinate, we have RAG — retrieval augmented generation — to avoid hallucination; that is covered in the post-mid-semester material.

Recap + bridge. The transformer replaced the LSTM's left-to-right chain with parallel attention over the whole sentence; BERT is the encoder side of that architecture, pre-trained on huge text and fine-tuned for tagging through a one-layer classification head, while the auto-regressive decoder side generates one token at a time — which is exactly where prompting, the next topic, enters.

Exam note: the attention mathematics — attention scores, multi-headed attention, key-query-value matrices — is post-mid-semester material; the neural topics in this session get application-oriented conceptual questions instead.

7.8 Prompting and Few-Shot POS Tagging

7.8.1 Soft and hard prompting

Instead of fine-tuning, you can prompt. Fine-tuning sometimes uses soft prompting or hard prompting — giving the model instructions. The idea: you give a prompt — for example, an instruction to "tag the following sentence using this Treebank dataset and output only the word-tag pairs" — and the LLM follows it. During training time you can also train the model with prompts, without providing a fine-tuning dataset; and you can prompt at runtime and make the model better on the fly with few-shot examples. Advanced techniques such as RLHF (reinforcement learning from human feedback) are out of scope here and covered in the next semester, along with more advanced fine-tuning techniques.

Intuition — instruct, do not rewire. Fine-tuning changes the model's weights; prompting just describes the job in words. The skill is already inside the model — the prompt is the question that calls it out. It is like asking a fluent speaker to label parts of speech rather than sending them back to school. Two flavours: zero-shot gives only the instruction; few-shot adds a handful of solved examples first, so the model copies the format and the exact tag set.

Worked example: tagging "The concert was great." by prompt. Zero-shot prompt: "Tag the following sentence using the Penn Treebank tagset. Output only the word/tag pairs. Sentence: The concert was great."

Step 1 — expected output: The/DT concert/NN was/VBD great/JJ ./. — determiner, noun, past verb, adjective, full stop.

Step 2 — a common zero-shot slip: left alone, the model may answer with the wrong vocabulary — great/ADJ or great/adjective instead of the Penn Treebank JJ. The grammar is right; the label convention is not.

Step 3 — few-shot fix: add two solved examples in the exact tag set first: Dogs/NNS bark/VBP ./. She/PRP left/VBD ./. Sentence: The concert was great. Now the model copies the convention and returns great/JJ.

Sense-check: a few in-context examples bought tag-set consistency with zero training — the prompt did the aligning that fine-tuning used to do.

Scope and pitfalls. LLMs can hallucinate a plausible-looking tag, drift off the requested tag set, or mis-split punctuation. For high-volume, accuracy-critical tagging, a fine-tuned transformer is still cheaper and steadier. And prompting is not free: every prompt consumes tokens, which is a real cost in production — the topic of the closing section.

Recap + bridge. Prompting asks a capable LLM to tag from a plain instruction (zero-shot), and a few in-prompt examples (few-shot) lock it onto the right tag set — no gradients, no fine-tuning corpus. The same describe-then-example pattern drives translation, extraction, and classification.

Exam note: prompting and few-shot behaviour on the neural side are tested as application-oriented conceptual questions, not mathematics.

7.9 LLM Agents and POS Tagging APIs

7.9.1 Function calling and task decomposition

LLM agents use POS tagging to a large extent — conversational AI, machine translation, everywhere POS tagging is a must. The way agent systems do it: the agent makes a function call to a POS tagging API, which automatically produces the tags, and similarly can call an API for named entity recognition that identifies names of places, organizations, and persons. That NER call is not trivial: a multiword institution name is a long sequence, and deciding whether the whole span should be treated as the name of a place, an organization, or a person is a hard problem. But with function calling and external tools, agents offload the work.

Intuition — the smart project manager. The LLM does not personally do every precise measurement. It hands the exact, repetitive part to a specialist tool and then writes up the result: planning from the generalist, precision from the specialist. Asked which rooms in a house face north, you would not eyeball it — you would grab a compass, read each room, then answer. The agent grabs a POS tagger the same way, for the part that needs exactness.

The agent loop has five moves: read the request; break it into steps; call a tool for the step that needs it; read the tool's output; finish the task.

Agents also decompose tasks. Given a task like "analyze the sentiment for this review," the agent breaks the review into subparts, finds the part-of-speech tags — adjectives contribute heavily to sentiment — passes the pieces to different APIs, and assembles the sentiment result. So POS tagging is used as a function-call tool by LLM agents, and the agents take its output to perform further, more complex tasks. And the reverse direction exists too: LLM agents can themselves be used for POS tagging, and Viterbi itself is used inside agentic AI for many applications.

Worked example: "Analyse the sentiment of all nouns in the user reviews."

Step 1 — plan: the agent splits the request. First, find the nouns. Second, judge the sentiment attached to each. Finding nouns needs accurate tagging — a job for a tool.

Step 2 — call the tool: POS_tag("The battery is amazing but the screen is dull .") returns the tags; the agent keeps the NN words: battery and screen.

Step 3 — use the tags: for each noun it reads the describing word. "Battery" is paired with "amazing" (+0.8). "Screen" is paired with "dull" (-0.6).

Step 4 — integrate and answer: it reports per-noun sentiment — battery is positive (+0.8), screen is negative (-0.6). That is exactly what the user asked for.

Sense-check: the LLM never had to be a great tagger itself. It called one (a fine-tuned BERT, typically) and spent its own effort on planning and the write-up.

Scope — what can go wrong. The agent must trust and correctly read the tool's output, and it can still mis-plan the overall task. Each tool call also costs time and money. The point is the division of labour, not magic: precise sub-tasks go to precise tools.

Recap + bridge. POS tagging becomes a quiet utility inside larger AI systems: agents call tagger and NER APIs through function calling and decompose bigger tasks (like per-noun sentiment) around them — while classical decoders like Viterbi keep running inside the agentic pipelines.

Real-world: this is the pattern the curriculum is heading toward — agents, agentic AI, MCP protocols, and A2A protocols are covered in next-semester courses, building on the background from this course.

7.10 Choosing an Approach: Explainability, Cost, and Open Challenges

7.10.1 Explainability matters

Hook: imagine your loan application is rejected and the bank can only answer "because of these 175 billion parameters." Would you open an account there? The statistical approaches survive in production for exactly this reason — they can say why.

The statistical approaches — HMM, Viterbi, MEMM — have one huge advantage the neural models lack: they are highly explainable. You know why a result came out. There is a famous practical story the professor tells: imagine your loan application is rejected because "the parameter beta is giving me less than 0.05 values" — people would stop opening accounts at that bank. You have to be able to say: this is the reason your loan is rejected. You cannot answer "because of these 175 billion parameters." So explainability is critical, and people are working on making the advanced algorithms explainable too — there are observability tools for that, such as TruLens (the professor's spoken "TrueLens"; the standard spelling is TruLens, an open-source observability library for LLM applications that traces how an answer was produced). Even so, explainability remains a reason the classical approaches stay in production.

7.10.2 Token costs and compute

LLM usage costs real money. When you use APIs you pay for tokens — on the order of 15 dollars per month for a personal API budget. The question for a business is whether those tokens give ROI. For a generic user it does not matter — you query the model again tomorrow — but for an enterprise earning money from the application, every API call is a cost: you pay per token. Production topics like prompt caching and KB cache exist precisely to reduce the cost of API tokens. Tokens also cause a carbon footprint — data centers are another environmental concern — and there is a data concern: NDAs. Enterprise organizations do not want their finance or medical data exposed to generic APIs.

Scope — who can afford what. The compute itself is expensive: an H100 server costs on the order of 20 lakh rupees (about two million rupees — the professor's verbal estimate) and supports only so much compute; fine-tuning or retraining a large language model may need many such servers, which not every enterprise can afford. If the budget is small, the simple, explainable, low-cost approaches are not a compromise — they are the sensible engineering choice.

7.10.3 Domain-specific and low-resource challenges

Modern POS tagging is not a solved problem despite all the fancy approaches and good accuracy. Generic LLMs do not work well on domain-specific vocabulary — medical vocabulary, finance vocabulary — where fine-tuning would be needed, and fine-tuning costs training time and money. There are also major challenges for low-resource languages, particularly Indian languages. These are flagged as topics for next-semester courses focusing on Indian languages and techniques for them.

7.10.4 Industry reality: hybrid approaches

The honest industry picture: nobody uses agentic tech for every problem. Agentic AI is still nascent — MCP and A2A protocols are still being put in place — and it carries hallucinations, guardrail issues, safety concerns, black-box and explainability issues, and money issues, since it needs a lot of compute power. Only the giant companies can afford hundreds of H100 servers. So all the approaches remain in use; people go for hybrid solutions and choose among them by requirement. When agents call APIs for POS tagging or other applications, they often use the simpler, low-cost APIs — so the classical approaches are popular even inside agent pipelines. If you want a highly accurate system and can afford it, you go advanced; under cost and time restrictions you take a simpler approach — which is also the explainable one. The industry is also moving toward smaller models.

Q: Even in today's world we still have applications for Viterbi POS tagging, right? Or do we always go with the best?

A: We still have Viterbi. People talk a lot about agentic tech, but if you actually go into industry, very few use agentic tech for each and every problem — it is a combination. When agents call the APIs for POS tagging, they use simpler, low-cost APIs, so these approaches are popularly used. All of them play an important role.

Q: If I am into prompting in one or two sentences — not giving paragraphs of data — could I always go with the Viterbi algorithm?

A: Yes, correct — because prompting has a cost. There are tokens when you use APIs — 15 dollars per month for those tokens — and the question is whether those tokens give you ROI. For an enterprise-level application earning money, tokens and API calls are money: you pay per token. So for short, structured tagging tasks, the classical algorithms remain a perfectly good choice.

Q: What kind of problems can we expect on the topics covered today?

A: Mostly application-oriented for the mid-semester: case-study style — given this kind of problem, which approach do you think is the most suitable, and why, with reasoning. Conceptual-level questions. Mathematical problems will not be possible on the neural topics. But in the statistical POS tagging part you can definitely expect mathematical problems — on Viterbi, on HMM, and also on MEMM. (An earlier in-session statement said "there won't be mathematical problems on MEMM; mathematical problems can be expected on HMM and Viterbi"; the closing recap included MEMM as well. Either way, HMM and Viterbi are the primary math targets — practice those numerically.)

Recap. Every approach from this session is still in use, chosen by requirement: HMM and Viterbi for explainable, low-cost, short structured tagging; MEMM when hand-built features matter; Bi-LSTM + CRF for the accurate neural baseline; fine-tuned transformers for near-perfect accuracy when compute and money allow; prompting when you need a quick answer without training; and agents that call all of the above as tools. Accuracy, explainability, cost, and data constraints decide which one is "most suitable" — the exact judgment the exam asks you to make.

Exam note: neural and LLM topics get application-oriented case-study questions — which approach is most suitable and why — while mathematical problems land on the statistical methods.

Exam Guidance Summary

Mathematical problems: expect a mathematical problem on Viterbi — the session opened by completing the Viterbi material precisely because "you can expect a mathematical problem on that," and it closed with the same message: expect a math problem on either HMM or Viterbi, any one of them.
Question style: the values in the exam will be simple — "a lot of 0 and lesser values" — because the aim is to test understanding of the concepts, not computational ability ("calculators are good at that"). Expect small probability values and at most two to three states with zeros that clear most paths.
Graph advice: in a Viterbi problem, show the grid/graph — "better would be to show the graph, a simple graph, not fancy" — and if the final path is asked, show the final path too. From the second word onward you select the maximum value alone, and among the final states you select the maximum as well.
Application-level question: be ready for a question like "how is the Viterbi efficient, or how is it useful in a POS tagging sequence problem?"
MEMM: no mathematical problems expected on MEMM (the closing recap mentioned MEMM too; treat HMM and Viterbi as the primary math targets).
Neural and LLM approaches: application-oriented conceptual questions — a case study where you must pick the most suitable approach and justify it with reasoning; mathematical problems will not be asked on these topics.
Sample paper: there may be a sample paper with an example to solve — worth working through.
Scope of the mid-semester exam: closed-book; based on the course handout content. The webinars were hands-on sessions aimed at the assignments, not a source of exam questions.
Weightage: word embedding and language modeling carry high weightage; a recap session walks through the modules, the marking scheme, and the structure of the paper.

Key Industry Applications

Viterbi: still used in many POS tagging algorithms and in agentic AI applications; the greedy dynamic-programming decoder remains relevant decades after it was introduced.
HMM-based POS tagging: the statistical baseline that powers many classical taggers.
MEMM: feature-based discriminative tagging; logistic regression — "softmax is nothing but a sigmoid function" — remains popular in real-world applications, including agentic AI.
Bi-LSTM + CRF: the neural baseline for sequence tagging, used for POS tagging and NER in conversational AI systems; around 97% accuracy with slower training than transformers.
Transformers / BERT: near-100% accuracy on POS tagging; parallelizable encoders; the encoder part of pre-trained models is fine-tuned for tagging tasks.
Libraries: Hugging Face hosts open-source BERT implementations including POS tagging models; SpaCy is a very good POS tagging library with transformer support.
LLM agents: agents call POS tagging and NER APIs through function calling and decompose tasks (for example, sentiment analysis of a review by tagging adjectives), with Viterbi still inside agentic AI pipelines.
Fine-tuned small language models: small language models fine-tuned with POS-tagging instructions give better results than generic prompts at lower cost.
Explainability in finance: loan-rejection decisions must be explainable ("the parameter beta is below 0.05") — a core reason classical models survive in production alongside observability tools like TruLens.
Cost reality: tokens cost money (15 dollars per month budgets, per-token enterprise billing, prompt caching), H100 servers cost about 20 lakh rupees each, and NDA constraints push enterprises toward on-premise and simpler approaches.
Open problems: domain-specific vocabulary (medical, finance) and low-resource languages (especially Indian languages) keep POS tagging an active research and engineering problem.

NLP Lecture 7 Notes · Part-of-Speech Tagging: Viterbi, MEMM, and Neural Approaches

Natural Language Processing· postgraduate· 2026-08-13

Sections Breakdown

17.1 Viterbi Algorithm: Decoding the Best State Sequence

Why brute-force tag enumeration explodes, the Viterbi probability, the max recurrence with backpointers, and the N x T saving over N^T sequences.

27.2 Worked Example: The Ice-Cream Weather Sequence

Day-by-day Viterbi decoding of Jason's ice-cream counts into the weather sequence, with real numbers and the final backtrack to the best path.

37.3 Worked Example: POS Tagging "I want to race"

The four-tag Viterbi grid for 'I want to race': the slide corrections, zero emissions that prune the grid, and the final column decision.

47.4 Worked Example: POS Tagging "The doctor is in"

Five-state Viterbi decoding of 'the doctor is in': the 0.21 determiner start, greedy pruning from word two, and the sequence probability.

57.5 Maximum Entropy Markov Models (MEMM)

The HMM's bidirectionality and generative limitations, the discriminative MEMM posterior with softmax feature classifiers, and the label-bias blind spot.

67.6 Bi-LSTM + CRF for Sequence Tagging

LSTM gates and the vanishing gradient, bidirectional context, CRF transition scores, and why the sequence-level view beats greedy per-word tags.

77.7 Transformers and BERT for POS Tagging

Attention as context without a window, BERT as the bidirectional encoder, fine-tuning a one-layer classification head, and auto-regressive decoding.

87.8 Prompting and Few-Shot POS Tagging

Soft and hard prompting, zero-shot versus few-shot tagging with the Penn Treebank tag set, and when prompting beats fine-tuning.

97.9 LLM Agents and POS Tagging APIs

Function calling to tagging and NER APIs, task decomposition, and the agent loop with POS tagging as a tool.

107.10 Choosing an Approach: Explainability, Cost, and Open Challenges

Why classical models survive for explainability, token and compute costs, domain and low-resource challenges, and the hybrid industry reality.

11Exam Guidance Summary

The mid-semester exam strategy: mathematical problems on HMM and Viterbi, application-oriented case studies on the neural side.

12Key Industry Applications

Where each tagging approach is used in industry today, from classical taggers inside agent pipelines to fine-tuned transformers.

Postgraduate students in Natural Language Processing

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Viterbi Algorithm: Decoding the Best State Sequence

Must-know: Viterbi decodes the best state sequence by dynamic programming: first column V_1(j) = pi_j * b_j(o_1); later cells V_t(j) = max_i V_{t-1}(i) * a_ij * b_j(o_t); backpointers recover the path; cost is N*T cells instead of N^T sequences.

$V_{t} (j) = i max (V_{t - 1} (i) \cdot a_{ij} \cdot b_{j} (o_{t}))$

⚠️ Top pitfall: Confusing 'one best path per state' with 'one global path': Viterbi keeps one candidate per state at every position; pruning a single global path early is what loses accuracy. A zero Viterbi value kills every path through that cell.

Self-check: Why is brute force infeasible for POS tagging but fine for the two-state three-day ice-cream problem? (45^8 tag sequences versus 2^3 = 8 weather sequences.)

Connects to: 7.2, 7.3, 7.4

Worked Example: The Ice-Cream Weather Sequence

Must-know: Viterbi on the ice-cream model: day-1 cells are prior x likelihood (0.32, 0.02); every later cell is max over previous states of stored value x transition x emission, and only the maximum path into each state is carried forward; the final answer is found by backtracking from the best last cell.

$V_{2} (cold) = max (0.32 \times 0.3 \times 0.5, 0.02 \times 0.6 \times 0.5) = 0.048$

⚠️ Top pitfall: Using a stale stored value: when computing day 3 you must use the latest stored day-2 Viterbi values, not the day-1 value 0.32. The next column reads only the previous column.

Self-check: Why is the best-sequence probability (0.0125) so much smaller than the day-1 value 0.32? (It is a product of six probabilities along one path; comparing sequences, not single cells, is the correct reading.)

Connects to: 7.1, 7.3, 7.4

Worked Example: POS Tagging "I want to race"

Must-know: First column: transition-from-start times emission (0.067 x 0.37 = 0.0248 for PPSS; all other first tags are 0 for "I"). Later columns: max over predecessors of stored value x transition x emission, and only the max is carried forward, including in the final column.

$V_{1} (PPSS) = 0.067 \times 0.37 = 0.0248, V_{2} (VB) = 0.0248 \times 0.23 \times 0.0093$

⚠️ Top pitfall: Misreading the emission direction: transition is with respect to the tags (states), emission with respect to the words — P(want | VB) is an emission, P(VB | PPSS) is a transition. Also, the slide printed 0.67 x 0.37; the correct value is 0.067 x 0.37.

Self-check: Why does "I" eliminate three of the four tags before any transition is used? (Its emission is zero for VB, TO and NN; a zero emission kills every path through that cell.)

Connects to: 7.1, 7.2, 7.4

Worked Example: POS Tagging "The doctor is in"

Must-know: The doctor chain: 0.21 (determiner start) x 0.9 (noun after determiner) x 0.4 (doctor given noun) = 0.0756. Greedy pruning starts at the second word; all first-word states are computed. Read emission tables as word given tag.

$V_{2} (noun) = 0.21 \times 0.9 \times 0.4 = 0.0756$

⚠️ Top pitfall: Reading the emission table backwards: the left side is the given, so P(doctor | noun) is an emission but P(noun | doctor) is the posterior we want, which equals likelihood (emission) times transition.

Self-check: Why does "the" leave only the determiner cell alive? (Emissions for noun, verb, preposition, adverb are all 0 for the word "the," and a zero first-column cell kills every path through it.)

Connects to: 7.1, 7.2, 7.3

Maximum Entropy Markov Models (MEMM)

Must-know: MEMM is discriminative: it directly maximizes the posterior P(y_1..y_n | x_1..x_n), factored into per-tag softmax classifiers P(y_i | y_{i-1}, x) over features, instead of the HMM's likelihood x prior. Its blind spot: no global view of the sequence.

$y^_{1.. n} = ar g y_{1}, \dots, y_{n} max P (y_{1}, \dots, y_{n} ∣ x_{1}, \dots, x_{n})$

⚠️ Top pitfall: Believing the MEMM sees the whole sentence: it looks at the next words as features, but it does not consider the sequence — each word's tag is chosen without a global view (label-bias problem).

Self-check: Why is logistic regression enough to build an MEMM? (Tagging is posed as a multi-class classification problem per word; softmax over feature scores gives the per-tag probabilities, and softmax with two classes is the sigmoid.)

Connects to: 7.1, 7.4, 7.6

Bi-LSTM + CRF for Sequence Tagging

Must-know: The CRF scores the whole tag sequence as P(Y|X) = exp(sum of per-position scores)/Z(X); in the Bi-LSTM+CRF recipe each score is an emission score from the Bi-LSTM plus a transition score from the CRF table, and the best sequence is decoded with Viterbi-style selection.

$P (Y ∣ X) = \frac{1}{Z ( X )} exp (i = 1 \sum N s (y_{i - 1}, y_{i}, X, i))$

⚠️ Top pitfall: Confusing the two score types: emission is word-fits-tag (from the Bi-LSTM), transition is tag-follows-tag (from the CRF table). Greedy per-word decoding throws away the transition scores — the information that keeps a sequence legal.

Self-check: Why did the CRF tag 'the plays' as DT NN even though VBZ had the best emission for 'plays'? (The DT->NN transition reward +4 outweighed the VBZ emission gain; the sequence score 11 beat the greedy 7.)

Connects to: 7.1, 7.5, 7.7

Transformers and BERT for POS Tagging

Must-know: BERT = bidirectional, encoder-only transformer, pre-trained on web-scale text and fine-tuned for tagging with a one-layer classification head (logits = Wh + b, softmax over tags); fine-tuning freezes most parameters. Encoders parallelize; auto-regressive decoders generate one token at a time.

$logits = W h + b, P (t) = \frac{e ^{logit_{t}}}{\sum _{t^{'}} e ^{logit_{t^{'}}}}$

⚠️ Top pitfall: Believing the decoder parallelizes: the decoder is auto-regressive — one token at a time, each step feeding the previous output back as input — while only the encoding side computes all positions in parallel.

Self-check: When the model predicts a wrong next word during decoder training, which output is fed back? (The training data is used to compute the loss and softmax; the maximum-probability word is produced one at a time.)

Connects to: 7.6, 7.8, 7.10

Prompting and Few-Shot POS Tagging

Must-know: Zero-shot prompting gives only the instruction; few-shot adds solved examples in the target tag set, so the model copies the format and the exact tag convention without any training.

⚠️ Top pitfall: The model may return grammatically right tags in the wrong vocabulary (great/ADJ instead of great/JJ); a few in-prompt examples fix the convention. Prompting also costs tokens and can hallucinate.

Self-check: Why does few-shot prompting beat zero-shot for tag-set consistency? (The solved examples show the exact tag vocabulary and format, so the model copies the convention instead of inventing its own.)

Connects to: 7.7, 7.9, 7.10

LLM Agents and POS Tagging APIs

Must-know: The agent loop: read the request, break it into steps, call a tool (POS tagging or NER API) for the step that needs it, read the tool's output, finish the task — tagging becomes a sub-step of a bigger task.

⚠️ Top pitfall: Assuming the agent itself must tag: the agent calls a fast specialised tagger as a tool; the risk is mis-planning the task or misreading the tool output, and each call costs time and money.

Self-check: How does an agent answer 'analyse the sentiment of all nouns in the reviews'? (It calls POS_tag on the review, keeps the NN words, reads the describing adjectives, and reports per-noun sentiment.)

Connects to: 7.7, 7.8, 7.10

Choosing an Approach: Explainability, Cost, and Open Challenges

Must-know: The choice among taggers is a trade-off: statistical methods (HMM/Viterbi/MEMM) are explainable and cheap but less accurate; neural and LLM methods are accurate but costly, black-box, and compute-hungry — industry uses hybrid combinations, and agents call simple low-cost APIs.

⚠️ Top pitfall: Assuming the most advanced approach is always best: prompting has token costs, fine-tuning needs expensive compute, and agentic tech still carries hallucination, guardrail, and explainability issues — for short structured tagging tasks, Viterbi remains a perfectly good choice.

Self-check: Why must a bank's loan-rejection decision be explainable? (Customers need 'the parameter beta is below 0.05' as a reason; 'because of 175 billion parameters' is not an acceptable answer.)

Connects to: 7.1, 7.5, 7.6, 7.7, 7.8, 7.9

Exam Guidance Summary

Must-know: Expect a math problem on HMM or Viterbi (not MEMM or neural topics); simple values, at most two to three states, zeros clearing paths; show the grid graph and the final path; application-level questions ask how Viterbi is efficient and useful in POS tagging.

⚠️ Top pitfall: Overcomplicating: exam values are small with many zeros by design — they test concept understanding, not arithmetic ability.

Self-check: Which topics carry mathematical problems and which carry application-oriented case studies? (Math: HMM and Viterbi. Case studies: neural and LLM approaches.)

Connects to: 7.1, 7.2, 7.3, 7.4, 7.5, 7.10

Key Industry Applications

Must-know: Industry runs hybrids: agents call simple low-cost tagging APIs (classical methods) for short structured tasks, while fine-tuned transformers and Bi-LSTM + CRF systems power high-accuracy pipelines; explainability and cost decide the choice.

⚠️ Top pitfall: Assuming agentic tech replaced everything: very few companies use agentic tech for every problem — simpler, low-cost, explainable APIs remain popular even inside agent pipelines.

Self-check: Why do classical models survive in production alongside 175-billion-parameter models? (Explainability — loan decisions need reasons — plus cost, NDA constraints, and per-token billing.)

Connects to: 7.1, 7.6, 7.7, 7.9, 7.10

Previous LectureLecture 06 · Large Language Models, Prompt Engineering, and Part-of-Speech Tagging

Next LectureLecture 08 · Mid-Semester Exam Revision: NLP Foundations

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

7.1 Viterbi Algorithm: Decoding the Best State Sequence

7.1.1 Why brute force fails

7.1.2 Storing intermediate results: Viterbi probabilities

7.1.3 The greedy recurrence, backpointers, and the complexity saving

7.1.4 Student questions: greedy behavior and the HMM–Viterbi distinction

7.2 Worked Example: The Ice-Cream Weather Sequence

7.2.1 Setup and the first day

7.2.2 The second day: competing paths and the max

7.2.3 The third day: use the stored value

7.3 Worked Example: POS Tagging "I want to race"

7.3.1 The problem, the tag set, and the matrices

7.3.2 The first word: reading values from the tables

7.3.3 The second word: greedy pruning and the 0.093 fix

7.3.4 The final stage: maximum everywhere

7.4 Worked Example: POS Tagging "The doctor is in"

7.4.1 Setup: five states and the initial probabilities

7.4.2 Word by word: "the" and "doctor"

7.4.3 "is," "in," and the overall sequence probability

7.4.4 Reading the emission table

7.5 Maximum Entropy Markov Models (MEMM)

7.5.1 HMM's bidirectionality limitation

7.5.2 MEMM as a discriminative classifier

7.5.3 Features for POS tagging

7.5.4 MEMM's blind spot

7.6 Bi-LSTM + CRF for Sequence Tagging

7.6.1 LSTM recap and the vanishing gradient

7.6.2 Why bidirectional

7.6.3 The CRF layer: conditional random fields

7.6.4 Combining Bi-LSTM emissions with CRF transitions

7.7 Transformers and BERT for POS Tagging

7.7.1 Attention: the "Attention Is All You Need" breakthrough

7.7.2 BERT: the bidirectional encoder

7.7.3 Fine-tuning for POS tagging

7.7.4 Parallelization, auto-regressive decoders, and RAG

7.8 Prompting and Few-Shot POS Tagging

7.8.1 Soft and hard prompting

7.9 LLM Agents and POS Tagging APIs

7.9.1 Function calling and task decomposition

7.10 Choosing an Approach: Explainability, Cost, and Open Challenges

7.10.1 Explainability matters

7.10.2 Token costs and compute

7.10.3 Domain-specific and low-resource challenges

7.10.4 Industry reality: hybrid approaches

Exam Guidance Summary

Key Industry Applications

NLP Lecture 7 Notes · Part-of-Speech Tagging: Viterbi, MEMM, and Neural Approaches

Sections Breakdown

Exam Revision Notes

Viterbi Algorithm: Decoding the Best State Sequence

Worked Example: The Ice-Cream Weather Sequence

Worked Example: POS Tagging "I want to race"

Worked Example: POS Tagging "The doctor is in"

Maximum Entropy Markov Models (MEMM)

Bi-LSTM + CRF for Sequence Tagging

Transformers and BERT for POS Tagging

Prompting and Few-Shot POS Tagging

LLM Agents and POS Tagging APIs

Choosing an Approach: Explainability, Cost, and Open Challenges

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat