Incremental Japanese Spoken Language Generationin Simultaneous Machine Interpretation
Koichiro Ryu† , Atsushi Mizuno†† , Shigeki Matsubara††† ,and Yasuyoshi Inagaki†††††
Graduate School of Engineering, Nagoya University††
Graduate School of Information Science, Nagoya University†††
Information Technology Center/CIAIR, Nagoya University††††
Faculty of Information Science and Technology, Aichi Prefectural University
Furo-cho, Chikusa-ku, Nagoya, 464-8601
E-mail:k ryu@inagaki.nuie.nagoya-u.ac.jp
Abstract
Towards smooth and natural multilingual speech communication, it is desired to develop simultaneous interpretation systems. This paper proposesa technique for incremental Japanesegeneration in English- Japanese simultaneous machine interpretation. Generally, the difference of word-order inboth languages causes a fatal problem in incremental translation between
English and Japanese. In our approach, the acceptable translation result can be generated as immediately
as possible by positively utilizing inversions, repetitions, corrections, etc. The
simultaneous interpretaion can be attained by synchronous execution of incremental dependency parsing, transferand generation. The prototype systemof Enligh-Japanese incremental translation was developed based on our technique. An experiment using ATIS corpus has shown our technique to be effective for improving the output-timingof translation results.

1 Introduction
In order to provide an environment supporting
natural and smooth dialogues between different
languages, it has been expected to develop simultaneous interpreting systems. Actually, there areseveral studies on simultaneous interpreting system (J. W. Amtrup, 1999; S. Matsubara, 1997;

H. Mima, 1998). We have already proposed a simultaneous interpreting system based on transferof syntactic structure and have developed its prototype system of English-to-Japanese interpreting
LINAS LINAS parses the dependency structure ofEnglish strings generated by speech recognition.
According to it, the LINAS determines the word
order of Japanese translation and excutes lexicalconversion.
LINAS generates translations fulfilled Japanese
dependency constraints and based on the basis of
the word order of input English utterances. Therefore, LINAS generates an acceptable translation
result. However, on the other hand, due to thepowerful acting of the constraints of the output
language, there is a delay between the input andoutput timing. Namely, our conventional technique of Japanese translation generation in theLINAS has adopted dependency grammar as thegrammar of a translation. As a result, it is difficult for the system to output a translation simultaneously.
In this paper, we propose a Japanese translation
generation technique utilizing inversions. The inversion is to permit that a dependency is directedfrom right to left. It is possible to generate atranslation with more high simultaneity by permitting a translation including inversions. Moreover we examine tendency of inversions in speech
dialogue corpus and acquire the feature of inversion from it. Fulfilling the feature makes it possible to generate the acceptable translation result.
Our technique using the inversion is introduced
into the LINAS. An experiment using ATIS corpus(M. P. Marcus, 1993) has shown our techniqueto be effective for improving the output-timing oftranslation results.
This paper is organized as follows: Section
2 explains an approach of incremental Japanesegeneration utilizing inversions and corrections.
Section 3 describes the overview of simultaneousinterpreting system LINAS. Section 4 describes
our method of a generation utilizing inversions.
And an experiment using our method is presented
in Section 5.

2 Incremental Japanese Generation
In this section, We explain our method that theacceptable translation result can be generated as
immediately as possible by positively utilizing inversions,
2.1

Incremental Japanese Generation
Utilizing Inversions

Let us consider the following English:(1) I’ll go to the park with your brotherThe standard Japanese for (1) is(2) anata-no ani-to (with your brother) koen-ni(to the park) iki-masu (I’ll go)
In this case, it is not until the input of “withyour brother” that translation can be started.
However, if Japanese(3) koen-ni (to the park) iki-masu (I’ll go), anatano ani-to (with your brother)is generated as its translation, the output of“koenni iki-masu” can be started as soon as theinput of “to the park” is finished. The Japanese
sentence (3) includes an inversion phenomenon.
Although no dependency is directed from right toleft in Japanese dependency grammar, the deviation from the principle occurs frequently in thecase of spoken language, and generally such aphenomenon is called inversion. In our research,
the inversion is positively used for translation, andtherefore less delay can be achieved in simultaneous interpretation.

2.2

Features of Inversion in Spoken
Language

