INTERSPEECH 2015

A Latent Variable Model for Joint Pause Prediction and Dependency Parsing
The Tung Nguyen, Graham Neubig1 , Hiroyuki Shindo1 ,Sakriani Sakti1 , Tomoki Toda1 , Satoshi Nakamura1
1

Graduate School of Information Science, Nara Institute of Science and Technology
Abstract

The prosody of speech is closely related to syntactic structureof the spoken sentence, and thus analysis models that jointly
consider these two types of information are promising. However, manual annotation of syntactic information and prosodic
information such as pauses is laborious, and thus it can be difficult to obtain sufficient data to train such joint models. In
this paper, we tackle this problem by introducing a joint pause
prediction and dependency parsing model that treats pauses between consecutive words as latent variables. Using this model,
it is possible to learn from not only data labeled with both syntax and pause information, but also data labeled with only syntactic information, which can be obtained in larger quantities.
Experiments find that a joint pause prediction and dependency
parsing model obtains better pause prediction F-measure thana decision-tree-based baseline trained on the same data, andthat the addition of more data using the proposed latent variable
model leads for further gains of up to 11.6 points in F-measure.
Index Terms: dependency parsing, structured perceptron,
speech, latent variables, beam search

Stack

Action

Stack

Queue

play
I play football

shift

Actionfootballshift+
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.

is described in detail in Section 3. This presents additional difficulties in training, however, as it is necessary to have data thatis annotated with both pauses and syntactic information, whichcannot be obtained in large quantities. To solve this problem,
we treat the pauses between words as latent variables, allowing
our parsing model to be trained on not only data fully annotatedwith syntax and pauses, but also text data only annotated withsyntactic trees.
In the experiments described in Section 4, we find that the
proposed model exceeds several baselines, and that the proposed latent variable allows for effective use of data not explicitly annotated with pauses, resulting in a 11.6% absolute improvement in pause F -measure.

1. Introduction
Prediction of prosodic information from text is a basic technology used in a number of speech-related applications. In particular, prediction of pauses is used in speech synthesis to allow for
more natural prosodic boundaries in long sentences [1]. While
early studies in pause prediction only relied on lexical information such as POS tags or punctuation [1, 2], recent works haveshown that the use of syntactic structure helps achieve better
accuracy [3].
In particular, in this work we focus on the use of dependency structure for pause prediction. Our method is inspiredby recent work by Honnibal and Johnson [4] on the related,but quite different task, of disfluency detection. In this work,
they propose a model that jointly performs dependency parsing
and disfluency detection, and demonstrate that a joint modelthat considers these two tasks in concert improves over solving
these two tasks individually. Thus, in this paper, we propose amethod 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 training data.
In our proposed model, we further expand the action set ofthe shift-reduce algorithm by adding an additional action thatpredicts pauses, as shown in the bold, red text in Figure 1, andCopyright © 2015 ISCA

Queue

2. Shift-reduce dependency parsing
2.1. Shift-reduce algorithm
Shift-reduce is a widely used algorithm in dependency parsingthat parses sentences one word at a time from left to right [5].
In shift-reduce parsers, we use a queue to store the input words
and a stack to store the dependency structure that has been built
so far. The shift-reduce process converts the input sentence into
dependency structure through a sequence of actions, an example
of which we show in Figure 1. In this paper, we adopt a modified version of arc-standard shift-reduce algorithm proposed by[6], which consists of 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.

2719

September 6- 10, 2015, Dresden, Germany

Algorithm 1 Structured perceptron
Input: Set of training samples D.
Init: Feature vector w = 0.
for iter ← 1, max dofor (xi ,ai ) ∈ D do
a0i = decode(w,xi )if a0i 6= ai thenw0 = w + f (xi ,ai ) - f (xi , a0i )end ifend forend forFor each edge in the dependency tree, the parent node is called
the head and the child node is called a dependent. Each word
must have exactly one head and can have multiple dependents.
To create the dependency structure of a sentence, our task is totake a sentence x as input, then choose the sequence of shiftreduce actions a achieve the correct tree y. Note that in thismodified arc-standard shift-reduce framework, there is a oneto-one correspondence between action sequences a and trees[7], so for convenience in the rest of this paper, we will assume
that we are attempting to find the correct action sequence a.
At every step of the shift-reduce process, each action a isgiven a score calculated by the following formula:
Score(S, Q, a) = wT f (S, Q, a).

(1)

2.3. Structured perceptron with latent variables

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.
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. This
process is repeated until both the stack and the queue are empty.
With beam search, first we choose a beam size k. At
each step we define the score of the sequence of actions a =a1 , . . . , aM by the formula:
Score(a) =MX

