言語処理学会 第22回年次大会 発表論文集 (2016年3月)

A Joint Model for Pause Prediction and Dependency Parsing using Latent
Variables
The Tung Nguyen, Graham Neubig, Hiroyuki Shindo,
Sakriani Sakti, Tomoki Toda1 , Satoshi Nakamura
Graduate School of Information Science, Nara Institute of Science and Technology
1. Introduction
Prediction of prosodic information from text is a basic technology used in a number of speech-related applications. In particular, pauses prediction is used in speech synthesis to allow for
more natural prosodic boundaries [1]. While early studies inpause prediction only relied on lexical information such as POS
tags or punctuation [1, 2], recent works have shown that using
syntactic structure helps achieve better accuracy [3].
This work focuses on the use of dependency structure forpause prediction. Our method is inspired by recent work by
Honnibal and Johnson [4] on the related, but quite different
task, of disfluency detection. In this work, they propose a modelthat jointly performs dependency parsing and disfluency detection, and demonstrate that a joint model that considers these twotasks improves over solving these two tasks individually. Thus,in this paper, we propose a method for joint dependency parsing
and pause prediction.
One of the most widely used methods for dependency parsing is the transition-based method based on the shift-reduce algorithm [5]. As shown in the black text of Figure 1, and explained in detail in Section 2, the shift-reduce method builds adependency tree expressing the syntactic structure of the sentence by performing a series of “shift” and “reduce” actions,and if the correct action sequence is chosen, the correct dependency tree will be created. A classifier to choose the correct
answer is trained from syntactically annotated data.
In our proposed model, we further expand the action set ofthe shift-reduce algorithm by adding actions that predict pauses,
as shown in the bold, red text in Figure 1, and is describedin detail in Section 3. This presents more difficulties in training, however, as it is necessary to have data that is annotatedwith both pauses and syntactic information, which cannot be
obtained in large quantities. To solve this problem, we treat
the pauses as latent variables, allowing our parsing model to be
trained on data fully annotated with syntax and pauses as well
as data only annotated with syntactic trees.
In the experiments described in Section 4, we find that the
proposed model exceeds all baselines, and that the proposed latent variable allows for effective use of data not explicitly annotated with pauses, resulting in an 11.6% absolute improvementin pause F -measure.2

2. Shift-reduce dependency parsing

Stack

Stack

Queue

I play footballshift

football

Actionshift+
pause

II

play football

play

shift

right
I

I playfootballfootball

play

left
I

footballlatent pause information

Figure 1: An example of shift-reduce dependency parsing, andthe proposed pause prediction action.
parsers use a queue to store the input words and a stack to store
the dependency structure that has been built so far. The shiftreduce process converts the input sentence into dependency
structure through a sequence of actions, an example of whichis shown in Figure 1. Our work adopts a modified version of
the arc-standard shift-reduce algorithm proposed by [7], which
has three different actions:
SHIFT: remove the first word in the queue and put it into thestack.
LEFT: create an edge from the first word in the stack to thesecond, then remove the second word from the stack.
RIGHT: create an edge from the second word in the stack to
the first, then remove the first word from the stack.
For each edge in the dependency tree, the parent node is called
the head and the child node is called a dependent. Each word
have exactly one head and can have multiple dependents. To
create the dependency structure of a sentence, our task is tochoose the sequence of shift-reduce actions a that achieve thecorrect tree y from input sentence x. Note that in this modified
arc-standard shift-reduce framework, there is a one-to-one correspondence between action sequences a and trees [8], so forconvenience in the rest of this paper, we will assume that weare attempting to find the correct action sequence a.
At every step of the shift-reduce process, the score of eachaction a is calculated by the following formula:
Score(S, Q, a) = wT f (S, Q, a).

Shift-reduce is a dependency parsing algorithm that parses sentences one word at a time from left to right [5]. Shift-reduce
2 This paper is a shortened version of [6].

Actionplay

2.1. Shift-reduce algorithm

1 Now with Nagoya University.

Queue

(1)

S is the stack and Q is the queue of the current step. f (S, Q, a)creates a feature vector given S, Q, and a, and w is the corresponding feature weight vector. The score of an action is theweighted sum of each feature of the current stack, queue andthe corresponding action.

― 1165 ―Copyright(C) 2016 The Association for Natural Language Processing.
All Rights Reserved.

