Computer Science
ComputerScience,1970-2008-Computer Science-1998.jsonl.gz.gz
Computer Science
effa1e03ad5d68c5cabbd2ddadb06cd8f1f6f1ef
Deriving Transfer Rules from Dominance-Preserving Alignments

1 Introduction Automatic acquisition of translation rules from parallel sentence-Migned text takes a variety of forms. Some machine translation (MT) svstems treat aligned sentences as unstructured word sequences. Other systems, including our own ((Gr-ishman, 1994) and (Meyers et al., 1996)), syntactically analyze sentences (parse) before acquiring transfer rules (cf. This has the advantage of acquiring structurM as well as lexical correspondences. A syntactically analyzed, aligned cor~ pus may serve ~s an example base for a form of example-based NIT (cf. an efficient algorithm for aligning a pair of source/target language parse trees; ~nd (2) a procedure for deriving transfer rules from this alignment. Each transfer rule consists of a pair of tree fragments derived bv "cutting up" the source and target trees. A set of transfer rules whose left-hand sides match a source language parse tree is used to generate a target language parse tree from their set of right-hand sides, which is a transla.-tion of the source tree. This technique resembles work on MT using synchronous Tree-Adjoining Grammars (cf. (Abeille et al., 1990)). The Proteus translation system learns transfer rules from pairs of aligned source and target reg-ularized parses, Proteus's representation of predicate argument structure(cf. Figure 1)? Then it uses these transfer rules to map source lan-L We thank Cristina Olmeda Moreno for work on parsing our Spanish text. 2Regularized parses (henceforth, "pmse trees") are like F-structures of Lexical }"tmctiou Grammar (LEG), except, that a depenclency st.ruct.ure is used." guage regularized parses generated by ou r source language parser into target language regularized parses. Finally a generator converts target reg-ularized parses into target language sentences. All Mignment f is a I-to-1 partial mapping from source nodes to target nodes. We consider only alignments which preserve the dominance relationship: If node a dominates node b in the source tree. then f(a) dominates f(b) in the target tree. In Figure 1. source nodes ,4. B, C and D map to the corresponding target nodes, marked with a prime, e.g., f(A) = A'. The alignment)nay be represented by the setsign a score to each Mignment f, based on the (weighted) number of pairs in f; finding the best alignment translates into finding the alignment with the highest score. Our algorithms are based on (Farach et al., 199.5) and related work. We needed efficient alignment algorithms because: (1) Corpus-based training requires processing a lot of text; and (2) An exhaustive search of all …


Introduction
Automatic acquisition of translation rules from parallel sentence-aligned text takes a variety of forms. Some machine translation (MT) systems treat aligned sentences as unstructured word sequences. Other systems, including our own ((Grishman, 1994) and (Meyers et al., 1996)), syntactically analyze sentences (parse) before acquiring transfer rules (cf. (Kaji et hi., 1992), (Matsumoto et hi., 1993), and (Kitamura and Matsumoto, 1995)). This has the advantage of acquiring structural as well as lexical correspondences. A syntactically analyzed, aligned corpus may serve as an example base for a form of example-based NIT (cf. (Sato and Nagao, 1990), (l(aji et al., 1992), and (Furuse and Iida. 1994)).
This paper 1 describes: (1) an efficient algorithm for aligning a pair of source/target language parse trees; and (9) a procedure for deriving transfer rules from this alignment. Each transfer rule consists of a pair of tree fragments derived by "cutting up" the source and target trees. A set of transfer rules whose left-hand sides match a source language parse tree is used to generate a target language parse tree from their set of right-hand sides, which is a translation of the source tree. This technique resembles work on NIT using synchronous Tree-Adjoining Grammars (cf. (Abeille et al.. 1990)). The Proteus translation system learns transfer rules from pairs of aligned source and target regularized parses, Proteus's representation of predicate argument structure (cf. Figure 1). 2 Then it uses these transfer rules to map source tan-guage regularized parses generated by our source language parser into target language regularized parses. Finally a generator converts target regularized parses into target language sentences.
An alignment f is a 1-to-1 partial mapping from source nodes to target nodes. We consider only alignments which preserve the dominance relationship: If node a dominates node b in the source tree, then f(a) dominates f(b) in the target tree. In Figure 1. source nodes .4. B, C and D map to the corresponding target nodes, marked with a prime, e.g., f(A) = A'. The alignment may be represented by the set {(d, A'), (B, B'), (C, C'), (D, D')}. We can assign a score to each alignment f, based on the (weighted) number of pairs in f; finding the best alignment translates into finding the alignment with the highest score. Our algorithms are based on (Farach et al., 1995) and related work.
We needed efficient alignment algorithms because: (1) Corpus-based training requires processing a lot of text; and (2) An exhaustive search of all alignments is too computationally expensive for realistically sized parse trees.
Eliminating dominance violations greatly reduced our search space. Similar work (e.g., (Matsumoto et hi., 1993)) considers all possible matches. Although. our system cannot account for actual dominance violations in a given bitext, there are no such violations in our corpus and many hypothetical cases can be avoided by adopting the appropriate grammar. Cases of adjuncts aligning with heads and vice versa are not dominance violations if we replace our dependency analysis with one in which internal nodes have category labels and the head constituents are marked by HEAD arcs and we assume the following Categorial Grammar (CG) style analyses. Suppose that verb (Vi) maps to adverb (A'I) and adverb (A2) maps to verb (V'2), where  We are willing to pay a small penalty to collapse the path from D to E, and align the resulting structure. This leads to new algorithms where the LeA-preserving restriction is replaced by the weaker, dominance-preserving constraint. The rationale behind allowing an edge, say (v, u) to be collapsed when matching two nodes v and v ~, is that we may find some children of u which correspond well to some children [nitially, we fill the matrix S with undefined values, and invoke the procedure SCOREdom, described below, to compute S(root(T), root(T')), the score for matching the root nodes of the trees. During the computation of the score for the roots, the procedure recursively finds the best-scoring matches for all the nodes in the trees. This yields the best alignment of the entire trees.
Table l(a) shows the values of S for the trees in Figure 1. Whenever we compute a score fox" internal nodes, we also record the best way of pairing up their children in Table l That is, the number of rows in M is one more than the number of children of v, and the number of columns is one more than number of children of v ¢. V~re label row d(v) + 1 and column d(v ~) + 1 with a "*". Fill the matrix M: compute the corresponding entry in Mij: The are filled in as in Table 2. The proper values for the parameter functions used above, such as the penalty function Pen and the translation ineasures, are chosen empirically, and constitute the tunable parameters of the procedure. Normally, we will expect that the values of Lexr, ode will be much larger than the values of Lex~rc and Pen.
In the example we used the following settings:

PEEP (i,j)EP
Here P is a legitimate pairing of v and its children against v' and its children. A legitimate pairing P is a set of elements of the matrix M. that conform to the following conditions: 1. each row and each column of M may contribute at most one element to P, except that the row and the column labeled * may contribute more than one element to P 2. if P contains an element Mij corresponding to the node pair (w. w'), and some child node u appears in the Children-Pairing for (w, w'), then the row or column of u may not contribute any elements to P.
We use/.7 ) = £7)(v. v') to denote the set of all legitimate pairings. There are O(d!) such pairings, where d is the greater of the degrees of u and v'. The summation in (l) ranges over all the pairs (i, j) that appear in a legitimate pairing P E /.7)(v, v'). We evaluate this summation for all O(d!) legitimate pairings in/.7), and then select the pairing Pbe~t with the maximum score. Pbest is then stored in the Children-Pairing matrix entry for (v, v'). Table 2       The greedy algorithm aligns trees with n nodes and maximal degree d in O(n2d 2) time.

Acquiring Transfer Rules
This section describes the procedure for deriving transfer rules from aligned parse trees.
First, the best-scoring alignment is recovered from the Children-Pairing matrix, (Table t(b)). 4 Start by including the root node-pair in the alignment, (here (D, DI)). Then, for each pair (v, v ~) already in the alignment, repeat the following steps, until no more pairs can be added to the alignment: (t) look up the Children:Pairing for (v.v The transfer rules derived from Figure t may be written as follows: 1. < root : Excel > --+ < root : Excel > 2. < root : valores > ~ < root : values > 3. < root : libro,subj : xl,a :< root : calcular,obj : x2,en : x3 > > < root : recalculate;subj : Tr(xl),obj : Tr(x2), in : Tr(x3) > Each substructure is represented as a list con-taining a root lexical item, and a set of arcvalue pairs. An arc (role) al with head (value) h is written as al : h, where h is a fixed label (word), a substructure or a variable. If the source substructure has n of the leaves labeled with variables xl, • •., x~, the target will have n of the leaves labeled with Tr(xl),..., Tr(x~), where Tr(x) is the texical translation function. This general structure allows us to capture relations between multi-word expressions in the source and target languages.

Translation
The described procedure for acquisition of transfer rules from corpora is the basis for our translation system. A large collection of transfer rules are collected from a training corpus. When new text is to be translated, it is first parsed. The source tree is matched against the left hand sides of the transfer rules which have been collected. If a set of transfer rules whose left-hand sides match the parse tree is found, the corresponding target structure is generated from the right hand sides of these transfer rules. Typically, several sets of transfer rules meet this criterion. They are ranked by their frequency in the training corpus. Once a target tree has been produced, it is converted to a word sequence by a target language generator. We have applied this approach to the translation of Microsoft Help files in English and Spanish. The sentences are moderately simple and quite parallel in structure, which has made the corpus suitable for our initial system development. To date, we have been using a training corpus of about 1,000 sentences, and a test corpus of about 100 sentences.

Evaluation
Real evaluation of performance of MT systems is time consuming and subjective. Nevertheless, some evaluation system is needed to insure that incremental changes are for the better, or at least, are not detrimental. We measured the success of our translation by how closely we reproduced Microsoft's English (target language) text. Our evaluation procedure computes the ratio between (a) the complement of the intersection set of words in our translation and the actual Microsoft sentence; and (b) the combined lengths of these two sentences. An exact translation gives a score of 0. If the system generates the sentence "A B C D E" and the actual sentence is "A B C F", the score is 3/9 (the length of D E F divided by the combined lengths of A B C D E and A B C F.) The dominancepreserving version of the program produced output for 88 out of 91 test sentences. The average score for these 88 sentences was 0.29:0.21 due to incorrect word matches and 0.08 due to failure to translate because insufficient confidence levels were reached. The LCA-preserving version produced output for only 83 sentences with an average score of over 0.30: about 0.23 due to incorrect word matches and about 0.08 due to insufficient confidence levels. This crude scoring technique suggests that the dominance-preserving algorithm improved our results: more sentences were translated with higher quality. One limitation of this scoring technique is that paraphrases are penalized. An imperfect score (even .20) may signify an adequate translation.