Data processing: speech signal processing – linguistics – language – Linguistics – Translation machine
Reexamination Certificate
1996-06-14
2001-05-15
Isen, Forester W. (Department: 2747)
Data processing: speech signal processing, linguistics, language
Linguistics
Translation machine
Reexamination Certificate
active
06233544
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to automatic language translation. More particularly, the present invention relates to methods and apparatus for direct translation utilizing a probabilistic lexical transduction model.
BACKGROUND OF THE INVENTION
Language translation involves the conversion of sentences from one natural language, usually referred to as the “source” language, into another language, typically called the “target” language. When performed by a machine, e.g., a computer, such translation is referred to as automatic language translation or machine translation.
Many different methods for automatic language translation have been proposed and implemented over the last few decades. See Hutchins, W. J. and Somer, H. L.,
An Introduction to Machine Translation
, (Academic Press, N.Y. 1992). Most translation systems utilize mapping via intermediate representation. For example, in the so called “interlingua” translation systems, the intermediate representation is a language-independent representation resulting from an initial analysis of the source language sentence. The intermediate representation is then converted into the target language by a generation phase. See, for example, Nirenburg et al.,
Machine Translation: A Knowledge-Based Approach
, (Morgan Kaufmann, San Mateo, Calif. 1992). A second example of mapping via intermediate representation are the “transfer” translation systems. Such systems include three phases; analysis of the source language sentence into a source representation, conversion of the source representation into a target representation, and generation of a target sentence from the target representation. See, van Noord et al., “An Overview of Mimo2,” v.6 Machine Translation, pp. 201-04, 1991.
A second type of translation system can be classified as a “direct” translation system. Such direct methods do not use intermediate representations. Some of the earliest translation systems utilized direct methods; however, they were ad-hoc in nature, depending on large collections of translation rules and exceptions.
Recently, more systematic direct translation methods have been proposed. One such method is based on a statistical model for mapping words of the source sentence into words and word positions in the target language. A drawback of that method is that it ignores the arrangement of phrases in the source and target sentences when mapping a word into its corresponding position in the target language sentence. The method therefore ignores lexical relationships that make one position in the target sentence more likely than another. Brown et al., “A Statistical Approach to Machine Translation,” v. 16 Computational Linguistics, pp. 79-85, 1990. In another direct method, a syntax tree is built up simultaneously for the source and target sentences, using special phrase structure rules that can invert the order of syntactic constituents. A drawback of this method is that it does not take into account word to word associations in the source and target languages. See, Wu, D., “Trainable Coarse Bilingual Grammars for Parallel Text Bracketing,” 1995 Proc. Workshop Very Large Corpora, Cambridge Mass.
A third direct translation system has been proposed that uses standard left-to-right finite state transducers for translation. Using such standard finite state transducers limits the ability of the method to allow for words in the target sentence being arbitrarily far away from their original position in the source sentence. This is because, for non-trivial vocabularies, the required number of transducer states becomes too large for practical use. See Vilar et al., “Spoken-Language Machine Translation in Limited Domains: Can it be Achieved by Finite-State Models?,” 1995 Proc. Sixth Int'l. Conf. Theoretical and Methodological Issues in Machine Translation, Leuven, Belgium.
Thus, there is a need for an improved system and method for automatic language translation.
SUMMARY OF THE INVENTION
An improved direct system and method for language translation is disclosed. According to the present invention, the translator consists of a plurality of finite state transducers referred to as head transducers, a bilingual lexicon associating pairings of words from the two languages with particular head transducers, a parameter table specifying “cost” values for the actions taken by the transducers and a transduction search engine for finding the lowest cost translation of an input phrase or sentence. The action costs code lexical associations in the source and target language; a lower cost corresponding to a stronger lexical association.
The head transducers utilized in the present invention are distinct from the standard finite state transducers known in the art. Standard transducers are typically limited to converting a single input sequence into a single output sequence, usually reading the input sequence from left to right. The present head transducers have the ability to read a pair of sequences, one scanned leftwards, the other scanned rightwards, and write a pair of sequences, one leftwards, the other rightwards.
Each head transducer is associated with a pair of “head” words with corresponding meanings in the source and target languages. A head word is typically the word carrying the basic or most important meaning of a phrase. Head words are associated with dependents, which are the head words of subphrases of the phrase. The purpose of a transducer for a particular head word pairing is to (i) recognize dependent words to the left and right of the source language head word and (ii) propose corresponding dependents to the left and right of the target language head word in the target sentence being constructed.
A bilingual lexicon with associated head transducers will allow for many possible translations of a sentence. This results from the many different possible choices for entries from the lexicon, including choices of target words, choices of the heads of phrases in the source sentence and choices of the dependent words in the source and target phrases. The parameter table provides different “costs” for such choices reflecting association strengths, i.e., indicative of the likelihood of co-occurence, for source-target word translations and for head-dependent word pairs in each of the two languages. Thus, a total translation cost may be defined as the sum of the costs of all the choices leading to that translation. The translation with the lowest total cost is selected as the output of the translator, that is, the translation.
The search for the lowest cost translation is carried out by the transduction search engine. The transduction search engine utilizes the head transducers to recursively translate first the head word, then the heads of each of the dependent phrases, and then their dependents, and so on. This process is referred to herein as recursive head transduction.
The present system and methods do not requiring modeling of word positions directly, avoiding the drawback of the method proposed by Brown. Furthermore, the present system and methods are purely lexical. As such, unlike the method proposed by Wu, the present invention does not require syntactic rules. Rather, the best translation is chosen on the basis of word-to-word association strengths in the source language and the target language. Moreover, the head transducers utilized in the present invention allows the words in the target sentence to be arbitrarily far away from their corresponding positions in the source sentence without a corresponding increase in the number of model states.
REFERENCES:
patent: 4868750 (1989-09-01), Kucera et al.
patent: 5136503 (1992-08-01), Takagi et al.
patent: 5477451 (1995-12-01), Brown et al.
patent: 5608624 (1997-03-01), Luciw
patent: 5621859 (1997-04-01), Schwartz
patent: 5625814 (1997-04-01), Luciw
patent: 5737621 (1998-04-01), Kaplan et al.
patent: 0 525 470 (1993-02-01), None
patent: 0 568 319 (1993-11-01), None
patent: 0 651 340 (1995-05-01), None
Brown, et al., “A Statistical Approach to machine Translation” Computational Linguistic
AT&T Corp
Edouard Patrick N.
Isen Forester W.
LandOfFree
Method and apparatus for language translation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for language translation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for language translation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2526896