Metric subspace indexing for fast spoken term detection

Taisuke Kaneko, Tomoyosi AkibaInterspeech 2010

TL;DR

This paper introduces a novel indexing method for Spoken Term Detection (STD) that leverages metric space indexing and the Hough transform. By treating phoneme matching as a line detection problem in a parameter space, the method efficiently finds spoken terms without requiring predefined distance thresholds, offering a more flexible and potentially faster approach than existing techniques.

What Problem Does This Paper Address?

Spoken Term Detection (STD) aims to find occurrences of a specific query term within a spoken document. A major challenge in STD is dealing with inaccuracies from Automatic Speech Recognition (ASR), which can introduce errors like insertions, deletions, and substitutions. Existing methods often rely on text-based indexing after full transcription or use sub-word units like phonemes. However, these approaches can struggle with the multiple recognition candidates produced by ASR, require strict thresholds that can miss valid matches, or lead to increased indexing complexity. This paper addresses the need for a more robust and efficient STD method that can handle ASR uncertainties and provide flexible output without rigid thresholds.

Methods

The core of the proposed method is a novel indexing technique that maps the problem of spoken term detection to a line detection problem in a parameter space, inspired by the Hough transform.

  • Metric Space Indexing: The authors define a "distance" between a phoneme in the query and a position in the spoken document. This creates a grid where each point represents a potential match. The cumulative distance along a diagonal line in this grid corresponds to the similarity of a spoken term occurrence.
  • Hough Transform Analogy: The paper draws an analogy to the Hough transform used in image processing. In this context, a spoken term occurrence is akin to a "line" in the phoneme-position space. Detecting these "lines" allows for identifying potential matches.
  • Phoneme Distance Vectors: For each phoneme in the query, a "phoneme distance vector" is pre-calculated. This vector stores the distance from that phoneme to every position in the spoken document.
  • Metric Subspace Indexing: These pre-calculated distance vectors are then used to build an index. The authors suggest sorting these vectors to create a "stack" (represented by Sa in the paper), which allows for efficient retrieval of potential matches in increasing order of their calculated distance.
  • Handling ASR Errors: The method incorporates mechanisms to deal with insertion and deletion errors by considering neighboring phonemes and using weighted distances based on ASR confidence scores for multiple recognition candidates.

Datasets

  • Japanese STD Test Collection: The evaluation was performed using a Japanese STD test collection.
  • Corpus of Spontaneous Japanese: This collection consists of one hundred lectures.
  • Automatic Transcription: The target document's transcription was obtained using a word-based LVCSR, with reported word error rates of approximately 21% and phoneme error rates of about 17%.
  • Queries: Fifty in-vocabulary (IV) words and fifty out-of-vocabulary (OOV) words were used as queries.

Key Insights and Ideas

  • STD as Line Detection: Reframing STD as a line detection problem in a phoneme-position parameter space is a novel conceptual leap, enabling the application of established geometric algorithms.
  • Threshold-Free Output: The most significant advantage is the ability to output detection results in increasing order of distance, eliminating the need for arbitrary thresholds and offering more flexibility in retrieving results (e.g., N-best results, results within a time limit).
  • Efficient Handling of Multiple Candidates: The metric space approach naturally accommodates multiple ASR candidates by incorporating confidence weights, improving recall without drastically increasing complexity.
  • Potential for Significant Speedup: The indexing mechanism, particularly when combined with the pre-sorted phoneme distance vectors, promises substantial speed improvements over baseline methods that lack indexing.

Key Results

The experimental results, while preliminary, show promising outcomes:

  • Processing Time: The proposed method achieved a processing time of 220.4 ms for IV words and 222.6 ms for OOV words, compared to 640.2 ms and 620.6 ms respectively for the baseline method. This represents a significant speedup (approximately 3x).
  • Performance: Precision and recall remained comparable to the baseline method, indicating that the speedup was achieved without sacrificing detection accuracy.
  • Zero-Valued Elements: The authors noted that approximately 6% of the elements in the phoneme distance vectors were zero-valued. This suggests that, theoretically, processing time could be reduced to around 6% of the baseline if these zero-valued elements could be fully exploited.

Limitations and Future Work

  • Indexing Unit: The authors acknowledge that using phonemes as the indexing unit still leaves a percentage of zero-valued elements that are unavoidably searched. They suggest that using larger units like syllables or syllable n-grams could further improve efficiency.
  • Distance Measure: The Hamming distance used for Distinctive Phonetic Features (DPFs) is considered too discrete. Future work could explore more continuous distance measures, such as the Bhattacharyya distance between acoustic models, to potentially improve performance.
  • Implementation Optimization: The current implementation is described as "simplest," indicating significant room for optimization to fully realize the theoretical speedup potential.
  • Application Areas: The threshold-free output capability is highlighted as a unique advantage, and the authors plan to investigate specific application areas that can best leverage this feature.

Summary updated

BibTeX
@inproceedings{kaneko2010metric,
  author = {Taisuke Kaneko and Tomoyosi Akiba},
  title = {{Metric subspace indexing for fast spoken term detection}},
  booktitle = {Interspeech},
  year = {2010},
}
Figure