JJ

Conditional Random Fields (CRF)

5 min read

A conditional random field (CRF) predicts related labels together. In sequence labelling, each input token receives a label, and neighbouring labels affect the choice.

For Named Entity Recognition (NER), a sentence can receive these labels:

TokenNewYorkshines
LabelB-LOCI-LOCO
MeaningStart of a locationContinuation of that locationOutside an entity

Other applications include POS tagging, phrase chunking, and word segmentation.

Features and Scores

A traditional CRF can use word identity, capitalisation, POS tags, and neighbouring words as features.

Two scores help explain a linear-chain CRF:

  • Emission score measures how well a label fits a token in its input context
  • Transition score measures how well two neighbouring labels fit together

The score for a complete label sequence combines its token scores and transition scores. Start and end scores can also affect the result.

The decoder selects the highest-scoring complete sequence. A label with the largest score at one token can lose when the whole sequence is considered.

Training and Decoding

During training, labelled sentences provide the target label sequences. The CRF learns feature weights to increase the conditional likelihood of those sequences. Regularisation limits overfitting. Common optimisation methods include L-BFGS and SGD.

During prediction, Viterbi decoding efficiently finds the best sequence in a linear-chain CRF. The probabilities are normalised over complete label sequences. See the original CRF paper.

Direction and context

A linear-chain CRF has undirected dependencies between adjacent labels and selects labels jointly. Its input features can use words on both sides. The left-to-right order of a decoding algorithm describes computation, rather than a restriction to past input context.

Combining a CRF with BiLSTM or BiGRU

The data path is:

tokens -> embeddings -> BiLSTM or BiGRU
       -> score for each possible tag at each token
       -> CRF -> complete label sequence

The bidirectional neural network learns input context from both directions. A linear layer converts its output into tag scores. The CRF adds label-transition information and chooses the final sequence. Stacked bidirectional layers add further processing before decoding. See the PyTorch BiLSTM-CRF tutorial.

Here is an intuitive way to see it:

Transformer encoder → understands token context
Linear layer → produces tag emission scores
CRF → models relationships between tags
Viterbi → selects the best tag sequence

The emission scores are essentially the probability or how likely these tags (POS tags or NER tags) represent each word. We can view the emissions as nodes:

Position 1 Position 2 Position 3
[B-LOC: 3] ───→ [B-LOC: 0] ───→ [B-LOC: 0]
[I-LOC: 0] ───→ [I-LOC: 2] ───→ [I-LOC: 0]
[O: 1] ───→ [O: 3] ───→ [O: 3]

Positions here represent each token in order. The CRF models tag relationships using a learned transition matrix. The transition matrix has previous possible tags from the Emission Scores as its rows and current possible tags as its columns. A very positive number signifies a very likely sequence while negative scores signifies a very unlikely sequence.

Code

1. Define a small decoding example

This explanatory example supplies scores directly. It demonstrates decoding with ordinary Python. A trained model would supply learned scores.

from itertools import product
 
tokens = ["New", "York", "shines"]
tags = ["B-LOC", "I-LOC", "O"]
 
emissions = [
    {"B-LOC": 3.0, "I-LOC": 0.0, "O": 1.0},
    {"B-LOC": 0.0, "I-LOC": 2.0, "O": 3.0},
    {"B-LOC": 0.0, "I-LOC": 0.0, "O": 3.0},
]
 
transitions = {
    ("B-LOC", "I-LOC"): 2.0,
    ("O", "I-LOC"): -4.0,
}
start_scores = {"B-LOC": 0.0, "I-LOC": -4.0, "O": 0.0}

The data structures:

  • emissions[t] is the score dictionary for token position t
  • emissions[1]["O"] is 3.0, the local score for labelling York as outside an entity
  • A transition key is (previous_tag, current_tag)
  • B-LOC followed by I-LOC receives a bonus of 2.0
  • O followed by I-LOC receives a penalty of 4.0

These values are scores. They can be negative and do not need to sum to one.

2. Score one complete label sequence

def sequence_score(path):
    score = start_scores[path[0]]
 
    for t, tag in enumerate(path):
        score += emissions[t][tag]
        if t > 0:
            pair = (path[t - 1], tag)
            score += transitions.get(pair, 0.0)
 
    return score

enumerate(path) gives both a token position and its candidate label. t > 0 checks whether a previous label exists. get(pair, 0.0) returns the transition score, or zero for an unspecified pair. This example uses zero for all end scores.

3. Compare local and complete-sequence decisions

local_path = [max(row, key=row.get) for row in emissions]
all_paths = product(tags, repeat=len(tokens))
best_path = max(all_paths, key=sequence_score)
 
print(local_path, sequence_score(local_path))
print(list(best_path), sequence_score(best_path))
print(list(zip(tokens, best_path)))
['B-LOC', 'O', 'O'] 9.0
['B-LOC', 'I-LOC', 'O'] 10.0
[('New', 'B-LOC'), ('York', 'I-LOC'), ('shines', 'O')]

max(row, key=row.get) selects each token's largest emission score independently. product(...) generates all 27 possible paths. The second max compares their complete-sequence scores.

Changing York from O to I-LOC loses one emission point and gains two transition points. The complete path therefore improves from 9.0 to 10.0.

Why practical models use Viterbi

Enumeration is clear for three tokens. Its number of paths grows exponentially with sequence length. Viterbi reuses the best partial-path scores to find the same optimum efficiently.

Graph View