Incremental Dependency Parsing of Japanese Spoken Monologue
Based on Clause Boundaries
Tomohiro Ohno†a), Shigeki Matsubara‡§, Hideki Kashioka§,
Naoto Kato§ and Yasuyoshi Inagaki\†Graduate School of Information Science, Nagoya University, Japan‡Information Technology Center, Nagoya University, Japan§ATR Spoken Language Translation Research Laboratories, Japan\Faculty of Information Science and Technology, Aichi Prefectural University, Japana)ohno@el.itc.nagoya-u.ac.jp

Abstract
In applications of spoken monologue processing such as simultaneous machine interpretation and real-time captions generation, incremental language parsing is strongly required. This
paper proposes a technique for incremental dependency parsing of Japanese spoken monologue on a clause-by-clause basis.
The technique identifies the clauses based on clause boundaries
analysis, analyzes the dependency structures of them, and tries
to decide the dependency relations with another clauses, simultaneously with the monologue speech input. The dependency
relations are generated at the stage before the input of the entire
monologue, and therefore, our technique can be used for language parsing in simultaneous Japanese speech understanding.
An experiment using Japanese monologues has shown that our
technique had the same degree of the performance as the usual
dependency parsing for monologue sentences.

1. Introduction
In applications of spoken monologue processing such as simultaneous machine interpretation and automatic real-time captions generation, incremental language parsing is strongly required. There exist several researches about incremental parsing (e.g. [1, 2, 3]). In these researches, what kind of language
unit is defined as a parsing unit becomes a point.
This paper proposes a technique for incremental dependency parsing of spoken Japanese monologue on a clause-byclause basis. The technique identifies the clauses based onclause boundaries analysis, analyzes the dependency structuresof them, and tries to decide the dependency relations with another clauses, simultaneously with the monologue speech input. The dependency relations are generated at the stage before the input of the entire monologue sentence, and therefore,
our technique can be used for language parsing in simultaneous
Japanese speech understanding. Furthermore, our technique
identifies the dependency structure for all bunsetsus 1 composing a monologue which is not divided into sentences. This corresponds to the monologue’s feature that it is difficult to preliminarily divide it into sentences because there is not sentence
breaks clearly in monologues. An experiment using Japanesemonologues has shown that our technique had the same degreeof the performance as sentence-by-sentence dependency parsing.
1 A bunsetsu is one of the linguistic units in Japanese, and roughly
corresponds to a basic phrase in English. A bunsetsu consists of one
independent word and more than zero ancillary words. A dependency
is a modification relation that a dependent bunsetsu depends on a headbunsetsu. That is, a dependent bunsetsu and a head bunsetsu work as amodifier and a modifyee, respectively.