However, the inversion cannot necessarily be generated in any dependency, and there are some tendencies in the appearance with the characteristicof bunsetsus. We investigated the appearance tendency of inversion using a Japanese spoken language corpus with dependency structures which
was constructed at CIAIR, Nagoya University (T.
Ohno, 2003). In addition, by this research, the dependency from right to left was defined as inversion. The following character became clear as aresult of observing all the 230 inversion phenomena included in 7781 utterances (11789 bunsetsu).
• The type of head bunsetsus is predicate.
• The number of bunsetsus which depend ahead bunsetsu is two or more corresponds toa basic phrase in English.
• The part-of-speech of the last morpheme ofdependent bunsetsus is particle, noun, adverb, etc. The kind of particle is “-wa”, “de”, “-ni”, etc.
• The number of inversion in a utterance is at
most one.
2.3

Japanese Generation Utilizing
Corrections

In our method, the inversion can be used
for Japanese generation only when the abovementioned character is fulfilled. However, generally it is not decided to the last of an input
sentence whether the character is fulfilled or not.
For this reason, when it becomes clear not to fill
above-mentioned restrictions after generating inversion, the generation of inversion is avoided bygenerating a bunsetsu again. For example, when
the complete English of (1) is(4) I’ll go to the park with your brother by his car
next Sunday.
in fact, it generates(5) koen-ni (to the park) iki-masu (I’ll go), anatano
ani-to (with your brother) kare-no kuruma-de(by his car) tsugi-no nichiyobi-ni (next Sunday)
ikimasu. This is equivalent to having a correction
as a result.

English Speaker
English Voice

Speech Recognition
English Text

Dictionary
Grammar
Rule

Dependency Structure
ParsingChart

English Dependency Structure

Transfer
BilingualDictionary

Japanese Modification Relation

Japanese GenerationJapanese Text

Translation
Rule

Speech Synthesis
Japanese VoiceJapanese Listener

Figure 1:LINAS

Simultaneous interpreting System

3 English-to-Japanese Simultaneousinterpreting system LINASIn this section, we introduce the simultaneousinterpreting system LINAS, which has two mainmodules, dependency structure parsing moduleand Japanese generation module. We’ll introduce
these modules in more detail.
3.1

Overview of LINASThe protoyepe system of incremental English-toJapanese tranlstion, LINAS, has been developed.
Figure 1 shows the overview of LINAS. LINAS
is composed of four language processing modules: speech recognition, incremental parsing,transfer, Japanese generation and speech synthesis. The incremental parsing constructs the dependency structures on a word-by-word bassis forEnglish spoken sentence. Efficient dependency
structure analysis is accomplished by utilizing
the reachability relations between categories (Y.
Kato, 2001). The transfer transforms from English dependency structure to Japanese modification relations and carries out lexical conversion.
Moreover, Japanese generation makes Japanesetranslation. In this paper, we change the Japanesegeneration utilizing inversions.
3.2

parsing, which is one of the syntax analysis techniquer using a context free grammar, expresses
the result in progress as the graph called chart(M. Kay, 1980). That is, the incremental chartparsing introduces two new operationns into thestandard bottom-up chart parsing. One is the application of grammar rules to an active edge andthe other is the replacement of the leftmost undecided term with the term of an active edge.
In the incremental chart parsing, when i-th word
wi is produced, the following procedures are performed in order:

Incremental Parsing

LINAS uses an incremental chart parsing (S. Matsubara, 1997) to parse. The incremental chart1)Consultation of a dictionary :If the category of a word wi is A, the edge labeled term [wi ]A is stretched between nodes
i − 1 and i in a chart.
2)Application of grammar rules :If the term of the edge stretched between
nodes i − 1 and i in a chart is [· · ·]A 1 and agrammar rule A → A1 A2 · · · An exsts, theedge labeled term [[· · ·]A 1 [?]A 2 · · · [?]A n ]A
is added between nodes i− 1 and i in a chart.
As much as possible, this operation is repeated.
3)Replacement of terms :Let [?]X be the leftmost undecided term of
the term σ of the edge stretched between
nodes 0 and i − 1 in a chart. If the category of the term τ of the edge stereched between i − 1 and i is X, the edge labeled theterm produced by replacing the leftmost undecided term of σ with τ is added between
nodes 0 and i in a chart.
In order to map from a syntactic structure
to English dependency relations, every grammar
rules are attached a head word and implement
words. We can get English dependency relations
by using these rules.
3.3

