Incremental Spoken Language Translation based on
A Normal-Form Conversion of CFG

Shigeki Matsubara , Hiroshi Ogawa , Katsuhiko Toyamaand Yasuyoshi Inagakiz

Faculty of Language and Culture, Nagoya University y
Department of Information Engineering, Nagoya University z
Center for Integrated Acoustic Information Research, Nagoya University x
Furo-cho, Chikusa-ku, Nagoya, 464-8601, Japanmatubara@lang.nagoya-u.ac.jp

Abstract
An incremental translation system for spoken language, which can produce the target language synchronously with a source language input, has been
proposed so far. Producing so much source language structures in the CFG-based parsing stage,
however, the system has two fatal problems: 1) difcult to work in real-time, and 2) dicult to generate correct results. This paper introduces a special
form of CFG, called M normal-form, and describes
a method of converting any CFG to M normal-form.
Since it produces less structures in the incremental
parsing, the system using M normal-from of CFG
can generate translation results with higher quality.
Experiments with a prototype system have shown
the e ectiveness of the conversion for ne-grained
incremental machine interpreting.
1 Introduction
Immediate speech comprehension and production bya spoken dialogue system are essential to a smooth
human-computer interaction. A cross-lingual spontaneous speech conversation through a machine interpreting system demands that the system should
also engage in the conversation without preventing
its coherence. Our intuitions suggest that the system should behave as an simultaneous interpreter.
In order to develop a simultaneous interpretingsystem, working synchronously with a spoken language input, a technique for translating natural language incrementally is strongly required (Iida et al.,
1996; Menzel, 1997). Towards such an ambitious application, some attempts have been recently madeso far. Kitano has proposed a technique of incremental sentence production for modeling simultaneous machine interpretation (Kitano, 1990; Kitano, 1993). As well, Amtrup has introduced chartbased incremental transfer framework for processing
head switching in German-English machine translation (Amtrup, 1995). Furuse and Iida has developed a technique of incremental translation utilizing
transfer patterns for language constituents (Furuseand Iida, 1996). Furthermore, Matsubara and Inagaki has proposed an incremental English-Japanesetranslation system (Matsubara and Inagaki, 1997b;
Matsubara and Inagaki, 1997a). In these studies,
Matsubara and Inagaki has achieved ne-grained incremental machine interpreting 1 , in spite of the difference in word-order between source and target language.
Generally speaking, the more incrementally machine interpreting system translates, the moresmoothly and eciently the cross-lingual spoken
conversation proceeds. We would like to emphasizethat an essential key to success of the ne-grained
incremental spoken language translation is to allow
the system to produce grammatically ill-formed sentences. Above all, utilizing repair expressions forthe target language production is indispensable tosimultaneous interpretation. Because the case thatthe system revises its understanding state after it
produces the target language for an initial source
fragment once is pretty common. However, we haveto pay attention to that utilizing repair expressions
so frequently brings the rather opposite e ect in thesense that the target spoken language becomes unnatural for the users. As a result of an incremental
translation experiment, there were a lot of cases thatthe system corrects itself so frequently that the user
could not understand it exactly, in spite that theresult is not incorrect (Matsubara et al., 1997a).
This paper considers a technique for reducing repair expressions which a ne-grained incremental
translation system produces. A repair usually occurs at the time when the system nds it to be incorrect later though choosing one from some possible source trees before in a deterministic way. Thismeans that the frequency in generation of repair expressions may become lower if the possibilities of
1 Fine-Grained Incremental Interpretation means that theprocessor analyses each small part of a sentence, such as eachword or morpheme, immediately it is encountered. In contrast, Coarse-Grained Incremental Interpretation occurs if
the processor waits until larger chunks of a sentence are encountered (Charter et al., 1995).

