Weighted finite state transducers
Motivation
- Transitions may be more or less preferred
- Paths through an FSA/FST need to be scored/ranked
Semirings
- A system with a "multiplication" operation and its "identity" element and an "addition" operation and its "identity" element such that the addition identity element is an annihlator for multiplication and multiplication distributes over addition
- Probability semiring: "multiplication" is multiplication, "addition" is addition
- Tropical semiring: "multiplication" is addition, "addition" is minimum
(for example, using negative log probabilities)
Weighted finite state automata/transducers
-
Each transition is augmented with a weight.
-
A cumulative weight is maintained for each path through the FSA/T by
"multiplying" the weights on the transitions.
-
If there are multiple paths through the FSA/T for a given input,
an overall weight is assigned by "adding" the weights for each path.
-
Examples: word model, language model, translation
