We empirically show that there are significant differences between the discourse structure of Japanese texts and the discourse structure of their corresponding English translations. To improve translation quality, we propose a computational model for rewriting discourse structures. When we train our model on a parallel corpus of manually built Japanese and English discourse structure trees, we learn to rewrite Japanese trees as trees that are closer to the natural English rendering than the original ones. Almost all current MT systems process text one sentence at a time. Because of this limited focus, MT systems cannot re-group and re-order the clauses and sentences of an input text to achieve the most natural rendering in a target language. Yet, even between languages as close as English and French, there is a 10% mismatch in number of sentences --what is said in two sentences in one language is said in only one, or in three, in the other (Gale and Church, 1993) . For distant language pairs, such as Japanese and English, the differences are more significant. Consider, for example, Japanese sentence (1), a word-by-word "gloss" of it (2), and a two-sentence translation of it that was produced by a professional translator (3). (1) [ (Mann and Thompson, 1988) . If we analyze the text fragments closely, we will notice that in translating sentence (1), a professional translator chose to realize the information in Japanese unit 2 first (unit 2 in text (1) corresponds roughly to unit 1 in text (3)); to realize then some of the information in Japanese unit 1 (part of unit 1 in text (1) corresponds to unit 2 in text (3)); to fuse then information given in units 1, 3, and 5 in text (1) and realize it in English as unit 3; and so on. Also, the translator chose to repackage the information in the original Japanese sentence into two English sentences. At the elementary unit level, the correspondence between Japanese sentence (1) and its English translation (3) can be represented as in (4}, where j C e denotes the fact that the semantic content of unit j is realized fully in unit e; j D e denotes the fact that the semantic content of unit e is realized fully in unit j; j = e denotes the fact that units j and e are semantically equivalent; and j ~ e denotes the fact that there is a semantic overlap between units j and e, but neither proper inclusion nor proper equivalence. .!1 D e2;jt -~ e3; .12 ----el; 33 C e3; .14 ~ e4;j4 ~ es; .15 ~ e3; .16 C e6; .17 C e6 (4) Hence. the mappings in (4) provide all explicit representation of the way information is re-ordered and re-packaged when translated from Japanese into English. However, when translating text, it is also the case that t he rhetorical rendering changes. What is realized ill Japanese using an CONTRAST relation can be realized in English using, for example, a COXl- PARISON or a CONCESSION relation. Figure I presents in the style of Mann and Thompson (1988) the discourse structures of text fragments (1) and (3), Each discourse structure is a tree whose leaves correspond to the edus and whose internal nodes correspond to contiguous text spans. Each node is characterized by a status (NUCLEUS or SATELLITE) and a rhetorical relation, which is a relation that holds between two non-overlapping text spans. The distinction between nuclei and satellites comes from the empirical observation that the nucleus expresses what is more essential to the writer's intention than the satellite: and that the nucleus of a rhetorical relation is comprehensible independent of tile satellite, but not vice versa. When spans are equally important, the relation is nmltinuclear: for example, the CONTRAST relation that holds between unit [3] and span [4.5] in the rhetorical structure of the English text in figure 1 is nmhinuclear. Rhetorical relations that end in the suffix "'-e'" denote relations that correspond to embedded syntactic constituents. For example, the ELABORATION-OBJECT-ATTRIBUTE-E relation that holds between units 2 and 1 in the English discourse structure corresponds to a restrictive relative. If one knows the mappings at the edu level, one can determine the mappings at the span (discourse constituent) level as well. For example, using the elementary mappings in (4), one call determine that Japanese span [1,2] [6,7] in the Japanese tree corresponds to a similar relation that. holds between span [1,5] and unit [6] in the English tree (modulo the fact that, in Japanese, the relation holds between sent ence fragments, while in English it holds between full sentences). However, the TEMPORAL-AFTER relation that holds between units [:3] and [4] ill the Japanese tree is realized as a CONTRAST relation between unit [3] and span [4.5] in the English tree. And because Japanese units [6] and [7] are fused into unit [6] in English, the relation ELABORATION-OBJECT-ATTRIBUTE-E is 11o longer made explicit in the English text. Some of the differences between the two discourse trees in Figure 1 in MT systems at the syntactic level. For example, the re-ordering of units 1 and 2, can be dealt with using only syntactic models. However, as we will see in Section 2, there are significant differences between Japanese and English with respect to the way information is packaged and organized rhetorically not only at the sentence level, but also, at the paragraph and text levels. More specifically, as humans translate Japanese into English, they re-order the clauses, sentences, and paragraphs of Japanese texts, they re-package the information into clauses, sentences, and paragraphs that are not a one-to-one mapping of the original Japanese units, and they rhetorically re-organize the structure of the translated text so as to reflect rhetorical constraints specific to English. If a translation system is to produce text that is not only grammatical but also coherent, it will have to ensure that the discourse structure of the target text reflects the natural renderings of the target language, and not that of the source language. In Section 2, we empirically show that there are significant differences between the rhetorical structure of Japanese texts and their corresponding English translations. These differences justify our investigation into developing computational models for discourse structure rewriting. In Section 3, we present such a rewriting model, which re-orders the edus of the original text, determines English-specific clause, sentence, and paragraph boundaries, and rebuilds the Japanese discourse structure of a text using English-specific rhetorical renderings. In Section 4, we evaluate the performance of an implementation of this model. We end with a discussion. In order to assess the role of discourse structure in MT, we built manually a corpus of discourse trees for 40 Japanese texts and their corresponding translations. The texts were selected randomly from the ARPA corpus (White and O'Connell, 1994) . On average, each text had about 460 words. The Japanese texts had a total of 335 paragraphs and 773 sentences. The English texts had a total of 337 paragraphs and 827 sentences. We developed a discourse annotation protocol for Japanese and English along the lines followed by . We used Marcu's discourse annotation tool (1999) in order to manually construct the discourse structure of all Japanese and English texts in the corpus. 10% of the Japanese and English texts were rhetorically labeled by two of us. The tool and the annotation protocol are available at http://www.isi.edu/~marcu/software/. The annotation procedure yielded over the entire corpus 2641 Japanese edus and 2363 English edus. We computed the reliability of the annotation using 's method for computing kappa statistics (Siegel and Castellan, 1988 ) over hierarchical structures. Table 1 displays average kappa statistics that reflect the reliability of the annotation of elementary discourse units, k~,, hierarchical discourse spans, ks, hierarchical nuclearity assignments, k,~, and hierarchical rhetorical relation assignments, k~. Kappa figures higher than 0.8 correspond to good agreement; kappa figures higher than 0.6 correspond to acceptable agreement. All kappa statistics were statistically significant at levels higher than a = 0.01. In addition to the kappa statistics, table 1 also displays in parentheses the average number of data points per document, over which the kappa statistics were computed. For each pair of Japanese-English discourse structures, we also built manually an alignment file, which specified in the notation discussed on page 1 the correspondence between the edus of the Japanese text and the edus of its English translation. We computed the similarity between English and Japanese discourse trees using labeled recall and precision figures that reflected the resemblance of tile Japanese and English discourse structures with respect to their assignment of edu boundaries, hierarchical spans, nuclearity, and rhetorical relations. Because the trees we compared differ from one language to the other in the number of elementary units, the order of these units, and the way the units are grouped recursively into discourse spans, we computed two types of recall and precision figures. In computing Position-Dependent (P-D) recall and precision figures, a Japanese span was considered to match an English span when the Japanese span contained all the Japanese edus that corresponded to tile edus in the English span, and when the Japanese and English spans appeared in tile same position with respect to the overall structure. For example, the English tree in figure 1 is characterized Table 2 : Similarity of the Japanese to their discourse structure below the sentence level has a recall of 4/10 and a precision of 4/11 (in Figure 1 , there are 11 sub-sentential Japanese spans). In computing Position-Independent (P-I) recall and precision figures, even when a Japanese span "floated" during the translation to a position in the English tree that was different from the position in the initial tree, the P-I recall and precision figures were not affected. The Position-Independent figures reflect the intuition that if two trees tl and t2 both have a subtree t, tl and t2 are more similar than if they were if they didn't share any tree. At the sentence level, we hence assume that if, for example, the syntactic structure of a relative clause is translated appropriately (even though it is not appropriately attached), this is better than translating wrongly that clause. The Position-Independent figures offer a more optimistic metric for comparing discourse trees. They span a wider range of values than the Position-Dependent figures, which enable a finer grained comparison, which in turn enables a better characterization of the differences between Japanese and English discourse structures. When one takes an optimistic stance, for the spans at the sub-sentential level in the trees in Table 1 In order to provide a better estimate of how close two discourse trees were, we computed PositionDependent and -Independent recall and precision figures for the sentential level (where units are given by edus and spans are given by sets of edus or single sentences); paragraph level (where units are given by sentences and spans are given by sets of sentences or single paragraphs); and text level (where units are given by paragraphs and spans are given by sets of paragraphs). These figures offer a detailed picture of how discourse structures and relations are mapped from one language to the other across all and English discourse structures discourse levels, from sentence to text. The differences at the sentence level can be explained by differences between the syntactic structures of Japanese and English. The differences at the paragraph and text levels have a purely rhetorical explanation. As expected, when we computed the recall and precision figures with respect to the nuclearity and relation assignments, we also factored in the statuses and the rhetorical relations that labeled each pair of spans. Table 2 smnmarizes the results (P-D and P-I (R)ecall and (P)recision figures) for each level (Sentence, Paragraph, and Text). The numbers in the "Weighted Average" line report averages of the Sentence-, Paragraph-, and Text-specific figures, weighted according to the number of units at each level. The numbers in the "All" line reflect recall and precision figures computed across the entire trees, with no attention paid to sentence and paragraph boundaries. Given the significantly different syntactic structures of Japanese and English, we were not surprised by the low recall and precision results that reflect the similarity between discourse trees built below the sentence level. However, as Table 2 shows, there are significant differences between discourse trees at the paragraph and text levels as well. For exampie, the Position-Independent figures show that only about 62% of the sentences and only about 53% of the hierarchical spans built across sentences could be matched between the two corpora. When one looks at the status and rhetorical relations associated with the spans built across sentences at the paragraph level, the P-I recall and precision figures drop to about 43% and 35% respectively. The differences in recall and precision are explained both by differences in the way information is packaged into paragraphs in the two languages and the way it is structured rhetorically both within and above the paragraph level. These results strongly suggest that if one attempts to translate Japanese into English on a sentence-bysentence basis, it is likely that the resulting text will be unnatural from a discourse perspective. For example, if some information rendered using a CON-TRAST relation in Japanese is rendered using an ELABORATION relation in English, it would be inappropriate to use a discourse marker like "but" in the English translation, although that would be consistent with the Japanese discourse structure. An inspection of the rhetorical mappings between Japanese and English revealed that some Japanese rhetorical renderings are consistently mapped into one or a few preferred renderings in English. For example, 34 of 115 CONTRAST relations in the Japanese texts are mapped into CONTRAST relations in English; 27 become nuclei of relations such as ANTITHE-SIS and CONCESSION, 14 are translated as COMPAR-ISON relations, 6 as satellites of CONCESSION relations, 5 as LIST relations, etc. Our goal is to learn these systematic discourse mapping rules and exploit them in a machine translation context. Towards a discourse-based machine translation system 3.1 Overall architecture We are currently working towards building the modules of a Discourse-Based Machine Translation system that works along the following lines. 1. A discourse parser, such as those described by Sumita et al. (1992) , Kurohashi (1994), and MarcH (1999), initially derives the discourse structure of the text given as input. 2. A discourse-structure transfer module rewrites the discourse structure of the input text so as to reflect a discourse rendering that is natural to the target language. 3. A statistical module maps the input text into the target language using translation and language models that incorporate discoursespecific features, which are extracted from the outputs of the discourse parser and discourse transfer modules. In this paper, we focus only on the discoursestructure transfer module. That is, we investigate the feasibility of building such a module. 3.2 The discourse-based transfer model In order to learn to rewrite discourse structure trees, we first address a related problem, which we define below: If for any tuple (Ts, Tt, C> such a sequence of actions can be derived, it is then possible to use a corpus of (Ts, Tt, C) tuples in order to automatically learn to derive from an unseen tree Ts,, which has the same structural properties as the trees Ts, a tree Ttj, which has structural properties similar to those of the trees Tt. In order to solve the problem in definition 3.1, we extend the shift-reduce parsing paradigm applied by Magerman (1995) , Hermjakob and Mooney (1997), and MarcH (1999). In this extended paradigm, the transfer process starts with an empty Stack and an Input List that contains a sequence of elementary discourse trees edts, one edt for each edu in the tree Ts given as input. The status and rhetorical relation associated with each edt is undefined. At each step, the transfer module applies an operation that is aimed at building from the units in T, the discourse tree Tt. In the context of our discourse-transfer module, we need 7 types of operations: • SHIFT operations transfer the first edt from the input list into the stack; • REDUCE operations pop the two discourse trees located at the top of the stack; combine them into a new tree updating the statuses and rhetorical relation names of the trees involved in the operation; and push the new tree on the top of the stack. These operations are used to build the structure of the discourse tree in the target language. • BREAK operations are used in order to break the edt at the beginning of the input list into a predetermined number of units. These operations are used to ensure that the resulting tree has the same number of edts as Tt. A BREAK operation is necessary whenever a Japanese edu is mapped into nmltiple English units. • CREATE-NEXT operations are used in order to create English discourse constituents that have no correspondent in the Japanese tree. • FUSE operations are used in order to fuse the edt at the top of the stack into the tree that immediately precedes it. These operations are used whenever multiple Japanese edus are mapped into one English edu. • SWAP operations swap the edt at the beginning of the input list with an edt found one or more positions to the right. These operations are necessary for re-ordering discourse constituents. • ASSIGNTYPE operations assign one or more of the following types to the tree at the top of the stack: Unit, MultiUnit, Sentence, Paragraph, MultiParagraph, and Text. These op- erations are necessary in order to ensure sentence and paragraph boundaries that are specific to the target language. For example, the first sentence of the English tree in Figure 1 can be obtained from the original Japanese sequence by following the sequence of actions (5), whose effects are shown in Figure 2 . For the purpose of compactness, the figure does not illustrate the effect of ASSIGNTYPE actions. For the same purpose, some lines correspond to more than one action,
A study by REF proposed a method for improving Japanese-to-English translation by transforming the source structure generated by a rhetorical structure theory (RST) parser, to the corresponding target structure.
The Automatic Translation Of Discourse Structures
Applied Natural Language Processing Conference And Meeting Of The North American Association For Computational Linguistics
Computer Science