Score(Si−1 , Qi−1 , ai ),While in the previous section we were concerned with only
observations x and labels a, the perceptron has also been extended to handle additional latent variables [11, 12]. Given thesequence of labels a = a1 , . . . , aM , in the latent structured
perceptron we assume that we have some latent information expressed as a sequence of hidden variables h = h1 , . . . , hM .
We assume that each label a corresponds to a set of latent labels
Ha , and that the sets of latent labels for each a are disjoint fromeach other. For example, Bohnet and Nivre [12] considered thecase of dependency parsing without POS tag information. In
this case, x is the sequence of words of input sentence. a issequence of standard shift-reduce actions, while h further appends a POS tag to each of the actions. The training algorithm
for the structured perceptron with latent variables is describedin Algorithm 2.

(2)

i=1

where Si and Qi are the stack and queue resulting from action
ai in sequence A. At each step, a set of new sequences of actions is generated by applying each of the 3 actions to the ksequences in the beam from the previous time step. From thisset, we choose k sequences with the highest score for the next
step. This process is repeated until both the stack and the queue
are empty. Then the sequence of actions that has the highest
score will be chosen to build the dependency tree. We can seethat greedy search is actually a special case of beam search withk = 1.
For the decoding process, recent studies have shown thatbeam search achieves better accuracy [8, 9]. We comparedbeam search with greedy search and observed similar results,
so in the remainder of this paper we use beam search in theshift-reduce process.

Algorithm 2 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 )end ifend forend for
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 forced decode(·) function. For updating the weights, thefeatures are created from sequences of observations and latentvariables.

2.2. Structured perceptron
The structured perceptron is a structured classifier introduced
by Collins [10]. 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 training algorithm for the structured perceptron is shown in
Algorithm 1.
The algorithm processes every sample in the training data
one-at-a-time, first performing the decoding step to obtain thehighest scoring action sequence a0i . Next, we check if a0i is different from the gold sequence ai , and if it is different then we
update the weights by increasing 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 ).

2720

3. Dependency parsing with latent pause
information

Algorithm 3 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 )end ifelse. standard perceptron
h0i = decode(w, xi )if h0i 6= hi thenw = w + f (xi , hi ) - f(xi ,h0i )end ifend ifend forend for3.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 [12], proposing a latent variable joint model
for pause prediction and dependency parsing.
In order to do so, we modify the shift-reduce algorithm tobe able to perform the two tasks jointly. Specifically, we divide
the 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.

Features

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, now our parser can do two jobs at the same time: predictthe correct sequence of actions in the shift-reduce process andpredict the pauses between words in the input sentence.
The bold, red line and words in Figure 1 show this additional latent information. In this case, we predict that there isa pause between two words “play” and “football” and thus theaction shift-pause (SPAUSE) is chosen.
With the modified set of shift-reduce actions, if we possess
the training data annotated with both pauses and dependency
syntax, the model can be trained using the normal structured
perceptron. However, because creating data with both manuallychecked pauses and manually checked parse trees is laborious,
we cannot obtain this data in large quantities. Since the quantityof data is insufficient, the parsing accuracy of a model trainedon data with both pauses and dependency syntax will not bevery high. However, if we were able to use syntactic data without pauses to increase dependency parsing accuracy, this could
potentially increase the accuracy of the model 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 labeled withpauses, the proposed method treats pauses as latent variables.
Thus, we use the standard structured perceptron on our small
set of data Ds labeled with both types of information, and thelatent perceptron on Dt labeled with only syntax information.
By making some modifications to the standard algorithm,
we can train the model on the combined data as shown in Algorithm 3.

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.
Distance: S−1 wd, S−1 pd, Q0 wd, Q0 pd, 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
the first element in the queue and Q−1 is the one before it in
the sentence. In this table, w indicates the surface form of theword, and p indicates its part-of-speech (POS) tag. For example, S−1 Q0 wp is the combination of text and POS tag of theword on the top of the stack and the first word in the queue. We
also define features regarding modifiers of stack items, wherel indicates the leftmost modifier and r indicates the rightmost
modifier of the word. We also created features based on the position of the word in the sentence where i indicates the index of
the word (starting at 1 for the first word in the sentence). Finally, we define features over distance between two words, withthe distance between the two words denoted as d.

3.2. Features

4. Experiments

