Inverting the point process model for fast phonetic keyword search

Keith Kintzley, Aren Jansen, Kenneth Church, Hynek HermanskyInterspeech 2012

TL;DR

This paper introduces a novel approach to keyword spotting that dramatically speeds up search times by reframing speech as a sparse sequence of phonetic events rather than a dense frame-by-frame representation. By inverting the typical convolution process, they achieve over 500,000x real-time search speeds with minimal loss in accuracy, making real-time, large-scale keyword search more feasible.

What Problem Does This Paper Address?

Current state-of-the-art spoken term detection (STD) systems, while accurate, are computationally expensive. They often rely on complex Automatic Speech Recognition (ASR) pipelines, leading to large index sizes and significant processing overhead for both index construction and querying. This makes them impractical for scenarios with continuously streaming audio or when rapid updates to the searchable index are needed. The paper aims to overcome these limitations by developing a much faster and more efficient keyword search mechanism.

Methods

The core innovation lies in inverting the standard convolution operation used in keyword spotting. Instead of processing speech frame-by-frame and convolving it with a keyword model, the authors represent speech as a sparse sequence of phonetic "impulses" (events). The keyword is then modeled as a set of filters, where each filter's impulse response corresponds to a phone. The detection function, which indicates the likelihood of a keyword, is computed by convolving the impulse train of phonetic events with these filters.

To achieve computational efficiency, they approximate the detection function with upper bounds. This allows them to avoid dense frame-by-frame calculations and instead focus on processing the sparse phonetic events. The key insight is that the detection function's changes are primarily driven by events entering or leaving a search window. By processing these events incrementally, the computation becomes linear in the number of phonetic events, rather than the number of frames, leading to significant speedups. They explore various bounding techniques, from a simple "bag-of-phones" approach to more refined multi-segment bounds, to balance computational savings with accuracy.

Datasets

The experiments were conducted on the Wall Street Journal (WSJ) datasets, specifically the WSJO and WSJ1 corpora. These datasets were partitioned into two folds, each containing 23 hours of speech. A list of 1521 keywords was extracted from the WSJ corpus for evaluation.

Key Insights and Ideas

  • Sparse Representation is Key: Representing speech as a sparse sequence of phonetic events, rather than dense frames, is the fundamental enabler of speedup.
  • Inverting the Convolution: Shifting from frame-based convolution to event-based processing dramatically reduces computational complexity.
  • Event-Driven Updates: The detection function only needs to be updated when phonetic events enter or leave the search window, leading to significant efficiency gains.
  • Bounding for Speed: Approximating the detection function with upper bounds is crucial for achieving real-time performance, with a trade-off between the tightness of the bound and computational cost.
  • Phonetic Timing Matters (but can be approximated): While precise phonetic timing is important for accuracy, simpler bounds that ignore some timing information can still yield good results with massive speedups.

Key Results

The paper demonstrates substantial speedups with minimal loss in accuracy.

  • A C++ implementation of the D-segment bound achieved search speeds over 500,000x faster than real-time.
  • Compared to a direct implementation, the simple upper bound (java) was 57x faster but resulted in a 75% relative decrease in average Figure of Merit (FOM).
  • A 3-segment upper bound (java) reduced speed by only 8% while recovering almost all of the FOM loss.
  • A D-segment bound (java) offered virtually identical FOM performance to the direct implementation, with a speedup of around 374,195x real-time.

Limitations and Future Work

  • Simple Upper Bound Looseness: The paper notes that the simplest "bag-of-phones" upper bound is loose and leads to poor performance, especially with non-oracle phonetic data.
  • MAP-based Models: The authors mention that their current experiments use Maximum Likelihood Estimation (MLE) for model parameters, but they have recently demonstrated that MAP-based models require significantly less training data and are a promising direction for future work.
  • Further Bound Refinement: While the D-segment bound is effective, the paper suggests that further refinement of these multi-segment bounds could potentially improve accuracy while maintaining speed.
  • Real-time Streaming: The presented approach is well-suited for real-time streaming, but further work could explore its integration into live systems with dynamic index updates.

Summary updated

BibTeX
@inproceedings{kintzley2012inverting,
  author = {Keith Kintzley and Aren Jansen and Kenneth Church and Hynek Hermansky},
  title = {{Inverting the point process model for fast phonetic keyword search}},
  booktitle = {Interspeech},
  year = {2012},
}
Figure