TL;DR
This paper introduces a novel pruning criterion for Large Vocabulary Continuous Speech Recognition (LVCSR) decoders, based on predicting when different acoustic paths will merge. This allows for significantly more aggressive pruning of the search space, leading to substantial speedups without sacrificing accuracy.
What Problem Does This Paper Address?
Efficiently decoding speech in LVCSR systems is a major challenge. The search space of possible word sequences and their corresponding acoustic and language model scores can be astronomically large. To make decoding feasible in real-time, systems employ "pruning" techniques to discard unlikely paths. While many heuristics exist, particularly for dynamic network decoders, the authors argue that these are often approximations of a more fundamental principle: anticipating when different acoustic paths will naturally converge. They aim to formalize this principle into a more principled and effective pruning strategy.
Methods
The core contribution is an "abstract pruning criterion" based on anticipated path recombination. The idea is that if two acoustic paths are likely to merge soon (i.e., they will share a common state in the acoustic model), then their future acoustic scores will be very similar. The primary difference between them will then be due to the language model. This allows for much tighter pruning than if the paths were expected to diverge for a long time.
Since directly calculating this abstract criterion is computationally prohibitive, the authors derive practical approximations:
- Symmetric Recombination Interval: They focus on recombination at word boundaries, a common bottleneck. They define a "recombination line" and approximate the interval until paths merge based on their distance to this line.
- Asymmetric Body Pruning: This method prunes states in the "body" of a word based on their predicted recombination interval with other states. It leverages precomputed distances to the recombination line.
- Recombination Set Pruning: This extends the idea to states in the "fan-out" and "fan-in" of words, considering which parts of the recombination line are reachable from a given state.
- Fan-Out Short Word Pruning: This specifically targets the common case where short words follow fan-out states, exploiting the predictable delay in recombination.
Datasets
The experiments were conducted on the RWTH Aachen Quaero English ASR system. This system uses a lexicon of 158k words, 45 phonemes, and a 4-gram language model with 50M n-grams. The acoustic model has 4501 Gaussian mixture models. The test corpus consists of 1482 segments totaling 3.4 hours of speech. They also mention verifying results on a similar Quaero Polish task.
Key Insights and Ideas
- Pruning as Anticipating Convergence: The paper reframes pruning not just as discarding low-probability paths, but as intelligently predicting when paths will naturally merge, thus becoming indistinguishable acoustically.
- Word Boundaries as Key Recombination Points: The authors highlight that most significant path recombination in LVCSR occurs at word boundaries, making this a prime target for optimization.
- Trade-offs in Pruning Complexity: The paper demonstrates a clear trade-off between the sophistication of the pruning method (e.g., recombination set pruning) and its computational overhead. Simpler methods like "body pruning" offer good gains with minimal cost, while more complex ones like "recombination set pruning" offer greater search space reduction but at a higher runtime cost.
- Short Word Pruning as an Approximation: The "Fan-Out Short Word Pruning" method is shown to be a good approximation of the more complex "Recombination Set Pruning," offering similar search space reduction with significantly less overhead.
- LM Look-ahead is Crucial: The authors found that non-approximated, full-order LM look-ahead is essential for their pruning methods to work effectively, as it ensures smooth LM score distributions necessary for accurate recombination prediction.
Key Results
The proposed pruning methods achieve significant improvements:
- Search Space Reduction:
- Body pruning: ~20% reduction.
- Recombination set pruning: ~50% reduction.
- Short word pruning: ~40% reduction.
- Real-Time Factor (RTF) Improvement: Short word pruning achieved a ~20% reduction in RTF at equal precision, making it the most effective method in terms of speed.
- Accuracy: The methods allow for substantial search space reduction at equal precision (i.e., without degrading Word Error Rate - WER).
Limitations and Future Work
- Parameter Tuning: The authors acknowledge that tuning the various parameters (fCONV, fDIS, fa, fL, fsw) is complex due to their interdependencies.
- WFST Decoders: The authors express strong interest in applying their methods to Weighted Finite State Transducer (WFST) decoders, where LM scores are inherently smoother and a lack of advanced pruning exists.
- Search Network Structure: They suggest that current WFST search networks, optimized for determinization, might not be ideal for their pruning criterion. Partially nondeterminizing the search network could potentially optimize pruning based on anticipated path recombination.
- Static Overhead: Recombination set pruning has a notable static runtime overhead, making it less competitive in faster configurations unless very close to optimal WER.
Summary updated