A Hybrid Approach to Interactive Machine Translation - Integrating Rule-based, Corpus-based, and Example-basedMethod

1 Introduction

With the rapid development of the Internet, demand for a supporting tool for reading and writing foreign lan­ guage document is rising high these days. While conven­ tional automatic machine translation systems are useful for reading support where quick and rough translation does its job, they are not necessarily appropriate for writ­ ing support where the main task is to create a short original document such as e-mail. Since the final quality is far more important, such tool is better to offer some interactive means to control the translation result.

·current Address: NEC Research Institute, U.S.A.

With this in mind, an incremental interactive machine-aided translation method was introduced and a realization as an English writing support tool was shown[Muraki et al. , 1994; Yamabana et al., 1997]. In this method, the source sentence is translated incremen­ tally in a bottom-up manner, from a smaller part to a larger structure. In respective steps, the user can inter­ actively control the process through simple operations of translation area correction and translation equivalent selection. A rule-based transfer engine provides trans­ lations obeying user's specification and shows them on a selection window. The partial results obtained in this manner are repeatedly combined to a larger expression in the subsequent translation steps, until the whole input is converted into a target language expression.

This method offers an interactive means to combine the word dictionary information with grammar rules to obtain a direct translation of the input sentence. How­ ever, rule-based method is not the only and desirable means for translation, especially considering its cost in describing and keeping the consistency of highly specific linguistic phenomena. Although various paradigms of machine translation such as rule-based, statistics-based and example-based method have been advocated these days, there now seems to be a consensus that none of these paradigms are uniformly adequate in all aspects of the translation task.

In this article, we propose a hybrid interactive ma­ chine translation method that integrates various trans­ lation paradigms with an interactive man-machine inter­ face. In section 2, we review the rule-based interactive translation method on which the proposed method is built. In section 3, the hybrid interactive machine trans­ lation method is described, and its basic architecture and the algorithm is presented. In section 4, the current implementation status is described. Section 5 is for discussions , and the final section concludes this article.

2 An Interactive Japanese to English Translation Method

An interactive machine-aided translation method was introduced to support non-natives of English to write English material [Muraki et al., 1994; Yamabana et al., 1997]. The target user of the method is those people who have difficulty in writing down English sentences directly, in spite of the fact that s/he has a basic knowl­ edge of English to read and understand it. In this section we show how the method works by an example.

. Suppose the user is writing e-mail in English, work­ mg on an editor of a mail program. Our tool is running background as a daemon, watching the keyboard input by the user. While the user is typing English characters, the system lets them through to the editor window. The tool awakens when the user toggles on the Japanese in­ put. As soon as the first Japanese character is typed in, the tool detects and fetches it from the input queue of the operating system, opens the main translation win­ dow, and puts it there. All the subsequent characters are captured in that window, instead of the editor win­ dow. Succeeding translation is performed in this main translation window.

Suppose the input sentence is the one shown in fig­ ure 1 (a) 1 . As soon as (a) is entered, dictionary look-up process is started automatically. First the morphologi­ cal analyzer recognizes word boundaries in the sentence looks up corresponding entries in the system dictionary: and shows the result on the main window (b). At this time, content words are replaced by one of its translation equiv~lents assumed most plausible by the system, while functiOnal words are left unchanged.

This representation step, in which English words (con­ tent words) and Japanese words (functional words) are mixed, is one of important characteristics of the method. This step separates steps into word translation and later structural transfer, making translation steps clearer. Since word order and functional words carrying gram­ matical functions are unchanged, the user can easily rec­ ognize the skeleton of the sentence, and clearly grasp the correspondence between the original word and its translation equivalent. This representation also carries all interactive operations of the method on it, and has a double role in interactive operations, showing the in­ formation by the system and providing the objects for interactive manipulation.

