Weighted automata and hidden Markov models

An unweighted automaton records whether a path exists. But what if some paths should count more than others? A weighted finite state automaton (WFSA) associates a weight with each transition and combines those weights along and across paths (Mohri 1997; Mohri et al. 2002).

Path and string weights

Let $w(e)$ be the weight of transition $e$. We use $\otimes$ to combine the transitions on a path and $\oplus$ to combine alternative paths. If $\pi=e_1\ldots e_n$ runs from $q_0$ to $q_n$, with initial weight $\lambda(q_0)$ and final weight $\rho(q_n)$, then

\[w(\pi)=\lambda(q_0)\otimes w(e_1)\otimes\cdots\otimes w(e_n)\otimes\rho(q_n).\]

An unweighted initial or final state has the multiplicative-identity weight, so those factors may be omitted in the simpler presentation.

The weight assigned to a string $x$ is the sum of the weights of all successful paths labeled $x$:

\[w(x)=\bigoplus_{\pi\,:\,\operatorname{label}(\pi)=x}w(\pi).\]

The set that supplies the weights together with $\oplus$, $\otimes$, and their identity elements is a semiring. This abstraction lets the same automaton algorithms operate over probabilities, log probabilities, or costs (Mohri et al. 2002). Two semirings will be useful here:

In the probability semiring, $\oplus=+$ and $\otimes=\times$. The weight of a string is the total probability of all of its paths.
In the tropical semiring, $\oplus=\min$ and $\otimes=+$. The weight of a string is the cost of its least-cost path.

The forward algorithm computes the first quantity (Rabiner 1989). The Viterbi algorithm computes the best-path version, which corresponds to replacing a sum over paths with the tropical-semiring best-path calculation (Mohri et al. 2002).

Question

Two paths labeled $x$ have probabilities $.2$ and $.3$. What probability does the WFSA assign to $x$? What would Viterbi return?

Answer

The forward calculation assigns $.2+.3=.5$ to $x$. Viterbi returns the more probable path and its probability, $.3$.

Hidden Markov models as WFSAs

Recall that a hidden Markov model (HMM) has hidden states $Q$, transition probabilities $p(q'\mid q)$, and emission probabilities $p(\sigma\mid q')$. HMMs are special cases of WFSAs (Mohri et al. 2002). Under the state-emitting convention used here, we represent one by adding, for each $q,q'\in Q$ and $\sigma\in\Sigma$, a transition of the following form (Rabiner 1989):

