Automatic Rule Learning for Resource-Limited MT

Jaime Carbonell, Christian Monson, Erik Peterson, Katharina Probst, Ralf Brown, Alon Lavie, and Lori Levin

Language Technologies Institute Carnegie Mellon University Pittsburgh, PA 15213

      {jgc, cmonson, eepeter, kathrin, alavie, ralf, lsl}@cs.cmu.edu

Abstract. Machine Translation of minority languages presents unique challenges, including the paucity of bilingual training data and the unavailability of linguistically-trained speakers. This paper focuses on a machine learning approach to transfer-based MT, where data in the form of translations and lexical alignments are elicited from bilingual speakers, and a seeded version-space learning algorithm formulates and refines transfer rules. A rule-generalization lattice is defined based on LFG-style f-structures, permitting generalization and specialization operators in the search for the most general rules consistent with the elicited data. Additionally, unsupervised learning of morphology reduces the potential rule version space. The paper presents these methods and illustrates examples.

1 Introduction

Machine Translation (MT) for minority languages offers significant potential benefits, but also presents serious scientific and economic challegens. Among the benefits are: communication between isolated, often economically disadvantaged groups (i.e. multiple indigenous groups in Latin America) and the speakers of majority languages, and the potential preservation of endangered languages – over half of the 6,000 presently existing languages worldwide. The primary scientific challenge is the creation of MT systems for languages of little economic importance at very low cost per language, including the acquisition of linguistic information with minimal pre-existing bilingual corpora and little or no previous linguistic analysis of the minority language.

In order to address these needs, we are investigating omnivorous MT systems, including statistical and example-based MT when some parallel training corpora can be acquired, and machine learning of transfer-based MT rules when access to a native non-linguist informant permits partial elicitation of linguistic information, such as translations of model sentences and lexical-level bilingual alignments. Both methods benefit from morphological analysis of the minority language. But, since we assume the morphology (as well as grammar) is unknown at the outset, we address methods for morphological paradigm discovery. This paper focuses on the last two objectives of our project: unsupervised morphology learning from monolingual corpora, and and supervised learning of transfer rules with the aid of an elicitation interface to a bilingual native speaker without any assumptions regarding his or her linguistic sophistication. First, we detail the elicitaiton phase. Then, we discuss our transfer engine, followed by the seeded-version-space learning method to aquire and refine the transfer rules. Subsequently, we present a first version of our morphology learning module, and conclude with directions of future investigation.

2 The Elicitation Corpus

Since there is usually little or no bilingual translated data available for minority languages, we elicit the minimal amount of information required from a bilingual informant. The informant translates a set of sentences constructed prior to learning – the same set all languages – designed to elicit all the basic grammatical constructions, for the principles of field linguistics. The informant supplies lexical alignments as well as translations, as illustrated in figure 1.

Fig. 1. AVENUE elicitation interace

The elicitation corpus contains sentences and sub-sentential constituents carefully constructed to obtain as much information as possible about typologically prevalent features (such as tense and number) and their possible values in the target language (such as singular, dual, plural). To this end, we rely on research done in field linguistics, and use lists that were designed for this task, such as [2] and [1]. The corpus exploits compositionality, starting with smaller constituents and recycling them in higher level ones, paralleling the compositional machine learning for Version Spaces discussed below.

In designing the corpus, we strive to maximize coverage while minimizing size by targeting specific constructions. For instance, we wish for the system to develop transfer rules for relative clauses. Therefore, we developed a set of sentences that exhibit different types of relative clauses, such as subject relative clauses, object relative clauses, relative clauses with a singular antecedent, etc. This way, we ensure that the system has training data for a wide variety of phenomena. If an uncontrolled corpus was used, it would need to be several orders of magnitude larger to cover a comparable range of linguistic variability, and therefore it would impose a much larger burden on the bilingual informant. For more detail on the elicitation process, please refer to [8] and [9].

3 AVENUE Translation Engine

Rule-based translation is done in AVENUE through a custom-built translation engine using an integrated transfer approach with analysis, transfer, and generation stages. In the AVENUE engine, as in the early METAL system [5], each analysis rule is also coupled with a corresponding transfer action. While this leads to some duplication of effort during analysis, since a particular parse could possibly be transferred in several different ways, it reduces search at transfer time and permits transfer-rule learnability, because credit (or blame) assignment for correct (or incorrect) translations becomes more deterministic.