Translation equivalent alternatives for the cursor po­ sition word (focus word) are displayed in an alternatives window, appearing nearby that word. Figure 2 is a snap­ shot of the alternatives window for ronbun (paper). The second line is highlighted to show that it is the current selection. The user can change the selection simply by a cursor movement or a mouse click on this window, then corresponding translation equivalent on the main win­ dow changes synchronously. To see the alternatives for another word, the user has only to move the cursor to that word on the main window. In addition, the user can choose an inflection in a similar manner on an inflection selection window, opened by the user's request.

1 Hereafter, slanted characters represent Japanese words in Japanese characters.

If the user needs only the result of dictionary lookup, s/he can signal the end of translation at this point. If syntactic transformation is necessary, the user needs to proceed another step. At the same time as the initial prediction of the translation equivalent, the system pre­ dicts an appropriate area for syntactic transformation, as shown by an underline in (b). Just like the translation equivalent selection, the area can be freely changed by the user . After the user confirms the selection of transla­ tion equivalents and translation area on (b) , s/he invokes translation. The system performs syntactic transfer us­ ing syntactic information in the dictionary such as ver­ bal case frame and transfer rules encoded in the system, shows the result on the main window, and replaces the original sentence with the result (c) . If there are more than one possible translations, they are shown in an al­ ternatives window similar to figure 2, allowing the user to choose among them. When the user triggers the end of translation, the result is sent to the original editor window.

Figure 3 shows translation steps for a sentence with a relative clause. This sentence has a dependency am­ biguity, so we also show how to resolve it through the interactive operation. The original sentence (a) contains a relative clause with verb kau (buy) with an antecedent bon (book). Since Japanese is head-final , the sentence­ initial case element kare-ga (he-SUBJ) can be the sub­ ject of either kau (buy) or yomu (read), causing syntactic

• (a) ~ tl'> ~-=> t~ ;$: ~ ~!v tC:. kare -ga kat -ta IJOIJ -o yoiJ -da he SUBJ buy PAST book OBJ read PAST
• (b) he tJ'> buy t~ book ~ read tC:.
• -ga -ta -o -da (c) the book he bought ~read tC:. -o -da
• (d) Someone read the book he bought
• (e) he tJ'> buy t~ book ~ read tC:.

• (f) he tJ'> the book someone bought ~read tC:. -ga -o -da
• (g) He read the book someone bought

Figure 3: Relative Clause and Syntactic Ambiguity

ambiguity.

First, let's suppose kare-ga is assumed to be the sub­ ject of the relative clause. Then the system pauses show­ ing (b), as soon as (a) is input. In (b), the translation area is assumed to be "he-ga buy-ta book". After trans­ lation trigger, the system pauses showing (c). Please note that the underlined part in (b) is replaced by its equivalent English expression "the book he bought", and the whole sentence is underlined now. After another translation trigger, (d) is obtained, with missing subject filled by some default word.

Suppose just after obtaining (d) the user noticed that this interpretation is not what s/he wants, and the case element kare-ga should be the subject of the verb of the matrix sentence. Then the user triggers undo of trans­ lation twice, returning to (b). Then sjhe notices that "he -ga buy -ta book" is treated as one phrase, against his/her interpretation. Then s/he changes the under­ lined area to "buy -ta book", excluding "he -ga" from the area (e), because this is the "correct meaningful phrase" in the user's interpretation. After translation trigger, (f) follows. Note that the subject of the relative clause is augmented by a default element. Finally (g), what the user wanted, follows. ·

3 A Hybrid Approach to Interactive Machine-Aided Translation

This section describes the model and the algorithm of the proposed method. First, the basic model of step­ wise bottom-up interactive translation is described in the subsection 3.1. Then the next subsection describes how different translation paradigms can be integrated in this model. There are also shown a brief description of re­ spective translation modules. The subsection 3.3 shows that the basic interactive operations of the method are capable of controlling the example-based translation pro­ cess as well as the rule-based translation process. This close connection between the interactive operation and the translation method is one of most important charac­ teristics of this method. In the last subsection an online learning scheme is introduced.

3.1 Basic Model of Interactive Translation

