Semi-Markov CRF

Unlike token-level linear-chain CRFs that predict labels for each word, Semi-Markov CRFs operate directly on variable-length text segments. The model scores entire spans—such as 'Bank of America' or 'acute myeloid leukemia'—as atomic units rather than independently labeling each token. This eliminates the need for BIO tagging schemes and naturally captures multi-word entity boundaries without post-processing heuristics.

Semi-Markov CRFs incorporate segment duration distributions that explicitly model how long an entity span is likely to be. This prevents the model from predicting implausibly short or long entities:

• Organization names typically span 1-5 tokens
• Person names rarely exceed 4 tokens
• Medical terms can extend to 8+ tokens

The duration prior acts as a regularizer, penalizing segment lengths that deviate from expected distributions.

The architecture enables rich feature extraction across entire spans rather than individual tokens. Segment features can capture:

• Internal capitalization patterns ('New York Times')
• Gazetteer matches against knowledge bases
• Syntactic constituency of the full phrase
• Character-level morphology across the span
• Embedding aggregations (mean, max, attention-pooled)

These holistic features are impossible to compute in token-level CRF architectures.

Standard CRFs enforce the Markov property—the next state depends only on the current state. Semi-Markov CRFs relax this constraint by conditioning transitions on the entire segment history, including:

• The entity type of the previous segment
• The length of the previous segment
• The textual content of adjacent segments

This enables modeling of long-range dependencies between entities, such as consistent labeling of co-referring mentions across a document.

Inference uses a segment-level Viterbi algorithm that efficiently searches over all possible segmentations. The dynamic programming approach computes:

codeCopy
score(s, i, j) = segment_score(i, j) + transition(s_prev, s) + max_path(prev_state, i)

where segment_score(i, j) evaluates the span from position i to j with label s. This guarantees finding the globally optimal segmentation without greedy decoding or beam search approximations.

Extensions of Semi-Markov CRFs can model non-contiguous and nested entity structures that linear-chain models cannot represent:

• Nested entities: '[[University of [California]] [San Francisco]]'
• Discontinuous mentions: 'insulin-dependent and non-insulin-dependent diabetes'
• Overlapping spans in biomedical text

This is achieved through higher-order factors or by relaxing the non-overlapping segment constraint, making the model suitable for complex information extraction tasks.