The transfer rule formalism is able to handle a variety of common translation divergences, including head-switching, thematic changes such as an object in one language being expressed as a subject in the target language, structural changes such as having an NP become a PP in another language, and lexical gaps where one target word replaces an entire source phrase [10]. Though the transfer engine does not currently have a component for deep semantic analysis or discourse processing, leaving some ambiguities unresolvable, it is sufficient for state-of-the-practice MT.

Translation starts with a bottom-up unification-based chart parser that produces an ambiguity-packed representation of the source language input. Rules are currently applied in the order they appear when read in, but work is underway to order the rule application by the complexity of the rule and the specificity of its constraint equations. Analysis builds both a syntactic constituent structure and an associated feature structure. For example, in the structural transfer rule in figure 2, which handles the transfer of some types of interrogative sentences from Mandarin to English, the feature structure for the S constituent (represented by x0) is built by setting the value of ’subj’ to the NP’s feature structure (referenced as x1), setting the subject’s case to nominative, its speech act (act)

Fig. 2. Sample Transfer Rules

; Rule to handle non-auxiliary verb ; question transfer from Chinese to ; English {S,3} S::S : [NP VP MA] -> [V NP VP ”?”] (;; Constituent alignments (X1::Y2) (X2::Y3) ;; x-side constraints ;; (parsing) ((x0 subj) == x1) ((x0 subj case) = nom) (x0 = x2) ((x0 act) = quest) ;; xy-constraints ;; (transfer) (y0 = x0) ((y0 act) =c quest) ;; y-side constraints ;; (generation) ((y1 form) = do) ((y1 agr) = (y2 agr)) (y2 == (y0 subj)) (y3 = y0))

; Sample lexical transfer rules AUX::AUX |: [zuo4] -> [do] ((x1::y1) ((y0 form) = do) ((y0 agr) = (*or* 1sg 2sg pl)) ((y0 tense) = present) )

AUX::AUX |: [zuo4] -> [does]

(

(x1::y1)

((y0 form) = do) ((y0 agr) = 3sg) ((y0 tense) = present))

to ‘quest’ for question, and finishing by copying over the feature structure of the VP (x2).

Transfer is done from the top down, starting at the top node in the chart created during parsing. Transfer rules explicitly state the alignment of source and target constituents through equations such as (X1::Y2) and (X2::Y3) in the example rule, which says that the first source constituent maps to the second target constituent, and the second source constituent maps to the third target constituent. Not all source constituents need map to the target (such as the Chinese question particle MA at X3 in this rule which is deleted during transfer). Target constituents that are not aligned to a source constituent will be created based upon the feature structure assigned to them in the transfer and generation equations. During transfer, the engine uses these alignments to reorder constituents to fit the target language grammar. Features may also be passed from source to target, such as the (y0 = x0) equation in the example which copies the entire source sentence feature structure to the target. More pinpoint feature transfers (such as transferring only number or tense) are also supported.

During generation, the target side feature structures are built and target constituent agreement constraints are checked. In the example rule, the first constituent V (Y1) has its form set to ‘do’, which is used later to choose the correct verb to insert. To enforce that the form of ‘do’ agrees with the subject NP at Y2, the ((y1 agr) = (y2 agr)) is used.

Once a selected transfer rule is applied, transfer and generation continues by recursively running applicable transfer rules on the sub-constituents of the rule until the lexical level is reached. Lexical transfer rules then apply to select the appropriate translation. In the example, the auxiliary ’do’ is inserted at the start of the sentence. The appropriate form of ’do’ is selected based upon the agreement constraint between the subject NP and initial V in the sentence rule and the agreement features in the individual lexical rules.

4 Seeded Version Spaces for Transfer Rule Learning

Transfer-rule learning can be divided into three steps. The first step is feature detection that determines which lingustic features are present in the new language. For instance, does the language have a number-agreement feature? If so, is the distinction between singular and plural, or between, singular, dual and plural? For details on feature detection, please refer to [8]. The second step is seed-rule generation, where preliminary transfer rules are generated based on lexically-aligned translated constituents. Seed generation produces transfer rules that are very specific to the training examples, essentially defining the operational S-boundary for Version-Space learning [7] [6] [4]. The third step, Seeded Version Space Learning, alleviates this problem by generalizing the seed rules in order to produce transfer rules that can be used to translate larger classes of unseen examples. Version spaces require well-defined generalization operators that define a lattice among concepts (i.e. among transfer rules in our application), as presented below.

4.1 Seed Generation

Version Space learning suffers worst-case exponential behavior as a function of the number of generalization (or specialization) steps required from initial instances. But, if the initial instances are already generalized and the number of additional generalization steps k-bounded – or limited to a greedy-search, the process is at worst a k-degree polynomial. Hence, to ensure a measure of computational tractability, we first build generalized rule-instances called “seed rules,” to the extent that we can build first-level deterministic error-free generalization. Future work will relax the error-free assumption by substituting a retractable S-boundary.

Seed rules represent generalizations over the lexical level, but are still very specific to the lexically-aligned sentence pair from which they are derived. The major-language (English) sentences in the training corpus have been pre-parsed and disambiguated in advance, so that the system has access to a correct feature (or for short f-)structure and a correct phrase or constituent (c-)structure for each sentence. The seed generation algorithm can proceed in different settings based on how much information is available about the target (unknown, minority) language. In one extreme case, we assume that we have a fully-inflected target language dictionary. The other extreme is the absence of any information, in which case the system makes assumptions about what linguistic feature values that transfer to the target language. For example, we assume, that number and definiteness transfer across languages, but not gender or case. This information is either defaulted or extracted in the earlier feature detection phase.

During seed generation, all transfer rule components are produced from the sentence pair, with the exception of xy-constraints.^{1}. Table 1 below summarizes how each part of the seed rule is produced.

Table 1. Summary of Seed Generation

SL part-of-speech sequence English c-structure
TL part-of-speech sequence 1) from the TL dictionary

2) from the English POS sequence

Alignments  from the user
x-side constraints  from the English f-structure
y-side constraints  from the TL dictionary

2) from the corresponding English words

xy-constraints  Not produced during seed generation

To make these concepts more concrete, consider an example of a seed rule as produced by our algorithm for simple NPs in English-German (for expositionary simplicity), as illustrated in figure 2 below. Everything preceded by two semicolons is ignored by the transfer engine. This rule was produced from the simple noun phrase ‘THE WOMAN’, translated into German as ‘DIE FRAU’. The English part-of-speech sequence was obtained from the English parse. The German part-of-speech sequence was obtained from a combination of the target language dictionary and the assumption that in the absence of unambiguous target language information, parts of speech transfer into the target language for aligned words. The lexical alignments were given by the bilingual informant. The x-side constraints came directly from the English c- and f-structures. The y-side constraints were again obtained by a combination of target language information and “safe” transfer heuristics. If feature information is given in the target language, it is used. If no such information is available, features such as agreement and count project their values onto the target language. This means that target language words obtain their feature values from their corresponding words in the source language. No xy-constraints are produced during seed generation.

We are currently investigating the important issue of compositionality: when producing a compositional rule e.g. for a sentence, we can make use of subconstituent transfer rules already learned. Then, the new seed rule is then no longer a flat rule, but consists of previously learned transfer constituents such as NPs.

1 xy-constraints are inferred during the Seeded Version Space Learning

4.2 Seeded Version Space learning

The first step in Seeded Version Space Learning is to group the seed rules by their part of speech sequences (constituent sequences in the compositional case), alignments, and type information. This means that in each group, the seed rules differ only in the constraint equations. The learning algorithm is run on each group separately, as each group corresponds to a target concept (i.e. a target generalized transfer rule). At the heart of the version space learning is the merging of two transfer rules to a more general transfer rule. To this end, it is necessary to clearly define the partial order by which the generality of transfer rules can be assessed (i.e. how the implicit generalization lattice is constructed):

Table 2. Seed Rules and Generalized Transfer Rule

