The Viterbi semiring is a commutative semiring defined over the set of probabilities (typically the interval [ 0 , 1 ] {\displaystyle [0,1]} ) with addition operation as the maximum (max) and multiplication as the usual real multiplication. Formally, it can be denoted as a 5-tuple ( S , ⊕ , ⊗ , 0 , 1 ) {\displaystyle (S,\oplus ,\otimes ,0,1)} where:
Carrier set ( S {\displaystyle S} ): [ 0 , 1 ] {\displaystyle [0,1]} , the set of probability values from 0 to 1 (inclusive). Additive operation ( ⊕ {\displaystyle \oplus } ): defined as the maximum of two elements. For any a , b ∈ [ 0 , 1 ] {\displaystyle a,b\in [0,1]} , a ⊕ b = max ( a , b ) {\displaystyle a\oplus b=\max(a,b)} . This operation is idempotent since a ⊕ a = a {\displaystyle a\oplus a=a} (taking the max of an element with itself yields the same element). The additive identity is 0 {\displaystyle 0} , because max ( 0 , x ) = x {\displaystyle \max(0,x)=x} for any x ∈ [ 0 , 1 ] {\displaystyle x\in [0,1]} . Multiplicative operation ( ⊗ {\displaystyle \otimes } ): defined as the standard product of real numbers. For a , b ∈ [ 0 , 1 ] {\displaystyle a,b\in [0,1]} , a ⊗ b = a × b {\displaystyle a\otimes b=a\times b} . The multiplicative identity is 1 {\displaystyle 1} , since 1 × x = x {\displaystyle 1\times x=x} for any x {\displaystyle x} . The additive identity 0 {\displaystyle 0} serves as the multiplicative zero (absorbing element) as well: 0 × x = 0 {\displaystyle 0\times x=0} . This structure satisfies all semiring axioms. Addition (max) is associative, commutative, and has identity 0 {\displaystyle 0} ; multiplication is associative (and commutative in this case, since real multiplication is commutative) with identity 1 {\displaystyle 1} ; and multiplication distributes over addition (for example, a × max ( b , c ) = max ( a × b , a × c ) {\displaystyle a\times \max(b,c)=\max(a\times b,a\times c)} ). Importantly, the max operation makes the semiring additively idempotent ( a ⊕ a = a {\displaystyle a\oplus a=a} ), imparting a natural partial order: a ≤ b {\displaystyle a\leq b} iff a ⊕ b = b {\displaystyle a\oplus b=b} . In this semiring, multiplying two values ≤ 1 {\displaystyle \leq 1} yields a value that is no greater than either factor, ensuring a ⊕ ( a ⊗ a ) = a {\displaystyle a\oplus (a\otimes a)=a} for a ∈ [ 0 , 1 ] {\displaystyle a\in [0,1]} (this property is sometimes called multiplicative subidempotence in the literature). Because max {\displaystyle \max } behaves like a "logical OR" over weighted probabilities and multiplication behaves like "AND" (combining independent probabilities), the Viterbi semiring is also known as the "max-times" semiring. It is closely related to the tropical semiring used in optimization: in fact, it is isomorphic to a tropical semiring via a logarithmic transformation. For example, mapping probabilities p {\displaystyle p} to log-costs − ln p {\displaystyle -\ln p} turns maximizing p {\displaystyle p} into minimizing a cost, and products of probabilities into sums of log-costs. This means algorithms formulated in the Viterbi semiring have equivalents in the min-plus (tropical) semiring commonly used for shortest path and other optimization problems.
… excerpt ends here. Continue reading the full article.
