Text streams are ubiquitous and contain a wealth of information, but are typically orders of magnitude too large in scale for comprehensive human inspection. There is a need for tools that can detect and group changes occurring within text streams and substreams, in order to find, structure, and summarize these changes for presentation to human analysts. This paper describes a procedure for efficiently finding step changes, trends, bursts, and cyclic changes affecting frequencies of words, or more general lexical items, within streams of documents which may be optionally labeled with metadata. The common phenomenon of over-dispersion is accommodated using mixture distributions. A streaming implementation is described which can process data from a continuous feed. Anomalies can be detected, grouped, and rendered visually for human comprehension.

Automated spoken dialog systems require systematic procedures for evaluating performance and diagnosing problems. We present an interactive tool that provides graphical views of how callers navigate through such systems, enabling fine-grained analysis for system evaluation and business intelligence. The input is a feed of call-logs. The output is an empirical dialog trajectory analysis represented as stochastic finite state machines, accessible via the web. Complexity is managed by an automatic tokenization procedure that hides fine details until needed. Users can generate selective views of parts of the dialog at high resolution (with access to call data), or zoom out to a summary. The tool provides dialog system developers with all the information they need from a single source, and is in use with directed-dialog and natural-language applications. 1.

Spoken dialog systems are becoming increasingly common in deployed services. These systems are not perfect, and are often deployed "open-loop" - lacking in systematic procedures for diagnosing problems and for making improvements. In order to target improvements where they will have the biggest impact, two things are needed: first, methods and tools for detailed analysis of a data feed of call logs and customer audio; second, an interactive tool for presenting an intuitive view of the results to those responsible for the application. We discuss the paradigm and an implementation through which we are able to close the loop between system execution and system evolution by providing an empirical dialog trajectory analysis represented via a stochastic finite state machine. Novel graph analysis algorithms are introduced for change detection, compression and pruning for display, based on user-interface objectives.

Large margin classifiers such as support vector machines (SVM) or Adaboost are obvious choices for natural language document or call routing. However, how to combine several binary classifiers to optimize the whole routing process and how this process scales when it involves many different decisions (or classes) is a complex problem that has only received partial answers. We propose a global optimization process based on an optimal channel communication model that allows a combination of possibly heterogeneous binary classifiers. As in Markov modeling, computational feasibility is achieved through simplifications and independence assumptions that are easy to interpret. Using this approach, we have managed to decrease the call-type classification error rate for AT&T's How May I Help You (HMIHY/sup (sm)/) natural dialog system by 50 %.

A natural language spoken dialog system includes a large vocabulary automatic speech recognition (ASR) engine, whose output is used as the input of a spoken language understanding component. Two challenges in such a framework are that the ASR component is far from being perfect and the users can say the same thing in very different ways. So, it is very important to be tolerant to recognition errors and some amount of orthographic variability. In this paper, we present our work on developing new methods and investigating various ways of robust recognition and understanding of an utterance. To this end, we exploit word-level confusion networks (sausages), obtained from ASR word graphs (lattices) instead of the ASR 1-best hypothesis. Using sausages with an improved confidence model, we decreased the calltype classification error rate for AT&T's How May I Help You (HMIHY ) natural dialog system by 38%.

Consider a conversational speech system incorporating spoken language understanding (SLU) and dialog manager (DM) modules. A prerequisite of natural dialog is that understanding takes place in context, which in turn necessitates a sharing of task knowledge between the two modules. However, because they are engaged in different activities it is often the case that the task knowledge representation is different for each of them, an undesirable duplication. In this paper we consider AT&T’s How May I Help You? SM natural dialog system. We present a method for automatically inducing the task knowledge representation used for spoken language understanding from that used for dialog management. Also, the context information needed by the SLU module for understanding each utterance is generated automatically by the DM from its own knowledge representation and the current dialog situation. This enables understanding-incontext to be implemented while avoiding the duplication involved in creating and maintaining separate task knowledge representations. The system has been evaluated using a database comprising 200k dialogs drawn from live customer traffic. 1.

Spoken dialogue systems promise efficient and natural access to a large variety of information sources and services from any phone. However, current spoken dialogue systems are deficient in their strategies for preventing, identifying and repairing problems that arise in the conversation. This paper reports results on automatically training a Problematic Dialogue Predictor to predict problematic human-computer dialogues using a corpus of 4692 dialogues collected with the 'How May I Help You' (SM) spoken dialogue system. The Problematic Dialogue Predictor can be immediately applied to the system's decision of whether to transfer the call to a human customer care agent, or be used as a cue to the system's dialogue manager to modify its behavior to repair problems, and even perhaps, to prevent them. We show that a Problematic Dialogue Predictor using automatically-obtainable features from the first two exchanges in the dialogue can predict problematic dialogues 13.2% more accurately than the baseline.

