Unsupervised spoken-term detection with spoken queries using segment-based dynamic time warping

Chun-an Chan, Lin-Shan LeeInterspeech 2010 · DOI

Introduction

Spoken-term detection (STD) is a fundamental task in audio information retrieval, focused on locating specific spoken queries within large audio archives. While traditional methods rely on high-quality Automatic Speech Recognition (ASR) systems to convert audio into text or phonemes, these systems require vast amounts of labeled training data. In scenarios where such data is unavailable, unsupervised methods like Dynamic Time Warping (DTW) are employed. However, standard frame-based DTW is computationally expensive and often fails to capture the long-term phonetic structure of speech. This paper introduces a segment-based DTW approach that significantly reduces search time by grouping acoustically similar frames into stable segments.

The Computational Challenge

Traditional DTW compares raw acoustic features on a frame-by-frame basis (typically every 10ms). For large databases, this leads to a "computational explosion" because a single query and document can consist of thousands of frames. Furthermore, individual frames are often unstable and redundant, representing stationary vocal tract stages rather than distinct phonetic transitions. The proposed segment-based approach aims to mitigate these issues by operating on higher-level acoustic units.

Proposed Methodology: Segment-based DTW

The core innovation lies in transitioning from frame-level analysis to segment-level analysis through a multi-step process:

  1. Segmentation via Hierarchical Agglomerative Clustering (HAC): To identify natural boundaries in the speech signal, the authors utilize HAC. This method groups consecutive frames to minimize the sum of squared errors within segments, effectively identifying stable acoustic stages.
Hierarchical Agglomerative Clustering (HAC) process for identifying speech segments through splitting and merging operations.
  1. Defining Basic Segments: A threshold parameter ($\beta$) determines the stopping point for merging frames. This ensures segments are long enough to provide speedup but short enough to preserve critical acoustic detail.
  2. Granularity and Representation: To maintain precision, the authors introduced a granularity parameter ($M$). Each segment is represented by $M$ sub-vectors (averages of sub-segments), allowing the system to capture internal temporal structure without the full complexity of frame-based comparisons.
  3. Distance Metric: The algorithm uses a modified distance formula that accounts for segment length and penalizes differences in the internal composition of these sub-segments.

Experimental Evaluation

The system was evaluated using two datasets:

  • TIMIT: Used to validate how well unsupervised segmentation aligns with actual phonetic boundaries.
  • Mandarin Broadcast News (2001): A corpus of 5,034 utterances used for the primary spoken-term detection benchmark, featuring a test set of 42 spoken terms.

Results and Analysis

The segment-based approach was compared against a traditional frame-based DTW baseline. The results demonstrate a significant improvement in efficiency with a manageable impact on accuracy.

Performance comparison between frame-based and segment-based DTW across different granularity levels (M).

As shown in the results, the segment-based method at a granularity of $M=5$ (the identified "sweet spot") reduced CPU time by 65.4%. At lower granularity ($M=3$), the time reduction reached as high as 78.7%. While there is a slight degradation in Mean Average Precision (MAP)—dropping from 36.0% for frame-based to 31.9% for segment-based ($M=5$)—the massive gains in computational efficiency make unsupervised search far more viable for real-world applications.

Conclusion and Future Directions

By moving from frames to segments, the authors successfully addressed the redundancy and computational intensity of traditional unsupervised STD. While the fixed boundaries of segments introduce some alignment errors compared to frame-based methods, the stability of the representation offers a robust alternative for large-scale search. Future research will focus on improving segmentation techniques to better capture phonetic transitions and refining distance measures to further close the accuracy gap with frame-based baselines.

Summary updated

BibTeX
@inproceedings{chan2010unsupervised,
  author = {Chun-an Chan and Lin-Shan Lee},
  title = {{Unsupervised spoken-term detection with spoken queries using segment-based dynamic time warping}},
  booktitle = {Interspeech},
  year = {2010},
  doi = {10.21437/interspeech.2010-262},
}
Figure