TL;DR
This paper introduces an improved incremental graph composition algorithm for speech recognition that incorporates "label pushing." This technique pushes word labels towards the beginning of words within the decoding graph, allowing for more efficient merging of common word suffixes and significantly reducing the final graph size. The result is a more compact decoding graph that is nearly as small as those produced by traditional methods but achieved with a more memory-efficient incremental approach.
What Problem Does This Paper Address?
Building efficient decoding graphs for speech recognition is crucial for fast and accurate recognition. Traditional methods involve a complex process of determinization, composition, and minimization of finite state transducers (FSTs). While effective, this can lead to very large intermediate and final graphs, consuming significant memory. Previous work by the authors introduced an "incremental composition" approach that avoids large intermediate graphs by interleaving composition and minimization steps. However, this method had a limitation: word labels had to align precisely with word boundaries, limiting the effectiveness of minimization. This paper addresses this limitation by enhancing the incremental approach with "label pushing," aiming to achieve graph sizes comparable to traditional methods while retaining the memory efficiency of the incremental approach.
Methods
The core of the paper is an updated incremental graph composition algorithm that integrates "label pushing." The authors build upon their previous incremental composition method, which constructs the decoding graph by composing smaller segments locally and immediately minimizing them. The key innovation here is the incorporation of label pushing, a technique that moves output labels (representing words) towards the initial states of the graph. This is achieved by introducing a special symbol to mark word ends and then pushing the word labels relative to these markers. This allows for the merging of common word suffixes that might not have been merged if labels were strictly fixed to word boundaries. The algorithm is described in two passes: the first pass handles left-context-dependent prefix trees, and the second pass establishes cross-word connections.
Datasets
Not discussed in the paper. The paper refers to using "English" and "Arabic" models for evaluation, implying standard speech recognition datasets were used, but specific dataset names are not provided.
Key Insights and Ideas
- Label pushing unlocks more minimization: By allowing word labels to be "pushed" towards the beginning of words, common word suffixes can be merged more effectively, leading to smaller graphs.
- Incremental composition + label pushing = best of both worlds: The paper demonstrates that combining the memory efficiency of incremental composition with the graph size reduction of label pushing yields highly compact decoding graphs.
- Context-dependent prefix trees are key for cross-word context: The two-pass approach, utilizing context-dependent prefix trees in the first pass, effectively handles cross-word phonetic contexts.
- Special symbols are needed for word boundary alignment: The use of a special symbol to mark word ends is essential for the decoder to correctly identify word alignments, even after label pushing.
Key Results
The paper reports significant reductions in graph size when using the incremental composition with label pushing. For an English model, the number of states and arcs is reduced compared to the incremental approach without label pushing. For an Arabic 4-gram system, the graph size reduction is even more substantial. While the graph size reduction is impressive, the paper notes that the improvement in decoding speed is only "small" for the Arabic 4-gram system, suggesting that graph size is not the sole determinant of decoding performance.
Limitations and Future Work
The authors acknowledge that the introduction of special labels for word ends presents a limitation compared to standard composition, as it restricts label pushing outside of word boundaries and can, in rare cases, reduce the minimization effect. They also note that while graph size reduction is significant, the impact on decoding speed is not always proportional. Future work could explore further optimizations for decoding speed and investigate the impact of label pushing on different types of language models and acoustic contexts.
Summary updated