Bidirectional RNNs › The BiLSTM-CRF Architecture in Detail

The BiLSTM-CRF model introduced by Lample et al. (2016) deserves extended treatment because it became such a dominant architecture for NER and is a canonical example of how bidirectionality and structured prediction complement each other.

After the BiLSTM produces per-token tag score vectors, the simplest output strategy is to apply a softmax at each position independently and take the argmax. This approach, called greedy decoding, produces the locally most probable tag at each position but ignores dependencies between adjacent tags.

Tag dependencies are real and important. In BIO tagging, the tag sequence "O, I-PER" is invalid: you cannot have an inside-entity tag without a preceding beginning-entity tag. "B-PER, I-ORG" is also invalid: you cannot be inside a different entity type than the one you began. These constraints cannot be captured by position-wise softmax, which sees each position in isolation.

The conditional random field (CRF) layer addresses this by modeling the joint probability of the entire tag sequence, rather than the product of per-position probabilities. It adds a matrix of transition scores $A$ where $A_{ij}$ is the score of transitioning from tag $i$ at position $t$ to tag $j$ at position $t+1$. The score of a full tag sequence $y_1, y_2, \ldots, y_T$ is:

$$s(x, y) = \sum_{t=1}^{T} P_{t, y_t} + \sum_{t=1}^{T-1} A_{y_t, y_{t+1}}$$

where:

• $P_{t, y_t}$ is the BiLSTM emission score for tag $y_t$ at position $t$
• $A_{y_t, y_{t+1}}$ is the transition score from tag $y_t$ to tag $y_{t+1}$

The model is trained to maximize the log-likelihood of the correct tag sequence. At inference time, the Viterbi algorithm finds the tag sequence with the highest score, efficiently searching over all possible sequences.

The transition matrix $A$ is initialized randomly and learned from data. For NER with BIO tags, the model quickly learns that transitions like "O to I-PER" should have very negative scores (essentially preventing that transition) while transitions like "B-PER to I-PER" should have high positive scores. Once learned, these constraints apply globally to every sentence.

The BiLSTM provides local evidence: what each position looks like in context. The CRF provides global structure: what tag sequences are coherent. The combination is more powerful than either component alone. The BiLSTM alone would make locally good but globally inconsistent decisions. The CRF alone, without the BiLSTM's rich contextual representations, would have only crude features to work with.

The Viterbi algorithm for CRF inference has time complexity $O(T \cdot K^2)$, where $T$ is the sequence length and $K$ is the number of tags. For typical NER tag sets (5 to 20 tags), this is very efficient: the quadratic dependence is on a small constant. For large tag sets (hundreds of tags, as in some semantic parsing applications), the CRF becomes computationally expensive and simpler approximations may be necessary.

Training is similarly efficient. The forward-backward algorithm computes the partition function needed for the CRF log-likelihood in $O(T \cdot K^2)$ time. For sequence lengths in the hundreds and tag sets in the tens, this adds negligible cost compared to the BiLSTM forward and backward passes.