Many labeling tasks cut a sequence into labeled segments: names in a sentence, keyphrases in an abstract, phones in an utterance. The model has to judge how long each segment should be. Two long-standing modeling habits get this judgment wrong in opposite ways. Hidden Markov models (HMMs) score length implicitly through a "stay in this state" probability. That makes every length geometrically distributed, so a length of one is always the most likely. Semi-Markov models score whole segments instead, and so can express any length preference. The cost is that they must enumerate every possible segment length, so in practice they impose a hard maximum length and never see anything longer.
We propose one duration score that behaves like a flexible semi-Markov score for common lengths and like an HMM's geometric decay for rare, long ones, with a smooth, learned hand-off between the two. The tool for the hand-off comes from Gaussian processes (GPs), which are priors over functions defined by a covariance function, or kernel. A known flaw of standard "stationary" kernels, whose correlation depends only on the distance between inputs, is that far from the data their predictions drift back to the prior mean. We argue that for duration scores this drift is useful, provided the prior mean is a geometric tail. Long segments then inherit a well-behaved, normalizable decay instead of an arbitrary value. The span cap can be removed entirely: segments beyond a moderate length are handled by an HMM-style self-loop at almost no extra cost.
Core Claim
The duration log-score for a segment of length $d$ in context $c$ is
$$f(d, c) = a(c) - \lambda(c)\, d + g(d),$$
where $a(c)$ and $\lambda(c) > 0$ come from a small network over the segment's context (for example sentence-level speaking rate or genre features). The rate $\lambda$ is kept positive with a softplus, and $g$ is a residual with a zero-mean stationary GP prior over length. Because a stationary kernel's correlation vanishes at long range, $g(d) \to 0$ as $d$ moves beyond the observed lengths. The score therefore reverts to a linear-in-$d$ penalty, which is exactly a geometric tail with context-dependent rate. This has three consequences.
First, the sum over all lengths of $\exp f(d,c)$ is finite whenever $g$ is bounded. Unbounded-length inference is therefore well defined.
Second, beyond a threshold $L_0$ the score is effectively linear. Those segments can be decoded exactly with a single self-loop "continuation" state per label. The trellis cost stays at roughly $O(T L_0 |Y|^2)$, where $T$ is the sequence length and $|Y|$ the number of labels, rather than growing with the longest possible segment.
Third, rare lengths borrow strength from their neighbors through the kernel instead of each getting an independent parameter.
The contrarian part of the claim concerns the improper, non-reverting kernels of Stationarity without mean reversion in improper Gaussian processes. That paper builds "walk" kernels whose predictions hold near the nearest observation instead of reverting to the mean. This is the right fix for forecasting prices. For duration log-scores it is the wrong fix: holding the last observed value makes the tail flat, and a flat tail makes the normalizer diverge unless a cap is reimposed. We will test this prediction directly.
Relation to Prior Work
The closest work is Duration modeling with semi-Markov Conditional Random Fields for keyphrase extraction. It puts Gamma or Gaussian length distributions into semi-Markov conditional random field (CRF) segment scores and found that the right family changed by domain: Gamma for engineering, history and economics, Gaussian for psychology. That finding motivates a family-free body. Our model differs in three ways: the body is nonparametric and context-dependent, the tail is tied to it, and there is no cap or syntactic pruning.
Semi-Markov CRFs themselves supply the method. Semi-Markov Conditional Random Fields for Information Extraction introduced segment-level scoring with length features. Hybrid semi-Markov CRF for Neural Sequence Labeling combined token-level and segment-level scoring and showed the segment view wins on entities of six or more words, with 76.55 versus 72.73 F1. It encodes length only through learned position embeddings within a fixed maximum. Filtered Semi-Markov CRF attacks the same cost problem from another direction, pruning null spans with a local filter. It pays for this with unrecoverable false negatives. Our tail state is a cap-free alternative that prunes nothing.
On the speech side, Phone Duration Modeling for LVCSR Using Neural Networks scored discrete length bins with a network and fell back to a geometric tail beyond a threshold $D$, applied post hoc in lattice rescoring. It is the nearest analogue to our body-plus-tail structure. The differences are that ours is continuous across the threshold, smooth across neighboring lengths, and trained inside the global model. That paper also reports diminishing returns against strong sequence-trained acoustic models, which constrains our expectations. Hidden semi-Markov model based speech synthesis supplies the argument that duration should be trained jointly rather than bolted on.
Gaussian Process Kernels for Pattern Discovery and Extrapolation supplies spectral mixture kernels. These are built from a mixture of frequencies and are one candidate for $g$ when length distributions are multimodal.
Research Program
We will build the model in four steps.
Representing the residual. The residual $g$ is represented by its values $u$ at lengths $1,\dots,L_0$. The GP prior acts as a penalty $u^\top K^{-1} u$ added to the CRF's conditional log-likelihood, where $K$ is the kernel matrix. Kernel hyperparameters are chosen on validation data, not by marginal likelihood. A Laplace approximation around the learned $u$ gives uncertainty about the duration score at rare lengths.
Continuity at $L_0$. Past $L_0$ we set $g$ to zero. The kernel's length scale controls how smoothly $g$ approaches zero before $L_0$, so there is no jump at the threshold of the kind a hard bin fallback produces.
Emissions for tail spans. Segments longer than $L_0$ enter the continuation state. Their content score is the hybrid model's token-level emission sum plus boundary features, so no span representation beyond $L_0$ is ever materialized. The encoder is a pretrained Transformer shared with all baselines.
Analysis. We will characterize how the choice of prior mean and kernel family (squared exponential, spectral mixture, walk kernel) determines tail behavior and normalizability. We will also measure the sensitivity of accuracy and speed to $L_0$.
Baselines
The naive reference is a token-level CRF on the shared encoder. It has no explicit duration model, only label-to-label transitions, and so behaves like the HMM's geometric duration at the label level.
The strongest existing competitor is the hybrid semi-Markov CRF of Hybrid semi-Markov CRF for Neural Sequence Labeling. It is the most direct test of whether learned length embeddings already suffice. The paper reports 91.38 F1 on CoNLL 2003 and 76.55 F1 on entities of six or more words. We will rerun it on our shared encoder with the same data, the same hyperparameter search budget and its best maximum span length, rather than compare to the published number alone.
The filtered semi-Markov CRF of Filtered Semi-Markov CRF is the speed competitor on OntoNotes 5.0. It reports up to 137× faster decoding than a standard semi-Markov CRF. The file has no reported F1 value for OntoNotes 5.0 on Lacuna, so we will measure it ourselves.
Three duration-model baselines go into the same semi-Markov CRF:
- a fixed Gamma duration in the style of Duration modeling with semi-Markov Conditional Random Fields for keyphrase extraction;
- a context-conditioned Gamma, whose shape and rate are produced by the same context network we use;
- discrete per-length bins with a geometric fallback beyond $D$, following Phone Duration Modeling for LVCSR Using Neural Networks.
Ablations isolate the key ingredient, the reverting-to-geometric prior mean. The first uses a zero-mean stationary GP with no linear term, which requires a cap to normalize. The second swaps in the Smooth Walk kernel from the improper-GP paper. The third keeps the geometric tail but sets $g$ to zero, which is essentially an HMM duration with a context-dependent rate.
Beating the hybrid model means higher F1 on the long-entity bucket and on the length-shift split described below, with overall F1 no worse than a 0.2-point tolerance. Beating the filtered model means comparable decoding speed with fewer missed spans.
Why not just…?
Why not just use an autoregressive sequence-to-sequence tagger? Exploring Sequence-to-Sequence Learning in Aspect Term Extraction shows such decoders learn segment structure without explicit transitions. However, they give no exact global decoding, no validity guarantee, and no explicit handle on length. Length extrapolation is the weakness we target, and we will include a sequence-to-sequence tagger on the length-shift split to see whether that weakness is real.
Why not just use a context-conditioned Gamma? This is the real threat. A Gamma distribution's log-density already has a linear tail, so it gets finite normalization and cap-free inference for free. The GP body earns its place only if lengths are multimodal or poorly fit by one shape, as the domain-dependence finding of the keyphrase paper hints. If the conditioned Gamma matches us across the evaluations, we will report that the tail construction, not the GP, is the contribution. We will then recommend the Gamma-plus-continuation-state model.
Why not just rely on position embeddings under a span cap? Embeddings have no values for lengths never seen in training and nothing above the cap. The length-shift split measures exactly this. The hybrid baseline is run at its best cap, so it gets a fair chance.
Why not just rescore lattices post hoc? Post-hoc duration creates the training/decoding inconsistency documented by Hidden semi-Markov model based speech synthesis. Our speech experiment compares the two directly on identical lattices.
Proposed Experiments
Named entities. We use CoNLL 2003 and OntoNotes 5.0, reporting span F1 overall and by entity-length bucket, plus decoding tokens per second. We also build a length-shift split: long entities in training are subsampled to a handful per type while the test set is untouched. This probes extrapolation directly.
Keyphrases and addresses. We use the Hulth dataset, where the file gives only an approximate "10% over baselines" claim for the duration-modeled semi-Markov CRF and no exact number. We also use the Indian Address corpus, where the original semi-Markov CRF reached 65.2 F1 on State extraction. These test cross-domain duration shapes, and we will fit one model across all four keyphrase domains to see whether the GP body absorbs the Gamma-versus-Gaussian split without manual selection.
Duration calibration. We report the held-out negative log-likelihood of gold segment lengths under each duration model, bucketed by how often each length was seen in training.
Speech. On WSJ lattices we replace the bin-plus-fallback duration model in rescoring. The baseline to match is that paper's reported 1% to 8% relative WER gain, including 1% to 3% over log-normal.
Decisive checks. Three results settle the proposal:
- The walk-kernel and zero-mean ablations should either diverge or require a cap and lose on long spans. If they do not, the core claim about prior means is wrong.
- The full model should beat the hybrid semi-Markov CRF on the long-entity and length-shift buckets.
- It should beat the context-conditioned Gamma on at least the keyphrase or speech settings. If it does not, the nonparametric body is unjustified.
References
- Stationarity without mean reversion in improper Gaussian processes
- Duration Modeling with Semi-Markov Conditional Random Fields for Keyphrase Extraction
- Semi-Markov Conditional Random Fields for Information Extraction
- Hybrid semi-Markov CRF for Neural Sequence Labeling
- Filtered Semi-Markov CRF
- Phone Duration Modeling for LVCSR Using Neural Networks
- Hidden semi-Markov model based speech synthesis
- Gaussian Process Kernels for Pattern Discovery and Extrapolation
- Exploring Sequence-to-Sequence Learning in Aspect Term Extraction