CRF Training: Forward-Backward Algorithm, Gradients & L-BFGS Optimization

Conditional Random Fields are powerful models for sequence labeling, but their power comes with computational challenges. Unlike simple classifiers that make independent predictions for each token, CRFs model dependencies between labels across the entire sequence. Training a CRF means finding weights that maximize the probability of correct label sequences given their input features, while accounting for all possible alternative labelings.

This chapter explores how to train CRFs effectively. You'll learn the mathematical foundation of the log-likelihood objective, understand why the forward-backward algorithm is essential for efficient gradient computation, see how modern optimizers like L-BFGS converge faster than simple gradient descent, and discover how feature templates and regularization shape what a CRF can learn. By the end, you'll be able to train CRFs on real sequence labeling tasks and understand what's happening under the hood.

Training a CRF means finding feature weights that make correct label sequences probable. Given training data consisting of observation sequences $\mathbf{x}^{(i)}$ and their correct label sequences $\mathbf{y}^{(i)}$, we want to maximize the conditional probability of seeing these correct labels.

For a single training example with observation sequence $\mathbf{x}$ and label sequence $\mathbf{y}$, the CRF defines the conditional probability as:

where:

• $\mathbf{y} = (y_1, y_2, \ldots, y_T)$: the label sequence of length $T$
• $\mathbf{x}$: the observation sequence (features at each position)
• $f_k(y_{t-1}, y_t, \mathbf{x}, t)$: the $k$-th feature function, which examines the previous label $y_{t-1}$, current label $y_t$, the full observation sequence $\mathbf{x}$, and position $t$
• $\lambda_k$: the weight for feature $k$ (what we're learning)
• $Z(\mathbf{x})$: the partition function, which sums over all possible label sequences to normalize probabilities

The partition function deserves special attention:

where:

• $\mathbf{y}'$: ranges over all possible label sequences
• The sum includes $|L|^T$ sequences, where $|L|$ is the number of possible labels

This summation over exponentially many sequences is what makes CRF training computationally interesting. With 9 labels and 20 tokens, we'd have $9^{20} \approx 10^{19}$ possible sequences. Enumerating them directly is impossible.

Taking the log of the conditional probability gives us the log-likelihood for a single example:

The first term is the "score" of the correct sequence, which is easy to compute. The second term, $\log Z(\mathbf{x})$, requires summing over all possible sequences, which is the computational bottleneck.

For the full training set with $N$ examples, we sum the log-likelihoods:

where:

• $\mathcal{L}(\boldsymbol{\lambda})$: the total log-likelihood as a function of all weights
• $\boldsymbol{\lambda} = (\lambda_1, \lambda_2, \ldots, \lambda_K)$: the vector of all $K$ feature weights

Our goal is to find $\boldsymbol{\lambda}^* = \arg\max_{\boldsymbol{\lambda}} \mathcal{L}(\boldsymbol{\lambda})$.

Let's visualize what this objective looks like for a simple case:

The log-likelihood function for CRFs has a crucial property: it is concave. This means there are no local maxima to get trapped in. Any hill-climbing algorithm will find the global optimum given enough iterations. This mathematical guarantee makes CRF training well-behaved compared to neural network training, where the loss landscape is riddled with local minima and saddle points.

Computing the partition function $Z(\mathbf{x})$ by enumerating all sequences is intractable. The forward-backward algorithm exploits the sequential structure of the model to compute it in polynomial time.

The key insight is that the CRF score decomposes into local terms. At each position $t$, the contribution depends only on the label at $t$ and the label at $t-1$. This Markov property enables dynamic programming: we can build up the sum over all sequences incrementally, position by position.

The forward variable $\alpha_t(j)$ represents the sum of scores for all partial label sequences that end with label $j$ at position $t$:

where:

• $\mathbf{y}_{1:t}$: all possible label sequences from position 1 to $t$
• $y_t = j$: constrained to end with label $j$
• The summation accumulates scores of all paths reaching state $j$ at time $t$

We compute forward variables recursively:

Base case (t = 1):

where $y_0$ is a special start symbol.

Recursive case:

This recursion says: to get the total score of paths ending in $j$ at position $t$, sum over all possible previous labels $i$, multiplying the forward score at $t-1$ (all paths ending in $i$) by the transition score from $i$ to $j$.

The partition function is simply the sum of all forward variables at the final position:

The backward variable $\beta_t(i)$ represents the sum of scores for all partial sequences starting from position $t+1$, given that position $t$ has label $i$:

where $y_t = i$ is fixed.

Base case (t = T):

Recursive case:

The forward and backward variables together give us the probability of any label at any position. The posterior marginal probability of label $j$ at position $t$ is:

And the probability of a specific transition from $i$ to $j$ at positions $t-1$ to $t$:

where $M_t(i, j) = \exp\left(\sum_k \lambda_k f_k(i, j, \mathbf{x}, t)\right)$ is the transition score matrix at position $t$.

Let's implement the forward-backward algorithm:

Notice how the marginals sum to 1.0 at each position. This is because they represent the probability distribution over labels at that position, marginalized over all possible label sequences. The forward-backward algorithm computes these marginals in $O(T \cdot |L|^2)$ time, compared to $O(|L|^T)$ for brute-force enumeration.

The trellis visualization shows how forward and backward passes combine. Each node's color intensity represents its marginal probability. States with high marginal probability (darker blue) are more likely to be part of the optimal sequence.

To optimize the log-likelihood, we need its gradient with respect to each weight $\lambda_k$. The gradient has an elegant form that emerges from the structure of the CRF.

Taking the derivative of the log-likelihood for a single example:

where:

• The first term is the observed feature count: how often feature $k$ fires on the correct label sequence
• The second term is the expected feature count: the expected number of times feature $k$ would fire under the model's current probability distribution

This gradient has an intuitive interpretation:

• If a feature fires more often in the training data than the model expects, increase its weight (positive gradient)
• If a feature fires less often than expected, decrease its weight (negative gradient)
• When observed counts match expected counts, the gradient is zero (we've reached a stationary point)

The expected feature count requires summing over all positions and all label pairs, weighted by their posterior probabilities:

The forward-backward algorithm gives us exactly what we need: the pairwise marginals $P(y_{t-1} = i, y_t = j | \mathbf{x})$.

The gradient reveals which adjustments would improve the model. Positive gradients at the true labels mean the model should increase those scores. Negative gradients at incorrect labels mean those should be suppressed. The transition gradient shows similar patterns: transitions that occurred in the true sequence but have low model probability will have positive gradients.

Simple gradient descent can optimize the CRF objective, but it converges slowly. Each step moves in the direction of the gradient, but the step size is tricky to tune: too large and you overshoot, too small and you crawl toward the optimum.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) is a quasi-Newton method that approximates the curvature of the objective function. Instead of using only the gradient direction, it uses gradient history to estimate how the objective curves in different directions, enabling larger steps in flat directions and smaller steps in steep directions.

The key advantages of L-BFGS for CRF training are:

• Faster convergence: Uses curvature information to take better steps
• No learning rate tuning: Line search automatically finds good step sizes
• Memory efficient: Stores only the last $m$ gradient pairs (typically $m = 10$), not the full Hessian
• Robust: Works well on the convex CRF objective without careful hyperparameter tuning

The convergence plots show the characteristic behavior of L-BFGS on a convex problem. The log-likelihood rises steeply at first, then levels off as we approach the optimum. The gradient norm drops exponentially, indicating we're getting closer to a point where the gradient is zero.

CRF features are the heart of the model. Well-designed features capture the patterns that distinguish correct label sequences from incorrect ones. Feature templates define how to extract features from the input, and the CRF learns which features matter most.

Features for sequence labeling typically fall into several categories:

• Lexical features: The word itself, lowercase form, word shape (capitalization pattern)
• Contextual features: Surrounding words in a window
• Morphological features: Prefixes, suffixes, presence of digits or punctuation
• Part-of-speech features: POS tags from a tagger (if available)
• Transition features: Combinations of previous and current labels

The feature extractor captures patterns that are predictive of entity labels. Title-cased words are often names. Words ending in "-ia" might be locations. Words preceded by "at" might be organizations. The CRF learns which of these patterns are actually reliable predictors.

Real NER systems use extensive feature templates. The sklearn-crfsuite library provides a convenient way to train CRFs with custom features:

The learned feature weights reveal what the CRF considers important. High positive weights for "word.istitle=True" on B-PER indicate that title-cased words are strong signals for person names. The CRF automatically discovers these patterns from the training data.

Without regularization, CRF training can overfit to the training data. If a feature appears only once in training and perfectly predicts a label, the optimal weight is infinity. Regularization prevents extreme weights and improves generalization.

The regularized log-likelihood objective is:

where:

• $\mathcal{L}(\boldsymbol{\lambda})$: the original log-likelihood
• $C_1$: L1 regularization coefficient (larger = less regularization)
• $C_2$: L2 regularization coefficient (larger = less regularization)
• $|\lambda_k|$: absolute value of weight $k$ (L1 penalty)
• $\lambda_k^2$: squared weight (L2 penalty)

L1 and L2 regularization have different effects:

The regularization plots show clear trends. With strong regularization (small C), many features get zeroed out, creating a sparse model that uses only the most informative features. Maximum weight magnitudes also decrease, preventing the model from over-relying on any single feature.

Let's put everything together and train a CRF on a real NER dataset:

The trained CRF achieves reasonable performance even on this limited training set. The model correctly identifies many entities by learning patterns from the feature templates. Errors often occur at entity boundaries or with rare entity types that don't have enough training examples.

The transition matrix reveals that the CRF has learned BIO constraints. High weights appear for valid transitions like O→B-LOC (starting a location entity) and B-LOC→I-LOC (continuing a location). Low or negative weights appear for invalid transitions like O→I-LOC (continuation without a beginning).

CRF training has both strengths and limitations that shape when and how to use these models effectively.

The forward-backward algorithm makes CRF training tractable, but it still requires $O(T \cdot |L|^2)$ time per sequence. For tasks with many labels like fine-grained NER or semantic role labeling, this quadratic scaling becomes expensive. A sequence with 50 labels and 100 tokens requires computing 250,000 transition scores per training example. This cost compounds across thousands of training sentences and hundreds of optimization iterations.

Feature engineering remains both a strength and weakness. Hand-crafted features like word shapes, prefixes, and context windows capture linguistic knowledge effectively. But designing features requires domain expertise and extensive experimentation. Features that work well for English NER may perform poorly on German or Japanese. This manual effort contrasts sharply with neural approaches that learn representations automatically from raw text.

CRFs also struggle with long-range dependencies. The Markov assumption means each label depends only on the immediately preceding label. If a token's correct label depends on context five words away, the CRF must propagate that information through intervening transitions. In practice, this limits how much global context the model can exploit.

Despite these limitations, CRFs made sequence labeling practical before deep learning. Their contribution extends beyond the models themselves to the training paradigms they established. The idea of discriminatively training structured models, using dynamic programming for efficient inference, and designing features to capture domain knowledge influenced subsequent developments in neural NLP. Modern neural CRF layers, which place a CRF on top of BiLSTM or transformer encoders, combine learned representations with the structured prediction framework that CRFs pioneered.

For practitioners today, CRFs remain valuable in several scenarios: when training data is limited (hundreds rather than thousands of examples), when interpretability matters (examining feature weights reveals model behavior), when computational resources are constrained (CRFs train on CPUs in minutes), or as components in hybrid systems (neural encoders + CRF output layers).

Training Conditional Random Fields requires balancing computational efficiency with model expressiveness. The key ideas covered in this chapter are:

• Log-likelihood objective: CRF training maximizes the probability of correct label sequences. The objective is concave, guaranteeing a unique global optimum.

• Forward-backward algorithm: Dynamic programming computes the partition function and marginal probabilities in $O(T \cdot |L|^2)$ time, making training tractable despite the exponential number of possible label sequences.

• Gradient computation: The gradient equals observed feature counts minus expected feature counts. When these match, the model has converged.

• L-BFGS optimization: Quasi-Newton methods converge much faster than gradient descent by approximating curvature information. Most CRF implementations use L-BFGS by default.

• Feature templates: Hand-designed features capture patterns like word shapes, context windows, and morphological properties. Good features are essential for CRF performance.

• Regularization: L1 and L2 penalties prevent overfitting by discouraging extreme weights. L1 produces sparse models; L2 shrinks all weights toward zero.

CRFs established the foundation for structured prediction in NLP. While neural approaches now dominate, the principles of discriminative training, dynamic programming, and structured output remain central to modern sequence labeling systems.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about CRF training.