choosing incorrect ones are getting fewer. There
are two ways of solving the problem. One is to
cut down the opportunities of choosing the only result from the candidates. This is nothing but tomake the translation unit larger. The other is to reduce in advance the candidates of the trees extracted
from an initial fragment. In these solutions, beingagainst a ne-grained incremental interpreting, anapproach of making the processing unit larger cannot be adopted in this study.
A ne-grained incremental translation system,
which is based on very orthodox compositional machine translation consisting of incremental parsing,transfer and generation, has been developed so far(Matsubara et al., 1997b). Our interest is to reduce
the syntax trees produced by incremental parsing
without using except syntactic information. To accomplish this, in this paper, we introduce a normalform of a set of context free grammar (CFG) rules.
It is called M normal-form. The incremental parsing can produce less syntax trees by converting any
set of CFG rules into M normal-form in advance. As
well, transfer rules conversion in advance enables theincremental transfer processing to choose one fromless trees. In the result, the incremental generation
can produce a target language including less repair
expressions. Experimental results have shown thee ectiveness of the M normal-form conversion.
This paper is organized as follows: Section 2 explains the incremental spoken language translation
system in brief. Section 3 describes M normal-form
conversion of CFG. Section 4 reports on experimental results.
2 Incremental Speech Translation
This section explains an overview of the system for
ne-grained incremental English-Japanese machineinterpreting. For further details, the reader shouldrefer to (Matsubara and Inagaki, 1997a; Matsubaraand Inagaki, 1997b).
The system is composed of three stages: incremental parsing, incremental transfer and incremental generation. These stages work in an orthodox
fashion as being shown below, except executing theprocedures on a possibly word-by-word basis.
(1) Parsing stage: produces syntax trees forthe initial fragment using context free grammar
rules whenever a word is inputed.
(2) Transfer stage: brings target expressions
by applying transfer rules to one tree wheneversyntax trees are revised.
(3) Generation stage: produces the target
language whenever the transfer processing is executed.
Executing step-by-step for every additional word,
as it turned out, each module comes to work synchronously with speech input. Both incrementals ! np vp
det ! thenp ! det adj n adj ! red
np ! det nn ! table
Figure 1: CFG rules
parsing and transfer are based on a chart processing technique (Kay, 1980). The chart is used as
the data for representing source-structures for initialfragment. The below in Section 2 illustrates incremental parsing.
2.1

Incremental Chart Parsing

The chart has been introduced into representing
parsing results. Since the chart can represent a partial sentence structure as an active edge, it is e ective to utilize charts for incremental parsing. Incremental chart parsing (Matsubara et al., 1997b)
is carried out applying to edges two main rules:
bottom-up rule and fundamental rule. The edge
formed by a fundamental rule could be used for thetransfer processing and the one formed by a bottomup rule is not. The method is a kind of the so-called
mixed mode left-corner chart parsing method basedon reachability relations. However, the method differs from the others in the point that the operations of applying a parsing rule to an active edge
and replacing the leftmost undecided term in an active edge with the term of another active edge areintroduced.
3 A Normal-Form Conversion ofCFG
This section provides an informal explanation of M
normal-form.
3.1

M Normal-Form

First of all, let us consider incremental chart parsing of the initial fragment \The red table" (Haddock, 1989), in a sentence, for instance, \The redtable looks very nice, isn't it." with a simple
grammar shown in Figure 1. For the rst word\the", analyses (A) [[[the]det [?]n ]np[?]vp ]s and (B)[[[the]det [?]adj [?]n ]np [?]vp ]s are realized. It should be
noted that two phrase-structure trees are producedin spite that \the" is not ambiguous syntactically.
This means no more than that there exist two possibilities with regard to the categories of the coming words. One is \n" and the other is \adj;n".
When the next word comes, it will be decided. To
a greater or less extent, such phenomena happen tocommon left-corner parsing utilizing accessibility relation. What needs to be emphasized is, however,that more trees are produced in incremental parsing because the system have to estimate the morecoming words.

s ! np vp det ! thenp ! det new adj ! red
new ! adj n n ! table
new ! nFigure 2: Converted CFG rules
Let us thus consider making a certain tree represent both (A) and (B), for instance, a tree (C)[[[the]det [?]new ]np [?]vp ]s where a category \new" canbe rewrote to both \n" and \adj n". This is nothing but to rewrite phrase-structure grammar. So,
we propose converting CFG rules to a special formin advance. For example, in the above case, thegrammar is converted to rules such as Figure 2 byintroducing a category \new". Using the grammar
such as Figure 2, the parsing produces the tree (C).
The rules can be produced by introducing a new
category for a set of rules whose left hand side (LHS)
and the leftmost of right hand side (RHS) are identical respectively. In this paper, we call such special
form of context free grammar rules M normal-form,and such rules, simply, M rules.

01)
2)

LHS is identical.
The leftmost of RHS is identical.

Step 2 Excluding rules:
ifthena set consists of only one rule
add the rule to G0

Step 3 Converting rules:
for each

set consisting of rules:! 0!. 1..
! Z
1) introduce ! :a category rewritable to 0; 1; 111 ;Z2) convert them to rules:! !
!!0! !. 1..
!!Z3) add the rules whose RHS is to G4) add the rules whose RHS is ! to G

M Normal-Form Conversion
An algorithm for M normal-form conversion isshown in Figure 3. Let ; ;! be categories and6; 1;Z be categories sequences. There is no dif-

4 Evaluation
An experimental system has been developed in GNU
Common Lisp 2.2.2 on a workstation. We havemade an experiment on the system to evaluate thee ectiveness of converting CFG grammar rules toM normal-form. The conversations, whose task istravel application, consisting of 4 dialogues and 278
spoken English sentences in ATR Dialogue Database
have been used. The average length is 7.2 words.
The dictionary and context free grammar have madein the scale of 570 words and 185 rules respectively.
The set of CFG rules has been converted according
to the M normal-form conversion algorithm. 159
rules became the target of the conversion, as a result,the number of the rules has increased by 77 to 262.
The success rate, number of trees and translation
time have been measured on the grammar before
the conversion and after that. Experimental results0

G := f g;
while G =6 f g dostep 1 Dividing rules:
divide G into sets consisting of the following rules:

3.2

ference in acceptable sentences between a grammar
and the converted grammar. The incremental parsing can produce less syntax trees by converting any
set of CFG rules to M rules in advance according
to Figure 3. As well, since they correspond to thegrammar rules in a one-to-one way, transfer rules
can be also converted in advance. The incremental
transfer processing have only to apply the converted
rules to a syntax tree.

a set of CFG rules G
a set of converted CFG rules G

Input:
Output:0Figure 3: An algorithm of M normal-form conversion
Table 1: Comparison of translation result between
before M normal-form conversion and after that
item
before aftersuccess rate(%)
59.7 70.5
repair occurrence per sentence
3.25 2.25
translation time per word (sec.) 2.65 0.046
parse trees per word
522.7 43.6
are shown in Table 1.
4.1

Experimental on success rate

