c2b_default

NLP ETH - Know your semirings

In the ETH NLP course, a variety of semirings is used to compute different things (normalizer, log-normalizer, most probable path, etc.) in algorithms like viterbi for conditional random fields or CYK

In the ETH NLP course, a variety of semirings is used to compute different things (normalizer, log-normalizer, most probable path, etc.) in algorithms like viterbi for conditional random fields or CYK

10
0.0 (0)
D. R.
Étudier
D. R.
Diese Lernkarten bieten eine Einführung in die Grundlagen von Semiringen und ihre Anwendung in der Informatik auf Universitätsniveau. Sie decken verschiedene Semiringe wie den Log-Semiring, den Counting Semiring, den Tropical Semiring, den Real Semiring, den Inside Semiring, den Viterbi Semiring und den Boolean Semiring ab. Diese Karteikarten sind ideal für Studierende und Forscher, die sich mit Algorithmen wie Viterbi, Inside und CRFs beschäftigen, da sie die mathematischen Strukturen hinter diesen Konzepten erklären und zeigen, wie sie in praktischen Anwendungen genutzt werden können.
Cartes-fiches
10
Utilisateurs
2
Langue
Allemand
Catégorie
Informatique
Niveau
Université
Créé / Mis à jour
15.02.2021 / 24.01.2022
  • 1  / 10

Cartes-fiches

Describe the Boolean Semiring

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\)

Describe the Viterbi Semiring

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\)

Describe the Inside Semiring

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

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

Describe the Real Semiring

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

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

Describe the Tropical Semiring

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\)

Describe the Counting Semiring

Used to find the number of paths in a graph

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

Describe the Log-Semiring

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

How do you show that something is a semiring?

  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)

Define a WFST

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

Define a CFG

\(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

Étudier