On the Disambiguation of Weighted Automata

Mehryar Mohri, Michael D. Riley

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, relevant to applications. 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.

Introduction

In fields like speech recognition (ASR) and machine translation (MT), Weighted Finite Automata (WFAs) are used 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: it may never terminate for certain automata, and even when it does, it can cause an "exponential explosion" in the number of states. This paper proposes disambiguation as a middle ground: an unambiguous automaton ensures each string has only one path, but it does not necessarily have to be deterministic, often resulting in a much smaller model.

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.
Figure 1: Illustration of the disambiguation process, showing the original ambiguous WFA (left) and its transformation (right).

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, any automaton that can be determinized can also be disambiguated by this method, but the reverse is not true—this algorithm handles a wider variety of models, including all acyclic weighted automata.

Experimental Results

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

  • Speech Recognition: Using 500 speech lattices from Google Android voice searches, disambiguation resulted in a mean expansion of 1.23x compared to 1.31x for determinization. Disambiguation also showed much lower variance (0.59 vs. 1.35), indicating it is more predictable for production systems.
  • Machine Translation: For 100 Chinese-to-English translation lattices, the benefits were dramatic. Disambiguation had a mean expansion of 4.53x, while determinization exploded to 54.5x.
  • Theoretical Efficiency: The authors demonstrated a synthetic 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.

Key Insights and Conclusion

The most striking insight is that by relaxing the requirement from "deterministic" to "unambiguous," functional goals like finding the $n$-best strings can be achieved with a significantly smaller memory footprint. This is particularly powerful for acyclic models, which cover the vast majority of lattices in modern NLP pipelines.

While the algorithm is more broadly applicable than determinization, it still requires the "weak twins property" to guarantee termination. Future work includes exploring these properties in semirings other than the tropical semiring and investigating the decidability complexity of the weak twins property.

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, relevant to applications. 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