There are two ways to build dependency trees with the shiftreduce algorithm: greedy search and beam search. With greedy
search, at each step the action with highest score is chosen. We
repeat this process until both the stack and the queue are empty.
With beam search, we choose a beam size k. At each step wedefine the score of the sequence of actions a = a1 , . . . , aM by
the formula:
M
X
Score(a) =Score(Si−1 , Qi−1 , ai ),(2)
i=1

Si and Qi are the stack and queue resulting from action ai insequence A. At each step, a set of new sequences of actions isgenerated by applying each of the 3 actions to the k sequencesin the beam from the previous time step and choose the best kfrom the resulting sequences. Previous research has found thatbeam search achieves better accuracy [9, 10], and thus, we use
beam search in the rest of this paper. Our parser is also capableof labeled parsing, in which the parser predicts not only the dependency arc, but also the grammatical relation represented by
the dependency [11]. This can be done by simply augmenting
LEFT and RIGHT with dependency labels.
2.2. Structured perceptron with latent variables
The structured perceptron is a structured classifier introduced
by Collins [12]. We assume a set of I training examples{hx1 , a1 i, . . . , hxI , aI i} where xi is a sequence of observations and ai is the corresponding action sequence for xi . Let
w be the weight vector and function f (x, a) be the feature
vector function calculated from observations x and action sequence a. The algorithm processes every sample in the training
data one-at-a-time, first performing the decoding step to obtain
the highest scoring action sequence a0i . Next, if a0i is different from the gold sequence ai then we update the weights byincreasing their value by the feature vector of the correct sequence f (xi , ai ) and decreasing its value by the features of the
1-best parse f (xi , a0i ).
Recently, the perceptron has also been extended to handle
additional latent variables [13, 11]. Given the sequence of labelsa = a1 , . . . , aM , in the latent structured perceptron, assume
that we have some latent information expressed as a sequenceof hidden variables h = h1 , . . . , hM . We assume that eachlabel a corresponds to a set of latent labels Ha , and that thesets of latent labels for each a are disjoint from each other. For
example, Bohnet and Nivre [11] considered the case of dependency parsing without POS tag information. In this case, x is
the sequence of words of input sentence. a is sequence of standard shift-reduce actions, while h further appends a POS tag toeach of the actions. The training algorithm for the structured
perceptron with latent variables is described in Algorithm 1.
The training algorithm is very similar to the normal structured perceptron except for a few minor modifications. In the
decoding step, the result is the sequence of latent variables h0ithat has the highest score among all sequences of latent variables. Then we make a projection from the sequence of latent variables h0i to a sequence of labels a0i in which a0i,j ischosen such that h0i,j ∈ Ha0i,j . We then compare this projected sequence with the true sequence ai and if they are different, perform a perceptron update. When we perform an update, we would like to update towards the “correct” sequenceof latent variables. However, since the correct sequence of latent variables is unobservable, we choose the sequence hi thathas highest score but satisfies the constraint ai = project(hi ).
This step is called forced decoding, which we express using the

Algorithm 1 Structured perceptron with latent variables
Input: Set of training samples D.
Init: Feature vector w = 0.
for iter ← 1, max dofor (xi ,ai ) ∈ D do
h0i = decode(w, xi )a0i = project(h0i )if a0i 6= ai thenhi = forced decode (w, xi , ai )w = w + f (xi , hi ) - f (xi , h0i )forced decode(·) function. For updating, the features are created from sequences of observations and latent variables.

