Conditional Random Fields › The CRF Formulation
Language AI HandbookAll chapters Conditional Random Fields › The CRF FormulationOne section · Sections in this chapter3 / 13 ↓
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
We've established that HMMs struggle with overlapping features because their generative structure demands independence between observations. Now we need a mathematical framework that preserves the sequential structure of HMMs while escaping their independence constraints. The solution lies in a family of models called log-linear models, which CRFs extend to sequences.
This section builds the CRF formulation step by step. We'll start with log-linear models for single classification decisions, then extend them to sequences, and finally examine the feature functions that give CRFs their expressive power. By the end, you'll see how CRFs elegantly solve the problems we identified with HMMs.
Log-Linear Models for Classification
Before tackling sequences, let's understand how log-linear models work for a single classification decision. The core idea is beautifully simple: instead of modeling how observations are generated, we directly score how well each possible label fits the observed input.
Consider classifying a single word. We want to compute , the probability of label given input features . A log-linear model builds this probability in three steps:
- Extract features: Define functions that measure relevant properties of the input-label pair
- Compute a score: Sum the weighted features to get an overall "compatibility score" for each label
- Normalize to probabilities: Convert scores to probabilities using the exponential function and normalization
This yields the fundamental log-linear equation:
Let's unpack each component:
- : the -th feature function, which extracts a property of the input-output pair. These are the building blocks of the model, returning real numbers (often 0 or 1 for binary features).
- : the weight for feature , learned from training data. Positive weights encourage labels where the feature fires; negative weights discourage them.
- : the total score for assigning label to input . This is just a weighted sum of features.
- : the exponential function converts scores into positive values. This ensures we can interpret results as probabilities.
- : the partition function, which sums over all possible labels to normalize the distribution.
The exponential function serves two purposes. First, it maps any real-valued score to a positive number, which is necessary for probabilities. Second, it has a useful property: if one label's score is much higher than others, the exponential amplifies this difference, making the model confident. If scores are similar, probabilities are more uniform. This "soft-max" behavior emerges naturally from the exponential.
The partition function deserves special attention. It ensures that probabilities sum to 1 by computing the total "mass" across all possible labels. For single classification with a small label set, computing is trivial. But as we'll see, computing for sequences becomes the central computational challenge of CRFs.
Why is this formulation powerful? Because feature functions can capture any aspect of the input-output relationship. Unlike HMMs, where each observation depends only on its label, log-linear models can incorporate overlapping, interacting features without any independence assumptions.
import numpy as np
def simple_log_linear_classifier(x_features, y, weights, all_labels):
"""
Compute P(y|x) for a simple log-linear classifier.
Args:
x_features: dict of feature values for input x
y: the label we're computing probability for
weights: dict mapping (feature_name, label) to weight
all_labels: list of all possible labels
Returns:
probability P(y|x)
"""
def compute_score(label):
"""Compute sum of weighted features for a label."""
score = 0.0
for feat_name, feat_value in x_features.items():
key = (feat_name, label)
if key in weights:
score += weights[key] * feat_value
return score
# Compute scores for all labels
scores = {label: compute_score(label) for label in all_labels}
# Compute partition function (sum of exp scores)
max_score = max(scores.values()) # For numerical stability
Z = sum(np.exp(s - max_score) for s in scores.values())
# Compute probability
prob = np.exp(scores[y] - max_score) / Z
return prob, scores
# Example: classifying a word as NOUN, VERB, or ADJ
word_features = {
"word=running": 1.0,
"suffix=-ing": 1.0,
"prev_word=is": 1.0,
}
# Learned weights (simplified)
example_weights = {
("word=running", "VERB"): 2.0,
("word=running", "NOUN"): 0.5,
("suffix=-ing", "VERB"): 3.0,
("suffix=-ing", "NOUN"): 1.0,
("prev_word=is", "VERB"): 1.5,
("prev_word=is", "ADJ"): 0.5,
}
labels = ["NOUN", "VERB", "ADJ"]Log-Linear Classification Example: ======================================================= Features for word 'running': word=running: 1.0 suffix=-ing: 1.0 prev_word=is: 1.0 Probabilities for each label: ---------------------------------------- P(NOUN | x) = 0.0067 (score: 1.50) P(VERB | x) = 0.9909 (score: 6.50) P(ADJ | x) = 0.0025 (score: 0.50) Total probability: 1.0000
| Label | Raw Score | exp(Score) | Probability |
|---|---|---|---|
| NOUN | 2.0 | 7.4 | 0.001 |
| VERB | 6.5 | 665.1 | 0.996 |
| ADJ | 4.0 | 54.6 | 0.004 |
Notice what happened here. Three features fired for the word "running": the word itself, its suffix, and the preceding word. Each feature contributed to the scores for different labels, and the model combined them through weighted summation. The suffix -ing combined with prev_word=is provides strong evidence for VERB, and the learned weights reflect this intuition. The model assigned VERB a probability of over 99% by combining multiple overlapping features, something an HMM could never do.
Extending to Sequences: Linear-Chain CRFs
The log-linear model handles single classification decisions elegantly. But sequence labeling requires something more: we need to model entire sequences of labels, where each label might depend on its neighbors. How do we extend the log-linear framework to sequences while preserving its ability to use arbitrary features?
The answer is the linear-chain CRF. The key insight is to treat the entire label sequence as a single structured output, then score it using features that can look at adjacent labels and any part of the input. Instead of independently classifying each position, we score complete label sequences and find the one with the highest probability.
For a sequence of observations and labels , the linear-chain CRF defines:
This formula looks similar to the single-classification case, but with one difference: we now sum over positions in the sequence, and feature functions examine pairs of adjacent labels. Let's break it down:
- : We accumulate scores across all positions in the sequence
- : Each feature function now takes four arguments
The four arguments to feature functions are the heart of CRF expressiveness:
| Argument | What it provides | Example use |
|---|---|---|
| Previous label | Capture transition patterns (DET → NOUN) | |
| Current label | Capture emission patterns (word → label) | |
| Entire input sequence | Look at any word, not just current position | |
| Current position | Position-specific features (first word often capitalized) |
This design is deliberate. By including both and , features can model label-label dependencies like HMM transitions. By including the entire sequence rather than just , features can examine context: the previous word, the next word, or even words further away. The position enables features that behave differently at sequence boundaries.
The term "linear-chain" refers to the dependency structure: each label directly depends only on its immediate neighbor . This isn't a limitation of CRFs in general, just a practical choice that enables efficient inference. Higher-order CRFs exist but are exponentially more expensive.
The partition function for sequences presents a computational challenge:
This sum ranges over all possible label sequences . With labels and sequence length , there are possible sequences. For a modest vocabulary of 10 labels and a 20-word sentence, that's sequences, far too many to enumerate. Fortunately, the linear-chain structure enables efficient computation through dynamic programming, which we'll explore in the next section.
Feature Functions in Detail
We've seen that CRFs score sequences using weighted sums of feature functions. But what exactly are these features, and how do we design them? This is where CRFs truly shine: feature functions can capture virtually any pattern you can imagine, from simple word-label associations to complex contextual dependencies.
A feature function maps a (previous label, current label, observation sequence, position) tuple to a real value. Binary features return 1 when a pattern is present and 0 otherwise. The weight determines how much this pattern influences predictions.
Feature functions fall into two main categories, each serving a distinct purpose in the model.
State Features: Linking Observations to Labels
State features capture the relationship between observations and labels. They answer the question: "Given what I observe at this position, which label is most appropriate?"
Consider a feature that fires when the word "bank" appears with the label NOUN:
The notation denotes the indicator function, which returns 1 if the condition is true and 0 otherwise. The product of two indicators returns 1 only when both conditions hold. So this feature "fires" (returns 1) precisely when:
- The current word is "bank", AND
- The current label is NOUN
If the learned weight is positive, this feature increases the score for labeling "bank" as NOUN. If negative, it discourages that labeling. The training process learns these weights from data.
But state features aren't limited to the current word. Because feature functions receive the entire observation sequence , they can examine context:
- Previous word: Does "river" precede this word? (suggests location)
- Next word: Does "account" follow? (suggests financial meaning)
- Suffixes: Does the word end in "-ing"? (suggests verb)
- Capitalization: Is the word capitalized mid-sentence? (suggests proper noun)
This flexibility is what HMMs lack. In an HMM, the observation "bank" can only depend on its own label. In a CRF, the feature for "bank" can simultaneously consider the previous word, the next word, and any other contextual signal.
Transition Features: Modeling Label Dependencies
Transition features capture patterns in how labels follow each other. They answer: "Given the previous label, which labels are likely to come next?"
Consider a feature for the common grammatical pattern where nouns follow determiners:
This feature fires when a NOUN follows a DET, capturing patterns like "the cat" or "a dog." A positive weight encourages this transition; a negative weight would discourage it.
Transition features serve a similar role to HMM transition probabilities, but with an important difference: they can also incorporate observations. A feature like "NOUN follows DET when the current word is capitalized" combines transition and observation information in ways HMMs cannot express.
def define_feature_templates():
"""
Define feature templates for a CRF tagger.
Templates describe patterns; actual features are instantiated
by applying templates to training data.
"""
templates = [
# State features (depend on current label and observations)
("current_word", lambda x, t, y_prev, y_cur: (x[t], y_cur)),
("word_lower", lambda x, t, y_prev, y_cur: (x[t].lower(), y_cur)),
(
"is_capitalized",
lambda x, t, y_prev, y_cur: (x[t][0].isupper(), y_cur),
),
(
"suffix_2",
lambda x, t, y_prev, y_cur: (
x[t][-2:] if len(x[t]) >= 2 else x[t],
y_cur,
),
),
(
"suffix_3",
lambda x, t, y_prev, y_cur: (
x[t][-3:] if len(x[t]) >= 3 else x[t],
y_cur,
),
),
(
"prefix_2",
lambda x, t, y_prev, y_cur: (
x[t][:2] if len(x[t]) >= 2 else x[t],
y_cur,
),
),
# Context features (depend on surrounding words)
(
"prev_word",
lambda x, t, y_prev, y_cur: (
x[t - 1] if t > 0 else "<START>",
y_cur,
),
),
(
"next_word",
lambda x, t, y_prev, y_cur: (
x[t + 1] if t < len(x) - 1 else "<END>",
y_cur,
),
),
(
"prev_word_suffix",
lambda x, t, y_prev, y_cur: (
x[t - 1][-2:] if t > 0 and len(x[t - 1]) >= 2 else "<START>",
y_cur,
),
),
# Transition features (depend on previous label)
("transition", lambda x, t, y_prev, y_cur: (y_prev, y_cur)),
(
"transition_word",
lambda x, t, y_prev, y_cur: (y_prev, y_cur, x[t].lower()),
),
]
return templates
def extract_features(words, position, prev_label, current_label, templates):
"""
Extract features for a specific position in the sequence.
Returns a dict of feature names to values (all 1.0 for binary features).
"""
features = {}
for template_name, template_func in templates:
try:
feature_value = template_func(
words, position, prev_label, current_label
)
feature_key = f"{template_name}={feature_value}"
features[feature_key] = 1.0
except (IndexError, TypeError):
pass
return features
# Demonstrate feature extraction
sample_sentence = ["The", "quick", "fox", "jumps"]
templates = define_feature_templates()
# Extract features for position 2 ("fox") with prev_label=ADJ, current_label=NOUN
features_pos2 = extract_features(sample_sentence, 2, "ADJ", "NOUN", templates)Feature Extraction Example:
============================================================
Sentence: ['The', 'quick', 'fox', 'jumps']
Position: 2 (word='fox')
Previous label: ADJ, Current label: NOUN
Extracted Features:
------------------------------------------------------------
current_word=('fox', 'NOUN')
is_capitalized=(False, 'NOUN')
next_word=('jumps', 'NOUN')
prefix_2=('fo', 'NOUN')
prev_word=('quick', 'NOUN')
prev_word_suffix=('ck', 'NOUN')
suffix_2=('ox', 'NOUN')
suffix_3=('fox', 'NOUN')
transition=('ADJ', 'NOUN')
transition_word=('ADJ', 'NOUN', 'fox')
word_lower=('fox', 'NOUN')Look at the variety of information captured by these features. For a single word "fox" at position 2, we extract:
- Word identity: The word itself and its lowercase form
- Morphological properties: Two-character and three-character suffixes and prefixes
- Capitalization: Whether the word starts with an uppercase letter
- Context: The previous word ("quick") and next word ("jumps")
- Label transition: The pattern of moving from ADJ to NOUN
Each of these features will have a learned weight. During training, the model discovers which features are predictive: perhaps words ending in "-ly" strongly indicate adverbs, or capitalized words following "the" often indicate proper nouns. The power lies in combining many weak signals into a strong prediction.
Connecting CRFs to HMMs
Having built up the CRF formulation, it's illuminating to see how it relates to HMMs. This comparison reveals that HMMs are a special case of CRFs with a restricted feature set.
An HMM has two types of parameters:
- Transition probabilities : How likely is each label given the previous label?
- Emission probabilities : How likely is each observation given its label?
We can express these as CRF features:
def hmm_as_crf_features(words, position, prev_label, current_label):
"""
Features that make a CRF equivalent to an HMM.
HMM has two types of parameters:
- Transition: P(current_label | prev_label)
- Emission: P(word | current_label)
These correspond to two feature templates.
"""
features = {}
# Transition feature: fires for each (prev_label, current_label) pair
# Equivalent to log P(current_label | prev_label) in HMM
features[f"transition_{prev_label}_{current_label}"] = 1.0
# Emission feature: fires for each (word, current_label) pair
# Equivalent to log P(word | current_label) in HMM
word = words[position]
features[f"emission_{word}_{current_label}"] = 1.0
return features
# Show HMM-equivalent features
hmm_features = hmm_as_crf_features(sample_sentence, 2, "ADJ", "NOUN")HMM as CRF (Minimal Feature Set): ================================================== Word at position 2: 'fox' Previous label: ADJ, Current label: NOUN HMM-equivalent features: emission_fox_NOUN transition_ADJ_NOUN In an HMM: - transition_ADJ_NOUN weight ≈ log P(NOUN | ADJ) - emission_fox_NOUN weight ≈ log P(fox | NOUN) CRFs generalize by allowing many more features!
The correspondence is precise: if we set the CRF weight for transition_ADJ_NOUN to and the weight for emission_fox_NOUN to , the CRF assigns the same relative probabilities to label sequences as the HMM.
CRFs can reproduce the HMM feature set and add arbitrary input-dependent features. While an HMM is limited to these two feature types, a CRF can add:
- Features that examine the previous word as well as the previous label
- Features that look at the next word
- Features based on word suffixes, prefixes, or character patterns
- Features that combine multiple signals (e.g., "capitalized word after a determiner")
- Features that span multiple positions
The HMM is a CRF with its hands tied. By removing the generative constraints, CRFs support a broader set of discriminative features for sequences. This is why CRFs consistently outperform HMMs on sequence labeling tasks: they can use the same information as HMMs, plus arbitrarily more.