Incremental Spoken Language Translation Utilizing
Grammatically Ill-formed Expressions
Shigeki Matsubara Satoru Asai Yasuyoshi Inagaki

Department of Computational Science and Engineering
Nagoya University
Furo-cho, Chikusa-ku, Nagoya 464-01 Japanfmatu,asai,inagakig@inagaki.nuie.nagoya-u.ac.jp
Katsuhiko Toyama

Department of Computer Science
Chukyo University
101 Tokodate, Kaizu-cho, Toyota 470-03 Japan
toyama@sccs.chukyo-u.ac.jp
Abstract
This paper proposes a system for incremental English-Japanese spoken languagetranslation, the system behaving like simultaneous interpretation. Since spontaneous speech appears continuously, each stage of a spoken language translation systemshould work incrementally. However, machine translation systems which have been
proposed so far can not achieve high degree of incrementality because of the di erence in word-order between the source language and the target one. In this paper, thesystem utilizing grammatically ill-formed expressions characterizing Japanese spoken
language such as repetitions, inversions, ellipses, repairs and hesitations, we have succeeded in the incremental transfer from English to Japanese. An experimental systemon the basis of incremental chart parsing framework has been implemented. To evaluate the system we have made an experiment with 278 English dialogue sentences.
228 of them are translated correctly, providing a success rate of 82.0%, and 47msec
on the average was taken to process one word. These results show our technique tobe useful for spoken language translation with acceptable accuracy and high real-timenature.

1 Introduction
Spontaneously spoken language, which is di erent
from written language, has the feature that the appearance process is continuous. In spoken languagetranslation, therefore, highly real-time processing isstrongly required. However, most machine translation systems which have been proposed so far work on
a sentence-by-sentence basis. This means that theirsystems cannot start transferring it until the utterance of the whole sentence nishes, so that shouldlose real-time nature of processing.
In order to develop advanced speech-to-speechtranslation systems, a technique for translating spoken language incrementally and synchronously is required [Menzel, 94]. As such frameworks, Kitano has

proposed a method of incremental sentence production for modeling simultaneous English-Japanese interpretation [Kitano, 90]. As well, Amtrup has introduced a method of chart-based incremental transfer
for head switching in German-English machine translation [Amtrup, 95]. We, however, should point out
that their methods do not achieve high degree of incrementality and synchronicity because of the di erence in word-order between the source language andthe target one. For example, let us consider to incrementally translate the following English simple sentence into Japanese, the word-order of which is different from that of English.
(1.1) Ken met her in the park near the school
yesterday.
The standard translation of (1.1) is considered to bethe following Japanese sentence:(1.2) ken-wa (Ken) kinoo (yesterday) gakko-no
soba-no (near the school) koen-de (in the park)
kanojo-ni (her) atta (met).
Noted that it is impossible to utter \kinoo" appearing
secondly in (1.2) until \yesterday" appearing lastlyin (1.1) is heard, that is to say, (1.2) can not be
outputted except \ken-wa" until the input of (1.1)
nishes. This example illustrates that the di erence
in word-order between the source language and thetarget one might cause the system to lose real-timenature. In fact, both of Kitano and Amtrup adopt
just such the translation method as they have theproblem discussed above. In order to overcome thisdiculty, it is necessary to develop a technique for incremental translation whose processing synchronizes
with the input [Inagaki and Matsubara, 95].
This paper proposes a system for incremental
English-Japanese spoken language translation, thesystem translating English input words into Japanese
according to the order of appearances of them. The
system utilizes grammatically ill-formed expressions
characterizing Japanese spoken language, that is tosay, produces Japanese translations including theexpressions such as repetitions, inversions, ellipses,
errors, repairs and hesitations. The frequent utilization of these expressions is a key to success ofthe exceedingly incremental translation of English
into Japanese. There have been many discussions
about the way of robustly analizing grammatically
ill-formed expressions peculiar to spoken language sofar. In contrast, since they are used frequently inhuman daily conversations, it seems to be quite allright for spoken language translation systems to utter grammatically ill-formed sentences.
An experimental system which translates English dialogues into Japanese on a possibly word-byword basis has been implemented on the basis of achart processing framework. The system is mainlycomposed of two modules: incremental parsing andtransfer, which work synchronously with each other.
Working in an exceedingly incremental fashion, thesystem can be expected to be available for advanced
real-time machine translation with simultaneous interpretation.
To evaluate the e ectiveness of the system,
we have made an experiment with 278 English spoken sentences in ATR Dialogue Database[Ehara et al., 90]. As a result, 228 of the sentences
are translated correctly, providing a success rate of
82.0%. Moreover, we have con rmed that the system
outputs the corresponding Japanese speech as soon
as a spoken English word is inputed. These show thesystem to be useful for spoken language translation
with acceptable accuracy and high real-time nature.

This paper is organized as follows: Section 2 explains the idea of using ill-formedness for the incremental translation. Section 3 describes the overview
of the incremental spoken language translation system. Section 4 reports on the experimental results.
Section 5 discusses that the system produces grammatically ill-formed sentences.

2 Utilizing Grammatically Illformed Expressions
The expressions such as repetitions, inversions, ellipses, repairs and hesitations are grammatically illformed but natural in Japanese daily convesation.
Japanese people can usually understand the speech
including them. For the purpose of translating simultaneously, the system which this paper proposes
utilizes these expressions in an e ective way. Thissection illustrates the way of utilizing them.

2.1 Ill-formed Expressions: How to
Utilize
2.1.1

Repetitions

In general, repetitions are used for adding the moredetailed information. For example, the system translates an English sentence (2.1) into the Japanese(2.2).
(2.1)

I live in a university dormitory.

(2.2) watashi (I) wa sunde-imasu (live). daigaku-no(university) ryoo-ni (in a dormitory) sunde-imasu(live).

As soon as an English verb \live" is inputed, the system outputs the corresponding Japanese verb \sundeimasu". Then, since a verb usually appears at the endof the sentence in Japanese, here ends the rst translation once. The system re ects the expressions which
follow the source verb into the second sentence of thetranslation, and additionally, outputs the target verb
\sunde-imasu" last again.
The standard translation of (2.1) is considered tobe the following Japanese sentences:(2.3) watashi-wa (I) daigaku-no (university)ryoo-ni (in a dormitory) sunde-imasu (live).

Here, we emphasize, as well as (2.3), that (2.2) represents the semantic content of (2.1) exactly and mostJapanese people can comprehend it correctly.

total processing time of the system
Input Ken met

her

in

the

park

near

the

schoolyesterday . source expression

target expression
OutputKen-wakinoo gakko-no soba-no koen-de kanojo-ni atta.
time

waiting time of the user

Figure 1: Timing of the output of (1.2)
total processing time of the system
Input Ken

met

her

in

the

park

near

the

schoolyesterday .

source expression
target expression

OutputKen

wa atta. kanojo-ni

koen-deeetogakko-no soba-no koen-de kinoo atta.
time

waiting time of the user

Figure 2: Timing of the output of (2.10)
2.1.2

Inversions

The word-order of Japanese is very di erent from thatof English. However, some else to be borne in mind
here is that the word-order of Japanese is considerably exible. This means that, even if the system produces the corresponding Japanese speech according tothe order of appearances of English words, the user
could understand it easily. For example, although theconventional Japanese translation of (2.4) is \konotsuaa-wa ikura desu-ka", most Japanese people canunderstand (2.5) which the system outputs.
(2.4) How much is this tour?
(how much) desu-ka (is). kono (this)(tour).

(2.5) ikura
tsuaa-wa
2.1.3

Ellipses

