Abstract
This paper introduces "predictive pruning," a novel approach to accelerate the decoding process in Automatic Speech Recognition (ASR), particularly for complex Dynamic Graphical Models (DGMs). By utilizing online adaptive filtering techniques like Least Mean Squares (LMS), the proposed method predicts the maximum scores of future search paths. This allows the decoder to discard unlikely hypotheses much earlier than traditional methods. Experimental results on the SVitchboard corpus demonstrate a 2x speedup in decoding time with no degradation in Word Error Rate (WER), effectively overcoming the computational bottlenecks inherent in high-dimensional state spaces.
Introduction
The decoding stage in ASR is essentially a massive search problem aimed at finding the most likely sequence of words given an acoustic signal. To manage the exponential growth of the search space, decoders employ pruning techniques to eliminate low-scoring hypotheses. The most common approach, beam pruning, keeps only those paths whose scores fall within a specific range of the current best score ($M_t$).
However, a fundamental "chicken-and-egg" problem exists: to prune effectively during the expansion of a search state, the maximum score of that state must be known. In complex models, this value is only available after the expansion is complete, missing the opportunity for significant computational savings. This issue is magnified in Dynamic Graphical Models (DGMs), where entangled state spaces make exact inference and standard pruning computationally expensive.
Predictive Pruning via Adaptive Filtering
The authors propose to break this dependency by predicting the maximum score ($\tilde{M}_t$) instead of waiting for its calculation. This prediction is performed using standard signal processing algorithms, specifically online adaptive filters such as Least Mean Squares (LMS) and Recursive Least Squares (RLS).
The core insight is that the maximum scores in a speech decoder do not fluctuate randomly; they follow a smooth, gradually decreasing trend over time. This predictability makes them ideal candidates for linear adaptive filters. The pruning rule is modified such that a hypothesis is discarded if its current score, combined with a "continuation heuristic" (an estimate of its future potential), falls below the predicted maximum score minus a predefined beam width ($b$).
Online Learning and Implementation
A key feature of this approach is its "online" nature. As the decoder progresses through the audio, it calculates the actual maximum score ($M_t$) for each completed time step. The error between the prediction ($\tilde{M}_t$) and the actual value ($M_t$) is then used to update the filter's parameters ($\theta$) on the fly.
This continuous learning allows the filter to adapt to the specific characteristics of the audio signal and the model's behavior. The computational overhead of running an LMS filter is negligible compared to the cost of state expansion in a DBN, resulting in a highly favorable cost-to-benefit ratio.
Experimental Results
The method was evaluated using the SVitchboard corpus, a subset of Switchboard-I, on a 500-word vocabulary task. The model used was a Dynamic Bayesian Network (DBN) with a trigram language model, featuring a state space of approximately $10^{11}$—a scale where exact inference is impossible.
Key findings include:
- 2x Speedup: Predictive pruning reached a 47% WER in approximately 6,000 seconds, while standard beam pruning required 12,000 seconds to achieve the same accuracy.
- Accuracy Preservation: Unlike many heuristic speed-up techniques, predictive pruning maintained the exact same WER as standard, slower methods.
- Filter Robustness: Even simple 2nd or 3rd-order LMS filters provided significant gains, with relative prediction errors consistently staying within 0.3%.
- Memory Efficiency: The system operated within 2GB of RAM, a stark contrast to the estimated >100GB required for exact decoding.
Conclusion
Predictive pruning represents a significant advancement in efficient decoding for complex speech models. By leveraging the temporal predictability of search scores through online adaptive learning, it successfully decouples pruning decisions from search completion. While demonstrated on a 500-word task, the principles of predictive pruning are potentially applicable to Large Vocabulary Continuous Speech Recognition (LVCSR) and modern neural-network-based architectures.
Summary updated