3. Dependency parsing with latent pause
information
3.1. Using pause information as latent variables
Previous work [3] has shown that syntactic structure has an important role in pause prediction. However, to our knowledge
there are no models that tackle dependency parsing and pause
prediction jointly. Thus in this paper, we build on the recent
success of latent variable models for joint dependency parsing
and POS tagging [11], proposing a latent variable joint model
for pause prediction and dependency parsing. To do that, we
modify the shift-reduce algorithm to be able to perform the twotasks jointly. Specifically, we divided pauses into two classes:
NoPause: no pause is perceivable to the human ear.
Pause: a pause perceivable to the human ear exists.
Next, we create a new set of actions:
RIGHT: same as standard shift-reduce.
LEFT: same as standard shift-reduce.
SNONE: same as SHIFT, for words preceded by NoPause.
SPAUSE: same as SHIFT, for words preceded by Pause.
Each SHIFT action in a sentence corresponds to a single word,
and thus the set of actions above allow us to perform pause prediction for each word in the sentence. By using these new actions, our parser can both predict the syntactic structure and thepauses between words in parallel. The bold, red line and words
in Figure 1 show this additional latent information. In this case,
we predict that there is a pause between two words “play” and“football” and thus the action shift-pause (SPAUSE) is chosen.
With the modified set of shift-reduce actions, if we havedata annotated with both pauses and dependency syntax, themodel can be trained using the normal structured perceptron.
However, because creating data with both manually checkedpauses and manually checked parse trees is laborious, we cannot obtain this data in large quantities. Since the quantity ofdata is insufficient, the parsing accuracy of a model trained onsuch data will not be very high. However, if we were able touse syntactic data without pauses to increase dependency parsing accuracy, this could potentially increase the accuracy of themodel as a whole.
Thus we envision a training setting in which we have alarge set of text data Dt annotated with only syntax trees, anda smaller set of speech data Ds annotated with syntax trees andpauses. In order to train on the data that is not annotated withpauses, the proposed method treats pauses as latent variables.
Thus, we use the standard structured perceptron on our small
set of data Ds annotated with both types of information, and― 1166 ―Copyright(C) 2016 The Association for Natural Language Processing.
All Rights Reserved.

Algorithm 2 Training algorithm for the proposed model.
Input: Set of training samples D = Dt ∪ Ds .
Dt is the set of text data with only syntax.
Ds is the set of speech data with syntax and pauses.
Init: Feature vector w = 0.
for iter ← 1, max dofor (xi ,ai ) ∈ D do
if (xi ,ai ) ∈ Dt then. latent perceptron
h0i = decode(w,xi )a0i = project(h0i )if a0i 6= ai thenhi = forced decode(w,xi ,ai )w = w + f (xi , hi ) - f (xi , h0i )else. standard perceptron
h0i = decode(w, xi )if h0i 6= hi thenw = w + f (xi , hi ) - f(xi ,h0i )the latent perceptron on Dt annotated with only syntax information.
By modifying the standard algorithm, we can train themodel on the combined data as shown in Algorithm 2.

two words denoted as d.

4. Experiments
4.1. Experimental setup
We conducted experiments to test the effectiveness of the proposed joint dependency parsing and pause prediction model. To
do so, we first prepare both text and speech data.
Text: As text data, we used the Wall Street Journal Section of
the Penn Treebank [14], the standard data set for English
parsers’ experiments. Following convention, sections 221 were used for training, section 23 was used for testingand sections 22&24 were used for development.
Speech: As speech data, we used the NAIST-NTT Ted Talk
Treebank [15], which is a corpus of TED talks annotatedwith syntactic structure. We manually annotated all talks
in the treebank with audibly perceptible pauses by first
performing forced alignment using an ASR system [16]to automatically detect sections of silence, then having ahuman annotator manually correct these pauses.1
Details of the size of each data set are shown in Table 2. We created models on two different sets of data: TED and TED+WSJ.
Test sets from WSJ and TED were used to measure the accuracy

3.2. Features
Most of the features used in our model were adopted from previous work [5, 7, 10]. We define S as the stack to store the
Features

Data Set

Train

Test

WSJ
TED

39,832
822

2,416
395

Table 2: Data size in sentences

