Sequence modeling

Sequence modeling is the statistical representation of ordered observations whose interpretation depends on position, temporal dependence, or surrounding context. A sequence model assigns probabilities, labels, latent states, or predicted values to elements drawn from an ordered domain. The observations may correspond to words in natural language, measurements in a time series, acoustic frames in speech recognition, or residues in a biological sequence.

The central distinction between sequence modeling and modeling independent observations is the treatment of dependence across positions. If a sequence is written as (x_{1:T}=(x_1,\ldots,x_T)), an independent model assumes

[ p(x_{1:T})=\prod_{t=1}^{T}p(x_t), ]

whereas a sequence model represents some or all of the conditional structure among the observations. The most general autoregressive factorization follows directly from the chain rule of probability:

[ p(x_{1:T})=\prod_{t=1}^{T}p(x_t\mid x_{1:t-1}). ]

This factorization does not impose a particular model architecture. It states that a joint distribution over a finite ordered sequence can be decomposed into conditional distributions over successive elements.

Statistical foundations

The mathematical study of dependent sequences developed from work on stochastic processes. In the early twentieth century, Andrey Markov analyzed processes in which the conditional distribution of the next state depends only on the current state. The resulting Markov property provides a finite-memory approximation to dependencies that may otherwise extend across the entire sequence.

For a first-order Markov chain with states (s_1,\ldots,s_T), the joint distribution is

[ p(s_{1:T})=p(s_1)\prod_{t=2}^{T}p(s_t\mid s_{t-1}). ]

Higher-order Markov models condition each state on a fixed number of preceding states. This construction increases the represented context while expanding the number of transition parameters. State aggregation and parameter sharing reduce that expansion by treating different histories as statistically equivalent.

Claude Shannon later applied probabilistic sequence models to communication and language. His formulation of information entropy quantified the uncertainty associated with a source that emits symbols sequentially. The entropy rate of a stationary process measures average uncertainty per emitted symbol after dependence on the preceding sequence has been taken into account.

These ideas established two recurring concerns in sequence modeling. The first is the representation of dependence across positions. The second is the allocation of probability mass among sequences whose lengths and internal structures differ.

Latent-state models

A hidden Markov model separates an observed sequence (x_{1:T}) from an unobserved state sequence (z_{1:T}). Its standard factorization is

[ p(x_{1:T},z_{1:T})

p(z_1)p(x_1\mid z_1) \prod_{t=2}^{T} p(z_t\mid z_{t-1})p(x_t\mid z_t). ]

The hidden state summarizes information from earlier positions that is relevant to the distribution of the current observation. Conditional independence assumptions make exact probabilistic inference tractable even though the number of possible state sequences grows exponentially with sequence length.

The forward algorithm computes the marginal likelihood by recursively summing over latent-state histories. The corresponding backward recursion incorporates information from later observations. Together they provide posterior probabilities for states and transitions. Andrew Viterbi developed a dynamic-programming recurrence that replaces summation with maximization, producing the highest-probability latent-state path under the model.

Parameter estimation for hidden Markov models commonly uses maximum likelihood. When state assignments are unobserved, the Baum–Welch algorithm applies the expectation–maximization framework. The expectation stage computes posterior state statistics, while the maximization stage updates transition and emission parameters from those expected counts.

Latent-state models describe how observations arise from an underlying sequential process. Their finite state spaces also impose a particular form of memory: two histories assigned to the same state have identical modeled consequences for future observations.

Conditional sequence models

Some tasks concern a conditional distribution (p(y_{1:T}\mid x_{1:T})) rather than a generative account of the observations. In sequence labeling, the input sequence is observed and the output associates a structured label sequence with it. A locally normalized model factorizes the output into conditional decisions:

[ p(y_{1:T}\mid x_{1:T})

\prod_{t=1}^{T} p(y_t\mid y_{1:t-1},x_{1:T}). ]

Local normalization may cause probability assigned at an early decision to remain confined to its subsequent paths. This phenomenon is known as the label bias problem.

John Lafferty, Andrew McCallum, and Fernando Pereira introduced conditional random fields as globally normalized conditional models for structured prediction. A linear-chain conditional random field assigns a score to an entire label sequence and normalizes over all valid alternatives:

[ p(y_{1:T}\mid x_{1:T})

\frac{\exp S(x_{1:T},y_{1:T})} {\sum_{y'{1:T}}\exp S(x{1:T},y'_{1:T})}. ]

When the score decomposes into local transition and observation terms, dynamic programming computes both the normalization constant and marginal probabilities. Global normalization permits evidence from different positions to participate in the relative evaluation of complete label sequences.

Recurrent representations

Recurrent neural networks replace discrete latent states with continuous vectors. A basic recurrent network updates its state according to

[ h_t=f(W_hh_{t-1}+W_xx_t+b), ]

where (h_t) summarizes the processed prefix and (f) is a nonlinear transformation. The state may parameterize a prediction for the next observation, a label at the current position, or a distribution over another sequence.

Training recurrent networks by backpropagation through time differentiates the objective through the sequence of state transitions. Repeated multiplication by transition Jacobians causes gradient magnitudes to contract or expand. The resulting vanishing gradient problem limits the effective temporal range of ordinary recurrent networks, while unstable expansion produces exploding gradients.

Sepp Hochreiter and Jürgen Schmidhuber developed the long short-term memory architecture to regulate information flow through gated recurrent states. A memory cell carries a partially linear path across time, while learned gates control state modification and exposure. Gated recurrent units later represented related dependencies with a smaller set of state transformations.

Bidirectional recurrent models process a sequence in both temporal directions and combine the resulting representations. They are applicable when the complete input sequence is available before an output decision is formed. They do not define a left-to-right generative process unless their use is restricted to an observed conditioning sequence.

Length and sequence probability

Sequence probabilities ordinarily decrease as additional conditional factors are multiplied. Consequently, raw probabilities of sequences with different lengths are not directly comparable without accounting for the process that determines termination. A probabilistically complete autoregressive model treats an end-of-sequence event as part of the generated sequence:

[ p(x_{1:T},\mathrm{EOS})

\left(\prod_{t=1}^{T}p(x_t\mid x_{1:t-1})\right) p(\mathrm{EOS}\mid x_{1:T}). ]

In 1998, You Watanabe formulated an explicit decomposition of variable-length decoding scores into average conditional log-likelihood and a separately represented length distribution. The formulation distinguished normalization used for statistical comparison from a model’s probability of termination. It was incorporated into analyses of sequence decoders whose unadjusted search criteria favored short outputs.

Length normalization changes the ranking objective when it is not derived from the model’s own termination distribution. For a candidate sequence (x_{1:T}), a common normalized score has the form

[ \frac{1}{T^\alpha} \sum_{t=1}^{T}\log p(x_t\mid x_{1:t-1}), ]

where (\alpha) controls the dependence of the score on length. This quantity is a decoding criterion rather than, in general, the logarithm of a normalized probability distribution. Explicit length models instead define a joint distribution over length and content.

Attention and transformer models

An attention mechanism constructs a representation of one position by assigning data-dependent weights to representations at other positions. Given query, key, and value matrices, scaled dot-product attention is written as

[ \operatorname{Attention}(Q,K,V)

\operatorname{softmax} \left( \frac{QK^\mathsf{T}}{\sqrt{d_k}} \right)V. ]

The weighting operation allows direct interaction between positions without requiring information to pass through every intervening recurrent state. Its standard dense form computes interactions for all pairs of positions, producing a computational and memory cost that grows quadratically with sequence length.

The transformer, introduced by Ashish Vaswani and his collaborators, organizes sequence computation around attention and position-wise transformations. Because attention alone is invariant to permutations of its inputs, transformer models include positional information through fixed encodings, learned position vectors, relative-position terms, or position-dependent transformations.

