CRF Training › The Log-Likelihood Objective

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.

The key insight is that we are learning a discriminative model, not a generative one. We never model the probability of observing a particular sentence; we only model the probability of a label sequence given that sentence. This is the same philosophical stance taken by logistic regression versus naive Bayes: rather than modeling the joint distribution $P(\mathbf{x}, \mathbf{y})$, we model $P(\mathbf{y} | \mathbf{x})$ directly. For sequence labeling, this matters because modeling the sentence itself is hard (it requires a language model), while modeling labels conditioned on a sentence is much more tractable. The CRF inherits this advantage from its discriminative design.

Think of each training example as a contest between the correct label sequence and every competing alternative. The CRF assigns a score to each sequence using a weighted sum of features. Maximizing the log-likelihood of the correct sequences is equivalent to training the model to assign the correct sequence a score that is higher, on average, than the scores of all competing sequences. The partition function $Z(\mathbf{x})$ is what forces this competition: it aggregates the scores of all alternatives and normalizes them into a probability distribution. Making the correct sequence more probable necessarily means making alternative sequences less probable in relative terms.

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

$$P(\mathbf{y} | \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp\left(\sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, \mathbf{x}, t)\right)$$

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:

$$Z(\mathbf{x}) = \sum_{\mathbf{y}'} \exp\left(\sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y'_{t-1}, y'_t, \mathbf{x}, t)\right)$$

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. Even if each evaluation took a nanosecond, computing the partition function by brute force would take longer than the age of the universe. The forward-backward algorithm, covered in the next section, is how we escape this combinatorial trap.

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

$$\log P(\mathbf{y} | \mathbf{x}) = \sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, \mathbf{x}, t) - \log Z(\mathbf{x})$$

where:

• The first term is the score of the correct label sequence, a simple weighted sum of features that fire along the correct path
• The second term, $\log Z(\mathbf{x})$, is the log of the partition function and represents the log-sum-exp of scores over all possible sequences

The first term is cheap to compute: just walk along the correct label sequence and sum the feature weights at each step. The second term is the bottleneck. It requires, at least conceptually, evaluating the score of every possible label sequence and then computing a softmax-like normalization. This is where the forward-backward algorithm earns its keep.

Notice that the objective is a difference of two quantities. The first rewards the correct sequence by adding its score. The second penalizes all sequences by subtracting the log of their collective scored mass. Maximizing this difference means pushing the correct sequence score up while keeping the partition function from growing too large, which is exactly the behavior you want from a probabilistic classifier.

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

$$\mathcal{L}(\boldsymbol{\lambda}) = \sum_{i=1}^{N} \log P(\mathbf{y}^{(i)} | \mathbf{x}^{(i)})$$

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: