Viterbi semiring

The Viterbi semiring provides the algebraic framework underlying a class of dynamic programming (DP) algorithms that compute optimal paths or optimal solutions by combining local decisions. In a DP context, the semiring's additive operation (max) is used to select the best (highest-weight) outcome among alternatives, and the multiplicative operation (×) is used to accumulate weights (probabilities or scores) along a path. The classic Viterbi algorithm – which finds the most probable sequence of states in a probabilistic model – can be understood as a DP computation over the ${\displaystyle (\max ,\times )}$ semiring.^[5] At each step, the algorithm applies the distributive law of the semiring to efficiently combine sub-solutions: rather than enumerating all possible state sequences, it uses the distributivity of multiplication over max to propagate only the best partial probabilities forward.^[2] This is analogous to how other DP algorithms (like shortest path algorithms) operate over different semirings (e.g. the Floyd–Warshall algorithm uses the ${\displaystyle (\min ,+)}$ semiring for path costs).^[2]

In practical terms, any DP recurrence that involves taking a maximum over weighted combinations can be seen as an instance of computing over the Viterbi semiring. For example, if we have a recurrence relation such as:

${\displaystyle DP[j]=\max _{i}\{DP[i]\times w_{i\to j}\},}$

this is exactly an expression in the Viterbi semiring – the max over ${\displaystyle i}$ corresponds to the semiring addition (choosing the best predecessor state ${\displaystyle i}$) and the multiplication ${\displaystyle DP[i]\times w_{i\to j}}$ corresponds to semiring multiplication (concatenating the weight/probability of transitioning from state ${\displaystyle i}$ to ${\displaystyle j}$). The Viterbi algorithm for sequence models uses this template: it iteratively computes the best path probability to each state at time ${\displaystyle t}$ by taking the max over all previous-state probabilities times the transition probability into the current state.^[6] Because the addition is idempotent (max), once a better path to a given state is found, worse alternatives are discarded, which is key to the efficiency of the algorithm.

Notably, this semiring perspective reveals that the forward-sum algorithm and the Viterbi-max algorithm are parallel concepts: they differ only in the choice of semiring. The forward (or inside) algorithm that sums over all paths uses the sum-product semiring ${\displaystyle (\mathbb {R} _{\geq 0},+,\times )}$, whereas the Viterbi algorithm uses the max-product semiring (the Viterbi semiring, ${\displaystyle (\mathbb {R} _{\geq 0},\max ,\times )}$).^[7][5] In fact, many parsing and inference algorithms can be generalized such that swapping out the semiring from sum to max turns a marginal probability computation into a maximum probability computation (this insight is sometimes called the semiring parsing framework).^[5] The distributive property of semirings is what enables these DP algorithms to aggregate a potentially exponential number of possibilities efficiently.

Hidden Markov Models provide a quintessential use case for the Viterbi semiring. In an HMM, we have a sequence of observed outputs and a sequence of hidden states with transition probabilities and emission probabilities. The decoding problem for HMMs asks: what is the most likely sequence of hidden states that could produce a given observation sequence? The Viterbi algorithm answers this by maximizing the joint probability of the state-path and observations. Algebraically, this is exactly a computation in the ${\displaystyle (\max ,\times )}$ semiring on the space of state sequences. At each time step, the algorithm selects the highest probability path that ends in each state, using max to choose the best predecessor state and multiplying by the transition and emission probabilities to extend the path.

Using the Viterbi semiring for HMM decoding means that instead of summing over all possible state paths (as one would in the forward algorithm for total likelihood), we track only the maximum probability for each partial path.^[6] In other words, the algorithm "forgets" the lower-probability paths at every step, keeping only the best path to each state. This approach finds the single most likely path (often called the Viterbi path or MAP sequence), along with its probability.^[8] Formally, if ${\displaystyle P_{t}(s)}$ is the maximum probability of ending in state ${\displaystyle s}$ at time ${\displaystyle t}$ (over all state sequences up to ${\displaystyle t}$), the Viterbi update is:

