A Parameter-Based Message-Passing Parser for MT of Korean and English

A Parameter-Based Message-Passing Parser for MT of Korean and English DekangLin§, Bonnie Dorr†, Jye-hoon Lee†, Sungki Suh‡ §Department of Computer Science †Department of Computer Science ‡Department of Linguistics University of Manitoba University of Maryland University of Maryland Winnipeg, MB, Canada, R3T 2N2 College Park, MD 20724 College Park, MD 20742 lindek@cs.umanitoba.ca {bonnie, jlee}@cs.umd.edu sksuh@wam.umd.edu Abstract The parsing component of previous principle-based machine translation systems are inefficient since they tend to adopt a generate-and-test paradigm. We combine the benefits of a message-passing paradigm with the benefits of a parametric approach in the implementation of a parser that avoids overgeneration and is easily ported to multiple languages. The algorithm has been implemented in C++ and successfully tested on well-known, translationally divergent sentences in a MT system called PRINCITRAN. Keywords: parameter-based MT, message passing, cross-linguistic divergences 1. Introduction This paper presents an efficient, implemented approach to cross-linguistic parsing for interlingual MT. Our design is based on Government-Binding (GB) Theory (Chomsky, 1981; Haegeman, 1991; van Riemsdijk and Williams, 1986). One of the drawbacks to alternative GB- based parsing approaches is that they generally adopt a filter-based paradigm, generating all possible candidate structures of the sentence that satisfy Xbar theory, and then subsequently applying filters to eliminate those structures that violate GB principles. (See, for example, Abney (1989), Correa (1991), Dorr (1991), Fong (1991), and Frank 1990.) The current approach provides an alternative to filter-based designs which avoids these difficulties by applying principles to descriptions of structures without actually building the structures themselves. In effect, structure building is deferred until the descriptions satisfy all principles. We combine the benefits of the message-passing paradigm with the benefits of the parameterized approach to build a more efficient, but easily extensible system, called PRINCITRAN.1 Our work extends that of Lin and Goebel (1993) and Lin (1993) in that it provides a parameterization mechanism along the lines of Dorr (1993b) that allows the system to be ported to languages other than English. We focus particularly on the problem of processing head-final languages such as Korean. The algorithm has been implemented in C++ and successfully tested on well-known, translationally divergent sentences. The next section presents a general framework for parsing by message passing. Section 3 presents our parameterization framework for handling cross-linguistic variation. Section 4 describes our technique for automatic precompilation of parameter settings on a per-language basis. The results of parsing translationally divergent sentences in Korean and English are presented in section 5. 1 The name PRINCITRAN is derived from the names of two systems, UN1TRAN (Dorr (1993a)) and PRINCIPAR (Lin (1993)). 149 Figure 1: Network Representations of Grammars We conclude with a discussion about the implications of this approach and its applicability to the problem of multi-language MT. 2. Message Passing Paradigm Our GB parser is an extension of the message-passing approach proposed by Lin (1993) and Lin and Goebel (1993), which uses a network to encode the grammar. The nodes in the grammar network represent grammatical categories (e.g., NP, Nbar, N) or subcategories, such as V:NP (i.e., …

Content truncated to 500 words