We are interested in spoken language understanding within the domain of automated telecommunication services. Our current methodology involves training statistical language models from large annotated corpora for recognition and understanding. Since the transcribing of large speech corpora is a resource consuming task, we are motivated to exploit speech without transcriptions. In particular, we learn the semantic associations for a task exploiting only phone-based sequences from the output of a task-independent ASR-system. In this paper we present a new multipass algorithm for acquiring salient phone sequences from untranscribed speech corpora and evaluate their utility for the HMIHY task. Compared to our previous strategy, this algorithm is shown to produce improved call-classification results while reducing up to 7-fold the number of salient phone-sequences selected for training.

This paper compares the effects of three different dialog initiative strategies (system initiative, mixed initiative and user initiative) on system performance and user acceptance on a large directory information access task. We used a personnel directory query application that could be accessed from a voice-only (telephony) and a multi-modal (kiosk) interface. Although the user initiative condition resulted in a lower proportion of in-grammar utterances, no significant effects of dialog initiative were observed for concept accuracy, perceived task completion, ease of use or user satisfaction. Dialogs were significantly shorter with the kiosk interface than with the telephony interface, and users preferred the kiosk interface and found it easier to use. 1.

Current methods for training statistical language models for recognition and understanding require large annotated corpora. The collection, transcription and labeling of such corpora is a major bottleneck for creating new applications and for refinements of existing ones. Thus, it is of great interest to develop methods for automatically learning vocabulary, grammar and semantics from a speech corpus without transcriptions. In this paper we report on an experiment where acoustic morphemes are automatically acquired from the output of a task-independent phone recognizer. The utility of these units is experimentally evaluated for call-type classification in the 'How may I help you?' task. Detected occurrences of the acoustic morphemes in the lattice output provide the basis for the classification of the test sentences. Using lattices, we achieve a reduction of 59% from the false rejection rate using best paths, albeit with a 5% reduction in the correct classification performance from that baseline.

Methods for utterance verification (UV) and their integration into statistical language modeling and spoken language understanding formalisms for a large vocabulary spoken understanding system are presented. The paper consists of three parts. First, a set of acoustic likelihood ratio based utterance verification techniques are described and applied to the problem of rejecting portions of a hypothesized word string that may have been incorrectly decoded by a large vocabulary continuous speech recognizer. Second, a procedure for integrating the acoustic level confidence measures with the statistical language model is described. Finally, the effect of integrating acoustic level confidence into the spoken language understanding unit (SLU) in a call-type classification task is discussed. These techniques were evaluated on utterances collected from a highly unconstrained call routing task performed over the telephone network. They have been evaluated in terms of their ability to classify utterances into a set of fifteen semantic actions corresponding to call-types that are accepted by the application.

A new method for automatically acquiring Fragments for understanding fluent speech is proposed. The goal of this method is to generate a collection of Fragments, each representing a set of syntactically and semantically similar phrases. First, phrases observed frequently in the training set are selected as candidates. Each candidate phrase has three associated probability distributions: of following contexts, of preceding contexts, and of associated semantic actions. The similarity between candidate phrases is measured by applying the Kullback-Leibler distance to these three probability distributions. Candidate phrases that are close in all three distances are clustered into a Fragment. Salient sequences of these Fragments are then automatically acquired, and exploited by a spoken language understanding module to classify calls in AT&T's "How May I Help You?" task. These Fragments allow us to generalize unobserved phrases. For instance, they detected 246 phrases in the test-set that we...

This paper describes VPQ (Voice Post Query), a dialog system that provides spoken access to the information in the AT&T corporate personnel database (>120,000 entries). An explicit design goal is to have the user’s initial interaction with the system be rather unconstrained and to rely on tighter, prompt constrained, dialog only when absolutely necessary. The purpose of VPQ is both a) to explore and exploit the capabilities of “state of the art” speech recognition systems for this highperplexity task, and b) to develop the natural language understanding and dialog control components necessary for effective and efficient user interactions. The VPQ task spans a wide range of possible dialog scenarios. They range from simple “one-shot” to complex multi-turn interactions. The former correspond to interactions where the initial utterance is unambiguous and the system’s response appropriately terminates the interaction either by providing the desired information or completing a call to the requested person. The more complex interactions occur primarily whenever ambiguities or errors require resolution. Current speech recognition accuracy of 80% is adequate to pursue such an ambitious task. This paper highlights the inherent challenges in such a task, the major components of the system, the rationale for their design, and how they perform. The VPQ project targets a variety of access devices, including telephony, desktop and handheld devices offering multi-modal user interfaces. In this paper we focus on describing the telephony interface.