The basic model of the interactive translation method as described above is a bottom-up evaluation scheme of syntax-directed translation. In this scheme, the at­ tribute of a syntax tree node is calculated from that of the children nodes by a semantic rule paired with the syntax rule used to build the node from the children. Attributes represent a partial translation result for the structure below the node, and the attribute calculation proceeds from the lexical nodes to the root node in a bottom-up manner. User interaction is associated with the attribute calculation at each node. Before each cal­ culation, the tool pauses to show an interpretation of the underlying structure, and allows the user to examine and change it if necessary. Interactive translation proceeds from a smaller component to a larger component in a bottom-up and inductive manner. As translation mech­ anism, any method can be used as long as it is compati­ ble with the general scheme. In the current system, the node at which the system automatically pauses for inter­ action are restricted to contain at most one predicate in order to reduce the operation cost, while this restriction is not applied to the user operations. The system looks for a lowest such node, then pauses there for user oper­ ation. When user triggers translation, the attribute of the focus node and below are calculated in a bottom-up manner, then the result replaces the tree rooted by the focus node. The node serves as a kind of lexical node in the subsequent translation.

3.2 Hybrid Translation Module

The basic idea about how to integrate different transla­ tion paradigms into the above basic model is to use re­ spective translation submodules in parallel at each trans­ lation step, while each submodule processes the input in­ dependently. All the results are sorted according to the priority, then presented to the user. By unifying the data structure of input and output of all submodules, the re­ sults can be freely combined in a subsequent translation step.

The algorithm can be described as follows.

Repeat the following until the whole sentence is trans­ lated.

1. Find a minimal area for translation.
2. Show the area to the user. S/he can change the presented area if it is not appropriate.
3. Obtain possible translations of the area using re­ spective translation modules. Calculate priorities of the results.
4. Show the results to the user in the order of priority. S/he may change the selection or even directly edit the results.

1. Replace the area with the selected/modified result.

Rule-based Module

The rule-based transfer module is the backbone of the whole translation module. It provides a default result for all kind of inputs. For some linguistic constructs, it is the default translation method. For example, translation of a simple sentence is performed by a case frame transfer rule that reorders the case elements of the main verb us­ ing the verb case frame correspondence encoded in the dictionary. Generally speaking, the skeleton of a sim­ ple sentence made of a main verb and its case elements are well described by the verbal case frame, and a rule­ based treatment is suitable. For this kind of linguistic constructs, the corpus-based or example-based method would be rather useful in building the knowledge base, than being applied directly in the translation process.

Corpus-based Module

A corpus-based method will be mainly used for lexical translation. Although words are translated using a bilin­ gual dictionary, corpus-based, more precisely statistics­ based, method enters here for the translation equivalent selection through the DMAX method [Doi and Muraki, 1992; 1993]. This method uses the word cooccurrence frequencies gathered from independent source and tar­ get language corpora, and combines them in terms of the word to word correspondence in the bilingual dictio­ nary, to eliminate an accidental cooccurrence between the translation equivalents of non-cooccurring words. A major advantage of this method is that the corpora need not to be parallel.

Example-based Module

An example-based method will be mainly used to trans­ late a syntactically uniform structure such as compound noun or noun phrase. Since these structures often lack a clear syntactic feature useful for the rule-based anal­ ysis or translation, example-oriented methods such as [Sumita and lida, 1992; Hisamitsu and Nitta, 1995] have been proposed to capture their semantic and idiosyn­ cratic property better. Although the rule-based method provides the baseline, these example-based method can offer a better result that depends on appearance of a particular word.

An example will be stored as a pair of the source language expression and the target language expression, with word to word correspondences wherever possible. It also keeps the information about the head word, which determines the behavior of the phrase as a whole. The input phrase to be translated is expressed as a sequence of words, where respective word is associated with the translation determined by the previous bottom-up trans­ lation steps, if any. This is the common data structure used by all the translation modules of the method. A

