Sequence Labeling via Semi-Markov Segment Modeling

77 concepts65 papers1 proposal

Traditional sequence labeling models, such as Hidden Markov Models (HMMs) or standard Conditional Random Fields (CRFs), operate on a token-by-token basis. They treat a sentence as a series of individual "beads on a string," assigning a label to each word or character in isolation. However, as Christian Scheible et al. argue, these models are often ill-suited for tasks like quotation detection because they cannot "see" the entire span at once. By forcing a model to make local decisions, we often lose the global context that defines a multi-word entity or a complex phrase.

Segment-level sequence labeling shifts the unit of analysis from the individual token to the variable-length segment. Instead of asking "What is the label of this word?", the model asks "Where does this segment start and end, and what is its collective identity?"

The Semi-Markov Intuition

The core mechanism behind this shift is the semi-Markov process. In a standard Markov model, the state at time $t$ depends only on the state at time $t-1$. In a semi-Markov model, a state can persist for a variable duration. As Alex Smola explains, these models assign labels to contiguous sequences of observations rather than individual points.

This allows the model to treat segments as unified, atomic entities. Wei Chu et al. note that this mechanism captures dependencies and properties inherent to entire structural blocks—such as internal consistency and length distributions—that token-level models simply cannot represent.

Why Segmenting Works Better

Treating sequences as segments provides three primary advantages over token-level tagging:

  1. Global Feature Extraction: Token-level models are restricted to local features. By contrast, segment-based models can incorporate features that describe the entire span. Bishan Yang et al. demonstrate that this allows for the inclusion of span-level properties, such as syntactic parse tree alignment, which are mathematically impossible to represent in traditional architectures.
  2. Joint Segmentation and Classification: Traditional pipelines often separate tokenization from labeling, leading to error propagation. Apostolos Kemos et al. show that semi-Markov CRFs (semi-CRFs) can simultaneously identify boundaries and assign tags, ensuring that the most likely segmentation and labeling are found together.
  3. Duration Modeling: Different types of entities have different expected lengths. Xiaolei Lu et al. explicitly model this "duration" using probability distributions, allowing the model to favor segments that match the typical length of a keyphrase or entity.

From Speech to Structured Data

The utility of segment-level modeling spans diverse domains. In speech recognition, Owen Kimball et al. pioneered segment-based scoring to move away from the rigid constraints of HMMs, allowing systems to compare different segmentation hypotheses fairly. Similarly, in music processing, Yujia Yan et al. used neural semi-CRFs to predict entire note intervals directly, eliminating the need for heuristic post-processing to group disjoint frame predictions.

In natural language tasks, the authors of several papers have found that semi-Markov structures are essential for capturing multi-word units. Xiao Li applied semi-CRFs to understand the semantic structure of noun phrase queries, where multi-word phrases function as single constraints. For named entity recognition (NER), Colin Cherry et al. showed that segment-based approaches allow models to extract features from the entire candidate entity span, which is particularly effective for the informal and chaotic text found on platforms like Twitter.

Integrating External Knowledge

Segment-level architectures also provide a more natural interface for external knowledge. Tianyu Liu 0004 et al. found that operating on text spans allows for a direct mapping between candidate segments and dictionary entries (gazetteers). This makes it easier to integrate structured lexicons, as the model can evaluate whether a multi-token span in the text matches a complete phrase in a database.

By relaxing the Markovian assumption and embracing the segment as the fundamental unit, researchers have created models that are more structurally realistic and better equipped to handle the complexities of natural sequences, whether they are found in human speech, clinical notes, or genomic data.

Key Foundational Work

Semi-Markov Conditional Random Fields for Information Extraction (2004) — contributed 2 concept elements to this direction.
Protein secondary structure prediction using sigmoid belief networks to parameterize segmental semi-Markov models (2004) — contributed 1 concept elements to this direction.
A Phrase-Based HMM Approach to Document/Abstract Alignment (2004) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 66 papers
  2. Version 1 · 2026-10-04 · 57 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_segment_level_sequence_labeling_e6ba0285,
  title = {segment-level sequence labeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/segment-level-sequence-labeling/rdr_e6ba0285fe7844d0b9d1efecd1ddcd56},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_segment_level_sequence_labeling_e6ba0285_v2,
  title = {segment-level sequence labeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/segment-level-sequence-labeling/rdr_e6ba0285fe7844d0b9d1efecd1ddcd56/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake