Sequence Labeling

Overview

Sequence labeling assigns a categorical label to each token in a sequence. It is a foundational task in NLP, underpinning part-of-speech tagging, named entity recognition, chunking, and more. The progression from handcrafted rules to statistical models to neural architectures mirrors the broader evolution of the field.

Part-of-Speech Tagging

POS tagging assigns grammatical categories (noun, verb, adjective, etc.) to each word.

Tag Sets

Hidden Markov Models (HMM)

A generative model that jointly models the tag sequence and the word sequence.

Components:

• Transition probabilities: P(t_i | t_{i-1}) -- how likely one tag follows another
• Emission probabilities: P(w_i | t_i) -- how likely a word given its tag
• Initial probabilities: P(t_1)

Decoding: The Viterbi algorithm finds the most probable tag sequence in O(T * K^2) time, where T is sequence length and K is the number of tags.

Limitations:

• Assumes each word depends only on its tag (not context words)
• Cannot use arbitrary overlapping features
• Unknown words handled by suffix-based heuristics

Conditional Random Fields (CRF)

A discriminative model that directly models P(tags | words), allowing rich overlapping features.

Advantages over HMM:

• No independence assumptions on observations
• Can include arbitrary features: word shape, prefixes, suffixes, capitalization, gazetteer membership
• Feature templates capture patterns like "current word is capitalized and previous tag is DET"

Training: Maximize conditional log-likelihood with gradient-based optimization. The partition function is computed efficiently with the forward algorithm.

Decoding: Viterbi algorithm (same complexity as HMM).

Neural POS Taggers

Modern approach: encode the sentence with a bidirectional model and classify each token.

Input tokens -> Embeddings -> BiLSTM / Transformer -> Linear -> Softmax per token

• Pretrained embeddings (or contextual encoders like BERT) provide rich input representations
• BiLSTM captures left and right context
• A CRF layer on top can model tag dependencies (see BiLSTM-CRF below)
• BERT-based taggers achieve >97.5% accuracy on Penn Treebank

Named Entity Recognition (NER)

NER identifies and classifies named entities in text: persons, organizations, locations, dates, etc.

BIO Tagging Scheme

Converts NER from a span identification problem to a token classification problem.

Barack  B-PER
Obama   I-PER
visited O
the     O
White   B-LOC
House   I-LOC

Variants:

• BIOES/BILOU: adds E (end) and S (single-token entity) tags for richer boundary information
• BIOES generally outperforms BIO for CRF-based models

Entity Types

Standard datasets define varying granularities:

BiLSTM-CRF

The dominant neural NER architecture before transformers.

Characters -> CharCNN/CharLSTM -> [char embedding]
Words -> Pretrained embedding -> [word embedding]
[char; word] -> BiLSTM -> CRF -> BIO tags

Why the CRF layer matters:

• Without CRF: each tag is predicted independently per token
• With CRF: the model learns transition scores (e.g., I-PER cannot follow B-LOC)
• CRF ensures globally consistent tag sequences
• Improves F1 by 1-2 points on standard benchmarks

Span-based NER

An alternative to sequence labeling that directly classifies text spans.

Approach:

1. Enumerate all spans up to a maximum length
2. Represent each span (e.g., concatenation of start, end, and span-width embeddings)
3. Classify each span as an entity type or "not an entity"

Advantages:

• Naturally handles nested entities ("Bank of [New York]_LOC")_ORG
• No BIO encoding needed
• Can share span representations with other tasks (coreference, relation extraction)

Challenge: O(n^2) candidate spans for a sequence of length n; pruning strategies needed.

Transformer-based NER

Fine-tuning BERT/RoBERTa for NER:

1. Tokenize with subword tokenizer
2. Encode with transformer
3. Take first subword token's representation for each word
4. Linear + CRF (or just linear + softmax) for BIO tag prediction

State-of-the-art on CoNLL-2003: ~94 F1 (ensemble approaches).

Chunking (Shallow Parsing)

Identifies non-recursive phrase constituents without building a full parse tree.

[NP The cat] [VP sat] [PP on] [NP the mat]

• Uses BIO tagging with chunk type labels (B-NP, I-NP, B-VP, etc.)
• Faster than full parsing; useful as a preprocessing step
• Often jointly trained with POS tagging in a multi-task setup

Semantic Role Labeling (SRL)

Identifies "who did what to whom, where, when, and how" by labeling predicate-argument structures.

[ARG0 The cat] [V sat] [ARGM-LOC on the mat]

Approaches:

• BIO sequence labeling: given a predicate, label each token with its role
• Span-based: classify candidate spans as arguments of a given predicate
• End-to-end: jointly identify predicates and their arguments
• Modern systems: BERT + span classification achieves ~87 F1 on OntoNotes

PropBank vs FrameNet

Coreference Resolution

Determines which mentions in a text refer to the same real-world entity.

[Barack Obama]_1 visited France. [He]_1 met [the president]_2.
[Macron]_2 welcomed [him]_1.

Mention detection: Find all noun phrases, pronouns, and named entities.

Approaches:

• Mention-pair: Binary classifier on all pairs of mentions; greedy clustering
• Mention-ranking: For each mention, score all antecedent candidates; pick the best
• End-to-end (Lee et al., 2017): Jointly detect mentions and resolve coreference
  • Span representations from BiLSTM/Transformer
  • Score each span as a mention, then score mention pairs
  • Coarse-to-fine pruning for efficiency
• Current SOTA: SpanBERT-based models achieve ~80 F1 on OntoNotes

Challenges:

• Long-distance references
• World knowledge required ("The company... its CEO")
• Gender bias in pronoun resolution

Evaluation Metrics

Key Takeaways

• Sequence labeling reduces structured prediction to per-token classification with BIO encoding
• CRF layers enforce global consistency of label sequences and improve neural taggers
• BiLSTM-CRF was the dominant architecture; transformer-based models now achieve state-of-the-art
• Span-based methods handle nested entities and bridge to relation extraction and coreference
• SRL and coreference resolution extend sequence labeling to deeper semantic analysis