Semirings allow us to generalize many many common operations. One of the most powerful usages is the algebraic view of dynamic programming.

Definition of a semiring

A semiring is a 5-tuple $R = (A, \oplus, \otimes, \bar{0}, \bar{1})$ such that.

1. $(A, \oplus, \bar{0})$ is a commutative monoid
2. $(A, \otimes, \bar{1})$ is a monoid
3. $\otimes$ distributes over $\oplus$.
4. $\bar{0}$ is annihilator for $\otimes$.

Monoid

Let $K, \oplus$ be a set and a operation, then:

1. $\forall a, b, c \in K$ we have that $a \oplus (b \oplus c) = (a \oplus b) \oplus c$
2. $\exists 1$ such that $\forall a \in K$ we have $1 \oplus a = a \oplus 1 = a$ A monoid has associativity and identity element. This structure allows us to use that sort of backpropagation. A simple example of a semiring would be $\left( \mathbb{R}^{+}, +, \times, 0, 1 \right)$. We can show every property above.

The deep insight is that dynamic programming just needs semirings with distributive property to work! All of the above derivation for the algebraic method for the algorithm just needs that our operation is a semiring! Then everything would work in the same manner.

Ring

We have a semiring, with the addition that addition is invertible. So instead of monoid, we have a group for the addition.\

If a semiring has a multiplication operation that is commutative, then it’s called communicative semiring. If semiring has idempotent operation, then it’s a idempotent semiring.

Anej Svete said there are also some cool applications of defining some sampling from transformers as operations over some special semirings.

Table of semirings

See (Huang 2008).

Applications

We usually lift some algorithm to a semiring to implement a generalized version of it. In this manner, a single proof of correctness can be applied to many algorithms.

Generalized Backward with Semi-rings

Usages and rings

TODO: in this section you should describe what semiring is used, and what is each for. Example: normal semiring is used to compute the normalizer, when the tropical semiring is used for the best part of speech tagging.

Other variations

Closed semiring

This is useful for applications like Transliteration systems. This definition follows Lehmann 1977. We say a semiring is closed if it has an additional unary operation, the Kleene Star, which satisfies this axiom:

$$ \begin{array} \\ x^{*} = 1 \oplus x \otimes x^{*} \\ x^{*} = 1 \oplus x^{*} \otimes x \end{array} $$

Example: infinite sum is a Kleene unary operation, let’s take an integer $x \in [0, 1)$ Then $x^{*} = \sum_{n = 1}^{\infty} x^{n} = \frac{1}{1 - x}$, and it’s easy to check the axioms.

For example $0$ should be the Kleene Star for the arctic semiring, also for the tropical semiring. $1$ is the Kleene for the boolean semiring.

K-closed semirings

We say a semiring is K-closed if the following is true:

$$ \bigoplus ^{k + 1}_{n = 1} x^{n} = \bigoplus^{k}_{n = 1} x^{n} $$

For all $x$ in the semiring. This means that adding more than $k$ elements has no effect. This is closely related to the definition of closeness. One can prove that with the above relation, it is true that

$$ \bigoplus^{k}_{n = 1} x^{n} = x^{*} $$

Matrix Semiring

Given a semiring $R = (A, \oplus, \otimes, \bar{0}, \bar{1})$ we can define a matrix semiring over $R$ as:

$$ \begin{align} \mathcal{M}_{n \times m}(R) = \left\{ A \in R^{n \times m} \right\} \\ \oplus = \oplus_{R} \\ \otimes = \otimes_{R} \\ \bar{0} = \bar{0}_{R} \\ \bar{1} = \bar{1}_{R} \end{align} $$

Where the operations are defined element-wise, the null operator is the matrix with all zeros, and the identity matrix is the matrix with all $\bar{1}$ on the diagonal and $\bar{0}$ elsewhere. We can prove that this is a semiring.

In the matrix semiring setting, is is useful to consider the Kleene Star operation. This is interpretable as the pathsum of all paths of length $k > 0$ starting and finishing at a certain index. This also motivates

References

[1] Huang “Advanced Dynamic Programming in Semiring and Hypergraph Frameworks” Coling 2008 Organizing Committee 2008