\[q \xrightarrow{\sigma\,/\,[p(q'\mid q)p(\sigma\mid q')]} q'.\]

Initial and final weights encode the initial-state and termination probabilities. The weight of a path

\[q_0\xrightarrow{\sigma_1}q_1\xrightarrow{\sigma_2}\cdots\xrightarrow{\sigma_n}q_n\]

\[p(q_0)\prod_{i=1}^n p(q_i\mid q_{i-1})p(\sigma_i\mid q_i),\]

up to the final termination weight. This is the joint probability of the observation string and that hidden-state sequence. Summing over all paths labeled $\sigma_1\ldots\sigma_n$ gives the marginal probability of the observations (Rabiner 1989).

Thus, an HMM is a particular probabilistic WFSA. Its hidden-state ambiguity is exactly path ambiguity in the automaton.

Weighted transducers

A weighted FST assigns a weight to each input-output pair, and composition combines rule systems using the operations of the chosen semiring (Mohri 1997; Mohri et al. 2002). In a phonological grammar, we can interpret unequal weights as preferences among surface realizations or underlying analyses without excluding the alternatives.

Weighted automata thus connect two earlier parts of the course. The finite state machinery supplies the paths, and the probability model supplies a measure over them. Determinization, minimization, and weight pushing can make these machines smaller or faster, though weighted determinization is not guaranteed to terminate for every transducer (Mohri 1997; Mohri et al. 2002). We will use that connection when HMMs assign morpheme-boundary labels in the section on structured prediction.

References

Mohri, Mehryar. 1997. “Finite-State Transducers in Language and Speech Processing.” Computational Linguistics 23 (2): 269–311. https://aclanthology.org/J97-2003/.

Mohri, Mehryar, Fernando Pereira, and Michael Riley. 2002. “Weighted Finite-State Transducers in Speech Recognition.” Computer Speech & Language 16 (1): 69–88. https://doi.org/10.1006/csla.2001.0184.

Rabiner, Lawrence R. 1989. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.” Proceedings of the IEEE 77 (2): 257–86. https://doi.org/10.1109/5.18626.

--- title: Weighted automata and hidden Markov models bibliography: ../../references.bib --- An unweighted automaton records whether a path exists. But what if some paths should count more than others? A **weighted finite state automaton** (WFSA) associates a weight with each transition and combines those weights along and across paths [@mohri_fst_1997; @mohri_weighted_2002]. ## Path and string weights Let $w(e)$ be the weight of transition $e$. We use $\otimes$ to combine the transitions on a path and $\oplus$ to combine alternative paths. If $\pi=e_1\ldots e_n$ runs from $q_0$ to $q_n$, with initial weight $\lambda(q_0)$ and final weight $\rho(q_n)$, then $$w(\pi)=\lambda(q_0)\otimes w(e_1)\otimes\cdots\otimes w(e_n)\otimes\rho(q_n).$$ An unweighted initial or final state has the multiplicative-identity weight, so those factors may be omitted in the simpler presentation. The weight assigned to a string $x$ is the sum of the weights of all successful paths labeled $x$: $$w(x)=\bigoplus_{\pi\,:\,\operatorname{label}(\pi)=x}w(\pi).$$ The set that supplies the weights together with $\oplus$, $\otimes$, and their identity elements is a *semiring*. This abstraction lets the same automaton algorithms operate over probabilities, log probabilities, or costs [@mohri_weighted_2002]. Two semirings will be useful here: - In the **probability semiring**, $\oplus=+$ and $\otimes=\times$. The weight of a string is the total probability of all of its paths. - In the **tropical semiring**, $\oplus=\min$ and $\otimes=+$. The weight of a string is the cost of its least-cost path. The forward algorithm computes the first quantity [@rabiner_tutorial_1989]. The Viterbi algorithm computes the best-path version, which corresponds to replacing a sum over paths with the tropical-semiring best-path calculation [@mohri_weighted_2002]. ::: {.callout-caution} ## Question Two paths labeled $x$ have probabilities $.2$ and $.3$. What probability does the WFSA assign to $x$? What would Viterbi return? ::: ::: {.callout-tip collapse=true} ## Answer The forward calculation assigns $.2+.3=.5$ to $x$. Viterbi returns the more probable path and its probability, $.3$. ::: ## Hidden Markov models as WFSAs Recall that a hidden Markov model (HMM) has hidden states $Q$, transition probabilities $p(q'\mid q)$, and emission probabilities $p(\sigma\mid q')$. HMMs are special cases of WFSAs [@mohri_weighted_2002]. Under the state-emitting convention used here, we represent one by adding, for each $q,q'\in Q$ and $\sigma\in\Sigma$, a transition of the following form [@rabiner_tutorial_1989]: $$q \xrightarrow{\sigma\,/\,[p(q'\mid q)p(\sigma\mid q')]} q'.$$ Initial and final weights encode the initial-state and termination probabilities. The weight of a path $$q_0\xrightarrow{\sigma_1}q_1\xrightarrow{\sigma_2}\cdots\xrightarrow{\sigma_n}q_n$$ is $$p(q_0)\prod_{i=1}^n p(q_i\mid q_{i-1})p(\sigma_i\mid q_i),$$ up to the final termination weight. This is the joint probability of the observation string and that hidden-state sequence. Summing over all paths labeled $\sigma_1\ldots\sigma_n$ gives the marginal probability of the observations [@rabiner_tutorial_1989]. Thus, an HMM is a particular probabilistic WFSA. Its hidden-state ambiguity is exactly path ambiguity in the automaton. ## Weighted transducers A weighted FST assigns a weight to each input-output pair, and composition combines rule systems using the operations of the chosen semiring [@mohri_fst_1997; @mohri_weighted_2002]. In a phonological grammar, we can interpret unequal weights as preferences among surface realizations or underlying analyses without excluding the alternatives. Weighted automata thus connect two earlier parts of the course. The finite state machinery supplies the paths, and the probability model supplies a measure over them. Determinization, minimization, and weight pushing can make these machines smaller or faster, though weighted determinization is not guaranteed to terminate for every transducer [@mohri_fst_1997; @mohri_weighted_2002]. We will use that connection when HMMs assign morpheme-boundary labels in the section on [structured prediction](../../morphological-patterns/segmentation-with-structured-prediction.qmd).