Most of the features used in our model were adopted from previous work [5, 6, 9]. To describe our features, we define S as
the stack to store the dependency structure that has been built
so far and Q to be the queue storing the input sentence. S−3 ,S−2 and S−1 are the top three elements of the stack, Q0 is

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.

2721

Text: As text data, we used the Wall Street Journal Section of
the Penn Treebank [13], the most standard set of data
for training and testing English parsers. Following convention, sections 2-21 were used for training the model,
section 23 was used for testing and sections 22 and 24
were used for development.
Speech: As speech data, we used the NAIST-NTT Ted Talk
Treebank [14], 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 [15]to automatically detect sections of silence, then having ahuman annotator manually correct these pauses.1

Train

Test

WSJ
TED

39,832
822

2,416
395

All Pause
Dec. Tree
ParserParser—
TED
TED
TED+WSJ

P

R

F

6.99%
37.77%
26.78%
26.41%

100.00%3.42%
12.90%
32.06%

13.07%
6.28%
17.41%
28.96%

35

30.51
28.96
25.81
25

26.51
25.06
23.67

F-measure

21.47
20.11
17.41
15

5

Table 2: Data size in sentences0of 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 based on a
research by [2] that used decision trees for learning intonational
phrasing rules. We adopted their work for a baseline model forpause prediction task. Due to the differences between the twotasks, we only use a subset of their features relevant to our task,
specifically POS tags of the current word, previous word andthe combination of them. As an evaluation measure for pause
prediction, we use pause prediction F-measure:
2 × precision × recall
F =.
precision + recall

Data

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

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
Data Set

Model

1/128

1/64

1/32
1/16
1/8
Amount of WSJ data added

1/4

1/2

1

Figure 2: Influence of WSJ data to pause prediction F-measure.
Finally, we examine the effect of latent pauses on dependency parsing accuracy. In this test, accuracy is measured using
UAS - Unlabeled Attachment Score. We compare the proposedmodel to a standard dependency parsing model that does not use
latent pause information. Training and testing are performed on
both WSJ and TED . From the results in Table 4, we can seethat the parsing results are essentially the same for both models, indicating that latent pauses cause little change in parsing
results.

(3)

Statistical significance of accuracy differences between methods was measured using pairwise bootstrap resampling with
95% confidence [16].

Model NameUAS on WSJ

UAS on TED

Standard model
Joint model

91.32%
91.25%

85.26%
85.54%

Table 4: Dependency parsing accuracy for different models.

5. Conclusions

4.2. Results
First, we show precision, recall, and F-measure for the pause
prediction task in Table 3. If we first compare the first threerows, it is clear that our joint dependency parsing and pause prediction model performs better than the baseline models. 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 thatby improving the accuracy of parsing itself, we were able toimprove pause prediction as well.
To examine this relationship in more detail, in Figure 2 weshow results of pause prediction F-measure for various sizes of
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.

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,
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.

6. Acknowledgements
Part of this work was supported by JSPS KAKENHI Grant
Number 24240032, and a grant from Nippon Telegraph andTelephone Corp.

1 Note that the written text in WSJ is likely slightly different in syn-tax than TED talks, but previous work [14] has shown that WSJ is datais still useful in parsing of TED speech.

2722

7. References[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.
[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?” pp. 405–408, 2008.
[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,” vol. 3, pp. 195–206, 2003.
[6] L. Huang, W. Jiang, and Q. Liu, “Bilingually-constrained (monolingual) shift-reduce parsing,” in Proc. EMNLP, 2009, pp. 1222–
1231.
[7] Y. Goldberg and J. Nivre, “A dynamic oracle for arc-eager dependency parsing.” in Proc. COLING, 2012, pp. 959–976.
[8] Y. Zhang and S. Clark, “Joint word segmentation and pos tagging
using a single perceptron.” in Proc. ACL, 2008, pp. 888–896.
[9] Y. Zhang and J. Nivre, “Transition-based dependency parsing withrich non-local features,” in Proc. ACL-HLT, 2011, pp. 188–193.
[10] M. Collins, “Discriminative training methods for hidden markov
models: Theory and experiments with perceptron algorithms,” inProc. EMNLP, 2002, pp. 1–8.
[11] X. Sun, T. Matsuzaki, D. Okanohara, and J. Tsujii, “Latent variable perceptron algorithm for structured classification.” vol. 9, pp.
1236–1242, 2009.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] P. Koehn, “Statistical significance tests for machine translation
evaluation,” in Proc. EMNLP, 2004.
[17] M. Collins and B. Roark, “Incremental parsing with the perceptron algorithm,” in Proc. ACL, 2004, p. 111.

2723