The various words are frequently omitted in Japanese.
The system also makes up more natural translations
by omiting various target words. Note that in (2.2)
the locative case of the rst sentence and the nominative case of the second one are omitted.
2.1.4

Repairs

Many input sentences include some structural/lexical
ambiguities. In incremental language processing, particularly, the ambiguities increase because of incompleteness of the input information. The system, however, is forced to select the most plausible one for the
purpose of achieving high incrementality. This meansthat the translations may include errors which could
be found later. Finding the errors, the system makes

up a correct translation by repairing them. For example, \these" in (2.6) can usually take two parts ofspeech: a demonstrative pronoun and a demonstrative adjective. Even if the system outputs a pronoun\korera-wa", it can repair the translation by uttering
an adjective \korera-no" later.
(2.6) And are these tours expensive?
(2.7) sore-to (and) korera-wa (these) tsuaa (tours),
korera-no (these) tsuaa-wa (tours) takai-desu-ka (areexpensive?).
2.1.5

Hesitations

The hesitations have a tendency of appearing before
the repair expressions [Matsubara and Inagaki, 96].
In the translation of (2.8), the system outputs thehesitation \eeto" before outputting the repair expression \nijuu-yokka-ni syuppatsu".
(2.8) Leaving on the 24th and leaving on the 31st?
(leaving on the(leaving on the(2.9) nijuu-yokka-ni syuppatsu-wa
eeto nijuu-yokka-ni syuppatsu
sore-tosanjuu-ichinichi-ni syuppatsu?

24th) ,
24th)
(and)(leaving on the 31st?).

The system can produce more natural utterances byutilizing hesitations e ectively.

2.2 Typical Example
According to the idea illustrated in the previous subsecsion, the system translates (1.1) as follows:ken (Ken) wa atta (met). kanojo-ni (her)(in the park), eeto, gakko-no soba-no(in the park near the school) kinoo(yesterday) atta (met).
Figure 1 and 2 show the timing of the output of (1.2)
and (2.10) respectively. Comparing Figure 2 with 1, it
is obvious that the incremental system can output thetarget language synchronously with the input, andtherefore both the waiting time of the user and thetotal translation time are getting shorter.
Comparing (2.10) with (1.2), what is more, thecharacteristic features of (2.10) are the following
points: The verb \atta" in the rst sentence is repeatedat the last in the second one.
 The locative case \koen-de" and the objective
case \kanojo-ni" are inversed in word-order.
 The objective case in the rst sentence is omitted and the nominative case in the second sentence is also done.
 The error \koen-de" is corrected by speaking\gakko-no soba-no koen-de" afterward.
 The hesitation \eeto" is inserted.
The Japanese sentence (2.10) includes the grammatically ill-formed expressions: repetition, inversion, ellipses, error, repair and hesitation. However, we
would like to emphasize that (2.10) does not only represent the semantic content of (1.1) correctly, but canalso be understood easily by most Japanese people.
Though we showed a translation example of a simple
declarative sentence here, the system can cope withvarious type of English sentences by utilizing various
ill-formed expressions e ectively.

(2.10)
koen-dekoen-de3 Overview of the System
To demonstrate the feasibility and the usefulness of
the incremental English-Japanese spoken languagetranslation system, we have developed an experimental system in GNU Common Lisp 2.2. For the purpose of the translation experiment with ATR Dialogue Database [Ehara et al., 90], the system has
been implemented in the scale of English lexicon 476
words and 204 grammar rules, and also the transfer rule has been established corresponding to eachgrammar rule.
Figure 3 shows the con guration of the system.
The system is composed of eight components: speech
recognition, speech synthesis, incremental parsing, incremental transfer, parsing rules, transfer rules, a dictionary and a chart. To represent incomplete struc-

English Speaker
English Speech
Speech Recognition
Parsing
Rules

English Word

Incremental Parsing

S-terms

Chart

Dictionary

Incremental Transfer
Transfer
Rules

