Named Entity Recognition (NER), an information extraction task, is typically applied to spoken documents by cascading a large vocabulary continuous speech recognizer (LVCSR) and a named entity tagger. Recognizing named entities in automatically decoded speech is difficult since LVCSR errors can confuse the tagger. This is especially true of out-of-vocabulary (OOV) words, which are often named entities and always produce transcription errors. In this work, we improve speech NER by including features indicative of OOVs based on a OOV detector, allowing for the identification of regions of speech containing named entities, even if they are incorrectly transcribed. We construct a new speech NER data set and demonstrate significant improvements for this task.

In this paper we investigate random forest based language model adaptation. Large amounts of out-of-domain data are used to grow the decision trees while very small amounts of in-domain data are used to prune them back, so that the structure of the trees are suitable for the desired domain while the probabilities in the tree nodes are reliably estimated. Extensive experiments are carried out and results are reported on a particular task of adapting Broadcast News language model to the MIT computer science lecture domain. We show 0.80% and 0.60% absolute WER improvement over language model interpolation and count merging techniques, respectively.

Vocabulary restrictions in large vocabulary continuous speech recognition (LVCSR) systems mean that out-of-vocabulary (OOV) words are lost in the output. However, OOV words tend to be information rich terms (often named entities) and their omission from the transcript negatively affects both usability and downstream NLP technologies, such as machine translation or knowledge distillation. We propose a novel approach to OOV recovery that uses a spoken term detection (STD) framework. Given an identified OOV region in the LVCSR output, we recover the uttered OOVs by utilizing contextual information and the vast and constantly updated vocabulary on the Web. Discovered words are integrated into system output, recovering up to 40 % of OOVs and resulting in a reduction in system error. Index Terms: language modeling, data selection, spoken term detection, oov detection

In this paper, we explore the model combination problem for rescoring Automatic Speech Recognition (ASR) hypotheses. We use minimum Empirical Bayes Risk for the optimization criterion and Deterministic Annealing techniques to search through the non-convex parameter space. Our experiments on the DARPA WSJ task using several different language models showed that our approach consistently outperforms the standard methods of model combination that optimize using 1-best hypothesis error.

