Part-of-Speech Tagging and Conditional Random Fields

Is "book" a noun ("a book") or a verb ("book a ticket")? Part-of-speech (POS) tagging assigns each word its grammatical category — noun, verb, adjective, preposition and so on. It supports parsing, lemmatisation, information extraction and text-to-speech (pronunciation can depend on POS: "record" as noun vs verb). It is also the classic testbed for structured prediction, where outputs are interdependent. This lecture introduces the Conditional Random Field (CRF), one of the most important models for such problems.

Tag sets#

The Penn Treebank uses 45 fine-grained English tags (NN, NNS, VB, VBD, JJ, …). Universal Dependencies defines 17 universal POS tags (NOUN, VERB, ADJ, ADP, PRON, DET, …) used consistently across more than 100 languages — ideal for multilingual work.

Why context matters#

A tagger that assigns each word its most frequent tag already achieves about 90% accuracy on English news, but context resolves the rest: "can" after "I" is an auxiliary verb; after "the" it is a noun. Tags also constrain each other: a determiner is usually followed by an adjective or noun.

Generative approach: HMM taggers#

An HMM models tags as hidden states and words as emissions:

Decoding uses the Viterbi algorithm (see the HMM lecture). HMMs struggle to use rich, overlapping features (suffixes, capitalisation, neighbouring words) because they must model how words are generated.

Discriminative approach: linear-chain CRFs#

Lafferty, McCallum and Pereira (2001) proposed modelling the conditional distribution of the whole tag sequence directly:

• Emission scores $\psi$ can use any features of the entire input — the current word, its suffix, neighbouring words, capitalisation, gazetteers — combined linearly (classical CRF) or produced by a neural network (BiLSTM-CRF, BERT-CRF).
• Transition scores $A$ capture which tag sequences are plausible.
• The partition function $Z(\mathbf{x}) = \sum_{\mathbf{y}'}\exp(\text{score}(\mathbf{x}, \mathbf{y}'))$ sums over all $K^n$ tag sequences — computed efficiently in $O(nK^2)$ with the forward algorithm.

Because it normalises over whole sequences (globally), a CRF avoids the label bias problem of locally normalised models like maximum-entropy Markov models.

Training and decoding#

Training maximises the conditional log-likelihood:

Its gradient equals observed feature counts minus expected feature counts under the model — computed with the forward–backward algorithm.

Decoding finds $\arg\max_{\mathbf{y}}\text{score}(\mathbf{x}, \mathbf{y})$ with Viterbi in $O(nK^2)$.

import torch

def crf_log_partition(emissions, transitions):
    """emissions: (n, K) scores; transitions: (K, K) with transitions[i, j] = score(i -> j)."""
    alpha = emissions[0]
    for t in range(1, len(emissions)):
        alpha = torch.logsumexp(alpha[:, None] + transitions, dim=0) + emissions[t]
    return torch.logsumexp(alpha, dim=0)

def crf_score(emissions, transitions, tags):
    s = emissions[0, tags[0]]
    for t in range(1, len(tags)):
        s = s + transitions[tags[t - 1], tags[t]] + emissions[t, tags[t]]
    return s

def viterbi(emissions, transitions):
    score, back = emissions[0], []
    for t in range(1, len(emissions)):
        total = score[:, None] + transitions          # (K_prev, K_cur)
        score, idx = total.max(dim=0)
        score = score + emissions[t]; back.append(idx)
    best = [int(score.argmax())]
    for idx in reversed(back):
        best.append(int(idx[best[-1]]))
    return best[::-1]

n, K = 6, 4
em, tr = torch.randn(n, K), torch.randn(K, K)
gold = [0, 1, 1, 2, 3, 0]
nll = crf_log_partition(em, tr) - crf_score(em, tr, gold)     # negative log-likelihood
print("NLL:", nll.item(), " Viterbi path:", viterbi(em, tr))

A feature-based CRF tagger in practice#

# pip install sklearn-crfsuite
import sklearn_crfsuite

def word2features(sent, i):
    w = sent[i]
    f = {"lower": w.lower(), "suffix3": w[-3:], "suffix2": w[-2:], "is_title": w.istitle(),
         "is_digit": w.isdigit(), "shape": "".join("X" if c.isupper() else "x" if c.islower() else "d"
                                                  if c.isdigit() else c for c in w)[:6]}
    f["prev"] = sent[i - 1].lower() if i > 0 else "<BOS>"
    f["next"] = sent[i + 1].lower() if i < len(sent) - 1 else "<EOS>"
    return f

train_sents = [["I", "can", "book", "a", "flight"], ["The", "book", "is", "on", "the", "table"]]
train_tags = [["PRON", "AUX", "VERB", "DET", "NOUN"], ["DET", "NOUN", "AUX", "ADP", "DET", "NOUN"]]
X = [[word2features(s, i) for i in range(len(s))] for s in train_sents]
crf = sklearn_crfsuite.CRF(algorithm="lbfgs", c1=0.1, c2=0.1, max_iterations=100).fit(X, train_tags)
test = ["They", "book", "the", "room"]
print(crf.predict([[word2features(test, i) for i in range(len(test))]]))

(With a real treebank such as a Universal Dependencies corpus, such taggers reach well above 95% accuracy on English.)

CRFs in the neural era#

Modern taggers use a transformer encoder to produce emission scores. Adding a CRF layer on top still helps when label dependencies are strong and data is limited — e.g. NER with BIO constraints, where the CRF prevents invalid sequences like O → I-PER. With large pretrained encoders and plenty of data, the gain is often small, and a simple softmax per token is common.