The success rate was examined. As Table 2 shows,
we classi ed the sentences according to their translation results. In the case of using the grammar before
the conversion, 166 of sentences, classi ed into A)or B), are correct, providing a success rate of 59.7%.
On the other hand, the experiment with M normalform grammar translated 196 sentences correctly.
The success rate increased by 10.5% to 70.5%. In addition, the number of repair expressions occurrenceReferences
Table 2: Success rate of 278 sentences
J.W. Amtrup. 1995. Chart-based Incremental
Transfer in Machine Translation. In Proc. ofsentences (rate)
type
beforeafter 6th International Conference of Theoretical andA)correct (no repair)0 (0.0 %) 35 (12.6 %) Methodological Issues in Machine Translation,B)correct (repair)
166 (59.7 %) 161 (57.9 %) pages 131{138.
C)unnatural76 (27.3 %) 38 (13.6 %) N. Charter, M. Pickering, and D. Milward. 1995.
D)incorrect
35 (12.6 %) 43 (15.5 %) What is incremental interpretation. In D. MilE)parsing failure
1 (0.4 %)
1 (0.4 %) ward and P. Sturt, editors, Incremental Interpretation, pages 1{22. Edinburgh Working Papers in
Cognitive Science, Vol. 11.
O. Furuse and H. Iida. 1996. Incremental Translaper sentence on the average decreased from 3.25 totion Utilizing Constituent Boundary Patterns. In
2.25. M normal-form conversion resulted in that 35
Proc. of 16th International Conference on Comsentences in B) and 30 sentences in C) are classi ed
putational Linguistics, pages 412{417.
into A) and B) respectively, because of the reduction N.J. Haddock. 1989. Computational Models of Inof repairs. The result shows the e ectiveness of M
cremental Semantic Interpretation. Language andnormal-form conversion for ne-grained incremental
Cognitive Precesses, 4(3/4):337{368.
spoken language interpreting. The reason why 8 sen- H. Iida, E. Sumita, and O. Furuse. 1996. Spokentences in 3) are classi ed into 4) is that the heuristic
Language Translation Method Using Examples.
about the order of the grammar rules was destroyed
In Proc. of 16th International Conference on
a little by the conversion.
Computational Linguistics, pages 1074{1077.
MKay. 1980. Algorithm Schemata and Data Struc4.2 Experimental on translation speedtures in Syntactic Processing. In Technical Report
Translation time per word was examined on aCSL-80-12.
SUN UltraSPARC-II workstation (Main memory: H. Kitano. 1990. Incremental Sentence Production
512MB, CPU: 248MHz). The time on the averagewith a Parallel Marker Passing Algorithm. Indecreased from 2.65sec to 0.046sec. Almost of theProc. of 13th International Conference on Comtranslation time is spent on parsing. Because theputational Linguistics, pages 217{222.
parsing have to produces all of possible trees though H. Kitano. 1993. Speech-to-Speech Translation:
both transfer and generation have only to deal with
A Massively Parallel Memory-based Approach.
one tree. The result leads to the conclusion thatKluwer Academic Publishers.
M normal-form converting is e ective for speech-to- S. Matsubara and Y. Inagaki. 1997a. Incremental
speech translation with high synchronization.
transfer in english-japanease machine translation.
IEICE Transactions on Information and Systems,
5 Concluding Remarks
E80-D(11):1122{1129.
S.
Matsubara and Y. Inagaki. 1997b. Utilizing
This paper has proposed a technique for reducing
Extra-Grammatical
Phenomena in Incremental
the repair expressions produced in an incremental
English-Japanese
MachineTranslation. In Proc.
spoken language translation system. A special formof7thInternational
Conferenceof Theoreticalof a set of CFG rules, called M rules, and a methodandMethodological
IssuesinMachineTranslaof converting any set to such form have been introtion,pages
131{138.
duced. Since incremental parsing can produce less S. Matsubara, S. Asai, Y. Inagaki, and K. Toyama.
trees by using M rules, incremental transfer might
1997a. Incremental Spoken Language Translation
be able to avoid choosing incorrect trees as the tarUtilizing
Grammatically Ill-formed Expressions.
get. Therefore, the system can decrease the freIn
Proc.
of
3rd Conference of Paci c Associationquency of repair expression occurrence in the target
for
Computational
Linguistics, pages 188{194.
speech. Experiments with a prototype system haveshown the technique to be e ective for ne-grained S. Matsubara, S. Asai, K. Toyama, and Y. Inagaki.
1997b. Chart-based Parsing and Transfer in Inincremental machine interpreting.
cremental Spoken Language Translation. In Proc.
Acknowledgements: The authors would like toof 4th Natural Language Processing Paci c Rim
thank Satoru Asai for his valuable contributions on
Symposium, pages 188{194.
an earlier version of this study. This paper owes W. Menzel. 1997. Parsing of Spoken Language unmuch to the valuable discussions with Yoshihide
der Time Constraints. In Proc. of 11th EuropeanKato. This research has been supported in part by
Conference of Arti cial Intellingence, pages 560{
The Hori Information Science Promotion Founda564.
tion.