Recently there has been a lot of interest in confusion network re-scoring using sophisticated and complex knowledge sources. Traditionally, re-scoring has been carried out by the N-best list method or by the lattices or confusion network dynamic programming method. Although the dynamic programming method is optimal, it allows for the incorporation of only Markov knowledge sources. N-best lists, on the other hand, can incorporate sentence level knowledge sources, but with increasing N, the re-scoring becomes computationally very intensive. In this paper, we present an elegant framework for confusion network re-scoring called `iterative decoding'. In it, integration of multiple and complex knowledge sources is not only easier but it also allows for much faster re-scoring as compared to the N-best list method. Experiments with language model re-scoring show that for comparable performance (in terms of word error rate (WER)) of iterative decoding and N-best list re-scoring, the search effort required by our method is 22 times less than that of the N-best list method.

This paper presents the advantages of augmenting a word-based system with sub-word units as a step towards building open vocabulary speech recognition systems. We show that a hybrid system which combines words and data-driven, variable length sub word units has a better phone accuracy than word only systems. In addition the hybrid system is better in detecting Out-Of-Vocabulary (OOV) terms and representing them phonetically. Results are presented on the RT-04 broadcast news and MIT Lecture data sets. An FSM-based approach to recover OOV words from the hybrid lattices is also presented. At an OOV rate of 2.5 % on RT-04 we observed a 8 % relative improvement in phone error rate (PER), 7.3 % relative improvement in oracle PER and 7 % relative improvement in WER after recovering the OOV terms. A significant reduction of 33 % relative in PER is seen in the OOV regions. Index Terms: hybrid LVCSR system, out-of-vocabulary, subword unit selection, phone recognition, OOV detection

This paper addresses the adjustment of the language model (LM) scaling factor of an automatic speech recognition (ASR) system for a new domain using only un-transcribed speech. The main idea is to replace the (unavailable) reference transcript with an automatic transcript generated by an independent ASR system, and adjust parameters using this sloppy reference. It is shown that despite its fairly high error rate (ca. 35%), choosing the scaling factor to minimize disagreement with the erroneous transcripts is still an effective recipe for model selection. This effectiveness is demonstrated by adjusting an ASR system trained on Broadcast News to transcribe the MIT Lectures corpus. An ASR system for telephone speech produces the sloppy reference, and optimizing towards it yields a nearly optimal LM scaling factor for the MIT Lectures corpus. Index Terms: LVCSR, language modeling, domain adaptation, semi-supervised learning, unsupervised learning

I am very grateful for the award you have

We present a novel language model capable of incorporating various types of linguistic information as encoded in the form of a token, a (word, label)-tuple. Using tokens as hidden states, our model is effectively a hidden Markov model (HMM) producing sequences of words with trivial output distributions. The transition probabilities, however, are computed using a maximum entropy model to take advantage of potentially overlapping features. We investigated different types of labels with a wide range of linguistic implications. These models outperform Kneser-Ney smoothed n-gram models both in terms of perplexity on standard datasets and in terms of word error rate for a large vocabulary speech recognition system.

The random forest language model (RFLM) has shown encouraging results in several automatic speech recognition (ASR) tasks but has been hindered by practical limitations, notably the space-complexity of RFLM estimation from large amounts of data. This paper addresses large-scale training and testing of the RFLM via an efficient disk-swapping strategy that exploits the recursive structure of a binary decision tree and the local access property of the tree-growing algorithm, redeeming the full potential of the RFLM, and opening avenues of further research, including useful comparisons with n-gram models. Benefits of this strategy are demonstrated by perplexity reduction and lattice rescoring experiments using a state-of-the-art ASR system. Index Terms: random forest language model, large-scale training, data scaling, speech recognition

We present an application of randomization techniques to class-based n-gram language models used in speech recognizers. The idea is to derive a language model from the combination of a set of random class-based models. Each of the constituent random class-based models is built using a separate clustering obtained via a different run of a randomized clustering algorithm. The random class-based model can compensate for some of the shortcomings of conventional class-based models by combining the different solutions obtained through random clusterings. Experimental results show that the combined random class-based model improves considerably in perplexity (PPL) and word error rate (WER) over both the n-gram and baseline class-based models.

The structured language model (SLM) aims at predicting the next word in a given word string by making a syntactical analysis of the preceding words. However, it faces the data sparseness problem because of the large dimensionality and diversity of the information available in the syntactic parsing. Previously, we proposed using neural network models for the SLM (Emami, A. et al., Proc. ICASSP, 2003; Emami, Proc. EUROSPEECH'03., 2003). The neural network model is better suited to tackle the data sparseness problem and its use gave significant improvements in perplexity and word error rate over the baseline SLM. We present a new method of training the neural net based SLM. This procedure makes use of the partial parsing hypothesized by the SLM itself, and is more expensive than the approximate training method used previously. Experiments with the new training method on the UPenn and WSJ corpora show significant reductions in perplexity and word error rate, achieving the lowest published results for the given corpora.

In this paper, we explore the use of Random Forests (RFs) in the struc- tured language model (SLM), which uses rich syntactic information in predicting the next word based on words already seen. The goal in this work is to construct RFs by randomly growing Decision Trees (DTs) us- ing syntactic information and investigate the performance of the SLM modeled by the RFs in automatic speech recognition. RFs, which were originally developed as classifiers, are a combination of decision tree classifiers. Each tree is grown based on random training data sampled independently and with the same distribution for all trees in the forest, and a random selection of possible questions at each node of the decision tree. Our approach extends the original idea of RFs to deal with the data sparseness problem encountered in language modeling. RFs have been studied in the context of n-gram language modeling and have been shown to generalize well to unseen data. We show in this paper that RFs using syntactic information can also achieve better performance in both perplexity (PPL) and word error rate (WER) in a large vocabulary speech recognition system, compared to a baseline that uses Kneser-Ney smoothing.

We investigate the performance of the Structured Language Model when one of its components is modeled by a connectionist model. Using a connectionist model and a distributed representation of the items in the history makes the component able to use much longer contexts than possible with currently used interpolated or backoff models, both because of the inherent capability of the connectionist model to fight the data sparseness problem, and because of the only sub-linear growth in the model size when increasing the context length. Experiments show significant improvement in perplexity and moderate reduction in word error rate over the baseline SLM results on the UPENN treebank and Wall Street Journal (WSJ) corpora respectively. The results also show that the probability distribution obtained by our model is much less correlated to regular N-grams than the baseline SLM model.

We study the impact of richer syntactic dependencies on the performance of the structured language model (SLM) along three dimensions: parsing accuracy (LP/LR), perplexity (PPL) and word-error-rate (WER, N-best re-scoring). We show that our models achieve an improvement in LP/LR, PPL and/or WER over the reported baseline results using the SLM on the UPenn Treebank and Wall Street Journal (WSJ) corpora, respectively. Analysis of parsing performance shows correlation between the quality of the parser (as measured by precision/recall) and the language model performance (PPL and WER). A remarkable fact is that the enriched SLM outperforms the baseline 3-gram model in terms of WER by 10% when used in isolation as a second pass (N-best re-scoring) language model.

The thesis concerns the development of a large vocabulary continuous speech recognition (LVCSR) system for highly inflectional languages, with special emphasis on the language modeling. An idea and usage of the automatic speech recognition is introduced and the basic principles of the statistical approach to the speech recognition and the decomposition of the system into basic components are explained. An overview of the existing statistical language modeling techniques is given and methods of inferring reliable probability estimates from sparse data and measures of the language model quality are described. There are offered a theoretical background to the finite-state machinery and the application of the finite-state machine framework to LVCSR. The goals of the thesis were to build a LVCSR system for the Czech language using standard techniques that were used for English and to analyze the system performance and propose and implement techniques that would improve the recognition accuracy. The development of the baseline system is described. The Czech language properties, especially from the automatic speech recognition point of view, were analyzed. The outcomes of this theoretical analysis are exploited and language models that take into account the specific features of the Czech language are presented. There is given a description of the class-based language models that strengthen the language model robustness and therefore reduce the perplexity and consequently improve the recognition accuracy. And finally a model that uses subword parts (morphemes) as the basic language modeling units is introduced. Such model offers a better coverage of an unknown text in comparison with standard word-based models given the same vocabulary size.

In state-of-art large vocabulary continuous speech recognition (LVCSR) systems, HMM state-tying is often used to achieve good balance between the model resolution and robustness. In this paradigm, tied HMM states share a single set of parameters and are nondistinguishable. To capture the fine differences among tied HMM states, a probabilistic classification of HMM states (PCHMM) is proposed in this paper for LVCSR. In particular, a distribution from a HMM state to classes is introduced. It is shown that the state-to-class distribution can be estimated together with conventional HMM parameters within the EM (Dempster et al., 1977) framework. Compared with HMM state-tying, probabilistic classification of HMM states makes more efficient use of model parameters. It also makes the acoustic model more robust against the possible mismatch or variation between training and test data. The viability of this approach is verified by the significant reduction of word error rate (WER) on the Switchboard (Godfrey et al., 1992) task.

A new language model for speech recognition inspired by linguistic analysis is presented. The model develops hidden hierarchical structure incrementally and uses it to extract meaningful information from the word history - thus enabling the use of extended distance dependencies - in an attempt to complement the locality of currently used trigram models. The structured language model, its probabilistic parameterization and performance in a two-pass speech recognizer are presented. Experiments on the SWITCHBOARD corpus show an improvement in both perplexity and word error rate over conventional trigram models.

In this paper we describe the statistical Structured Language Model (SLM) that uses grammatical analysis of the hypothesized sentence segment (prefix) to predict the next word. We first describe the operation of a basic, completely lexicalized SLM that builds up partial parses as it proceeds left to right. We then develop a chart parsing algorithm and with its help a method to compute the prediction probabilities P (w i+1 jW i ): We suggest useful computational shortcuts followed by a method of training SLM parameters from text data. Finally, we introduce more detailed parametrization that involves non-terminal labeling and considerably improves smoothing of SLM statistical parameters. We conclude by presenting certain recognition and perplexity results achieved on standard corpora. 1. INTRODUCTION In the accepted statistical formulation of the speech recognition problem [1] the recognizer seeks to find the word string c W : = arg max W P (AjW)P (W) where A denotes the observab...

The goal of this paper is to investigate various language model smoothing techniques and decision tree based language model design algorithms. For this purpose, we build language models for printable characters (letters), based on the Brown corpus. We consider two classes of models for the text generation process: the n-gram language model and various decision tree based language models. In the first part of the paper, we compare the most popular smoothing algorithms applied to the former. We conclude that the bottom-up deleted interpolation algorithm performs the best in the task of n-gram letter language model smoothing, significantly outperforming the back-off smoothing technique for large values of n. In the second part of the paper, we consider various decision tree development algorithms. Among them, a K-means clustering type algorithm for the design of the decision tree questions gives the best results. However, the n-gram language model outperforms the decision tree language models for letter language modeling. We believe that this is due to the predictive nature of letter strings, which seems to be naturally modeled by n-grams. Das Ziel dieses Beitrags ist verschiedene Techniken zur Glättung von Sprachmodellen und Algorithmen zum Entwurf von Sprachmodellen auf der Basis von Entscheidungsbäumen zu untersuchen. Zu diesem Zweck verwenden wir den Brown-Korpus um Modelle von Buchstabenfolgen zu erstellen. Wir betrachten zwei Klassen von Modellen zur Textgenerierung: das n-Gramm Sprachmodell sowie verschiedene auf Entscheidungsbäumen basierende Verfahren. Im ersten Teil dieses Beitrags vergleichen wir die am häufigsten benutzten Glättungsalgorithmen angewandt auf n-Gramme. Wir folgern, daß der “bottom-up deleted interpolation”-Algorithmus am besten zur Glättung von n-Gramm Sprachmodellen geeignet ist und für große n dem “back-off”-Verfahren deutlich überlegen ist. Im zweiten Teil dieses Beitrags betrachten wir dann verschiedene Algorithmen zur Bildung von Entscheidungsbäumen. Unter diesen erzielt ein K-means-ähnlicher Algorithmus die besten Ergebnisse beim Entwurf der Fragen die der Entscheidungsbaum stellt. Für die Modellierung von Buchstabenfolgen erzielt das n-Gramm Sprachmodell aber trotzdem noch bessere Ergebnisse als alle Entscheidungsbäume. Wir glauben, daß dies durch die Fähigkeit der n-Gramme Buchstabenfolgen vorherzusagen begründet ist. Le but de cet article est d'étudier différentes techniques de lissage de modèles de langage et différents algorithmes de construction de modèles de langage à base d'arbres de décision. Pour cela, nous construisons des modèles de langage pour des caractères écrits (lettres) à partir du Brown corpus. Nous considérons deux classes de modèles pour le processus de génération du texte: le modèle de langage n-gram, et différents modèles de langage à base d'arbres de décision. Dans la première partie de l'article, nous comparons les algorithmes de lissage les plus couramment appliqués au modèle de langage n-gram. L'algorithme “bottom-up deleted interpolation” donne les meilleurs résultats pour le lissage du modèle de langage n-gram, dépassant de façon significative la technique de lissage “back-off” pour de grandes valeurs de n. Dans la seconde partie de l'article, nous considérons différents algorithmes de développement d'arbres de décision. Parmi eux, un algorithme de type classification K-means aboutit aux meilleurs résultats pour la construction des arbres de décision. Cependant, le modèle de langage n-gram fournit de meilleurs résultats que les modèles de langage à arbres de décision pour la modélisation du langage écrit. Nous croyons que cela est dû à la nature prédictive des chaı̂nes de caractères, qui semble être naturellement modélisée par les n-grams.

We describe a generative probabilistic model of natural language, which we call HBG, that takes advantage of detailed linguistic information to resolve ambiguity. HBG incorporates lexical, syntactic, semantic, and structural information from the parse tree into the disambiguation process in a novel way. We use a corpus of bracketed sentences, called a Treebank, in combination with decision tree building to tease out the relevant aspects of a parse tree that will determine the correct parse of a sentence. This stands in contrast to the usual approach of further grammar tailoring via the usual linguistic introspection in the hope of generating the correct parse. In head-to-head tests against one of the best existing robust probabilistic parsing models, which we call P-CFG, the HBG model significantly outperforms P-CFG, increasing the parsing accuracy rate from 60% to 75%, a 37% reduction in error.

A method for assigning a word to many classes based on the context in which the word occurs is presented. A trigram language model is used to determine the classes which are called statistical synonyms for that word. This classification method is used to build an adaptive language model that incorporates unknown words after their first occurrence by using their statistical synonyms in determining the model's probabilities for the added words. It is shown that the dynamic coverage of the language model increases significantly with a rather low perplexity on the added words.>

A description is presented of the authors' current research on automatic speech recognition of continuously read sentences from a naturally-occurring corpus: office correspondence. The recognition system combines features from their current isolated-word recognition system and from their previously developed continuous-speech recognition system. It consists of an acoustic processor, an acoustic channel model, a language model, and a linguistic decoder. Some new features in the recognizer relative to the isolated-word speech recognition system include the use of a fast match to prune rapidly to a manageable number the candidates considered by the detailed match, multiple pronunciations of all function words, and modeling of interphone coarticulatory behavior. The authors recorded training and test data from a set of ten male talkers. The perplexity of the test sentences was found to be 93; none of sentences was part of the data used to generate the language model. Preliminary (speaker-dependent) recognition results on these talkers yielded an average word error rate of 11.0%.>

The Speech Recognition Group at IBM Research in Yorktown Heights has developed a real-time, isolated-utterance speech recognizer for natural language based on the IBM Personal Computer AT and IBM Signal Processors. The system has recently been enhanced by expanding the vocabulary from 5,000 words to 20,000 words and by the addition of a speech workstation to support usability studies on document creation by voice. The system supports spelling and interactive personalization to augment the vocabularies. This paper describes the implementation, user interface, and comparative performance of the recognizer.

The Speech Recognition Group at IBM Research in Yorktown Heights has designed a real-time, isolated-utterance speech recognizer for natural language with a 5,000-word vocabulary based on the IBM Personal Computer (PC) AT model and two IBM Signal Processors realized in VLSI technology. The enrollment period for a new user is approximately 20 minutes. The basic vocabulary is chosen from the most common words in several collections of documents such as office memoranda and business letters. The system supports spelling and interactive personalization to augment this vocabulary. Signal processing, vector quantization, and acoustic matching algorithms are programmed on the IBM Signal Processors which fit into the PC AT chassis. The PC AT controls the Processors and implements the decoder stack search and the language model, as well as the application-specific interface. The modular architecture of the design is expandable to a 20,000-word vocabulary system by the addition of two more IBM Signal Processors housed in a PC Expansion Unit.

The Speech Recognition Group at IBM, Yorktown Heights, has recently completed the implementation of an experimental, real-time, isolated-word, speech recognition system with a 5,000-word vocabulary which can be used for dictating office correspondence. Typical recognition accuracy is greater than 94% correct word recognition for words within the vocabulary. We first describe the architecture of this system, and then give some recent experimental results obtained with it for read and spontaneously dictated speech from five speakers.

This paper describes an experimental real-time recognizer of isolated word dictation implemented at the IBM Thomas J. Watson Research Center, on a system of commercially available computers and array processors. The recognizer's intended use is creation of office memoranda. It is based on a 5000-word vocabulary. A specially designed workstation enables the user to correct and edit the transcribed speech. The paper outlines the self-organized, statistical approach underlying the basic algorithms of the recognizer. Results of several recognition experiments are then presented. The rest of the paper considers important issues in the future development of dictation recognizers, such as vocabulary selection, language model creation, and human factors.

This paper deals with two experiments with a large vocabulary isolated word recognizer. The first compares word error rates for 1) meaningful sentences belonging to actual documents and 2) random word lists from the same vocabulary. The error rate is considerably lower for random word lists. The second experiment investigates the performance of the recognition system on sentences containing words outside the vocabulary of the recognizer. Sentences from a 5000 word vocabulary task are recognized with a recognizer limited to a 2000 word subvocabulary. The error rate is only slightly higher than it would be if recognition of the full 5000 word vocabulary was allowed.

Recognition results on sentences from a 5000-word vocabulary drawn from office correspondence are presented. The sentences were read with pauses between the words. The vocabulary comprises the 5000 most frequently occurring words in a data-base of 14,000 office memoranda and letters, and has a perplexity of 90, measured from a trigram language model. Experiments were carried out with 6 speakers (4 male, 2 female) in an office environment using a close-talking microphone. The recognition system was automatically trained to each speaker by having the speaker read 100 typical sentences from the office correspondence data-base. Recognition was carried out for each speaker on 20 test sentences, consisting of 299 words. The recognition rate (% words correct) averaged across the 6 speakers was 94.5%.

Speech recognition is formulated as a problem of maximum likelihood decoding. This formulation requires statistical models of the speech production process. In this paper, we describe a number of statistical models for use in speech recognition. We give special attention to determining the parameters for such models from sparse data. We also describe two decoding methods, one appropriate for constrained artificial languages and one appropriate for more realistic decoding tasks. To illustrate the usefulness of the methods described, we review a number of decoding results that have been obtained with them.

The stack linguistic decoder described in references (1,3,6) has been modified to operate directly on continuous parameter vectors produced by an acoustic processor, thereby bypassing entirely labeling and segmentation of the speech signal. A recognition experiment has been carried out on a natural speech corpus using five-dimensional vectors composed of the four Dutch vowel factors of Klein, Plomp, and Pols, plus an indicator of short-term changes in overall power. The results are compared to those from an earlier experiment in which a centisecond labeling acoustic processor was used.

This paper describes the results of an experiment in which we have applied our speech recognition system to the problem of recognizing sentences from our restricted laser-patent corpus when the sentences are read with pauses between the words. Except for changes to the phonology and the training data, nothing has been done to adapt the system to isolated word recognition. On 20 sentences a word error rate of 3.1% was obtained. This compares with 8.7% for the same sentences when spoken continuously by the same talker.

Automatic selection of acoustic prototypes is an important step towards making speech recognition systems automatically adaptable to new speakers. Two methods for automatically obtaining a set of acoustic prototypes for use by a centisecond labeling acoustic processor are described. One method is based on bootstrapping, the other on clustering. Recognition results using these automatically obtained prototypes on the 1000-word vocabulary natural language Laser Patent task are presented. These results are compared to those from an experiment in which the acoustic prototypes were manually selected.

Further results have been obtained on the recognition of continuously read sentences from a natural language corpus of laser patents. The vocabulary is limited to the 1000 most frequently occurring words in the corpus. Our model of the task language has a perplexity of 24.1 words (corresponding to an entropy of 4.6 bits/word). This paper describes modifications and improvements to the system which have resulted in the lowering of the word error rate from the previously reported 33.1% to 8.9%.

The statistical training and decoding procedures developed at IBM Research can be used with a wide variety of acoustic processors. We have recently (July and August 1978) achieved error-free or nearly error-free decoding results with several different acoustic processors on sentences from the New Raleigh Language (vocabulary 250 words, perplexity 7.27 words). One of these processors, which achieved a 0% error rate on New Raleigh sentences, has been used to decode sentences from the New Raleigh Language without the benefit of syntactic guidance during the decoding process. On this much more difficult task, it has achieved an error rate of 8.8% at the word level, corresponding to a sentence error rate of 53%. All of these processors are non-segmenting processors which produce output once every 10ms.

We report performance results on the recognition of continuously spoken sentences from the finite state grammar for the "New Raleigh Language" (vocabulary-250 words; average sentence length-8 words; entropy-2.86 bits/word; perplexity-7.27 words). Sentence and word error rates of 5% and 0.6% , respectively, are achieved, using a new centisecond-level model for the acoustic processor. We also report results for the "CMU-AIX05 Language" (vocabulary-1011 words; average sentence length-about 7 words; entropy-2.18 bits/word; perplexity-4.53 words), using both our earlier phone-level model and the centisecond-level model. With the phone-level acoustic-processor model, sentence and word error rates of 2% and 0.8%, respectively, are achieved. With the centisecond-level model, sentence and word error rates are 1% and 0.1%, respectively.

Preliminary results have been obtained with a system for recognizing continuously read sentences from a naturally-occurring corpus (Laser Patents), restricted to a 1000-word vocabulary. Our model of the task language has an entropy of about 4.8 bits/word and a perplexity of 21.11 words. Many new problems arise in recognition of a substantial natural corpus (compared to recognition of an artificially constrained language). Some techniques are described for treating these problems. On a test set consisting of 20 sentences having a total of 486 words, there was a word error rate of 33.1%.

This report presents results obtained in some experiments on the computer recognition of continuous speech. The experiments deal with two simple languages having vocabularies of 11 and 250 words.

A model for channels in which an input sequence can produce output sequences of varying length is described. An efficient computational procedure for calculating Pr\{Y\mid X\}is devised, whereX = x_1,x_2,\cdots,x_MandY = y_1,y_2,\cdots,y_Nare the input and output of the channel. A stack decoding algorithm for decoding on such channels is presented. The appropriate likelihood function is derived. Channels with memory are considered. Some applications to speech and character recognition are discussed.

A new hybrid coding scheme is introduced that bears the same relation to Viterbi decoding as bootstrap hybrid decoding [3] bears to sequential decoding. Bounds on the probability of error are developed and evaluated for some examples. In high-rate regions of interest, the computed exponents are more than three times as large as those for Viterbi decoding. Results of simulations are also presented.

Most current attempts at automatic speech recognition are formulated in an artificial intelligence framework. In this paper we approach the problem from an information-theoretic point of view. We describe the overall structure of a linguistic statistical decoder (LSD) for the recognition of continuous speech. The input to the decoder is a string of phonetic symbols estimated by an acoustic processor (AP). For each phonetic string, the decoder finds the most likely input sentence. The decoder consists of four major subparts: 1) a statistical model of the language being recognized; 2) a phonemic dictionary and statistical phonological rules characterizing the speaker; 3) a phonetic matching algorithm that computes the similarity between phonetic strings, using the performance characteristics of the AP; 4) a word level search control. The details of each of the subparts and their interaction during the decoding process are discussed.

The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered. The decoding of linear block and convolutional codes to minimize symbol error probability is shown to be a special case of this problem. An optimal decoding algorithm is derived.

Tree codes are known to be capable of performing arbitrarily close to the rate-distortion function for any memoryless source and single-letter fidelity criterion. Tree coding and tree search strategies are investigated for the discrete-time memoryless Gaussian source encoded for a signal-power-to-mean-squared-error ratio of about 30 dB (about 5 binary digits per source output). Also, a theoretical lower bound on average search effort is derived. Two code search strategies (the Viterbi algorithm and the stack algorithm) were simulated in assembly language on a large digital computer. After suitable modifications, both strategies yielded encoding with a signal-to-distortion ratio about 1 dB below the limit set by the rate-distortion function. Although this performance is better than that of any previously known instrumentable scheme, it unfortunately requires search computation of the order ofl0^5machine cycles per source output encoded.

This paper presents the best obtainable random coding and expurgated upper bounds on the probabilities of undetectable error, oft-order failure (advance to depthtinto an incorrect subset), and of likelihood rise in the incorrect subset, applicable to sequential decoding when the metric biasGis arbitrary. Upper bounds on the Pareto exponent are also presented. TheG-values optimizing each of the parameters of interest are determined, and are shown to lie in intervals that in general have nonzero widths. TheG-optimal expurgated bound on undetectable error is shown to agree with that for maximum likelihood decoding of convolutional codes, and that on failure agrees with the block code expurgated bound. Included are curves evaluating the bounds for interesting choices ofGand SNR for a binary-input quantized-output Gaussian additive noise channel.

The problem of buffer overflow in variable-length-to-block and block-to-variable-length coding of fixed-rate finite-state homogeneous Markov sources for transmission through fixed:rate noiseless channels is investigated. Asymptotically optimal converging upper and lower bounds on the probability of overflow are derived. They decrease exponentially with the buffer sizeB. The least ratesR(\gamma)that achieve exponents\gammafor both coding methods are obtained, as are the corresponding optimal word assignments. It is shown that for the class of state-calculable sources, variable-length-to-block and block-to-variable-length ratesR(\gamma)are equal.

Since the birth of rate-distortion theory with the landmark paper of Shannon, research has centered on the extension of his theory to new situations and on the calculation of rate-distortion functions. Comparatively little has been done toward developing efficient algorithms for encoding information sources at rates near Shannon's rate-distortion limit. This paper reports one such algorithm, the 2-cycle algorithm, used with randomly chosen tree codes. In analyzing the 2-cycle algorithm, we present the first theoretical analysis of a realizable algorithm for tree coding of sources with a fidelity criterion. The algorithm may prove to be the first practical method of coding whose design actually derives from rate-distortion theory. Analysis proceeds by bounding methods related to difference equations and branching processes. Upper bounds on average distortion and encoding work are obtained and the latter are shown bounded as long as the coding rate exceeds Shannon's rate-distortion function. Of particular interest is the stack-searched branching process bound of Section IV. The two cycles of the algorithm are described fully in terms of expectations and probabilities, and recursions are listed to compute these quantities. Concluding the paper is numerical analysis, by theory and by simulation, with respect to the binary i.i.d, source and Hamming distortion measure. These numerical results are sufficient to optimize the algorithm over its free parameters.

An efficient bidirectional search algorithm for computing the free distance of convolutional codes is described.

We show what choice there is in assigning output digits to transitions of a binary rate1/ncode trellis so that the latter will correspond to a convolutional code. We then prove that in any rate\frac{1}{2}noncatastrophic code of constraint length\upsiloneach binary sequence of length2j(1 \leq j \leq \upsilon - 1)is associated with exactly2^{\upsilon -j -1}distinct pathsjbranches long. As a consequence of the above properties nondegenerate codes with branch complementarity are fully determined by the topological relationship of the trellis transitions associated with output pairs 00. Finally, we derive a new upper bound on free distance of rate1/nconvolutional codes and use our results to determine the length of the largest input sequence that can conceivably result in an output whose weight is

Source encoding techniques based on permutation codes are investigated. For a broad class of distortion measures it is shown that optimum encoding of a source permutation code is easy to instrument even for very long block lengths. Also, the nonparametric nature of permutation encoding is well suited to situations involving unknown source statistics. For the squared-error distortion measure a procedure for generating good permutation codes of a given rate and block length is described. The performance of such codes for a memoryless Gaussian source is compared both with the rate-distortion function bound and with the performance of various quantization schemes. The comparison reveals that permutation codes are asymptotically ideal for small rates and perform as well as the best entropy-coded quantizers presently known for intermediate rates. They can be made to compare favorably at high rates, too, provided the coding delay associated with extremely long block lengths is tolerable.

Variable-length-to-block codes are a generalization of run-length codes. A coding theorem is first proved. When the codes are used to transmit information from fixed-rate sources through fixed-rate noiseless channels, buffer overflow results. The latter phenomenon is an important consideration in the retrieval of compressed data from storage. The probability of buffer overflow decreases exponentially with buffer length and we determine the relation between rate and exponent size for memoryless sources. We obtain codes that maximize the overflow exponent for any given transmission rate exceeding the source entropy and present asymptotically optimal coding algorithms whose complexity grows linearly with codeword length. It turns out that the optimum error exponents of variable-length-to-block coding are identical with those of block-to-variable-length coding and are related in an interesting way to Renyi's generalized entropy function.

The structure of a class of rate\frac{1}{2}convolutional codes called complementary codes is investigated. Of special interest are properties that permit a simplified evaluation of free distance. Methods for finding the codes with largest free distance in this class are obtained. A synthesis procedure and a search procedure that result in good codes up to constraint lengths of 24 are described. The free and minimum distances of the best complementary codes are compared with the best known bounds and with the distances of other known codes.

We study here the use of tree codes to encode time-discrete memoryless sources with respect to a fidelity criterion. An easily instrumented scheme is proposed for use with binary sources and the Hamming distortion metric. Results of simulation with random and convolutional codes are given.

In this paper we derive an infinite tree code ensemble upper bound on the\nuth(\nu \leq 1)moments of the computational effort connected with sequential decoding governed by the Fano \footnote[1]{algorithm}. It is shown that the\nuth moment of the effort per decoded branch is hounded by a constant, provided the transmission rateR_{0}satisfies inequality (2), This result, although often conjectured, has previously been shown to hold only for positive integral values of\nu. For a wide class of discrete memoryless channels (that includes all symmetric channels), our bounds agree qualitatively with the lower bounds of Jacobs and Berlekamp [8].

In this paper we show that for memoryless time-discrete sources with a bounded fidelity criterion, the limiting average distortion achievable by tree codes of rateRisD, the solution of the equationR = R(D), whereR( )denotes the usual rate distortion function. Thus the performance of tree codes is as good as that of block codes. Some theoretical and experimental results are also discussed indicating that tree codes and corresponding encoding algorithms exist having for given values ofRandDan implementation complexity that is far smaller than the one obtainable from block codes.

In this paper, we develop and analyze an easily instrumentable scheme for variable length encoding of discrete memoryless fixed-rate sources in which buffer overflows result in codeword erasures at locations that are perfectly specified to the user. Thus, no loss of synchronism ever occurs. We find optimal (i.e., minimizing the probability of buffer overflow) code-wold length requirements under the Kraft inequality constraint, relative to various constant transmission ratesR, and show that these do not result in the minimal average code-word length. The corresponding bounds on the probability of buffer overflow provide a linkup between source coding and Rényi's generalized source entropy. We show, further, that codes having optimal word lengths can be constructed by the method of Elias, and we develop corresponding sequentially instrumented encoders and decoders. We show that the complexity of these encoders and decoders grows only linearly with the encoded message block lengthk, provided the sizedof the coder alphabet is a power of2, and otherwise grows no worse than quadratically withk.

In this paper, we investigate the problem of optimizing the expurgated upper bound to the probability of error associated with transmission over discrete memoryless channels. We find a general sufficient condition under which, for a given value of the parameter\varrho \varepsilon [1, \infty), the channel input distribution that leads to the optimal exponent corresponds to a constant memoryless source. We then derive a necessary and sufficient condition that the above property holds for all1 \leq \varrho < \infty(even then, different values of o would, in general, induce different optimal input distributions). Finally, we define a class of equidistant channels that includes all binary input channels, and show that for this class and all\varrho \varepsilon [1, \infty)the optimal expurgated exponent is attained by the uniform distribution over the inputs.

A discrete memoryless two-way channel is defined by a set of transmission probabilitiesP(y, \bar{y}/x, \bar{x}), wherexand are the transmitted signals, andyand\bar{y}are the received signals. Shannon showed that ifxand\bar{x}are generated independently and without regard to the past, then the rates(R, \bar{R})of information transmitted through the opposite channel directions will lie in a region ofG_{I}of the plane. The present paper investigates whetherG_{I}can be exceeded if the past is allowed to influence the selection of the input signals. Two-way channels are analyzed in order to determine the statistical characteristics of matching signal sources. Appendix I shows how independent messages can be encoded so that during communication the channel signal statistics would approach those caused by sources which generate inputs with arbitrary probabilities Pr(x/x_{-1}, \cdot, x_{-l}; y_{-1}, \cdot, y_{-l})and Pr(\bar{x}/ \bar{x}_{-1}, \cdot, \bar{x}_{-l}; \bar{y}_{-1}, \cdot, y_{-l}). Under certain natural restrictions, the binary two-way channel can be canonically decomposed into an interconnection of pairs of oppositely oriented memoryless one-way channels connected in cascade to special channels that are noiseless whenever the signal transmitted in the opposite direction is an appropriate one. Three distinct categories are defined into which the totality of all binary channels can be partitioned, according to the type of their decomposition. If the transmission probabilitiesP(y, \bar{y}/x, \bar{x})are symmetrical, equivalent channel representations can be obtained, consisting of interconnections of switches, binary adders, and independent noise sources. In the light of this characteristics of appropriate source signal generation probabilities are discussed and classes of symmetrical channels determined with the conjecture that here the best possible signal sources are memoryless.