Sequence Models & Labelling · Natural Language Processing

01 · Motivation

Why order matters

Bag-of-words threw word order away. But “dog bites man” and “man bites dog” are different news; “not good” is the opposite of “good”. Many tasks need a model that reads tokens in sequence and labels each one in context.

Sequence labelling assigns a label to every token: part-of-speech tags, named-entity spans, chunk boundaries. The label of one token depends on its neighbours, so we need representations that carry context along the sequence.

02 · Recurrence

Recurrent neural networks

A recurrent neural network processes a sequence one token at a time, maintaining a hidden state $\mathbf{h}_t$ that summarises everything seen so far. At each step it combines the current input with the previous hidden state:

RNN cell

\mathbf{h}_t = \tanh\!\bigl(\mathbf{W}_{hh}\mathbf{h}_{t-1} + \mathbf{W}_{xh}\mathbf{x}_t + \mathbf{b}\bigr), \qquad \mathbf{y}_t = \mathbf{W}_{hy}\mathbf{h}_t

The same weights are reused at every step (parameter sharing), so an RNN handles sequences of any length. “Unrolling” it through time turns it into a deep feed-forward net with shared layers.

Train it by backpropagation through time (BPTT): unroll the network across the sequence and backpropagate as usual. That deep, shared-weight structure is exactly where the trouble starts.

03 · The problem

The vanishing-gradient problem

Backpropagating through many time steps multiplies many small derivatives together. If the recurrent weight’s effective gradient magnitude is below 1, the product shrinks exponentially with distance — the vanishing gradient. The network cannot learn dependencies more than a few steps apart: by the time the error signal reaches early tokens, it is essentially zero. (The mirror failure, gradients above 1, explodes — usually patched with gradient clipping.)

!

The concrete symptom

A plain RNN reading “The cats that the dog chased … were hungry” struggles to enforce the plural agreement, because the gradient connecting “were” back to “cats” has decayed across the intervening words. Long-range dependencies are exactly what natural language is full of.

04 · The fix

LSTMs — gated memory

The Long Short-Term Memory cell adds a separate cell state $\mathbf{c}_t$ that flows along the sequence with only minor, gated edits — an “information highway” the gradient can travel without vanishing. Three gates (each a sigmoid, outputting 0–1) control it:

Forget gate

Decides what to erase from the old cell state.

Input gate

Decides what new information to write.

Output gate

Decides what part of the cell state to expose as the hidden state.

Hands-on 1

The forget gate is the gradient highway

At t = 0 a memory is written into the cell state. The forget gate f decides how much survives each step: C_t = f·C_(t-1) + i·C̃_t. Push f toward 1 and the memory persists for the whole sequence; drop it and the cell forgets at once.

Forget f0.95

Input i1.00

Output o1.00

Retention f^9

0.63

∂C_t/∂C_0

f^t

Memory

Preserved

Try thisSet f = 1.00: the cell state is a flat line — perfect memory, and the gradient factor ∂C_t/∂C_0 = f^t stays 1, so nothing vanishes. Now drag f down to 0.5 and watch both the memory and the gradient highway collapse. The output gate o only rescales the dashed h_t — it never touches the cell's persistence.

TakeawayVanishing gradients come from multiplying many factors below 1. The LSTM's additive cell update with f ≈ 1 replaces that product with a single near-1 factor — a highway the gradient travels without decaying. The forget gate, not the output gate, is what defeats vanishing.

Q

Why LSTMs beat plain RNNs

The additive cell-state update (rather than the repeated multiplication of an RNN’s hidden state) lets gradients flow across many steps without vanishing. The forget gate learns when to keep or drop information, so the network can hold a fact for hundreds of steps and release it on cue. GRUs are a lighter two-gate variant with similar benefits.

05 · Both directions

Bidirectional models

For labelling, the whole sentence is available at once — so use it. A BiLSTM runs one LSTM left-to-right and another right-to-left, then concatenates their hidden states at each position. Now the representation of a token reflects both its left and right context. “He went to the bank to fish” vs ”… to deposit a cheque” — the disambiguating word comes after “bank”, and only a model that reads rightward can use it. BiLSTMs (and BiLSTM-CRF for globally consistent tags) were the state of the art for POS/NER before transformers.

06 · Task 1

POS tagging

Part-of-speech tagging assigns each token a grammatical category (noun, verb, adjective, …). It is the canonical sequence-labelling task and a building block for parsing and information extraction. Local cues (suffixes, capitalisation, a lexicon) go far, but ambiguous words need context.

Hands-on

Part-of-speech tagger

Type a sentence; each token gets a POS tag from a small lexicon plus suffix rules. Local cues (capitalisation → PROPN, -ly → ADV, -ing/-ed → VERB) carry a lot of the signal — but ambiguous words (“flies”, “bank”) show why context matters.

Sentence

theDET

quickADJ

brownADJ

foxNOUN

jumpsVERB

overADP

theDET

lazyADJ

dogNOUN