constituent sub-phrase is justly identified with its head word, since translation of that phrase is already fixed. The transfer module looks for the best matching exam­ ples, and outputs the target language expression, replac­ ing the constituents with the translation specified in the matched phrase when necessary.

Example-oriented method is also used in order to de­ termine the translation equivalents of strongly cooccur­ ring words, such as an idiomatic expression. This aug­ ments the statistics-based translation equivalent selec­ tion described before.

Idiomatic Expressions

There are some words that have special syntac­ tic/semantic behavior, when appearing simultaneously. An example is denwa-wo kakeru, which usually means "make a phone call", not a literal word-by-word trans­ lation "hang a telephone". Possible translations include "make a phone call", "telephone" or expressions with similar meaning, but no literal translation can convey the proper meaning of the original expression. Since the proper translation for an idiomatic expression is not pre­ dictable from the individual behavior of the constituent words, they are seemingly exceptions to the bottom-up compositional scheme of the method. However, they can be handled without modifying the method, by combining an example-oriented method and a rule-based method.

The key idea is to separate the step of translation equivalent selection for each constituent word from the syntactic transfer step, and attribute the idiomatic prop­ erty entirely to the former. The former can be han­ dled by an example-oriented augmentation of translation equivalent selection method, whereas the latter will be performed by a purely rule-based method. This separa­ tion is justified as long as the structure of the resulting expression obeys the common rules of the target lan­ guage grammar. For example, the characteristics of the correspondence between denwa-wo kakeru and "make a phone call" can be reduced to particular correspondence between kakeru and "make". When the system detects cooccurrence between denwa and kakeru, it adds a trans­ lation equivalent "make" to the window of kakeru. The user can choose an idiomatic interpretation of this ex­ pression simply by choosing this alternative. Later pro­ cess can proceed entirely by a general transfer rule. Sim­ ilarly, the same expression can be translated into a verb "telephone" simply by giving translation "telephone" to kakeru, while denwa-wo is left without translation equiv­ alent so that it disappears in the result. Thus the essen­ tial task of idiom translation is reduced to an example­ oriented method of translation equivalent selection.

3.3 Interactive Operat ions

As described before, the basic interactive operations of the method are translation area correction and translation equivalent selection. From the viewpoint of the rule-based method, the translation equivalent selection operation is more than simply choosing from among syn­ onyms, as discussed in [Yamabana et al., 1995]. First, by specifying the translated area, one can directly resolve the dependency ambiguity. Secondly, part-of-speech of the translation equivalent may be specified through this operation, since translation equivalents with different part-of-speech appear distinctly in the alternatives win­ dow. Thirdly, the translation equivalent for functional words can be specified, and that can specify the syntac­ tic behavior of the result. Although functional words remain unchanged in the intermediate representation, some words provide an alternatives window when the cursor is located on them.

From the viewpoint of the example-based method, in­ teractive operations have different meaning. By these operations the user can control two major decisions of the method, that is, how to cover the source sentence and which example should be used. Changing the trans­ lation area implies changing the covering, and a new ex­ ample that fits better to the expanded or shortened area will be chosen as a primary candidate. Changing transla­ tion equivalent selection after translation implies chang­ ing the example used for translation. Thus, the two ma­ jor decisions in the example-based translation method can be interactively controlled without ever introducing new kind of operation.

3.4 Online Learning of Translation Instances

This scheme can offer a simple mechanism of online learning. As discussed above, the user has a control over the major decisions of either rule-based or example­ based translation. This control information can be used to learn better choice of rules or examples used. An­ other source of information is the translation result it­ self. Since the method allows interactive corrections of respective translation at each step, the correspondence between a source language expression and its translation is expected to make a satisfactory translation pair for the user. By accumulating these translation pairs, the sys­ tem will grow and adapt to the environment, especially to the user's preference.

4 Current Status of Implementation

This method was implemented as an English writing sup­ port software on personal computers, with a rule-based translation module and an idiom processing mechanism. The system dictionary contains about 100,000 Japanese entries and more than 15,000 idiomatic expressions, the latter built from scratch by the method in [Tamura et al., 1996]. Addition of the statistics-based lexical trans­ fer module and example-based transfer modules are currently under way, as well as the example learning mod­ ule.

