Introduction
In modern speech and language processing, Weighted Finite State Transducers (WFSTs) are ubiquitous for representing complex search spaces, such as lattices in machine translation or speech recognition. A significant challenge arises when these transducers are "non-functional"—meaning a single input string can map to multiple output strings—and "ambiguous"—where multiple paths exist for the same input. Disambiguation is the task of pruning these lattices to retain only the highest-scoring path for each unique input. Crucially, this must be done while preserving the original arc-level alignments (e.g., which source word corresponds to which target tag), a requirement that standard determinization algorithms often fail to meet efficiently.
Methodology: Sparse Topological Features
The proposed framework addresses these challenges through a novel three-step process centered on a "Tropical Sparse Tuple Vector Semiring."
1. Mapping with Topological Features
The first step involves mapping the original WFST into a Weighted Finite State Automaton (WFSA). Unlike standard mappings that only preserve weights, this approach uses topological features—sparse vectors that act as pointers to the original arcs in the transducer. For instance, an arc in the original transducer is assigned a unique index which is then carried through the semiring as metadata.
2. Determinization and Expansion
Once mapped, standard WFSA determinization is applied. The sparse vector semiring ensures that the identity of the "best" original paths is preserved even as paths are collapsed. The core innovation is the EXPANDTFEA algorithm, which traverses the determinized automaton and "pops" these topological features to reconstruct the original arc-level alignments.
3. Handling Minimization
If the automaton undergoes minimization that reorders features, the authors employ a two-pass expansion strategy. This ensures that the mapping between the compressed lattice and the original alignments remains consistent, even when the topological history is shifted during the minimization process.
Experimental Evaluation
The researchers evaluated the algorithm on two demanding tasks: Part-of-Speech (PoS) tagging and Neural Network Bilingual Rescoring for machine translation.
PoS Transducer Disambiguation
Using 4,664 lattices from the NIST English CTS RT Dev04 set, the "topological" algorithm demonstrated a significant speed advantage. Within a 50ms processing window, it successfully disambiguated 3,540 transducers, outperforming the previous "categorial" semiring state-of-the-art, which managed only 2,771. For the most complex lattices, the speedup was nearly fourfold (60 seconds vs. 230 seconds).
Machine Translation Scalability
On large translation lattices (averaging over 38,000 states) from NIST Arabic-English tasks, the algorithm's scalability was evident. It processed 1,953 out of 2,075 lattices within a 10-second limit, whereas the baseline completed only 1,405. In the most extreme cases, processing time dropped from 6,700 seconds to just 1,000 seconds. Furthermore, the method successfully integrated a bilingual neural network language model (BiLM), yielding BLEU score gains of ~0.8 to 1.0 points.
Conclusion
By treating semiring weights as a metadata trail rather than just costs, this work enables efficient disambiguation of massive, non-functional lattices. The use of sparse vectors minimizes computational overhead, making it a viable solution for real-time integration into decoding pipelines for speech and translation engines. Future work may focus on further optimizing the two-pass expansion required after minimization to streamline the implementation.
Summary updated