TakeawayPOS tagging is per-token classification, but the right tag depends on neighbours — “flies” is a verb in “time flies” and a noun in “fruit flies”. Sequence models (HMM/Viterbi, BiLSTM) condition on context to resolve that.

Q

Why POS tagging needs context

The same word takes different tags by context: “time flies” (verb) vs “fruit flies” (noun); “I book a flight” vs “a book”. A purely per-token classifier with no neighbour information cannot resolve these — which is why HMMs, CRFs, and BiLSTMs condition on surrounding tokens/tags.

07 · Task 2

Named-entity recognition

NER finds and types spans — people, organisations, locations, dates. Spans can be multi-token (“New York Times”), so it is encoded as token labelling with the BIO scheme: **B-**TYPE begins a span, **I-**TYPE continues it, O is outside any entity.

Hands-on

Named-entity recognition (BIO tagging)

Entities are highlighted by type (PER / ORG / LOC) and shown as a B-/I-/O tag sequence. B-marks the beginning of a span, I- the inside, O outside any entity.

Text

Tim^PER Cook is the CEO^PER of Apple^ORG in Cupertino^LOC California . Apple^ORG released the new iPhone .

B-PERI-PEROOB-PEROB-ORGOB-LOCI-LOCOB-ORGOOOOO

TakeawayBIO tagging turns span extraction into per-token classification, so any sequence labeller (CRF, BiLSTM, transformer) can do NER. The B-/I- distinction is what lets two adjacent entities of the same type stay separate.

Q

Why the B-/I-/O scheme

BIO turns variable-length span extraction into fixed per-token classification, so any sequence labeller can do NER. The B-/I- split is essential: it keeps two adjacent entities of the same type (”… visited [Paris] [London] …”) from merging into one span. Variants (BIOES/BILOU) add explicit end and single-token tags.

08 · Structured decoding

Viterbi — globally consistent tags

A per-token classifier can produce illegal sequences — an I-PER with no preceding B-PER, for instance. Structured models (HMM, CRF) score the whole tag sequence, including transition scores between adjacent tags, and decode the single best sequence with the Viterbi algorithm — dynamic programming over a trellis:

Viterbi recursion

\delta_t(k) = \max_{j}\;\bigl[\delta_{t-1}(j) + T(j \to k)\bigr] + E_t(k)

$\delta_t(k)$ is the best score of any path ending in tag $k$ at position $t$ ; $T$ is the transition score, $E$ the emission. Backtrack from the best final cell to recover the path. Cost O(T·K²), versus exponential K^T brute force.

Hands-on

Viterbi decoding

Find the single most probable tag sequence. Each cell δₜ(k) is the best score of any path ending in tag k at token t. Step fills one column; Backtrack traces the best path back from the final column.

tag \ token	John t=0	Smith t=1	visited t=2	Paris t=3
O	0.00	·	·	·
B-PER	0.00	·	·	·
I-PER	−∞	·	·	·

TakeawayViterbi is dynamic programming over a trellis: it finds the globally best tag sequence in O(T·K²) instead of the exponential K^T of brute force. The −∞ transitions encode hard constraints (you cannot start an entity with I-PER).

Q

Greedy vs Viterbi decoding

Greedy decoding picks the best tag at each position independently and can paint itself into a corner (a locally good tag forcing an illegal or low-scoring continuation). Viterbi considers transition scores and finds the globally optimal sequence — the −∞ transitions encode hard constraints like “O cannot be followed by I-PER”.

09 · Self-check

Questions before you move on

What causes the vanishing-gradient problem in plain RNNs?

How does the LSTM cell state help with long-range dependencies?

In the BIO tagging scheme, what does I-LOC mean?

Why use the Viterbi algorithm instead of greedy per-token decoding?

10 · Recap

One-screen summary

Chapter 05 — load-bearing ideas

Sequence labelling assigns a label to every token; word order and context matter (unlike BoW).
RNNs carry a hidden state across time with shared weights, trained by backpropagation through time.
Vanishing gradients stop plain RNNs from learning long-range dependencies; exploding gradients are clipped.
LSTMs add a gated cell state (forget / input / output gates) — an additive memory highway that preserves gradients.
BiLSTMs read both directions, so each token’s representation uses left and right context.
POS tagging (grammatical category) and NER (typed spans, BIO scheme) are the two canonical token-labelling tasks.
Viterbi decodes the globally most probable tag sequence via DP over a trellis — O(T·K²), respecting transition constraints.

11 · Exam · past papers

Past-paper questions

Answered 0 / 8 · 0 correct

Q-SEQ1What does the hidden state of an RNN represent?
Q-SEQ2The vanishing-gradient problem in RNNs primarily prevents the network from:
Q-SEQ3Which component is unique to the LSTM (vs a plain RNN)?
Q-SEQ4A BiLSTM differs from a unidirectional LSTM in that it:
Q-SEQ5In NER with BIO tagging, the tag B-ORG means:
Q-SEQ6The Viterbi algorithm computes:
Q-SEQ7Why can POS tagging not be done reliably by a context-free per-word dictionary lookup?
Q-SEQ8Greedy decoding of tags can fail where Viterbi succeeds because greedy decoding: