NLP ETH - Know your semirings

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)

A Weighted Finite State Transducer consists of the following components:

T = <Q,Σ,Ω,λ,ρ,δ>

● Q: a finite set of states (including initial or ending state)
● Σ: input vocabulary, e.g., an alphabet
● Ω: output vocabulary, e.g., a different alphabet
● λ: function mapping states to initial scores
● ρ: function mapping states to final scores
● δ: transition function mapping transitions (arcs) to scores

\(G = \langle N,S,\Sigma,\mathcal{R}\rangle\)

Where

• N is the non-terminal alphabet
• S is starting symbol
• \(\Sigma\) is the terminal alphabet
• R are the production rules