S-termJapanese
Speech Synthesis
Japanese Speech

Japanese Listener

Figure 3: Con guration of the systemtures gained by incremental syntactic analysis, wehave adopted a chart-based framework in both theparsing module and the transfer one. The chart component is the data structure which represents possible
phrase structures of the source language on the wayof the input. The system translates English sentences
incrementally and synchronously by executing the below (1)-(2) sequentially for each word.
(1) Incremental parsing makes edges with theterms, whose syntactic categories are sentences,
as the labels. From now on, we call such theterm, simply, s-term. The parsing procedure follows the bottom-up chart processing framework.
The altering point for the orthodox bottom-up
chart parsing method [Kay, 80] is that for embodying the s-term gradually, the syntactic operation of replacing an undecided term in the sterm with the other active one has been de ned.
Therefore, the parsing module behaves in thesame way as combinatory categorial grammar[Steedman, 87] which is well-known as a framework of incremental parsing. If no s-term can begained newly, the system fails in the translation.
(2) Incremental transfer transforms the sentence structure which incremental chart parser
has made, to the target expressions by applying transfer rules in a top-down fashion. How
the system utilizes grammatically ill-formed expressions is described as the transfer rules. In
the spoken language translation, the source expressions transferred once does not have to betransferred any longer. Therefore, the incremental transfer marks such the expressions in s-term
as transferred.

Table 1: Translation results of 278 sentences

Occurrences

type
sentences rate(%)(A) correct
228
82.0(B) unnatural33
11.9(C) incorrect
165.7(D) failed
1
0.4

3

Table 2: Incorrect translations

1

cause
sentences rate(%)
too many repairs
33
11.9
structural ambiguity
8
2.9
lexical ambiguity
3
1.1
idiomatic phrase
3
1.1
ill-formed source sentence10.4
euphonic changes
1
0.4
parsing error
1
0.4

4 Evaluation
We have made an experiment on the prototype system. The conversations consisting of 4 dialogues
and 278 English sentences in ATR Dialogue Database[Ehara et al., 90] have been used. The average sentence length is 6.8 words. The dialogue task is applications of travels. However, since the purpose ofthis study is to enhance the real-time nature of spoken language translation, the inputs are restricted ongrammatically well-formed sentences from which theill-formedness such as hesitations and errors were excluded.
First, the success rate was examined. As Table 1
shows, we have classi ed the sentences according to
the translation results. 228 sentences are translated
correctly, providing a success rate of 82.0%. Appendix shows typical correct translations. The result shows the system to be acceptable for spoken
language translation. The translations gained on thesystem are di erent from those on a conventional system in the sense that they include many ill-formed
expressions. However, the translations represent thesemantic contents of the source sentences correctly.
As Table 2 shows, furthermore, unsuccessful 50 sentences can be also classi ed according to the causes.
Next, the translation time of one input word
was measured on SparcCenter 1000 (SuperSPARC
50MHz). The average time, 47msec, is less than the
average speech time for one word, therefore, we canconclude the system to be usable for speech-to-speechtranslation with high real-time nature.

Average

2

0

0

5

10
Length of Sentence15(Words)Figure 4: Relation between source sentence lengthand occurrences of repairs

5 On Producing Grammatically Ill-formed Sentences
Spontaneous spoken language, which is di erent
from written language, can be characterized as
the frequent appearances of ill-formed expressions[Sagawa et al., 94]. Accordingly, the methods of robustly analizing ill-formed sentences have been required. Likewise, the e ective techniques for producing spontaneous speech should be developed. To
this end, utilizing grammatically ill-formed expressions must be one of such the techniques. In particular, as this paper demonstrates, it is considered thatthe appropriate use of repairs is e ective for various
real-time speech production systems.
The problem of the appearance of too many illformed expressions, however, has been left. As Table
2 shows, 11.9% translations have been judged as incorrectness because of too frequent appearances ofrepairs. In particular, the longer the source sentence
becomes, the more repairs appear in the translation,
as Figure 4 illustrates. In order to solve this problem, (1) the elaborate studies on the frequency ofill-formed expressions in utterances of human speakers/interpreters, and (2) the investigations that theusers evaluate the Japanese speech which the systemproduces are required.