SeedRule1  SeedRule2  Generalized Rule
;;SL: THE MAN  ;;SL: THE WOMAN  ;;SL:
;;TL: DER MANN  ;;TL: DIE FRAU  ;;TL:
NP::NP [DET N] → [DET N] NP::NP [DET N] → [DET N] NP::NP [DET N] → [DET N]
(;;alignments:  (;;alignments:  (;;alignments:
(X1::Y1)  (X1::Y1)  (X1::Y1)
(X2::Y2)  (X2::Y2)  (X2::Y2)
;;x-side constraints:  ;;x-side constraints:  ;;x-side constraints:
((X1 AGR) = *3-SING)  ((X1 AGR) = *3-SING)  ((X1 AGR) = *3-SING)
((X1 DEF) = *DEF)  ((X1 DEF) = *DEF)  ((X1 DEF) = *DEF)
((X2 AGR) = *3-SING)  ((X2 AGR) = *3-SING)  ((X2 AGR) = *3-SING)
((X2 COUNT) = +)  ((X2 COUNT) = +)  ((X2 COUNT) = +)
;;y-side constraints:  ;;y-side constraints:  ;;y-side constraints:
((Y1 AGR) = *3-SING)  ((Y1 AGR) = *3-SING)  ((Y1 AGR) = *3-SING)
((Y1 CASE) = *NOM)  ((Y1 CASE) =

(*NOT* *GEN *DAT))

((Y1 DEF) = *DEF)  ((Y1 DEF) = *DEF)  ((Y1 DEF) = *DEF)
((Y2 GENDER) = *M)  ((Y2 GENDER) = *F)  ((Y2 GENDER) = *F)
((Y2 AGR) = *3-SING)  ((Y2 AGR) = *3-SING)  ((Y2 AGR) = *3-SING)

((Y2 CASE) = *NOM)

((Y2 GENDER) = *M) ((Y2 GENDER) = *F) ((Y2 GENDER)

= (Y1 GENDER))

Definition 1 A transfer rule tr_{1} is strictly more general than another transfer rule tr_{2} if all f-structures that are satisfied by tr_{2} are also satisfied by tr_{1}. The two transfer rules are equivalent if and only if all f-structures that are satisfied tr_{1} are also satisfied by tr_{2}.

Based on this definition, we can define operations that will turn a transfer rule tr_{1} into a strictly more general transfer rule tr_{2}. In particular, three generalization operations have been identified:

1. Deletion of a value constraint 2. Deletion of an agreement constraint

3. Merging of two value constraints into one agreement constraint. Two value constraints can be merged if they are of the following format: ((X_{i} feature_{k}) = value_{l}) ((X_{j} feature_{k}) = value_{l}) → ((X_{i} feature_{k}) = (X_{j} feature_{k})), or similarly for y-side constraints.

Generalization is achieved by merging transfer rules, which in turn is based on the three generalization operations defined above. Suppose we wish to merge two transfer rules tr_{1} and tr_{2} to produce the most specific generalization of the two, stored in tr_{3}. The algorithm proceeds in three steps:

1. Insert all constraints that appear in tr_{1} and tr_{2} into tr_{merged} and subsequently eliminate them from tr_{1} and tr_{2}.

2. Consider tr_{1} and tr_{2} separately. Perform all instances of operation 3 that are possible given the constraints.

3. Repeat step 1.

The seeded version space algorithm itself is the repeated application merging two transfer rules in a group and checking whether the merged rule is specific enough to translate correctly all those sentences that the unmerged rules could also translate. If this is the case, a merge is accepted. Merging continues until no two transfer rules in the cluster can be merged any more. Note that this method is a greedy approach to generalization, without guaranteeing that the optimal (most general) transfer rule will be found. However, the method is sound with respect to allowable generalizations and computationally tractable.

Figure 2 is an example of a very simple version space, seeded with only two transfer rules, a rule produced by ‘THE MAN’ and one produced by ‘THE WOMAN’. We show the seed rules as well as the merged rule. In this case, the merged rule can be used to translate both ‘THE MAN’ and ‘THE WOMAN’, whereas each of the seed rule can only be used to translate the NP they were produced from.

5 Morphology

Morphology is a requisite pre- and post-processing step for virtually any MT system. However, the rules governing morphology for many minority languages are either unknown or uncodified. Hence, the ability to learn inflectional and derivational morphology from data is of value, especially if the learning requires only monolingual text, rather than the much scarcer bilingual sentence alignable required for statistical or example-based MT.

Whereas the goal of morphology learning in AVENUE is a synthesis of datadriven automatic learning methods and active learning methods relying on a bilingual informant, the current system is restricted to learning suffixes and suffix-substitutions based on unsupervised learning over a monolingual corpus.

In recent work Gaussier [3] investigated learning inflectional morphology and common derivational patterns. In AVENUE our first steps are similar to Gaussier: specifically, we define p-similarity between words and the notions of a suffix pair:

Definition 2 Two words w_{1} and w_{2} are p-similar if and only if:

– trunc(w_{1}, p) = trunc(w_{2}, p) where trunc(w, k) is composed of the first k characters of w

– there is no q such that: q > p and trunc(w_{1}, q) = trunc(w_{2}, q)

Definition 3 A suffix pair is a pair of strings obtained after truncation of the first p characters from two p-similar words which

– occur more than once in the corpus and

– are at least k-similar. (Where we set k equal to some small number, such as 4 or 5).

Using these definitions we construct a data structure in which each suffix pair indexes the set of all strings which, when concatenated to either suffix of the pair, produces a word in the vocabulary. Each suffix pair can then be ranked by the size of the set of stems it contains. For example, we have derived this data structure for the Brown Corpus. Table 3 contains the fifteen suffix pairs with the largest associated stem sets, along with a small sample of stems for each pair.

Table 3. The 15 Most Common Suffix Pairs from the Brown Corpus

Suffix Pair Count  Examples
-NULL:-s 5048 discourse- navigator- halfway-
-NULL:-'' 3264  kings- peaceful- thereof-
-ed:-ing  1851 conclud- reappear- demonstrat-
-NULL:-'s 1553  smith- cicero- china-
-NULL:-ed 1467  slim- reappear- munch-
-NULL:-ing 1275  reappear- munch- respond-
-'':-s 1123 risk- cook- proprietorship-
-NULL:-ly 1051  slim- remote- peaceful-
-NULL:-d 998  lodge- delude- scare-
-ed:-s  903  bother- patent- barb-
-d:-s  810  lodge- relate- discusse-
-ing:-s  775  bother- patent- brief-
-e:-ing  709  conclud- stifl- demonstrat-
-NULL:-' 576  louis'- rogues- that-
-':-s  549  soul'- golf'- well'-

The suffix pairs are useful because they determine the morphological paradigms present in the language. In the English example the suffix pairs indicate that many words take the suffix ’-s’. Using our knowledge of English, we know that most nouns are pluralized by adding ’-s’ and also that verbs take ’-s’ when they agree with third person singular subjects. Similarly, and more interestingly, we also learn from the suffix pairs that many words can take both an ’-ed’ as well as an ’-ing’ suffix (namely verbs). Thus, morphological paradigms surface in the suffix pairs. Derivational morphology begins to appear in lower-frequency suffix pairs than those included in the table.

The current aim of morphology learning is twofold: first, to use the suffix pairs to correctly analyze a surface string into its constituent morphemes, and second, to extend this approach to languages with richer morphology than English, such as Mapudungun. Next, we expect to examine data-driven morphological learning beyond suffix-chain additions or substitutions.

6 Conclusions and Future Work

We presented a novel approach to learning in machine translation, a method that we hope will open MT up to a variety of languages in which little training data are available. We realize that our system presents a large undertaking: it requires a specially adapted transfer engine, a system that infers transfer rules, as well as a morphology learning module. This paper presents the current state of our system. Over the next months, we hope to develop each part of the system further. In particular, we wish to complete compositionality aspect of our seedtransfer-rule generation algorithm. Further, we plan to refine the search through the seeded version space by definining a function that determines what merge is the best at any one step, given that there is more than one possible merge. The transfer engine will be extended to output partial translations if no full translation can be given. This will be especially important as our system will be integrated into a multi-engine system, together with statistical and examplebased MT methods.

References

1. Luc Bouquiaux and Jacqueline M.C. Thomas: Studying and Describing Unwritten Languages. The Summer Institute of Linguistics. (1992)

2. Bernard Comrie and Norval Smith: Lingua Descriptive Series: Questionnaire. In: Lingua. 42 (1977) 1–72

3. Gaussier, E.: Unsupervised learning of derivational morphology from inflectional lexicons. In: Proceedings of the Workshop on Unsupervised Learning in Natural Language Processing. Association for Computational Linguistics. (1999) 24–30

4. Hirsh Haym: Theoretical Underpinnings of Version Spaces. In: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI91). Morgan Kaufmann Publishers. (1991) 665–670

5. Hutchins, W. John and Somers, Harold L.: An Introduction to Machine Translation. Academic Press, London. (1992)

6. Tom Mitchell: Machine Learning. McGraw Hill (1996)

7. Mitchell, T. M.: Version Spaces: An Approach to Concept Learning. Stanford University. December (1978)

8. Katharina Probst and Ralf Brown and Jaime Carbonell and Alon Lavie and Lori Levin and Erik Peterson: Design and Implementation of Controlled Elicitation for Machine Translation of Low-density Languages. Workshop MT2010, Machine Translation Summit 2001. (2001)

9. Katharina Probst and Lori Levin: Challenges in Automated Elicitation of a Controlled Bilingual Corpus. TMI 2002. (2002)

10. Trujillo, A.: Translation Engines: Techniques for Machine Translation. Springer-Verlag London Limited, London. (1999)