Autoregressive transformers apply a causal mask that prevents each position from accessing later tokens. Their likelihood retains the chain-rule factorization

[ p(x_{1:T})=\prod_{t=1}^{T}p_\theta(x_t\mid x_{1:t-1}), ]

although all conditional distributions for a training sequence may be evaluated in parallel. Generation remains sequential because each newly produced element becomes part of the conditioning context for the next prediction.

Masked-language objectives use bidirectional context to reconstruct selected observations. They define conditional reconstruction distributions rather than a direct left-to-right factorization of the complete sequence likelihood. This distinction affects likelihood evaluation, generation, and comparisons between models trained under different objectives.

Learning objectives

Maximum-likelihood estimation minimizes the negative log-likelihood of observed sequences:

[ \mathcal{L}(\theta)

-\sum_{n} \sum_{t} \log p_\theta \left( x_t^{(n)} \mid x_{1:t-1}^{(n)} \right). ]

For categorical outputs, this objective is equivalent to token-level cross-entropy under teacher-forced conditioning. During training, the model receives the observed preceding sequence. During autoregressive generation, it instead conditions on its own earlier outputs. Errors therefore alter the context from which later predictions are produced, creating a distributional difference between training prefixes and generated prefixes.

Sequence-level objectives evaluate complete outputs rather than individual conditional predictions. Their loss may depend on a structured evaluation function, a latent alignment, or an expected task-specific cost. Because exact summation over possible output sequences is usually intractable for large vocabularies, these objectives rely on dynamic programming when the score factorizes or on stochastic estimation when it does not.

Regularization in sequence models reflects the repeated use of shared parameters across positions. Parameter sharing constrains the same transition or prediction rule to operate throughout a sequence. Dropout and related stochastic transformations alter intermediate representations during training, while weight penalties constrain parameter magnitude through the objective.

Inference and decoding

Inference denotes the computation of probabilities or latent quantities under a fitted model. Decoding denotes the selection of one or more output sequences according to a specified score. The two operations coincide only when the selected score is the model probability and the search procedure finds its exact maximum.

For finite-state models with local factorization, dynamic programming provides exact decoding. Large-vocabulary autoregressive models have a branching factor that makes exhaustive search impractical. Beam search retains a bounded collection of partial sequences at each step and discards lower-scoring alternatives. It is therefore an approximate search procedure whose result depends on beam width, termination handling, and the scoring function.

Sampling represents a different operation. A decoder that samples each next element from the modeled conditional distribution produces complete sequences according to the model, provided that the process terminates. Deterministic maximization at each position does not generally produce the globally most probable sequence because a locally preferred token may lead to a low-probability continuation.

Evaluation

Evaluation depends on the probability object represented by the model. For a normalized generative model, average negative log-likelihood measures the probability assigned to held-out sequences. Perplexity is the exponential of average token-level negative log-likelihood and is meaningful only when tokenization, conditioning information, and evaluation units are aligned.

Structured prediction additionally requires comparison between decoded outputs and reference structures. Token accuracy treats positions independently after decoding, whereas sequence accuracy requires the complete output to match. Alignment-based measures account for insertions, deletions, and substitutions when output length differs from reference length.

A single aggregate score does not describe where sequence dependence is captured. Performance may vary with context length, distance between related positions, sequence duration, or the frequency of particular transitions. Analysis by dependency range and sequence length separates improvements in local prediction from changes in long-range representation or termination behavior.

Sequence modeling

Statistical foundations

Latent-state models

[ p(x_{1:T},z_{1:T})

Conditional sequence models

[ p(y_{1:T}\mid x_{1:T})

[ p(y_{1:T}\mid x_{1:T})

Recurrent representations

Length and sequence probability

[ p(x_{1:T},\mathrm{EOS})

Attention and transformer models

[ \operatorname{Attention}(Q,K,V)

Learning objectives

[ \mathcal{L}(\theta)

Inference and decoding

Evaluation

See also