Head Automata and Bilingual Tiling: Translation with Minimal Representations (Invited Talk)

INVITED TALK Head Automata and Bilingual Tiling: Translation with Minimal Representations Hiyan Alshawi AT&T Research 600 Mountain Avenue, Murray Hill, NJ 07974, USA hiyan@research.att.com Abstract 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 asso- ciations 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. Experimen- tal results are reported comparing methods for assigning cost functions to these mod- els. We conclude with a discussion of the adequacy of annotated linguistic strings as representations for machine translation. 1 Introduction Until the advent of statistical methods in the main- stream of natural language processing, syntactic and semantic representations were becoming pro- gressively more complex. This trend is now revers- ing itself, in part because statistical methods re- duce the burden of detailed modeling required by constraint-based grammars, and in part because sta- tistical models for converting natural language into complex syntactic or semantic representations is not well understood at present. At the same time, lex- ically centered views of language have continued to increase in popularity. We can see this in lexical- ized grammatical theories, head-driven parsing and generation, and statistical disambiguation based on lexical associations. These themes -- simple representations, statisti- cal modeling, and lexicalism -- form the basis for the models and algorithms described in the bulk of this paper. The primary purpose is to build effec- tive mechanisms for machine translation, the oldest and still the most commonplace application of non- superficial natural language processing. A secondary motivation is to test the extent to which a non-trivial language processing task can be carried out without complex semantic representations. In Section 2 we present reversible mono-lingual models consisting of collections of simple automata associated with the heads of phrases. These head automata are applied by an algorithm with admissi- ble incremental pruning based on semantic associa- tion costs, providing a practical solution to the prob- lem of combinatoric disambiguation (Church and Patil 1982). The model is intended to combine the lexical sensitivity of N-gram models (Jelinek et al. 1992) and the structural properties of statistical con- text free grammars (Booth 1969) without the com- putational overhead of statistical lexicalized tree- adjoining grammars (Schabes 1992, Resnik 1992). For translation, we use a model for mapping de- pendency graphs written by the source language head automata. This model is coded entirely as a bilingual lexicon, with associated cost parame- ters. The transfer algorithm described in Section 4 searches for the lowest cost 'tiling' of the target dependency graph with entries from the bilingual lexicon. Dynamic programming is again used to make exhaustive search tractable, avoiding the com- binatoric explosion of shake-and-bake translation (Whitelock 1992, Brew 1992). In Section 5 we present a general framework for as- sociating costs with the solutions of search processes, …

Content truncated to 500 words