Single word: S−1 w, S−1 p, S−1 wp, S−1 wi, S−2 w,
S−2 p, S−2 wp, S−2 wi, S−3 w, S−3 p, S−3 wp, S−3 wi,
Q0 w, S0 p, Q0 wp, Q0 wi.
Two words: S−3−2 w, S−3−2 p, S−3−2 wp, S−2−1 w,
S−2−1 p, S−2−1 wp, S−1 Q0 w, S−1 Q0 p, S−1 Q0 wp,
S−2 wpS−1 wp,
S−2 pS−1 wp,
S−2 wS−1 wp,
S−2 wpS−1 w,
S−2 wpS−1 p,
S−1 wpQ0 wp,
S−1 wpQ0 p, S−1 wpQ0 w, S−1 wQ0 wp, S−1 pQ0 wp.
Three words: S−3−2−1 w, S−3−2−1 p, S−2−1 Q0 w,
S−2−1 Q0 p.
Index+Distance:
S−1 wi, S−1 pi, Q0 wi, Q0 pi,
S−1 Q0 wd, S−1 Q0 pd.
Modifiers: S−3 lw, S−3 lp, S−3 rw, S−3 rp, S−2 lw,
S−2 lp, S−2 rw, S−2 rp, S−1 lw, S−1 lp, S−1 rw,
S−1 rp.
Previous word: Q−1 w, Q−1 p,Q−10 w, Q−10 p.
Table 1: List of features
dependency structure that has been built so far and Q to be thequeue storing the input sentence. S−3 , S−2 and S−1 are the top
three elements of the stack, Q0 is the first element in the queue
and Q−1 is the one before it in the sentence. In Table 1, w indicates the surface form of the word, and p indicates its part-ofspeech (POS) tag. For example, S−1 Q0 wp is the combinationof text and POS tag of the word on the top of the stack and thefirst word in the queue. We also define features regarding modifiers of stack items, where l indicates the leftmost modifier andr indicates the rightmost modifier of the word. The position of
the word in the sentence is also used in our model where i indicates the index of the word (starting at 1 for the first word in
the sentence). Finally, we define features over distance betweenof dependency parsing. To measure the performance of pause
prediction, only test data from TED was used. The beam sizeused for beam search is fixed at 12 in all experiments.
We compare with two baseline models: “All Pause” and“Dec. Tree.” “All Pause” is a trivial baseline that always selects pauses for every word. ”Dec. Tree” is a model basedon a research by Hirschberg and Prieto [2] that used decision
trees for learning intonational phrasing rules. We adopted theirwork for a baseline model for pause prediction task. Due to thedifferences between the two tasks, we only use a subset of theirfeatures relevant to our task, specifically POS tags of the current
word, previous word and the combination of them. Finally, toexamine the effect of predicting both syntax and pauses jointly,
we test a “Pipeline” built by using two separate models, the firstone is a normal parser model trained on WSJ data and the second is a joint model trained on TED data. Then, we use the firstmodel to predict parse trees on TED test data and used thesetrees for forced decoding using the second model. As an evaluation measure for pause prediction, we use pause prediction
F-measure:F =2 × precision × recall.
precision + recall(3)

Statistical significance of accuracy differences between methods was measured using pairwise bootstrap resampling with
95% confidence [17].
1 Note that the written text in WSJ is likely slightly different in syntax than TED talks, but previous work [15] has shown that WSJ is datais still useful in parsing of TED speech.

― 1167 ―Copyright(C) 2016 The Association for Natural Language Processing.
All Rights Reserved.

F-measure

35

25

Unlabeled parsing
Labeled parsing

surpassing several baselines. Our most notable result is that amodel trained on a combination of data annotated with pauses
and syntax, as well as data annotated with only syntax achieved
better results on pause prediction than when using only the data
annotated with pauses. In the future, we hope to adapt this latentvariable model to other tasks such as joint dependency parsing
and disfluency detection.
Acknowledgements:Part of this work was supported by
JSPS KAKENHI Grant Number 24240032, and grants from
Nippon Telegraph and Telephone Corp. and Honda ResearchInstitute Japan Co., Ltd.

6. References

15[1] A. W. Black and P. A. Taylor, “Assigning phrase breaks from partof-speech sequences.” Computer speech and language, vol. 12,
pp. 99–117, 1998.

Amount of WSJ data added

Figure 2: Influence of WSJ data on pause prediction F-measure.
4.2. Results
First, we show precision, recall, and F-measure for the pause
prediction task in Table 3. All the models in this table aretrained using the unlabeled parsing method. If we first compare
the first three rows, it is clear that our joint dependency parsing
and pause prediction model performs better than the baselinemodels. Next, and more interestingly, we can see that adding
WSJ data greatly improves recall and F-measure. This is notable, because the WSJ data contains no annotation of pauses,
demonstrating that by improving the accuracy of parsing itself,
we were able to improve pause prediction as well.
To examine this relationship in more detail, in Figure 2 weshow results of pause prediction F-measure for various sizesof WSJ data. Although the increase is not entirely consistent,
we can see that in general by adding more WSJ data to TED
data, we improve F-measure for pause prediction significantly.
We also performed experiments on both unlabeled parsing andlabeled parsing. From the chart, the difference is not consistent,
although labeled parsing tends to achieve slightly higher scores.
Finally, we examine the effect of latent pauses on dependency parsing accuracy. In this test, accuracy was measured
using UAS - Unlabeled Attachment Score. Compared to a
standard model that used no latent pause information, the proposed model achieved essentially the same accuracy, with UAS
scores for the standard and proposed models being 91.32% and91.25% on WSJ, and 85.26% and 85.54% on TED respectively.