6 Concluding Remarks
This paper has proposed a system for incremental
English-Japanese spoken language translation. Utilizing ill-formed expressions characterizing Japanesespeech has been a key to success of translating English speech to Japanese speech incrementally. Since
the high degree of incrementality is required rather
than that of quality in spoken language translation, it
seems to be quite all right for spoken language translation systems to produce the sentences including illformed expressions.
We have implemented a prototype system in Common Lisp. The experiment with the system has shown
the system to be usable for spoken language translation with acceptable accuracy and high real-timenature.
In this paper, the system utilizing the grammatical ill-formedness as the output has been described.
On the other hand, we have not been concerned withthe grammatically ill-formed input. In spontaneous
speech, however, the ill-formedness as utilized in thispaper appears frequently. Though it is not evident
whether the chart parser introduced in this paper canprocess ill-formed sentences incrementally, it might
be possible to construct incremental parser for illformed inputs by extending the methods of parsing ill-formed inputs on a sentence-by-sentence way[Mellish 89, Kato 94]. It is necessary to investigate amethod of incrementally translating ill-formed input
using the parser.
The achievement of this paper can be regarded
as the rst step toward the development of simultaneous interpreting system, which is just one ofambitious applications in the near future. As therelated application system, we can consider multimodal dialogue translation. In order that the user
may simultaneously understand various information
through some modalities such as speech, text, face expressions, glances and gesture, the system is required
to output the translation in a synchronous fashion.
This system can be expected to be also available forthis application.

Acknowledgements
The authors wish to thank Mr. Keiichi Iwashima,
Mr. Yoshihide Kato and all members of their laboratory for their helpful discussions. The rst author
has been supported by Support Center for Advanced
Telecommunications Technology Research, Foundation (SCAT).