Procedures of Generation Utiliaing NoInversion

In this section, the procedure for generating aJapanese translation including no inversion isshown. When a word is inputed, the following
procedures are performed in order:

1)Dicides whether a word can be outputed :It dicides that input words can be outputed ifeither following condition is fulfilled.
Condition 1 :No word modifies the word
Condition 2 :All words modifying the word
have already been outputed or can beoutputed.
This continue until no word is judged that it
can be outputed.
2)Dicision of the word order of a translation :In order to fulfill dependency constraints inJapanese it orders the tranlation words which
can be outputed.
3)Output :It outputs a translation ordered in Step2 andchanges the state of the words outputed “output”.
4)Correction caused by parsing error :If a word have already been outputed and theother word modifying it have not been outputed, then it changes the state of it “Notoutput”and corrects.

4 Method of Generation Utilizing
Inversion
In this section, the procedure for generating aJapanese translation including inversion is shown.
4.1

Procedures of Generation Utilizing
Inversion

When a word is inputed, the following proceduresare performed in order:
1) Dicides whether a word can be outputed :It dicides that input words except predicate
can be outputed if either following condition
is fulfilled.
Condition 1 :No word modifies the word
Condition 2 :All words modifying the word
have already been outputed or can beoutputed.
This continue until no word is judged that it
can be outputed.

2)Dicision of the word order of a translation :In order to fulfill dependency constraints inJapanese it orders the tranlation words which
can be outputed. If a predicate has alreadybeen outputed, then go to Step 3.1 else go to
Step 3.2.
3.1)Dicides whether predicate can be outputed:
It dicides that a predicate can be outputed, if
conditions of the generation of a predicate isfulfilled.
3.2)Correction caused by inversions :If the features of inversions described in Section 2.2 is not fulfilled, then it changes thestate of predicate “Not-output” and corrects.
4)Output :It outputs the translation ordered in Step2
and changes the state of outputed words“output”.
5)Correction caused by parsing error :If a word have already been outputed and theother word modifying it has not been outputed, then it changes the state of the word
“Not-output”and corrects.
4.2 Example of Generation
Table 1 shows the system processing when thesentence “I prepare the room with the bath foryou.” is inputed. The parsing uses the following
grammar rules. S →S0 $ ∗S0 → NPsubj VP∗
NP → PRON∗ | DET N∗
VP→ V∗ NPobj PP
PP→ P∗ NP
PRON→ I | you
N→ room | bathV→ prepare
DET→ the$→ .

| DET N∗PPThe above rules have one special cate-gory called head, which is indicated by the symbol “*”. The other categories in right-hand sideof rules are called complement. And the case information, subject and object, is indicated by thesubindex of the category symbols.

5 Experiment
A English-to-Japanese translation experiment
was made on LINAS and the effectiveness of ourReferences

Table 2: Experimental result
MethodOld Method
New Method

delay
2.65
2.03

Good1817J. W. Amtrup. 1999. Incremental Speech Translation.
Lecture Notes in Artificial Intelligence, 1735.

Quality of Translation
Acceptable
Unacceptable
846
748

technique utilizing inversions was evaluated. In
the experiment, 578 sentences of ATIS corpus
were used, and the delay and the quality of translations was compared between Japanese Generation using inversions and that using no inversion.
To evaluate the delay we examined an average delay time of translation words in these generation
methods. We used the following expression tocompute the average delay time D.
D=ndkk=1n(1)In the above expression, dk is an elapsed timefrom input the kth word until output its translation word. (When a correction is used, dk is until
restate its translation word.) An elapsed time goesup one unit time whenever a word is inputed. And
n is the number of words of English sentence.
We evaluated the quality of translations in threestages, good, acceptable and unacceptable, manually. Figure 2 showns the result of the experiment. As a result of the experiment, Inversions
were used in 72 translations among 578 translations and Corrections were used in 12 translations. Moreover the delay time decreased an average of about 23% per a word and the quality oftranslations decreased about only 2.8%. So theeffect of this technique can be confirmed by theexperiment.

6 Conclusion
In this paper, we proposed the method of aJapanese generation utilizing inversions so thatthe simultanesous interpreting system had beenadvanced in respect of the simultaneity of output. The English-to-Japanese translation experiment was made on LINAS and the effectiveness of
our technique utilizing inversions was evaluated.
As a result of the experiment, the improvement in
the simultaneity and the maintenance in the quality can be confirmed in the experimnet.

Y. Kato, S. Matsubara, K. Toyama and Y. Inagaki.
2001. Efficient Incremental Dependency Parsing.
Proceedings of 6th International Workshop of Parsing Technology, pp.225-228.
M. Kay 1980. Algorithm Schemata and Data Structure in Syntactic Processing. Technical Report
CSL-80-12.
M. P. Marcus, B. Santorini and M. A. Marcinkiewicz.
1993. Building a large annotated corpus of English:Penn treebank. Computational Linguistics, 19(2).
S. Matsubara, and Y. Inagaki. 1997. Incremental Transfer in English-Japanese Machine Translation. IEICE Transactions on Information and System, Vol. E80-D, No. 11, pp. 1122-1129.
H. Mima, H. Iida, O. Furuse. 1998. SimultaneousInterpretation Utilizing Example-based IncrementalTransfer. Proceedings of 15th International Conference on Computational Linguistics. pp. 858-861.
T. Ohno, S. Matsubara, N. Kawaguchi, and Y. Inagaki. 2003 Spiral Construction of SyntacticallyAnnotated Spoken Language Corpus. Proceedingsof 2003 IEEE International Conference on NaturalLanguage Processing and Knowledge Engineering,pp. 477-483.

Table 1: Example of interpretation process in LINAS
Input

Parse Tree

Modification Relation

Iprepare[[[[I]pron ]np [?]vp ]s0 [?]$ ]s[[[[I]pron ]np [[prepare]v [?]np [?]pp ]vp ]s0[?]$ ]sthe[[[[I]pron ]np [[prepare]v [[the]det [?]n[?]pp ]np [?]pp ]vp ]s0 [?]$ ]sroom[[[[I]pron ]np [[prepare]v [[the]det [room]n[?]pp ]np [?]pp ]vp ]s0 [?]$ ]s< subj, I, ? >< subj, I, prepare >< obj, ?, prepare >< null, ?, prepare >< null, prepare, ? >< subj, I, prepare >< obj, ?, prepare ><?, ?, prepare >< null, the, ? >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare ><?, ?, prepare >< null, the, room >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare >< with, with, prepare >< null, the, room >< null, ?, with >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare >< with, with, prepare >< null, the, room >< null, ?, with >< null, the, ? >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare ><?, ?, prepare >< null, the, room >< with, with, room >< null, bath, with >< null, the, bath >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare >< f or, f or, prepare >< null, the, room >< with, with, room >< null, bath, with >< null, the, bath >< null, ?, f or >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare >< f or, f or, prepare >< null, the, room >< with, with, room >< null, bath, with >< null, the, bath >< null, you, f or >< null, prepare, ? >< subj, I, prepare >< obj, room, prepare >< f or, f or, prepare >< null, the, room >< with, with, room >< null, bath, with >< null, the, bath >< null, you, f or >< null, prepare, . >with[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [?]np ]pp ]np [?]pp ]vp ]s0 [?]$ ]sthe[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [[the]det [?]n ]np ]pp ]np[?]pp ]vp ]s0 [?]$ ]sbath[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [[the]det [bath]n ]np ]pp ]np[?]pp ]vp ]s0 [?]$ ]sfor[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [[the]det [bath]n ]np ]pp ]np[[f or]p [?]np ]pp ]vp ]s0 [?]$ ]syou[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [[the]det [bath]n ]np ]pp ]np[[f or]p [[you]pron ]np ]pp ]vp ]s0 [?]$ ]s.

[[[[I]pron ]np [[prepare]v [[the]det [room]n[[with]p [[the]det [bath]n ]np ]pp ]np[[f or]p [[you]pron ]np ]pp ]vp ]s0 [.]$ ]s

No Inversion
OutputOutputPossible

OutputPossibleIwatashi-ha

Iwatashi-ha

the
room

heya-wotheroom

heya-woeetothebathwith
the
room

yokushitsu
no-aruheya-wo

youforanata
no-tameni

preparejyunbi-shimasu

Inversions
Outputeetothebathwith
theroom
prepareyouforyokushitsu
no-aruheya-wojyunbi-shimasu

anatano-tameni