Model

Data

All Pause
Dec. Tree
Parser
Pipeline
Parser—
TED
TED
TED+WSJTED+WSJ

P

R

F

6.99%
37.77%
26.78%
27.87%
26.41%

100.00%3.42%
12.90%
17.74%
32.06%

13.07%
6.28%
17.41%
22.19%
28.96%

Table 3: Pause prediction precision, recall and F-measure. Bold
indicates a statistically significant gain over other methods.

[2] J. Hirschberg and P. Prieto, “Training intonational phrasing rules
automatically for english and spanish text-to-speech,” SpeechCommunication, vol. 18, no. 3, pp. 281–290, 1996.
[3] J. Tauberer, “Predicting intrasentential pauses: Is syntactic structure useful?” in Proc. Speech Prosody. Citeseer, 2008, pp. 405–
408.
[4] M. Honnibal and M. Johnson, “Joint incremental disfluency detection and dependency parsing,” Transactions of the Associationof Computational Linguistics, 2014.
[5] H. Yamada and Y. Matsumoto, “Statistical dependency analysis
with support vector machines,” in Proc. IWPT, vol. 3, 2003, pp.
195–206.
[6] T. T. Nguyen, G. Neubig, H. Shindo, S. Sakti, T. Toda, and
S. Nakamura, “A latent variable model for joint pause prediction
and dependency parsing,” in Proc. InterSpeech, Dresden, Germany, September 2015.
[7] L. Huang, W. Jiang, and Q. Liu, “Bilingually-constrained (monolingual) shift-reduce parsing,” in Proc. EMNLP, 2009, pp. 1222–
1231.
[8] Y. Goldberg and J. Nivre, “A dynamic oracle for arc-eager dependency parsing.” in Proc. COLING, 2012, pp. 959–976.
[9] Y. Zhang and S. Clark, “Joint word segmentation and pos tagging
using a single perceptron.” in Proc. ACL, 2008, pp. 888–896.
[10] Y. Zhang and J. Nivre, “Transition-based dependency parsing withrich non-local features,” in Proc. ACL-HLT, 2011, pp. 188–193.
[11] B. Bohnet and J. Nivre, “A transition-based system for joint partof-speech tagging and labeled non-projective dependency parsing,” in Proc. EMNLP, 2012, pp. 1455–1465.
[12] M. Collins, “Discriminative training methods for hidden markov
models: Theory and experiments with perceptron algorithms,” inProc. EMNLP, 2002, pp. 1–8.
[13] X. Sun, T. Matsuzaki, D. Okanohara, and J. Tsujii, “Latent variable perceptron algorithm for structured classification.” in Proc.
IJCAI, vol. 9, 2009, pp. 1236–1242.
[14] M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini, “Buildinga large annotated corpus of English: The Penn treebank,” Computational linguistics, vol. 19, no. 2, pp. 313–330, 1993.
[15] G. Neubig, K. Sudoh, Y. Oda, K. Duh, H. Tsukada, and M. Nagata, “The NAIST-NTT TED talk treebank,” in Proc. IWSLT,
Lake Tahoe, USA, December 2014.
[16] S. Sakti, K. Kubo, G. Neubig, T. Toda, and S. Nakamura, “TheNAIST english speech recognition system for IWSLT 2013,” inProc. IWSLT, Heidelberg, Germany, December 2013.

5. Conclusions[17] P. Koehn, “Statistical significance tests for machine translation
evaluation,” in Proc. EMNLP, 2004.

In this paper, we introduced a method that is able to jointly
perform dependency parsing and pause prediction. Our model
achieved an F-measure of 28.96% on our pause prediction task,[18] M. Collins and B. Roark, “Incremental parsing with the perceptron algorithm,” in Proc. ACL, 2004, p. 111.

― 1168 ―Copyright(C) 2016 The Association for Natural Language Processing.
All Rights Reserved.