CRF Training › L-BFGS Optimization
Language AI HandbookAll chapters CRF Training › L-BFGS OptimizationOne section · Sections in this chapter5 / 11 ↓
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
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.
L-BFGS is a quasi-Newton optimization algorithm that uses a limited memory approximation to the inverse Hessian matrix. It converges much faster than gradient descent for convex problems like CRF training, typically requiring 50-200 iterations instead of thousands.
The Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm was independently discovered by four researchers in 1970 and has since become one of the most widely used optimization algorithms in scientific computing. The original BFGS method maintains a dense approximation to the inverse Hessian matrix, which requires memory for parameters. This is impractical for problems with thousands or millions of parameters. Jorge Nocedal addressed this in 1980 by proposing the L-BFGS variant, which stores only the last pairs of gradient differences rather than the full matrix. By using a two-loop recursion discovered later, L-BFGS can apply the implicit inverse Hessian approximation using only these stored vectors, reducing memory from to . For CRF training, where features can number in the millions but is typically just 5 to 20, this is a massive practical improvement. L-BFGS became the de facto optimizer for CRF training and maximum entropy models throughout the 2000s.
To understand why L-BFGS converges faster than gradient descent, consider what the Hessian tells you. The Hessian matrix of second derivatives describes the curvature of the objective in every direction. Directions with high curvature (large second derivatives) require small steps to avoid overshooting; directions with low curvature (small second derivatives) can tolerate large steps. Gradient descent uses the same step size (or a line-searched step size) in all directions, which means it is either too aggressive in high-curvature directions or too conservative in low-curvature ones. By approximating the inverse Hessian, L-BFGS can scale each direction appropriately, taking large steps in flat directions and small steps in steep ones. This is the key reason it converges in far fewer iterations.
For CRF training specifically, the curvature of the log-likelihood objective depends on the feature correlations in the training data. Features that are highly correlated with each other create directions of low curvature that gradient descent handles poorly. L-BFGS handles this naturally by building up an estimate of these correlations over iterations.
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 gradient pairs (typically ), not the full Hessian
- Stable: Works well on the convex CRF objective without careful hyperparameter tuning
def crf_objective(params, X_features, y_sequences, num_labels):
"""
Compute negative log-likelihood and gradient for CRF.
Args:
params: Flattened parameter vector (emissions + transitions)
X_features: List of feature matrices, one per sequence
y_sequences: List of label sequences
num_labels: Number of possible labels
Returns:
neg_ll: Negative log-likelihood (to minimize)
neg_grad: Negative gradient
"""
# Unpack parameters
# For simplicity, we use emission weights per label and transition matrix
emission_weights = params[:num_labels]
transition_matrix = params[num_labels:].reshape(num_labels, num_labels)
total_ll = 0.0
total_emission_grad = np.zeros(num_labels)
total_transition_grad = np.zeros((num_labels, num_labels))
for X, y in zip(X_features, y_sequences):
T = len(y)
# Compute emission potentials
log_potentials = np.outer(np.ones(T), emission_weights) + X
# Forward-backward
log_alpha, log_beta, log_Z = forward_backward(
log_potentials, transition_matrix
)
# Log-likelihood contribution
sequence_score = sum(log_potentials[t, y[t]] for t in range(T))
sequence_score += sum(
transition_matrix[y[t - 1], y[t]] for t in range(1, T)
)
total_ll += sequence_score - log_Z
# Gradient contribution
emission_grad, transition_grad = compute_gradient(
log_potentials, transition_matrix, y, log_alpha, log_beta, log_Z
)
total_emission_grad += emission_grad.sum(axis=0)
total_transition_grad += transition_grad
# Return negative (for minimization)
neg_grad = np.concatenate(
[-total_emission_grad, -total_transition_grad.flatten()]
)
return -total_ll, neg_grad# Generate synthetic training data
np.random.seed(42)
num_sequences = 50
seq_length = 10
num_labels = 3
# Create synthetic sequences with some structure
X_features = []
y_sequences = []
for _ in range(num_sequences):
# Random features
X = np.random.randn(seq_length, num_labels) * 0.5
# Generate labels with realistic BIO patterns
y = []
in_entity = False
for t in range(seq_length):
if in_entity:
if np.random.random() < 0.7: # Continue entity
y.append(2) # I-PER
else: # End entity
y.append(0) # O
in_entity = False
else:
if np.random.random() < 0.2: # Start entity
y.append(1) # B-PER
in_entity = True
else:
y.append(0) # O
X_features.append(X)
y_sequences.append(y)
# Initial parameters
init_params = np.zeros(num_labels + num_labels * num_labels)
# Track optimization progress
history = {"ll": [], "grad_norm": []}
def callback(params):
ll, grad = crf_objective(params, X_features, y_sequences, num_labels)
history["ll"].append(-ll) # Convert back to positive LL
history["grad_norm"].append(np.linalg.norm(grad))from scipy.optimize import minimize
# Run L-BFGS optimization
result = minimize(
crf_objective,
init_params,
args=(X_features, y_sequences, num_labels),
method="L-BFGS-B",
jac=True, # Function returns both value and gradient
callback=callback,
options={"maxiter": 100, "disp": False},
)
optimal_params = result.xL-BFGS Optimization Results ================================================== Number of sequences: 50 Sequence length: 10 Number of labels: 3 Optimization converged: True Number of iterations: 50 Number of function evaluations: 61 Final log-likelihood: -295.0034 Final gradient norm: 0.007801 Learned emission weights: O: +7.4421 B-PER: +5.7706 I-PER: -13.2127 Learned transition matrix: From/To O B-PER I-PER O +2.9210 +2.4835 -26.2274 B-PER +2.2342 -13.0289 +23.8245 I-PER +2.1959 -17.7993 +23.3965
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.
Notice that the gradient norm does not decrease monotonically at each step. L-BFGS performs a line search along the descent direction computed from the approximate inverse Hessian, and this line search may occasionally accept a step that temporarily increases the gradient norm. This is normal and expected: the optimizer is exploring the curvature structure of the objective in order to build a better approximation. Over a window of several iterations, the trend should be consistently downward.
In practice, L-BFGS convergence on a well-conditioned CRF typically takes 50 to 200 iterations. The exact count depends on the number of training examples, the number of features, and the regularization strength. Stronger regularization generally leads to faster convergence because it smooths the objective and reduces the condition number of the Hessian. If your CRF training is taking thousands of iterations to converge, suspect either a very large feature set with many correlated features, a very small regularization coefficient, or numerical issues in the gradient computation.