Abstract
The performance of keyword spotting systems suffers severe degradation when the index stage is so fast that the lattice may lose critical information. This paper presents an approach named Unconstrained Word Graph Expansion (UWGE) to retain pruned hypotheses that are typically discarded during decoding but may contain correct keywords. By eliminating N-gram language model state limitations and reconstructing the lattice into an unconstrained word graph, the system achieves significant performance gains. Evaluations on Mandarin conversational telephone speech demonstrate that UWGE outperforms traditional trigram lattices in both recall and error rates.
Introduction: The Speed-Accuracy Trade-off
In Spoken Term Detection (STD), processing massive volumes of audio data requires high-speed indexing. Systems typically follow a two-stage architecture: indexing and searching. During indexing, an Automatic Speech Recognizer (ASR) generates a "lattice"—a directed graph of possible word or syllable sequences.
The primary bottleneck occurs when indexing speed is prioritized (e.g., 0.36x Real-Time). To maintain speed, the ASR aggressively prunes the search space. In standard N-gram lattices, nodes represent both a time boundary and a language model (LM) state. Paths that do not lead to a valid sentence ending are discarded as "dead paths." However, these dead paths often contain the specific keywords a user is searching for, leading to high miss rates in high-speed environments.
Methods: Unconstrained Word Graph Expansion (UWGE)
To mitigate information loss, the authors propose Unconstrained Word Graph Expansion (UWGE). The core innovation lies in decoupling time from the language model state.
In a traditional trigram lattice, a node is constrained by its N-gram history. If this history fails to align with future sentence structures, the preceding arcs are deleted. UWGE redefines nodes to represent time only. By removing LM state limitations:
- Independent Arcs: Arcs with identical time boundaries connect to the same nodes regardless of their linguistic history.
- Preserving Dead Paths: Pruned paths are no longer automatically deleted; they remain in the "unconstrained" graph, preserving local evidence that might be globally improbable but locally accurate for a keyword.
- Sausage-like Structure: The resulting graph is denser, retaining a significantly higher percentage of hypotheses generated during initial decoding.
This modification is confined to the indexing stage, allowing the search algorithm to remain unchanged while benefiting from increased recall.
Experimental Setup
The UWGE approach was evaluated on two Mandarin Conversational Telephone Speech (CTS) datasets:
- Set1: 1 hour of controlled laboratory audio with 100 keywords (397 occurrences), featuring standard accents and minimal noise.
- Set2: 10 hours of real-world audio with strong regional accents and background noise, featuring 100 keywords (1,934 occurrences). Both sets used an acoustic model trained on 400 hours of Mandarin CTS data.
Key Results
The UWGE approach consistently outperformed traditional trigram lattices across all primary metrics on both datasets.
Key improvements include:
- Equal Error Rate (EER): A relative reduction of approximately 10.61% on average.
- Figure of Merit (FOM): A 9.29% relative improvement, indicating superior detection across various false alarm rates.
- Max Recall: Improved by 6.76%, confirming that keywords previously pruned in standard lattices were successfully recovered.
- Graph Error Rate (GER): On Set1, the GER dropped from 29.48% to 22.69%, proving the unconstrained graph is a more accurate representation of the underlying speech.
Discussion and Future Work
UWGE demonstrates that for keyword spotting, local acoustic evidence is often more valuable than global sentence probability. By increasing the information density—keeping nearly 7 times more hypotheses per frame than standard lattices—the system bridges the "recall gap" inherent in high-speed indexing.
Future research could address the slight "accuracy loss" caused by merging arcs with identical start and end nodes, which may obscure specific path probabilities. Additionally, exploring the memory overhead of these denser graphs and testing the approach on non-tonal or morphologically complex languages would further validate the generalizability of UWGE.
Summary updated