${\displaystyle P_{t}(s)=\max _{s'}\left\{\,P_{t-1}(s')\times {\mathsf {Trans}}(s'\to s)\times {\mathsf {Emit}}(s,o_{t})\,\right\},}$

where the max runs over all previous states ${\displaystyle s'}$ and ${\displaystyle {\mathsf {Trans}}}$ and ${\displaystyle {\mathsf {Emit}}}$ are the transition and emission probabilities, respectively. This recurrence uses max as the combine operation and multiplication to accumulate probabilities along a path – precisely the Viterbi semiring operations. As a result, the most probable state sequence for the whole observation sequence is obtained at the final time by taking the best ending state probability.^[9]

In HMM applications, the Viterbi semiring is contrasted with the inside (forward) semiring: the forward algorithm computes ${\displaystyle P({\text{observations}})}$ by summing over paths, whereas the Viterbi algorithm (using the max-times semiring) computes ${\displaystyle \max P({\text{observations and state path}})}$, i.e. the probability of the single best path.^[10] Both are dynamic programming algorithms on the same HMM trellis, but instantiated with different semiring operations. It's also common to refer to the outcome of the Viterbi algorithm as a Viterbi alignment or Viterbi parse in contexts like speech or parsing, emphasizing that it represents an optimal sequence rather than a probability sum. The term "Viterbi" has thus become synonymous with the max-product computation on probabilistic models.

Viterbi training is a related concept in HMM learning: instead of the Expectation-Maximization (EM) algorithm which sums over all paths (the Baum-Welch algorithm uses forward-backward sums), one can train by only considering the single best path for each training example (using the Viterbi semiring in the E-step). This is essentially a hard approximation to EM. While Viterbi training can converge faster, it may find a suboptimal local maximum since it ignores probability mass off the best path. Nevertheless, it highlights again how simply switching to the max-operation (Viterbi semiring) in the algorithm yields a different approach to the problem.^[11]

In software, the Viterbi semiring is typically implemented implicitly through the use of standard data types (for probabilities or log-probabilities) combined with appropriate operations. The key consideration is numerical stability: probabilities multiplied together can become extremely small for long sequences, so it is common to perform computations in the log domain. Implementing the Viterbi algorithm in log-space means using ${\displaystyle \log }$ probabilities, converting multiplication into addition of logs, and using ${\displaystyle \max }$ on log-probabilities (which corresponds to ${\displaystyle \max }$ on the original probabilities since log is monotonic). In practice, one might represent each score as a floating-point log-probability and then use addition for transitions and use the standard max function to select the best path. This is equivalent to using an isomorphic semiring ${\displaystyle (\mathbb {R} \cup \{-\infty \},\max ,+)}$ often called the log-max semiring, which corresponds to a tropical semiring with min if using negative logs.^[4] Working in log-space prevents underflow and turns multiplications into faster additions. Indeed, many speech and language processing systems use ${\displaystyle \log }$ probabilities and then perform a max over sums of logs; for example, "typically use log probabilities" in Viterbi decoding for speech recognition to avoid numerical underflow.^[9]

Another important implementation detail is retrieving the argmax path (the actual sequence of states or decisions) and not just its probability. The Viterbi semiring itself computes the max probability values, but to recover the optimal sequence, the standard technique is to maintain backpointers: along with each ${\displaystyle P_{t}(s)}$, store the argmax choice of predecessor state ${\displaystyle s'}$ that achieved that maximum. After the DP table is filled, one can backtrack via these pointers to reconstruct the optimal path. This can be seen as augmenting the semiring with extra information (the argmax derivation), effectively working in an extended semiring that carries both the probability and the argmax history.^[2] Some formalisms define an argmax semiring or use tuples to carry this information, but in practice a separate parallel array of backpointers is straightforward and efficient.

Higher-level libraries and frameworks sometimes make the semiring abstraction explicit. For instance, in finite-state machine libraries like OpenFST, the default tropical weight is essentially the Viterbi semiring implemented in log-space (using ${\displaystyle -\ln p}$ as weights, so that the shortest path corresponds to the highest probability).^[12] The library provides generic algorithms (like composition or shortest-path) that work with any semiring specified, and using the tropical semiring yields Viterbi-style results. In another example, the torch_semiring_einsum library for PyTorch allows tensor operations to be carried out in different semirings; it provides a Viterbi semiring implementation out-of-the-box.^[5] This means a programmer can switch from summing to maximizing simply by changing the semiring context, illustrating the flexibility of abstracting DP algorithms by semiring type.

From an encoding standpoint, implementing the Viterbi semiring might involve a small wrapper or class that defines the two operations. However, since max and * (or + in log-space) are primitive operations, many implementations of the Viterbi algorithm just use control flow to apply these operations without an explicit "Semiring" object. The pattern typically looks like nested loops over states and time, with an inner calculation that does exactly the ${\displaystyle \max }$ over (previous score ${\displaystyle \times }$ transition ${\displaystyle \times }$ emission). Pseudocode or high-level languages often make this clear. The benefit of understanding it as a semiring is more apparent when writing generic algorithms: for example, a CKY parser or a matrix multiplication can be generalized to different semirings. Indeed, by plugging in the Viterbi semiring into a generic parsing algorithm, one obtains a parser that returns the single best parse (often called a Viterbi parse) instead of a distribution over parses.

The Viterbi semiring (max-times) is widely used in areas that require decoding the most likely sequence or structure under probabilistic models. Below are key application domains and examples:

In computational linguistics, the Viterbi algorithm is used for tasks like part-of-speech tagging, named entity recognition, and probabilistic parsing.^[2] For instance, in a probabilistic context-free grammar (PCFG), one can use a dynamic programming parser with the Viterbi semiring to find the single most likely parse tree for a sentence (often called the Viterbi parse). Similarly, an HMM-based tagger uses Viterbi to find the most likely sequence of tags for a given word sequence. The semiring framework also appears in probabilistic parsing algorithms more generally – by switching between the inside semiring (summing probabilities of all parses) and the Viterbi semiring (taking max), systems can compute either parse probabilities or the best parse without changing the core algorithm. Overall, whenever a "best sequence" needs to be inferred (as opposed to a sum or expectation), NLP systems employ the Viterbi/max-product approach.

Many problems in bioinformatics involve finding an optimal sequence alignment or annotation, often using HMM variants.^[6] For example, profile HMMs (used to model protein or DNA sequence families) apply the Viterbi algorithm to align a new sequence to the profile, yielding the single best alignment path (the highest scoring alignment). This is analogous to finding the most likely evolutionary path or gene structure. Gene prediction can also involve HMMs where states represent coding or non-coding regions; Viterbi decoding will produce the most likely segmentation of a DNA sequence into genes. The principle is the same: instead of summing over all gene architectures, the algorithm picks the highest probability gene model. Notably, sequence alignment algorithms like Needleman–Wunsch or Smith–Waterman (though often not framed in probability terms) are effectively using a max-plus semiring (max for the best score, plus for adding match/mismatch scores), which is conceptually similar to the Viterbi semiring approach.^[13] Thus, the Viterbi semiring underlies a range of bioinformatics tools for sequence analysis, from multiple sequence alignment to protein structure prediction, whenever a best hypothesis needs to be identified.

Automatic speech recognition (ASR) heavily relies on the Viterbi semiring in decoding. In HMM-based speech recognition (e.g. with Gaussian mixture or acoustic models), the goal is to find the most likely word sequence given an acoustic signal. The search through the state-space of all possible word pronunciations is conducted with the Viterbi algorithm, which finds the best path through a lattice of HMM states representing words or sub-word units.^[9] The Viterbi decoder uses max (taking the most probable hypothesis) at each time frame rather than summing over alternate hypotheses (which would correspond to the impractical task of computing the total probability of all possible utterances). This yields the single best transcription. Even in modern deep learning-based ASR, decoding often involves a Viterbi or Viterbi-like beam search. The semiring concept also appears in weighted finite-state transducer (WFST) frameworks for speech: the tropical semiring (a variant of the Viterbi semiring with log weights) is used to find the lowest-cost path, which corresponds to the highest probability sentence.^[12] ASR uses Viterbi decoding as a core algorithm ("takes MAX, not SUM" in the process of choosing state transitions)^[14] to output the single best recognition hypothesis.

Beyond these areas, the max-times semiring has applications in machine learning and AI wherever one needs maximum a posteriori (MAP) inference. For example, in graphical models or factor graphs, the max-product algorithm (for MAP estimation) is essentially an instance of propagating messages in the Viterbi semiring (as opposed to the sum-product semiring for marginal inference). In domains like computer vision (e.g. decoding the best segmentation of an image) or computational finance (optimal policy paths), one can often spot the same algebraic pattern. The Viterbi semiring's reach is so broad that it has been described as a "universal" tool for maximization problems in sequence analysis and beyond.

• ${\displaystyle {\text{Viterbi semiring: }}(\max ,\times )}$
• ${\displaystyle {\text{Inside semiring: }}(+,\times )}$
• ${\displaystyle {\text{Tropical semiring: }}(\min ,+)}$