NLP ETH - Know your semirings

The Boolean Semiring can be used for things like recognition algorithms (e.g. can this string be expressed by a syntax tree for CYK).

\(\langle \{0,1\}, \lor, \land, 0, 1\rangle\)

The Viterbi Semiring corresponds to finding the most probable sequence of states. It is defined as follows:

\(\langle [0,1], \max, \times, 0, 1\rangle\)

The Inside Semiring is used to find the Normalizer of a CRF

\(\langle \mathbb{R}^+ \cup \{+\infty\}, +, \times, 0, 1\rangle\)

The Real Semiring is used for shortest path if there are negative weights

\(\langle \mathbb{R} \cup \{+\infty\}, min, +, +\infty ,0\rangle\)

The tropical semiring is used to find the shortest path in cases when there are no negative weights in the graph

\(\langle \mathbb{R}^+ \cup \{+\infty\}, min, +, +\infty ,0\rangle\)

Used to find the number of paths in a graph

\(\langle \mathbb{N}, +, \times, 0 ,1\rangle\)

The Log-Semiring can be used to compute the Log-Normalizer for CRFs or CYK

\(\langle \mathbb{R} \cup \{-\infty, +\infty\}, log(e^a + e^b), a + b, -\infty ,0\rangle\)

Note that the base can be something different than e but not = 1

1. Show that \(\langle set, \oplus,\overline{0}\rangle\) is a commutative monoid
   • Show that it is closed regarding \(\oplus\)
   • (a + b) + c = a + (b + c)
   • 0 + a = a + 0 = a
   • a + b = b + a
2. Show that \(\langle set, \otimes,\overline{1}\rangle\)is a monoid
   • Show that it is closed regarding \(\otimes\)
   • (a x b) x c = a x (b x c)
   • 1 x a = a x 1 = a 
3. Show that \(\overline{0}\) annihilates \(\otimes\)
   • 0 x a = a x 0 = 0
4. Show that \(\otimes\) distributes over \(\oplus\)
   • a x (b + c) = (a x b) + (a x c)
   • (a + b) x c = (a x c) + (b x c)