We describe a procedure for contextual interpretation of spoken sentences within dialogs. Task structure is represented in a graphical form, enabling the interpreter algorithm to be efficient and task-independent. Recognized spoken input may consist either of a single sentence with utterance-verification scores, or of a word lattice with arc weights. A confidence model is used throughout and all inferences are probability-weighted. The interpretation consists of a probability for each class and for each auxiliary information label needed for task completion. Anaphoric references are permitted. 1. INTRODUCTION We are interested in spoken dialog systems in which the caller responds using fluent natural language to the prompt "How may I help you?" (HMIHY). In previous work we have described the speech recognizer [1], automatic acquisition of salient phrase and grammar fragments, and call-type classification [2,3], the dialog manager [4], and the incorporation of utterance verification [...

This paper describes a number of techniques for language verification based on acoustic processing and n-gram language modelling. A new technique is described which uses anti-models to model the general class of languages. These models are then used to normalise the acoustic score giving a 34% reduction in the error rate of the system. An approach to automatically generate discriminative subword strings for language verification is presented. The occurrence of recurrent strings are scored using a Poisson-based significance test. It is shown that when significant substrings do occur in the test material they are strong indicators of the target language occurring.

A stochastic parser is described which creates a phrase structure for a tagged sentence on the basis of statistical information inferred from a manually-bracketed training corpus. The information employed consists of measured probabilities for tag unigrams, symbol bigrams, bracket enclosures, bracket opening and closing, and length distribution. For experimental purposes a tree-search algorithm is used to find the highest-scoring bracketing, and a tree metric is used to measure the accuracy of the results for a test corpus. Finally, a fast algorithm for implementation is based on a finite-state approximation to the tree-search algorithm. Using these procedures, a gross level of syntactic structure is found quickly, with the main aim being that of pause insertion in real-time text-to-speech systems.

Phoneme substrings that are recurrent within training data are detected and logged using dynamic programming procedures. The resulting keystrings (cluster centroids) are awarded a usefulness rating based on smoothed occurrence probabilities in wanted and unwanted data. The rankings of the keystrings by usefulness measured on training, development test and final test data for three language-pairs from the OGI multi-language corpus are highly consistent, showing that language-specific features are being found. Statistical measures of local association also suggest that keystring occurrences can be correlated in a manner similar to that of keywords for a particular topic. With improved recognition accuracy it should be possible to exploit this information in order to enhance performance in topic identification.

This paper describes a language model in which context-free grammar rules are integrated into an n-gram framework, complementing it instead of attempting to replace it. This releases the grammar from the aim of parsing sentences overall (which is often undesirable as well as unrealistic), enabling it to be employed selectively in modelling phrases that are identifiable within a flow of speech. Algorithms for model training and for sentence scoring and interpretation are described. All are based on the principle of summing over paths that span the sentence, but implementation is node-based for efficiency. Perplexity results for this system (using a hierarchy of grammars from empty to full-coverage) are compared with those for n-gram models, and the system is used for re-scoring N-best sentence lists for a speaker-independent recogniser.

Keywords are chosen on the basis of their usefulness for discriminating a topic from background speech. Good topic recognition can be achieved with a small set of well-chosen keywords, but particular combinations of keywords often achieve better discrimination than can be accounted for by regarding them as independent. This paper describes a higher-order statistical approach involving models of keyword-topic interdependence. A linear-logistic model brings some improvement in performance, but better results are obtained using log-linear contingency table models. Although the potential number of these is very large, good models tend to be simple and are suggested by heuristic measures inferred from the training data. The approach is tested using a broadcast radio database.

Describes a language model for speech recognition which incorporates a substring parser (to take advantage of syntactic structure covered by a context-free grammar) and extended bigrams (to take advantage of remote dependencies between words). The use of extended bigrams significantly reduces the perplexity and a distribution clustering algorithm alleviates the additional storage cost. The substring parser is the foundation for training and scoring procedures based on paths at all levels through the syntactic structures, with subtrees linked by bigrams. The word bigram score is therefore absorbed into a grammar framework, consolidating the two kinds of language model, and again a significant reduction in perplexity is observed. The aim is an integrated, robust language model that is adaptive to the speaker.>

An experimental PC-based isolated-word sentence recognizer with two competing language models is described. A probabilistic grammar acts as the main language model and gives the best performance for sentences within its scope, and a bigram model services as backup for the exceptions. Automatic language model selection is based on probability. Context-free parse tree probabilities are products of probabilities of the rules invoked. This context-freeness is unrealistic, and a method for imposing limited context dependence on the rules is described, using first-order conditional probabilities controlled by mutual information. The method has the advantage of being data-driven, based on measured joint distributions of pairs of symbols.>

A 'probabilistic context-free grammar (PCFG)' is one step up from a Markov model. Any Markov model can be formulated as a PCFG but not the other way round. In this respect it is possible to formulate a grammar model which can't do any worse than a Markov model in speech recognition. However, this would not normally be the approach to grammar formulation. A grammar is better suited to the structural modelling of language, and grammars for application to speech recognition are likely to be derived from efforts to model the language used in a corpus. There is therefore no guarantee that such grammars will perform better than the bigram or trigram models also derived from that corpus, at least at first. Language modelling for engineering applications (as opposed to linguistics) is still in its infancy, so it would seem that the most important things to do at this stage are to develop the tools and establish the feasibility of the approaches. The paper reports progress in these directions. >