References[Amtrup, 95] Amtrup J. W. Chart-based Incremental Transfer in Machine Translation.
Proc. of 6th Int. Conf. of Theoretical andMethodological Issues in Machine Translation (TMI'95), 188-195 1995.

[Ehara et al., 90] Ehara T., Inoue N., Kohyama H.,
Hasegawa T., Shohyama F. and Morimoto T. Contents of the ATR Dialogue Database. Technical Report TRI-0186, ATR Interpreting Telephony Research Laboratories, 1990. (in Japanese)[Kato 94] Kato T. Yet Another Chart-Based Techniques for Parsing Ill-Formed Input. Proc.
of 4th Conf. on Applied Natural Language
Processing (ANLP'94), 107{112 1994.

[Inagaki and Matsubara, 95] Inagaki Y. and Matsubara S. Models for Incremental Interpretation of Natural Language. Proc. of 2nd

Symposium on Natural Language Processing (SNLP'95), 51{60 1995.

[Kay, 80] Kay M. Algorithm Schemata and Data
Structures in Syntactic Processing. Technical Report CSL-80-12, Xerox PARC,
Oct. 1980.
[Kitano, 90] Kitano, H. Incremental Sentence Production with a Parallel Marker-Passing
Algorithm. Proc. of 13th Int. Conf.
on Computational Linguistics,
ING'90), 217{222 1990.

(COL-[Matsubara and Inagaki, 96] Matsubara S. and Inagaki Y. A Study on Features and Phenomena of Japanese Spoken Language in
Simultaneous Interpretation. Proc. of IE-

ICE Fall Information and Systems Society
Conf. '96, 55 1996. (In Japanese)[Mellish 89] Mellish C.S. Some Chart-Based Techniques for Parsing Ill-Formed Input. Proc.
of 27th Annual Meeting of Association
for Computational Linguistics (ACL'89),

102{109 1989.
[Menzel, 94] Menzel W. Parsing of Spoken Language under Time Constraints. Proc. of

11th European Conf. on Arti cial Intelligence (ECAI'94), 560-564 1994.

[Sagawa et al., 94] Sagawa Y., Ohnishi N. and Sugie
N. A Parser Coping with Self-Repaired
Japanese Utterances and Large Corpusbased Evaluation. Proc. of 15th Int. Conf.
on Computational Linguistics,
ING'94), 593{597 1994.

(COL-[Steedman, 87] Steedman M. Combinatory Grammar and Human Sentence Processing. J.
Gar eld (ed.), Modurality in Knowledge
Representation and Natural Language Understanding, MIT Press, 187{205 1987.

Appendix
Typical Correct Translations 1

 Hi, yes, I am interested in booking a tour toHong-Kong, please.
もしもし (hi), はい (yes), 興味があります (I aminterested). ツアーを予約することに (in booking
a tour) えーと, 香港への (to Hong-Kong), ツアーを予約することに (in booking a tour) 興味があります (interested).
 And what does that include?
それと (and) 何は (what), あっ, 何を (what) それは (that) 含みますか (inclue) ?
 I think it was 3days.
思います. (I think) それが (it) ３日間であったと(was 3days).
 I am looking forward to hearing from you.
楽しみにしています (I am looking forward). 話
しを聞くこと (to hearing), えーと, あなたから話しを聞くことを (to hearing from you) 楽しみにしています (am looking forward).
 I would like to stay longer if possible.
滞在したいです (I would like to stay). より長く
(longer) もし可能なら (if possible) 滞在したいです (would like to stay).
 Does that price include meals?
それは (that), えーと, その値段は含みますか(does that price include)？ 食事を (meals) 含
みますか (does include)？
 How much would this trip cost?
いくら (How much) この旅行は (this trip) 費用がかかる (cost) だろうか (would)？
 Actually 6 or 7 would be best for me?
実際 (actually), 6 時または 7 時は (6 or 7) 最もよい (be best), あのー, 私にとって (for me) 最もよいものであるだろう (would be best).
 I am in Japan for a short visit with my husband.
日本に (in Japan) 少しの間います (am for ashort visit). えー, 私の夫といます (am with myhusband).
 Well, I am kind of interested in seeing someJapanese temples and Buddas and things likethat.
えーと (well), ちょっと興味があります (I amkind of interested). いくつかの日本の寺と仏1 \えーと", \あっ", \あのー", \えー" and \あ" are kinds ofhesitations in Japanese.

陀, それとそのような類のものを見ることに (inseeing some Japanese temple and Buddas andthings like that) ちょっと興味があります (amkind of interested).
 I like taking showers.
好きです (I like). シャワーをすることが (taking
showers) 好きです (I like).
 I am staying at the Marunouchi Hotel.
泊まっています (I am staying). えーと, 丸の内ホ
テルに (at the Marunouchi Hote) l 泊まっています (am staying).
 Leaving on the 24th and leaving on the 31st?
24 日に出発 (leaving on the 24th) と (and) 31 日に出発 (leaving on the 31st)？
 I don't think that's possible.
思いません (I don't think). それが可能であると(that's possible).
 Sure, the name is Lenelle Degenhardt.
ええ (sure), 名前は (the name) レネーレ デーゲ
ンハルドです (is Lenelle Degenhardt).
 I don't have a phone.
もっていません (I don't have). 電話を (a phone).
もっていません (don't have).
 I'm a university student here in Japan and I am
interested in booking a tour to India.
大学生 (a university student), えー, ここ (here)
日本の大学生です (am a university student inJapan). それと (and) 興味があります (I am interested). ツアー (a tour), あ, インドへのツアーを (a tour to India) 予約することに (in booking)
興味があります (am interested).