The current system consists of the interface module and the translation module, communicating through in­ terprocess protocol. One important feature of this im­ plementation from application viewpoint is that it works as a language conversion front-end to an arbitrary appli­ cation, as described in section 2. The system works as a kind of a keyboard extension, converts a Japanese in­ put into an English equivalent, and send the result to an arbitrary application program (figure 4). This feature allows the tool to be used as an add-on function of a familiar document writing environment.

5 Discussion

There have been several approaches to integrating differ­ ent translation paradigms. The Pangloss system [Niren­ burg ed., 1995; Brown, 1996] adopts a multi-engine archi­ tecture, in which Knowledge-Based MT, Example-Based MT and Lexical Transfer MT engines independently pro­ duce translations for a part of the input sentence. The translations are registered, selected and combined on a chart-like structure. Translations from different mod­ ules are treated in a uniform manner, and selected by the priorities assigned by the respective translation en­ gines. [Chen and Chen, 1995] proposes a hybrid trans­ fer method that combines statistics-based transfer for smaller chunks and rule-based transfer for sentence-level chunks. Translation method is changed according to the size and nature of the substructure to be translated.

Our method shares the basic strategy with these pre­ vious works in that it divides the problem into subprob­ lems of translating the substructures, and tries to use the most appropriate translation method for respective problem. The point of our method is that this scheme naturally fits into the interactive translation scheme for­ merly proposed and provides a common platform for in­ tegrating various approaches to translation. In the lexi­ cal translation step, statistics-based DMAX method sup­ plies the baseline, and example-oriented recognition of idiomatic expressions provides a fine improvement. At later steps of structural transfer, the hybrid translation module enables to employ the most appropriate trans­ lation method, depending on the nature of the focused structure. The interactive operations are not only used to confirm and correct the initial selection, but also they provide a means to control various decisions in the course of the translation process.

From an application point of view, the important thing about this hybridization is that it offers a systematic method to add example-based improvement to the base­ line rule-based translation. As is well-known, some ex­ pressions used in communication are not subject to com­ positional principle of meaning interpretation. Since the word sequence itself contains some meaning not calcula­ ble from meanings of constituent words, a direct transla­ tion of the original sentence does not necessarily convey the same meaning in the target language. This is one reason that many conventional foreign language writing support tools employ an approach based on translation examples. However, these tools are often too rigid to al­ low truly free composition, only allowing one to replace a word or two in the example sentence. On the other hand, our method allows to freely combine rule-based and example-based translation results. A rule-based re­ sult can be embedded in an example-based skeleton of sentence, or vice versa. In addition, the idiom dictionary mechanism enables to detect idiomatic expressions with far separated constituents.

Finally we briefly discuss the cost of the interactive operation. Although the method is interactive, the only indispensable operation is the "next" trigger to confirm that the system's choice is fine. All other operations such as translation equivalent selection are optional. If the user continues to simply confirm the system's choice, all the judgement by the system is employed and accord­ ing result is obtained. If the user carries out a detailed interaction, changing the alternative or even editing di­ rectly, then a result comparable to a fully manual trans­ lation can be obtained. Thus the method lies between the automatic machine translation and the dictionary­ aided manual translation, where the precise location is determined by the user.

6 Conclusion

We proposed a hybrid interactive translation method, in which rule-based, corpus-based and example-based translation methods are integrated with an interactive man-machine interface for stepwise bottom-up transla­ tion. This integration will give the user a freedom to combine most appropriate results obtained from various strategies and resources. Currently the example-based and statistics-based modules are being added to the cur­ rent implementation as an English writing support tool, which is provided with the rule-based transfer module and the idiomatic expression processing function realized as a mixture of an example-oriented translation equiv­ alent selection method and rule-based structural trans­ fer. We are planning to measure the effectiveness of this method when the expansion is completed.