Unconstrained Word Graph Based Keyword Spotting

Zhen Zhang, Yujing Si, Yong Liu, Qingwei Zhao, Yonghong YanProceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013) 2013 · DOI

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.

System architecture for keyword spotting, illustrating the index and search stages.

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.

Performance comparison between traditional Trigram Lattices and the proposed UWGE Lattices across two 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

Abstract

The performance of keyword spotting system suffers severe degradation when the index stage is so fast that the lattice may lose lots of information to retrieve the spoken terms . In this paper , We focus on this problem and present an approach named unconstraint word graph expansion (UWGE) to keep the pruned hypotheses which are discarded in the decoding procedure but may contain correct hypotheses. The proposed approach is to eliminate the N-gram language model state limitation of lattice and reconstruct lattice to unconstrained word graph. On two Mandarin conversation telephone speech sets, we compare performance using UWGE with that on traditional trigram lattice , and our approach gives satisfying performance gains over trigram lattice. We also show the relationship between the performance and the system speed based on this approach.
BibTeX
@inproceedings{zhang2013unconstrained,
  author = {Zhen Zhang and Yujing Si and Yong Liu and Qingwei Zhao and Yonghong Yan},
  title = {{Unconstrained Word Graph Based Keyword Spotting}},
  booktitle = {Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013)},
  year = {2013},
  doi = {10.2991/iccsee.2013.251},
}

Loading related content...

Figure