Weighted Finite State Transducer

A Weighted Finite State Transducer is a finite state transducer with weighted transitions (weighted edges).

• AKA: Weighted Automata, WFST.
• Example(s):
  • a CRF Model.
  • an HMM Model.
  • …
• Counter-Example(s):
  • Unweighted Finite State Transducer.
• See: Semiring, Log Semiring, Boolean Semiring, Stochastic Finite State Machine.

---

---

References

2015

• (Wikipedia, 2015) ⇒ http://en.wikipedia.org/wiki/Finite_state_transducer#Weighted_automata Retrieved:2015-1-16.
  • Finite State Transducers can be weighted, where each transition is labeled with a weight in addition to the input and output labels. A Weighted Finite State Transducer (WFST) over a set K can be defined similarly to an unweighted one as an 8-tuple T=(Q, Σ, Γ, I, F, E, λ, ρ), where:
    • Q, Σ, Γ, I, F are defined as above;
    • [math]\displaystyle{ E \subseteq Q \times (\Sigma\cup\{\epsilon\}) \times (\Gamma\cup\{\epsilon\}) \times Q \times K }[/math] (where ε is the empty string) is the finite set of transitions;
    • [math]\displaystyle{ \lambda: I \rightarrow K }[/math] maps initial states to weights;
    • [math]\displaystyle{ \rho: F \rightarrow K }[/math] maps final states to weights.
  • In order to make certain operations on WFSTs well-defined, it is convenient to require the set of weights to form a semiring. Two typical semirings used in practice are the log semiring and tropical semiring: unweighted automata may be regarded as having weights in the Boolean semiring.

2007

• (Allauzen et al., 2007) ⇒ Cyril Allauzen, Michael Riley, Johan Schalkwyk, Wojciech Skut, and Mehryar Mohri. (2007). “OpenFst: A General and Efficient Weighted Finite-state Transducer Library.” In: Implementation and Application of Automata.

2002

• (Mohri et al., 2001) ⇒ Mehryar Mohria, Fernando Pereirab, and Michael Rileya. (2001). “Weighted Finite-state Transducers in Speech Recognition.” In: Computer Speech & Language, 16(1). doi:10.1006/csla.2001.0184
  • QUOTE: 2002_WeightedFiniteStateTransiSpRecogWe survey the use of weighted finite-state transducers (WFSTs) in speech recognition. 2002_WeightedFiniteStateTransiSpRecogWe show that WFSTs provide a common and natural representation for hidden Markov models (HMMs), context-dependency, pronunciation dictionaries, grammars, and alternative recognition outputs.

---