Conditional Random Fields › Computing the Partition Function

Fortunately, the linear-chain structure enables efficient computation via dynamic programming. The forward algorithm computes $Z(\mathbf{x})$ in $O(nK^2)$ time, similar to the forward algorithm for HMMs.

The key idea is to define a forward variable $\alpha_t(y)$ that accumulates scores for all partial label sequences ending in label $y$ at position $t$:

$$\alpha_t(y) = \sum_{\mathbf{y}_{1:t-1}} \exp\left( \sum_{t'=1}^{t} \sum_k \lambda_k f_k(y_{t'-1}, y_{t'}, \mathbf{x}, t') \right) \quad \text{where } y_t = y$$

where:

• $\alpha_t(y)$: the forward variable at position $t$ for label $y$
• $\mathbf{y}_{1:t-1}$: all possible label assignments for positions 1 through $t-1$
• The sum aggregates scores over all ways to reach label $y$ at position $t$
• The constraint $y_t = y$ fixes the label at position $t$

Intuitively, $\alpha_t(y)$ represents the total "mass" of all paths that end in label $y$ at position $t$. The useful property is that we can compute $\alpha_t(y)$ recursively from the previous position:

$$\alpha_t(y) = \sum_{y'} \alpha_{t-1}(y') \cdot \exp\left( \sum_k \lambda_k f_k(y', y, \mathbf{x}, t) \right)$$

where:

• $y'$: iterates over all possible labels at position $t-1$
• $\alpha_{t-1}(y')$: the forward variable from the previous position
• $\exp\left( \sum_k \lambda_k f_k(y', y, \mathbf{x}, t) \right)$: the score for transitioning from $y'$ to $y$ at position $t$

This recurrence says: to compute the total score of paths ending in $y$ at position $t$, sum over all possible previous labels $y'$, multiplying the score of reaching $y'$ by the score of the transition from $y'$ to $y$.

Once we've computed forward variables for all positions, the partition function is simply the sum over all labels at the final position:

$$Z(\mathbf{x}) = \sum_y \alpha_n(y)$$

where the sum is over all possible labels $y$ at the final position $n$. This works because every complete label sequence must end with some label at position $n$.

The forward algorithm exploits the linear-chain structure: at each position, we only need to consider transitions from labels at the previous position. This reduces the exponential enumeration to polynomial computation.

Throughout CRF computations, we work in log space. Multiplying many probabilities (or exponentials of scores) quickly leads to numerical underflow. By using the log-sum-exp operation, we maintain numerical stability:

$$\log\left( \sum_i e^{x_i} \right) = \max_i(x_i) + \log\left( \sum_i e^{x_i - \max_i(x_i)} \right)$$

where:

• $x_i$: the $i$-th value we want to sum (in our case, log-scores for different label sequences)
• $\max_i(x_i)$: the maximum value among all $x_i$
• $e^{x_i - \max_i(x_i)}$: the exponentiated value after subtracting the maximum

This identity is mathematically exact but numerically superior. The trick works because subtracting the maximum ensures that at least one term in the sum equals $e^0 = 1$, while all other terms are less than 1. This prevents both overflow (from exponentiating large positive numbers) and underflow (from exponentiating large negative numbers).