()!
&  
"#$'%'&]b^c_`d]^_a ehfafgif_j]_akj cii`oin_b qop^rs_fn ]fi^bfc]nc]_j ]qoi^_ncfj^qg_if]cs] `cbmt`nc]fiu ]`^m_aq_`qc]f`s_ i_cavwxsd fj
lmmfn_
q``qLKMfsi]f`^NicG]OBPGJGQKBNRQSTTGHBLJJIDJHBUKABIKABNULVGJUGHLKBQKALK@ABCDEFGHKAICBNLGJGKIGJCIF
AK
TLU9WIHL/KGJXK/ABHLC5;GKLF5CDJ6GQAO55BJ9KG3QJBLN
FV5YZ[=\ 3
I/,.012ITCBIC,34F5B67I.8
;
5
7:
,
,-,.
,.
,
:
:
.7
,
4
:
**++,-,.
<.:<<.:,-,./,.012,34567.897:,/,-,./,.5;<.:,5:<6:59,34:5;<.:?3,5:<,7;:=<4073/440<:,4<:,* 4<:, 7<.421*?34<:,*><.:,5:<Figure 1: Relation between clause boundary and dependency
structure

2. Parsing Unit of Japanese Monologues
In our research, we adopt a clause as a parsing unit and workout the incremental dependency parsing system which can output the dependency structure of a clause simultaneously withthe monologue speech input. In Japanese, a clause basicallycontains one verb phrase. Therefore, a complex sentence or acompound sentence contains one or more clauses. Moreover,since a clause constitutes a syntactically sufficient and semantically meaningful language unit, it can be used as an alternative
parsing unit to a sentence. Our proposed method assumes that amonologue is a sequence of one or more clauses, and every bunsetsu in a clause, except the last bunsetsu, depends on anotherbunsetsu in the same clause. As an example, the dependency
structure of a part of a Japanese spoken monologue:“先日総理府が発表いたしました世論調査によりますと死刑を支持するという人が八十パーセント近くになっております（The public opinion poll that Prime Minister’s Officeannounced the other day indicates that the ratio of people ofadvocating the capital punishment is nearly 80%.)”is presented in Fig. 1. Here, although it is essentially difficult todivide a monologue into clauses on one dimension [4], a monologue can be approximately segmented into clauses by a clauseboundary annotation program [5]. In our research, we call theunit sandwiched between two clause boundaries detected by theclause boundary analysis clause boundary unit and adopt it as
an alternative paring unit.

3. Incremental Dependency Parsing Basedon Clause Boundaries
In this section, we describe incremental dependency parsing
based on clause boundaries. This method detects a clauseboundary for speech input as needed and whenever the clauseboundary unit is identified, it executes dependency parsing for asequence of bunsetsus which was provided up to that point. The
detection of a clause boundary is parsed by CBAP [5]. In dependency parsing, our method constructs the dependency structure
within a clause boundary unit and decides the head bunsetsusof the last bunsetsus of clause boundary units which was previously provided if possible.
In this method, the transcribed sentence for which a morphological analysis, clause boundary detection, and bunsetsu
segmentation are provided is considered as an input. In addition, in the above both procedures, our method assumes thefollowing three syntactic constraints:
1. No dependency is directed from right to left.
2. Dependencies don’t cross each other.
3. Each bunsetsu, except the last one in a sentence, depends
on only one bunsetsu.
These assumptions are usually used for Japanese dependency
parsing.
In what follows in the section, we describe the following
processing. Note that the concrete algorithm is described in
Section 4.
1. The dependency relations of a clause boundary unit inside are identified for every clause boundary unit in amonologue. (clause-level parsing)
2. The dependency relations of which the dependent bunsetsus is the last bunsetsus of a clause boundary units ina monologue are identified. (monologue-level parsing)In this paper, we describe a sequence of clause boundary units in a monologue as C1 , · · · , Cm , a sequence ofbunsetsus in a clause boundary Ci as bi1 , · · · , bini , a dependency relation of which a dependent bunsetsu is a bunsetsu
bik as dep(bik ), and a dependency structure of a monologue as{dep(b11 ), · · · , dep(bmnm −1 )}.
3.1. Clause-level Dependency Parsing
Dependency parsing within a clause boundary unit, if a sequence of bunsetsus in an input clause boundary unit Ci is described as Bi (= bi1 , · · · , bin ), identifies the dependency structure Si (= {dep(bi1 ), · · · , dep(bini −1 )}), which maximizes theconditional probability P (Si |Bi ). At this level, the head of thelast bunsetsu in a clause boundary unit is not identified.
Assuming that each dependency is independent each other,
P (Si |Bi ) can be calculated as follows:niYrel
P (Si |Bi ) =P (bik → bil |Bi ),
(1)
k=1
rel

where P (bik → bil |Bi ) is the probability that a bunsetsu bik depends on a bunsetsu bil when the sequence of bunsetsus Bi isprovided. The structure Si , which maximizes the conditional
probability P (Si |Bi ) is regarded as the dependency structureof Bi and calculated by dynamic programming (DP).
rel
Next, we explain the calculation of P (bik → bil |Bi ). First,
the basic form of independent words in a dependent bunsetsu isrepresented by hik , its parts-of-speech tik , type of dependency
rki , and the basic form of the independent word in a head bunsetsu hil , its parts-of-speech til . Furthermore, the distance between bunsetsus is described as dii
kl . Here, if a dependent bunsetsu has one or more ancillary words, the type of dependency
is the lexicon, part-of-speech and conjugated form of the rightmost ancillary word, and if not so, it is the part-of-speech andconjugated form of the rightmost morpheme [6]. By using the                                        
Figure 2: Flow of incremental dependency parsing
relabove attributes, the conditional probability P (bik → bil |Bi ) is
calculated as follows:
rel
i
i i
i i
i
i
ii
P (bik → bil |Bi ) ∼= P (bk → bl |hk , hl , tk , tl , rk , dkl ) (2)=F (bik → bil , hik , hil , tik , til , rki , diikl ).
F (hik , hil , tik , til , rki , dii)klNote that F is a cooccurrence frequency function. In order to resolve sparse data problems, we adopted the smoothing method
proposed by Collins [7].
3.2. Monologue-level Dependency Parsing
Here, the head bunsetsu of the last bunsetsu of a clause boundary unit is identified. Let B (= B1 , · · · , Bn ) be the bunsetsus sequence of one monologue, and Slast be a set of dependency relations whose dependent bunsetsu is the last bunsetsu
of a clause boundary unit, {dep(b1n1 ), · · · , dep(bm−1
nm−1 )}, thenSlast , which makes P (Slast |B) the maximum, is calculated.
The P (Slast |B) can be calculated as follows:
m−1
Y
rel
(3)
P (Slast |B) =P (bini → bjl |B),
rel

i=1

where P (bini → bjl |B) is the probability that a bunsetsu binidepends on a bunsetsu bjl when the sequence of bunsetsus B ofa monologue is provided. It is calculated as in Eq. (2). The
parameter Slast , which maximizes the conditional probability
P (Slast |B), is regarded as the dependency structure of B andis calculated by DP.

4. Algorithm of Incremental Parsing
In monologue-level dependency parsing, since it is not clear
when their head bunsetsus are provided, the timing on which
the dependency relation is decided is important. In our research,by taking into consideration that a dependency relation whichcrosses over a sentence boundary does not exist and that thelength between dependent bunsetsu and head one is not long,
we thought of deciding the head bunsetsu when the analysis advances to some degree after the last bunsetsu of a clause boundary unit is provided. Concretely speaking, in our method, whenever a clause boundary unit is provided, the maximum likelihood dependency structure of that point is parsed by the technique described in Section 3.2 and if a dependency relation forthe last bunsetsu of a clause boundary unit does not change during a fixed input time (hereinafter referred to as a fixed value),the dependency relation is decided as having the head bunsetsu.
4.1. Algorithm
Figure 2 shows the flow of incremental dependency parsing forthe last bunsetsus of clause boundary units. This algorithm executes incremental parsing by updating the dependency structure
D = {(dep(bjnj ), k)| 1 ≤ j ≤ i − 1} for the last bunsetsus
b1n1 , · · · , bi−1
ni−1 of clause boundary units C1 , · · · , Ci−1 whichwere already provided whenever a new clause boundary unit



 

   
(#$$)"%&$%!'$&$'!'!$'!
!"     





 !"#$% #!%$! "&$#%'$!%"' )"#!*:455;2675.61.85./75/81.81"5#/81!(9,-./0.12/0-. 3+    %# 

+,
/012

'




&
#3!"
$
()
.

4567 389:;< 746:8<;38 9=;:<577>6;8<739>7 @9:8A84CB8<7:6*D83EA F>#9=8<4;7A@;74<6747<6787@3468;F=8?
[TUU\RVWUNVQNXUNOWUOXQNXQ9U:OXQ83?ZI YS SI 38<GHI83 >9?8 9 :LMNOPNQROPMN J K J G
345      







!



"#$% !&'()* %"$(&*)!& '+)(*#%%,$)&*%!',% .'(&/&"10&*
C=>>D:?@>6?96A>67@>7A96A9'>(7A9&!-B< <4567869:7856 3 ;2      6  . / (0& '
12
(&'$%!)*
      "#! $%)* -+,!-./01 -2"34#56 1!02-2 34 102,+.465 37546/1825-691-381 :342;2.=<261-402>62-?;2-@8837236.9521; MNOPQ MRSTUV QNPTRMVUR STSTWUVOQQXUVPRMRYQMSXQ ZSTTR[R\RVN]QMTPR^VRM_[RM`XSVVU
