On the Disambiguation of Weighted Automata

Mehryar Mohri, Michael D. Riley

TL;DR

This paper introduces a novel two-stage algorithm to "disambiguate" weighted finite automata (WFAs)—ensuring that every string is represented by at most one accepting path. This approach is a powerful alternative to standard determinization, as it is applicable to a broader class of models and can produce results that are exponentially smaller in size, significantly boosting efficiency in speech recognition and machine translation.

What Problem Does This Paper Address?

In fields like speech recognition (ASR) and machine translation (MT), we often use Weighted Finite Automata to represent a "lattice" of possible hypotheses. However, these lattices are frequently ambiguous: multiple different paths through the graph might represent the exact same sequence of words.

This ambiguity makes it difficult and computationally expensive to find the "most likely" string or the top $n$ results. The traditional solution is weighted determinization, which transforms the graph so that each state has only one outgoing transition for any given label. While effective, determinization has two major flaws:

  1. It doesn't work for all automata (it may never terminate).
  2. Even when it does work, it can cause an "exponential explosion" in the number of states, making the resulting model too large to use.

The authors tackle this by aiming for a middle ground: disambiguation. An unambiguous automaton is one where each string has only one path, but it doesn't necessarily have to be deterministic.

Methods

The authors propose a two-stage disambiguation algorithm:

  1. Pre-disambiguation: This stage constructs a new WFA where the weight of any path equals the sum (in the semiring sense) of all paths with that same label in the original automaton. This is a "family" of algorithms parameterized by a relation $R$ between states.
  2. Transition Removal: This stage prunes redundant transitions to ensure that only one path remains for any given string, without changing the total weight assigned to that string.

A key theoretical contribution is the introduction of the weak twins property. The authors prove that this property is a sufficient condition for their algorithm to terminate. Crucially, they show that any automaton that can be determinized can also be disambiguated by their method, but the reverse is not true—their algorithm handles a wider variety of models.

Datasets

The researchers evaluated their algorithm on two real-world datasets and one synthetic case:

  • ASR Lattices: 500 speech lattices sampled from anonymized Google Android voice searches.
  • Machine Translation Lattices: 100 Chinese-to-English translation lattices from the DARPA Gale task.
  • Synthetic Benchmark: A specific unweighted automaton (Figure 3 in the paper) designed to show the theoretical limits where determinization fails (exponential growth) while disambiguation remains efficient (linear/quadratic growth).

Key Insights and Ideas

  • Unambiguity is "Cheaper" than Determinism: The most striking insight is that by relaxing the requirement from "deterministic" to "unambiguous," you can achieve the same functional goals (like finding the $n$-best strings) with a much smaller memory footprint.
  • The Power of Acyclic Models: The algorithm is guaranteed to work for all acyclic weighted automata, which covers the vast majority of "lattices" produced in modern NLP and speech pipelines.
  • Stability: In the experiments, disambiguation showed much lower variance in "expansion" (how much the graph grows) compared to determinization. This makes it a more reliable choice for production systems where memory spikes are a concern.

Key Results

  • Speech Recognition: Disambiguation resulted in a mean expansion of 1.23x compared to 1.31x for determinization. More importantly, the standard deviation for disambiguation was much lower (0.59 vs. 1.35), indicating it is more predictable.
  • Machine Translation: The benefits were even more dramatic. For translation lattices, disambiguation had a mean expansion of 4.53x, while determinization exploded to 54.5x.
  • Theoretical Efficiency: The authors demonstrated a case where an unambiguous automaton of size $O(n^2)$ would require more than $2^n$ states if converted to a deterministic one. Their algorithm leaves such an automaton unchanged, whereas determinization would fail due to size constraints.

Limitations and Future Work

  • Termination Limits: While the algorithm is more broadly applicable than determinization, it still doesn't work for every possible weighted automaton. It requires the "weak twins property" to guarantee termination.
  • Semiring Specifics: The proofs regarding the sufficient conditions were primarily developed for the tropical semiring (common in ASR/MT). The authors suggest that exploring these properties in other semirings is a necessary next step.
  • Decidability: The authors noted that while testing for the "twins property" is known to be PSPACE-complete, it remains to be seen if testing for the "weak twins property" is similarly complex or more easily decidable.

Summary updated

Abstract

We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property. In particular, the algorithm can be used with all acyclic weighted automata and more generally any determinizable weighted automata. While disambiguation can sometimes be achieved using determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.
BibTeX
@inproceedings{mohri2015disambiguation,
  author = {Mehryar Mohri and Michael D. Riley},
  title = {{On the Disambiguation of Weighted Automata}},
  booktitle = {CIAA},
  year = {2015},
  doi = {10.1007/978-3-319-22360-5\_22},
}

Loading related content...

Figure