An A* algorithm for very large vocabulary continuous speech recognition

An A* algorithm for very large vocabulary continuous speech recognition I P. Kenny, R. Hollan 2, G. Boulianne, H. Garudadri, M. Lennig 2 and D. O'Shaughnessy INRS-T616communications 3 Place du Commerce Montreal, Quebec, Canada H3E 1H6 ABSTRACT We present a new search algorithm for very large vocabulary contin- uous speech recognition. Continuous speech recognition with this algorithm is only about 10 times more computationally expensive than isolated word recognition. We report preliminary recognition results obtained by testing our recognizer on "books on tape" using a 60,000 word dictionary. 1. Introduction In this paper we will give a preliminary report on our efforts to extend our earlier work on very large vocabulary isolated word recognition [16, 17, 19] to continuous speech tasks. We are aiming to perform speaker-dependent continuous speech recognition using a trigram language model and a vocabulary of 50,000-100,000 words. Although the problem of very large vocabulary isolated word recognition has largely been solved [I, 19], no experiments have yet been conducted in continuous speech recognition with comparably large vocabularies because the search prob- lem is so formidable. The best known approach to the search problem uses the word as the fundamental search unit and a stack decoding algorithm [II, 20] (also known as an A* search [14]). The effectiveness of this approach depends on having a good fast match strategy to identify candidate words whenever a word boundary is hypothesized. Many different fast match algorithms have been proposed [3, 4, 5, 15] but they have yet to be shown to perform satisfactorily on con- tinuous speech tasks having a vocabulary larger than 5,000 words [2]. An alternative approach developped by Phillips [6] (on a 103300 word vocabulary in German) uses the phoneme as the fundamental search unit and consists ofa Viterbi search of the hidden Markov model obtained by combining phoneme HMMs with a Markovian language model (such as a trigram model). Aggressive pruning is necessary since the search space is very large. (For instance, if a trigram language model is used then one copy of the lexical tree is needed for every possible bigram.) The phoneme inventory is surf- icently small that exact matches can be calculated whenever 1This work was supported by the Natural Sciences and Engineering Re- search Council of Canada 2Also with Bell-Northern Research, Montreal, Canada they are needed. However, it remains to be seen whether the phoneme unit is capable of attaining respectable accuracies on very large-scale recognition tasks. A new type of bi-directional search strategy has emerged re- cently. The basic idea is to guide the search by means of a heuristic obtained by first carrying out an inexpensive search in the reverse time direction (subject to relatively weak lin- guistic and/or lexical constraints). This type of approach appears to have been discovered independently by several groups and has been shown to work effectively on a variety of applications [8, 9, 16]. In [16] we presented a very efficient algorithm for very large vocabulary isolated word recogni- tion using this paradigm and …

Content truncated to 500 words