RSNYRQ[ZUQNVPSQNQVPQRQZMNPTRU`WRYQaTPQSSNN[TQW
X
KDELE>FGFE>?G?A>HE?HA J: IC C: 89: 8887
SLMMTINOMENHEPMEFOMFPHEPHMFPH R QK K<=>EB?@>ABA>HE?@=>HA ; ; ; 7 8
CDEFGEHIFGDE JA B JA

Figure 3: Example of incremental dependency parsing (in case that fixed value is 3)
Ci is provided. k is a number called continuation, that is, thenumber of times into which dep(bjnj ) does not change. The
following indicates the algorithm of dependency parsing. Here,
we describe the fixed value as σ.
(1) The clause boundary unit Ci , whose inside dependency
structure was decided, is provided.
(2) The dependency relations containing a dependent bunsetsu whose head bunsetsu is not identified and which is
the last bunsetsu of a clause boundary unit are parsed by
the method described in Section 3.2.
(3) Based on the dependency relations dep(bjnj ) (1 ≤ j ≤i − 1) which were generated in (2), the dependency
structure D for the last bunsetsus is updated. Here, ifdep(bjnj ) does not change, continuation k is updated intok + 1, and if not so, it is updated into 1.
(4) Assuming that the dependency relations (dep(bjnj ), k) ∈D which satisfy k = σ are reliable enough to be decided,
the dependency relations are generated.
(5) After all clause boundary units were provided, the dependency relations which are undecided, that is, satisfy
k < σ in (dep(bjnj ), k) ∈ D are generated.
In addition, our method parse the bunsetsus corresponding
to the sentence end as not depending on any bunsetsu. Therefore, the probability that a bunsetsu does not have a head bunsetsu is also calculated in dependency parsing for the last bunsetsus of clause boundary units. Concretely, the probability ofa bunsetsu not having a head bunsetsu can also be calculated
in formula (2) by considering that such a bunsetsu depends on
itself ( i.e. bini = bjl ).
4.2. Parsing Example
Figure 3 shows the process analyzing the head bunsetsus of thelast bunsetsus of clause boundary units in“正当な事由がない限り契約期間が切れたといっても明け渡しを請求できない点にあるといわれています (It is said that the
problem is in the point that the surrender cannot be claimed even
if the contract term passed as long as there is no right reason),”which is a part of a monologue. This figure consists of 6 processes (a)–(f), which respectively show the dependency structure in the top figure and the dependency relations for the

Table 1: Size of the experimental data (Asu-Wo-Yomu)
Test data Learning data
Program
7
95
470
5,532
Sentence
Clause2,140
26,318
Bunsetsu
5,054
65,821Morpheme
12,753
165,129
last bunsetsus of clause boundary units in the bottom table.
dep(bjnj ) and k of (dep(bjnj ), k) ∈ D respectively correspondto “Dependent bunsetsu and Head bunsetsu” and “Continuation” in the table. Here, we explain the process based on theassumption that the fixed value is 3.
(a) and (b) respectively shows the state on which the firstclause boundary unit I was provided and the state on which thenext clause boundary unit II was provided and the dependency
structure {dep( 限り (as long as))} was parsed. dep( 限り (aslong as)) corresponds to the dashed arrow between the dependent bunsetsu “限り (as long as)” and the head bunsetsu “切れたと (passed)” in the top figure. 1 is recorded to the continuation in the bottom table. Similarly, (c) and (d) respectively
shows the state on which each maximum likelihood dependency
structure {dep( 限り (as long as)), dep( 切れたと (passed))}，{dep( 限り (as long as)), dep( 切れたと (passed)), dep( いっても (even if))} was parsed when the clause boundary unit III,IV respectively was provided.
(e) shows the state on which the new clause boundary unit
V was provided and the maximum likelihood dependency structure {dep( 限り (as long as)), dep( 切れたと (passed)), dep(
いっても (even if)), dep( 請求できない (cannot be claimed))}was parsed. In this time, since the continuation of the dependency relation dep( 切れたと (passed)) reaches to 3, the dependency relation is decided and generated. (f) shows the state
similar to (e).

5. Parsing Experiment
To evaluate the effectiveness of our method for incremental
dependency parsing of Japanese spoken monologue, we conducted an experiment.

Table 2: Dependency accuracy for each fixed value
Fixed
Last bunsetsu of
Totalvalue a clause boundary unit
1
57.6% (1,228/2,133) 74.9% (3,778/5,047)2
60.8%(1,296/2,133) 76.2%(3,847/5,047)
360.8%(1,296/2,133) 76.2%(3,847/5,047)460.4% (1,289/2,133) 76.1% (3,840/5,047)
59.8% (1,276/2,133) 75.8% (3,827/5,047)
5659.4% (1,268/2,133) 75.7% (3,819/5,047)
758.8% (1,254/2,133) 75.4% (3,805/5,047)
58.6% (1,251/2,133) 75.4% (3,803/5,047)8958.7% (1,253/2,133) 75.4% (3,805/5,047)
1058.4% (1,245/2,133) 75.2% (3,797/5,047)
1157.6% (1,229/2,133) 74.9% (3,780/5,047)
1257.9% (1,235/2,133) 75.0% (3,786/5,047)
Table 3: Experimental result of clause boundary analysis
Recall
97.6% (2,088/2,140)
Precision 99.1% (2,088/2,106)
5.1. Outline of Experiment
We used the spoken monologue corpus “Asu-Wo-Yomu2 .”Table 1 shows the data used in the experiment. We used 7 programs (470 sentences) as the test data, to which information
about a morphological analysis and bunsetsu segmentation isannotated. On the other hand, we used 95 programs (5,532 sentences), as the learning data, to which information about a morphological analysis, clause boundary detection, bunsetsu segmentation and dependency analysis is annotated.
We executed parsing by using the above-mentioned data,and evaluated the dependency accuracy and parsing time. We
implemented our parsing method on Linux PC (Pentium4 2.4GHz, with main memory 2 GB) using GNU Common Lisp.
In addition, we performed the parsing experiment 12 times, bychanging the fixed value described in Section 4.1 from 1 to 12.
5.2. Experimental Result
Table 2 shows the dependency accuracy for the last bunsetsusof all clause boundary units and for all bunsetsus by each fixedvalue. When the fixed value was 2 or 3, the dependency accuracy for the last bunsetsus of all clause boundary units was highest and the total dependency accuracy became 76.2%. Here, thedependency accuracy for all bunsetsus except the last bunsetsu
within clause boundary units was 87.5%. Table 3 shows the accuracy of the clause boundary analysis, executed by CBAP. The
numerator value of this table, 2,088, is the number of the clauseboundary whose the position was corresponding to the correct
answer. Since the recall and precision is high, the result parsedby CBAP doesn’t influence the following dependency parsing
so much.
The relation between the fixed value and the parsing timeis shown in Fig. 4. The parsing time increases as a fixed value
grows. When the fixed value was 3, the parsing time was theshortest and was 1.8 second/program.Here, the parsing time
contains the time taken on not only the dependency parsing but
also the clause boundary analysis. The average time taken on
the clause boundary analysis was about 0.3 second/program.
From the result, in this experiment, it can be understood that
our method has the highest performance when a fixed value is
3. By considering of the performance, we can confirm that our
2 Asu-Wo-Yomu is a collection of transcriptions of a TV commentary program of the Japan Broadcasting Corporation (NHK). The commentator speaks on some current social issue for 10 minutes.


 
 
  
 

Figure 4: Relation of fixed value and parsing time
technique has the same performance as sentence-by-sentence
dependency parsing method3 implemented for comparison.

6. Conclusions
In this paper, we have proposed a technique for incremental dependency parsing of Japanese spoken monologue on a clauseby-clause basis. Our technique identifies dependency relations
incrementally for a monologue which is not divided into sentences. Moreover, our technique parses a monologue by considering that the bunsetsus corresponding to sentence end do
not depend on any bunsetsu. To evaluate the effectiveness of our
method for incremental dependency parsing of Japanese spokenmonologue, we conducted an experiment. As the result of theexperiment. we have confirmed that our technique had the same
degree of the performance as our past dependency parsing formonologue sentences. Future research will involve improving
the accuracy of incremental dependency parsing by using information of pauses effectively.
Acknowledgements The research reported here was supported in part by a contract with the Telecommunications Advancement Organization of Japan entitled, “A study of speech
dialogue translation technology based on a large corpus.”

7. References
[1]

[2]
[3]
[4]
[5]

[6]

[7]

Kato, Y., Matsubara, S., Toyama, K. and Inagaki,
Y., “Incremental dependency parsing based on headed
context-free grammar,” Systems and Computers in Japan,
36(2):63–77, 2005.
Nivre, J., “Incrementality in deterministic dependency
parsing,” Proc. of the ACL-2004 Workshop Incremental
Parsing, pp.697–708, 2004.
Roark, B., “Probabilistic top-down parsing and language
modeling,” Computational Linguistics, 27(2):249–276,
2001.
Kashioka, T. and Maruyama, T., “Segmentation of semantic unit in Japanese monologue,” Proc. of ICSLT-OCOCOSDA, pp.87–92, 2004.
Maruyama, T., Kashioka, T. and Tanaka, H., “Development and evaluation of Japanese clause boundaries annotation program,” Journal of Natural Language Processing,11(3):39–68, 2004. (In Japanese)Ohno, T., Matsubara, S., Kawaguchi, N. and Inagaki,
Y., “Robust dependency parsing of spontaneous Japanese
spoken language,” IEICE Transactions on Informationand Systems, E88-D(3):545–552, 2005.
Collins, M., “A New Statistical Parser Based on Bigram
Lexical Dependencies,” Proc. of the 34th ACL, pp. 184–
191, 1996.

3 This method executes dependency parsing by setting a sentence tothe parsing unit. Moreover, this parsing is not incremental. In the result
which this method parsed the above-mentioned experimental data, thedependency accuracy was 79.0% and the parsing time was about 2.1
second/program.