Many statistical learning problems in NLP call for local model search methods.But accuracy tends to suffer with current techniques, which often explore either too narrowly or too broadly: hill-climbers can get stuck in local optima, whereas samplers may be inefficient.We propose to arrange individual local optimizers into organized networks.Our building blocks are operators of two types: (i) transform, which suggests new places to search, via non-random restarts from already-found local optima; and (ii) join, which merges candidate solutions to find better optima.Experiments on grammar induction show that pursuing different transforms (e.g., discarding parts of a learned model or ignoring portions of training data) results in improvements.Groups of locally-optimal solutions can be further perturbed jointly, by constructing mixtures.Using these tools, we designed several modular dependency grammar induction networks of increasing complexity.Our complete system achieves 48.6% accuracy (directed dependency macro-average over all 19 languages in the 2006/7 CoNLL data) -more than 5% higher than the previous state-of-the-art.

In this paper we investigate the utility of three aspects of named entity processing: detection, localization and value extraction. We corroborate this task categorization by providing examples of practical applications for each of these subtasks. We also suggest methods for tackling these subtasks, giving particular attention to working with speech data. We employ Support Vector Machines to solve the detection task and show how localization and value extraction can successfully be dealt with using a combination of grammar-based and statistical methods. 1.

In speech and language processing, information about the errors made by a learning system is commonly used to assess and improve its performance. Because of high computational complexity, the context of the errors is usually either ignored, or exploited in a simplistic form. The complexity becomes tractable, however, for phone recognition because of the small lexicon. For phonebased systems, an exhaustive modeling of local context is possible. Furthermore, recent research studies have shown phone recognition to be useful for several spoken language processing tasks. In this paper, we present a mechanism which learns patterns of context-sensitive errors from ASR-output aligned with the “true” phone transcriptions. We also show how this information, encoded as a context-sensitive weighted transducer, can provide a modest improvement to phone recognition accuracy even when no transcriptions are available for the domain of interest.

Data collection and annotation are major bottlenecks in rapid development of accurate syntactic and semantic models for natural-language dialogue systems. In this paper we show how human knowledge can be used when designing a language understanding system in a manner that would alleviate the dependence on large sets of data. In particular, we extend BoosTexter, a member of the boosting family of algorithms, to combine and balance hand-crafted rules with the statistics of available data. Experiments on two voice-enabled applications for customer care and help desk are presented.

The paper defines weighted head transducers, finite-state machines that perform middle-out string transduction. These transducers are strictly more expressive than the special case of standard left-to-right finite-state transducers. Dependency transduction models are then defined as collections of weighted head transducers that are applied hierarchically. A dynamic programming search algorithm is described for finding the optimal transduction of an input string with respect to a dependency transduction model. A method for automatically training a dependency transduction model from a set of input-output example strings is presented. The method first searches for hierarchical alignments of the training examples guided by correlation statistics, and then constructs the transitions of head transducers that are consistent with these alignments. Experimental results are given for applying the training method to translation from English to Spanish and Japanese.

We describe a method for automatically learning head-transducer models of translation from examples consisting of transcribed spoken utterances and their translations. The method proceeds by first searching for a hierarchical alignment (specifically a synchronized dependency tree) of each training example. The alignments produced are optimal with respect to a cost function that takes into account co-occurrence statistics and the recursive decomposition of the example into aligned substrings. A probabilistic head-transducer model is then constructed from the alignments. We report results of applying the method to English-to-Spanish translation in the domain of air travel information and English-to-Japanese translation in the domain of telephone operator assistance. We also report on a variation on this model-construction method in which multi-word pairings are used in the computation of the hierarchical alignments and head transducer models. 1.

We compare the effectiveness of two related machine translation models applied to the same limited-domain task. One is a transfer model with monolingual head automata for analysis and generation; the other is a direct transduction model based on bilingual head transducers. We conclude that the head transducer model is more effective according to measures of accuracy, computational requirements, model size, and development effort.

We define a general method for ranking the solutions of a search process by associating costs with equivalence classes of state transitions of the process. We show how the method accommodates models based on probabilistic, discriminative, and distance cost functions, including assignment of costs to unseen events. By applying the method to our machine translation prototype, we are able to experiment with different cost functions and training procedures, including an unsupervised procedure for training the numerical parameters of our English-Chinese translation model. Results from these experiments show that the choice of cost function leads to significant differences in translation quality.

We present a language model consisting of a collection of costed bidirectional finite state automata associated with the head words of phrases.The model is suitable for incremental application of lexical associations in a dynamic programming search for optimal dependency tree derivations.We also present a model and algorithm for machine translation involving optimal "tiling" of a dependency tree with entries of a costed bilingual lexicon.Experimental results are reported comparing methods for assigning cost functions to these models.We conclude with a discussion of the adequacy of annotated linguistic strings as representations for machine translation.

This paper presents statistical language and translation models based on collections of small finite state machines we call "head automata".The models are intended to capture the lexical sensitivity of N-gram models and direct statistical translation models, while at the same time taking account of the hierarchical phrasal structure of language.Two types of head automata are defined: relational head automata suitable for translation by transfer of dependency trees, and head transducers suitable for direct recursive lexical translation.

Aspects of semantic interpretation, such as quantifier scoping and reference resolution, are often realised computationally by non-monotonic operations involving loss of information and destructive manipulation of semantic representations.The paper describes how monotonic reference resolution and scoping can be carried out using a revised Quasi Logical Form (QLF) representation.Semantics for QLF are presented in which the denotations of formulas are extended monotonically as QLF expressions are resolved.

The paper describes work on applying a general purpose natural language processing system to transfer-based interactive translation. Transfer takes place at the level of Quasi Logical Form (QLF), a contextually sensitive logical form representation which is deep enough for dealing with cross-linguistic differences. Theoretical arguments and experimental results are presented to support the claim that this framework has good properties in terms of modularity, compositionality, reversibility and monotonicity.

This paper describes a 'Logical Form' target language for representing the literal meaning of English sentences, and an intermediate level of representation ('Quasi Logical Form') which engenders a natural separation between the compositional semantics and the processes of scoping and reference resolution. The approach has been implemented in the SRI Core Language Engine which handles the English constructions discussed in the paper.