Describes a successful approach taken at Mercedes-Benz Technology Center (MTC), with the goal of obtaining high-quality requirements specifications for cars while minimizing the additional workload of the core development teams. The system to be specified was the set of embedded systems responsible for driver and passenger comfort. The focus of the specification process was on software requirements. The basic idea was to assign and hire supplementary staff to do the job. At first glance, the overall effort of about 100 person-months to obtain the requirements specifications needed may seem quite high. Nevertheless, we are convinced that this expense represents an excellent investment. The point is that the obtained high-quality, uniform and well-structured requirements stored in a single requirements management database can be efficiently reused in subsequent development cycles for future passenger car models. This partial reuse of specifications promises two major advantages: better specifications in less time.

Initially introduced in the late 1960s and early 1970s, dynamic programming algorithms have become increasingly popular in automatic speech recognition. There are two reasons why this has occurred. First, the dynamic programming strategy can be combined with a very efficient and practical pruning strategy so that very large search spaces can be handled. Second, the dynamic programming strategy has turned out to be extremely flexible in adapting to new requirements. Examples of such requirements are the lexical tree organization of the pronunciation lexicon and the generation of a word graph instead of the single best sentence. We attempt to review the use of dynamic programming search strategies for large-vocabulary continuous speech recognition (LVCSR). The following methods are described in detail: searching using a lexical tree, language-model look-ahead and word-graph generation.

This paper presents the time-conditioned approach in dynamic programming search for large-vocabulary continuous-speech recognition. The following topics are presented: the baseline algorithm, a time-synchronous beam search version, a comparison with the word-conditioned approach, a comparison with stack decoding. The approach has been successfully tested on the NAB task using a vocabulary of 64000 words.

We describe the integration of across-word models in the RWTH large vocabulary continuous speech recognition system, where our main focus is on the realization of the acoustic recognition process. This paper presents a study of two search methods based on the principle of dynamic programming. For both methods we discuss the implementation details and give experimental results on the Verbmobil and on the Wall Street Journal data. In addition, we introduce a score interpolation of within-word and across-word models for both search methods. In combination with across-word models this interpolation technique gives an improvement of the recognition accuracy by 14% relative to our standard system.

This paper presents an efficient method for constructing high quality word graphs for large vocabulary continuous speech recognition. The word graphs are constructed in a two-pass strategy. In the first pass, a huge word graph is produced using the time-synchronous lexical tree search method. Then, in the second pass, this huge word graph is pruned by applying a modified forward-backward algorithm. To analyze the characteristic properties of this word graph pruning method, we present a detailed comparison with the conventional time-synchronous forward pruning. The recognition experiments, carried out on the North American Business (NAB) 20000-word task, demonstrate that, in comparison to the forward pruning, the new method leads to a significant reduction in the size of the word graph without an increase in the graph word error rate.

We present an overview of the RWTH Aachen large vocabulary continuous speech recognizer. The recognizer is based on continuous density hidden Markov models and a time-synchronous left-to-right beam search strategy. Experimental results on the ARPA Wall Street Journal (WSJ) corpus verify the effects of several system components, namely linear discriminant analysis, vocal tract normalization, pronunciation lexicon and cross-word triphones, on the recognition performance.

This paper describes some extensions to the language model (LM) look-ahead pruning approach which is integrated into the time-synchronous beam search algorithm. The search algorithm is based on a lexical prefix tree in combination with a word-conditioned dynamic search space organization for handling trigram language models in a one-pass strategy. In particular, we study several LM look-ahead pruning techniques. Further, we improve the efficiency of this look-ahead technique by exploiting subtree dominance. This method avoids the computation of redundant subtrees within the copies of the lexical prefix tree and thus reduces the memory requirements of the search algorithm. In addition, we present a pruning criterion depending on the state index. The experimental results on the 20000-word NAB'94 task (ARPA North American Business Corpus) indicate that the computational effort can be reduced to 4 times real time on a ALPHA5000 PC without a significant loss in the recognition accuracy.

This paper describes two methods for constructing word graphs for large vocabulary continuous speech recognition. Both word graph methods are based on a time-synchronous, left-to-right beam search strategy in connection with a tree-organized pronunciation lexicon. The first method is based on the so-called word pair approximation and fits directly into a word-conditioned search organization. In order to avoid the assumptions made in the word pair approximation, we design another word graph method. This method is based on a time conditioned factoring of the search space. For the case of a trigram language model, we give a detailed comparison of both word graph methods with an integrated search method. The experiments have been carried out on the North American Business (NAB'94) 20,000-word task.

This paper presents two look-ahead techniques for speeding up large vocabulary continuous speech recognition. These two techniques, which are referred to as language model look-ahead and phoneme look-ahead, are incorporated into the pruning process of the time-synchronous one-pass beam search algorithm. The search algorithm is based on a tree-organized pronunciation lexicon in connection with a bigram language model. Both look-ahead techniques have been tested on the 20000-word NAB'94 task (ARPA North American Business Corpus). The recognition experiments show that the combination of bigram language model look-ahead and phoneme look-ahead reduces the size of search space by a factor of about 30 without affecting the word recognition accuracy in comparison with no look-ahead pruning technique.

This paper studies algorithms for reducing the computational eort of the mixture density calculations in HMM-based speech recognition systems.These likelihood calculations take about 70 85% of the total recognition time in the RWTH system for large vocabulary continuous speech recognition.To reduce the computational cost of the likelihood calculations, we investigate several space partitioning methods.A detailed comparison of these techniques is given on the North American Business Corpus (NAB'94) for a 20 000word task.As a result, the so-called projection search algorithm in combination with the VQ method reduces the cost of likelihood computation by a factor of about 8 with no signi cant loss in the word recognition accuracy.

In this paper, we present an efficient look-ahead technique which incorporates the language model knowledge at the earliest possible stage during the search process.This so-called language model look-ahead is built into the time synchronous beam search algorithm using a tree-organized pronunciation lexicon for a bigram language model.The language model look-ahead technique exploits the full knowledge of the bigram language model by distributing the language model probabilities over the nodes of the lexical tree for each predecessor word.We present a method for handling the resulting memory requirements.The recognition experiments performed on the 20 000-word North American Business task (Nov.'96)demonstrate that in comparison with the unigram look-ahead a reduction by a factor of 5 in the acoustic search effort can be achieved without loss in recognition accuracy.

In this paper, we compare the search effort of the word conditioned and the time conditioned tree search methods.Both methods are based on a time-synchronous, left-to-right beam search using a treeorganized lexicon.Whereas the word conditioned method is well known and widely used, the time conditioned method is novel in the context of 20 000-word vocabulary recognition.We extend both methods to handle trigram language models in a one-pass strategy.Both methods were tested on a train schedule inquiry task (1 850 words, telephone speech) and on the North American Business (Nov.'94)development corpus (20 000 words).

In this paper we investigate the search effort for large vocabulary continuous speech recognition. In particular, we study the effect of different pruning techniques on the search effort and on search errors. The experimental results show that it is much more efficient in the search procedure to use a tree lexicon than a linear lexicon. For the tree search method, we study the search space in detail. For the 20 000-word task under consideration, a reasonable compromise between the search effort and the recognition accuracy can be achieved by an average number of 13 000 state hypotheses per time frame. This effort is five orders of magnitude lower than the potential size of the search space. All experiments are based on our phoneme-based large vocabulary speech recognition system used in the 1994 ARPA benchmark test [?]. 1. INTRODUCTION In a series of recognition experiments, we have successfully used the so-called time synchronous beam search algorithm which is based on using word de...