Optimizing Segmentation Strategies for Simultaneous Speech Translation
Yusuke Oda

Graham Neubig Sakriani Sakti Tomoki Toda Satoshi Nakamura
Graduate School of Information Science
Nara Institute of Science and Technology
Takayama, Ikoma, Nara 630-0192, Japan{oda.yusuke.on9, neubig, ssakti, tomoki, s-nakamura}@is.naist.jp

Abstract

impairs the simultaneity of translation because thesystem needs to wait too long until the appearanceof a estimated sentence boundary. For this reason,
segmentation strategies, which separate the input
at appropriate positions other than end of the sentence, have been studied.
A number of segmentation strategies for simultaneous speech translation have been proposed inrecent years. Fügen et al. (2007) and Bangalore etal. (2012) propose using prosodic pauses in speech
recognition to denote segmentation boundaries,
but this method strongly depends on characteristics of the speech, such as the speed of speaking.
There is also research on methods that depend on
linguistic or non-linguistic heuristics over recognized text (Rangarajan Sridhar et al., 2013), and it
was found that a method that predicts the locationof commas or periods achieves the highest performance. Methods have also been proposed using
the phrase table (Yarmohammadi et al., 2013) or
the right probability (RP) of phrases (Fujita et al.,2013), which indicates whether a phrase reordering occurs or not.
However, each of the previously mentioned
methods decides the segmentation on the basisof heuristics, so the impact of each segmentation strategy on translation performance is not directly considered. In addition, the mean numberof words in the translation unit, which strongly affects the delay of translation, cannot be directly
controlled by these methods.2
In this paper, we propose new segmentation algorithms that directly optimize translation performance given the mean number of words in thetranslation unit. Our approaches find appropriate segmentation boundaries incrementally using
greedy search and dynamic programming. Eachboundary is selected to explicitly maximize trans-

In this paper, we propose new algorithms
for learning segmentation strategies for simultaneous speech translation. In contrast
to previously proposed heuristic methods,
our method finds a segmentation that directly maximizes the performance of themachine translation system. We describe
two methods based on greedy search anddynamic programming that search for the
optimal segmentation strategy. An experimental evaluation finds that our algorithm
is able to segment the input two to threetimes more frequently than conventional
methods in terms of number of words,
while maintaining the same score of automatic evaluation.1

1Introduction

The performance of speech translation systems
has greatly improved in the past several years,
and these systems are starting to find wide use ina number of applications. Simultaneous speechtranslation, which translates speech from thesource language into the target language in realtime, is one example of such an application. Whentranslating dialogue, the length of each utterance
will usually be short, so the system can simply
start the translation process when it detects the endof an utterance. However, in the case of lectures,for example, there is often no obvious boundary
between utterances. Thus, translation systems require a method of deciding the timing at whichto start the translation process. Using estimatedends of sentences as the timing with which to starttranslation, in the same way as a normal text translation, is a straightforward solution to this problem(Matusov et al., 2006). However, this approach2

The method using RP can decide relative frequency ofsegmentation by changing a parameter, but guessing thelength of a translation unit from this parameter is not trivial.

1

The implementation is available at
http://odaemon.com/docs/codes/greedyseg.html.

551
Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Short Papers), pages 551–556,
Baltimore, Maryland, USA, June 23-25 2014. c 2014 Association for Computational Linguistics

lation accuracy as measured by BLEU or anotherevaluation measure.
We evaluate our methods on a speech translation task, and we confirm that our approaches canachieve translation units two to three times as finegrained as other methods, while maintaining thesame accuracy.

2

Figure 1: Concatenated translation M T (f , S).

Optimization Framework

Based on this representation, choose K segmentation boundaries in F to make the set
S ∗ that maximizes an evaluation function ω
as below:

Our methods use the outputs of an existing machine translation system to learn a segmentation
strategy. We define F = {fj : 1 ≤ j ≤ N },E = {ej : 1 ≤ j ≤ N } as a parallel corpus
of source and target language sentences used totrain the segmentation strategy. N represents thenumber of sentences in the corpus. In this work,
we consider sub-sentential segmentation, where
the input is already separated into sentences, andwe want to further segment these sentences into
shorter units. In an actual speech translation system, these sentence boundaries can be estimatedautomatically using a method like the period estimation mentioned in Rangarajan Sridhar et al.
(2013). We also assume the machine translation
system is defined by a function M T (f ) that takes
a string of source words f as an argument and returns the translation result ê.3
We will introduce individual methods in the following sections, but all follow the general framework shown below:

S ∗ :=

arg max

S∈{S ′ :|S ′ |=K}

ω(S; F, E, EV, M T ).

(2)
In this work, we define ω as the sum of theevaluation measure for each parallel sentencepair ⟨fj , ej ⟩:ω(S) :=N∑

EV (M T (fj , S), ej ),

(3)

j=1

where M T (f , S) represents the concatenation of all partial translations {M T (f (n) )}given the segments S as shown in Figure 1.
Equation (3) indicates that we assume allparallel sentences to be independent of eachother, and the evaluation measure is calculated for each sentence separately. This locality assumption eases efficient implementation of our algorithm, and can be realized using a sentence-level evaluation measure such
as BLEU+1 (Lin and Och, 2004).

1. Decide the mean number of words µ and themachine translation evaluation measure EV
as parameters of algorithm. We can use an
automatic evaluation measure such as BLEU
(Papineni et al., 2002) as EV . Then, we calculate the number of sub-sentential segmentation boundaries K that we will need to insert into F to achieve an average segment
length µ:⌋)( ⌊∑f ∈F |f |− N . (1)K := max 0,µ

3. Make a segmentation model MS ∗ by treating
the obtained segmentation boundaries S ∗ as
positive labels, all other positions as negative
labels, and training a classifier to distinguishbetween them. This classifier is used to detect segmentation boundaries at test time.
Steps 1. and 3. of the above procedure are trivial. In contrast, choosing a good segmentation according to Equation (2) is difficult and the focusof the rest of this paper. In order to exactly solve
Equation (2), we must perform brute-force searchover all possible segmentations unless we makesome assumptions about the relation between theω yielded by different segmentations. However,the number of possible segmentations is exponentially large, so brute-force search is obviously intractable. In the following sections, we propose 2

2. Define S as a set of positions in F in which
we will insert segmentation boundaries. For
example, if we will segment the first sentence
after the third word and the third sentence after the fifth word, then S = {⟨1, 3⟩ , ⟨3, 5⟩}.
3
In this work, we do not use the history of the language
model mentioned in Bangalore et al. (2012). Considering thisinformation improves the MT performance and we plan toinclude this in our approach in future work.

552

WORD: I
POS: PRP

Segments already selected at the k-th iteration

I

ate

lunch

ω = 0.5butω = 0.8sheω = 0.7
WORD: I
POS: PRP

Figure 2: Example of greedy search.

Group
NN+CC

an orangeDTNN

sentences using features of the position, and introduce a constraint that all positions with identicalfeatures must be selected at the same time. Figure
3 shows an example of how this grouping works
when we use the POS bigram surrounding eachpotential boundary as our feature set.
By introducing this constraint, we can expectthat features which have good performance overall will be selected, while features that have relatively bad performance will not be selected even if
good performance is obtained when segmenting at
a specific location. In addition, because all positions can be classified as either segmented or notby evaluating whether the corresponding feature isin the learned feature set or not, it is not necessary
to train an additional classifier for the segmentation model when using this algorithm. In otherwords, this constraint conducts a kind of feature
selection for greedy search.
In contrast to Algorithm 1, which only selected
one segmentation boundary at once, in our new
setting there are multiple positions selected at one
time. Thus, we need to update our search algorithm to handle this setting. To do so, we use
dynamic programming (DP) together with greedy
search. Algorithm 2 shows our Greedy+DP searchalgorithm. Here, c(ϕ; F) represents the number
of appearances of ϕ in the set of source sentencesF, and S(F, Φ) represents the set of segments defined by both F and the set of features Φ.
The outer loop of the algorithm, like Greedy,
iterates over all S of size 1 to K. The inner loop
examines all features that appear exactly j times
in F, and measures the effect of adding them tothe best segmentation with (k − j) boundaries.

∗
s∈S


2.1 Greedy Search
Our first approximation is a greedy algorithm that
selects segmentation boundaries one-by-one. In
this method, k already-selected boundaries are left
unchanged when deciding the (k+1)-th boundary.
We find the unselected boundary that maximizes ωand add it to S:
{
}
s∈S
 k

an apple and
DT
NN
CC

Figure 3: Grouping segments by POS bigrams.

arg max ω(S ∗ ∪ {s})arg max ω(Sk ∪ {s}) .

ate
VBD

DT+NN

methods that approximately search for a solution
to Equation (2).

Sk+1 = Sk ∪Group
PRP+VBDGroup

Algorithm 1 Greedy segmentation searchS∗ ← ∅
for k = 1 to K{do}end forreturn S ∗she left
PRP VBDleft(k+1)-th segment

S∗ ← S∗ ∪ate lunch but
VBD
NN
CC

(4)

Figure 2 shows an example of this process for asingle sentence, and Algorithm 1 shows the algorithm for calculating K boundaries.
2.2 Greedy Search with Feature Grouping
and Dynamic Programming
The method described in the previous section
finds segments that achieve high translation performance for the training data. However, because
the translation system M T and evaluation measure EV are both complex, the evaluation function
ω includes a certain amount of noise. As a result,the greedy algorithm that uses only ω may find asegmentation that achieves high translation performance in the training data by chance. However,these segmentations will not generalize, reducing
the performance for other data.
We can assume that this problem can be solved
by selecting more consistent segmentations of the
training data. To achieve this, we introduce a constraint that all positions that have similar characteristics must be selected at the same time. Specifically, we first group all positions in the source

2.3 Regularization by Feature Count
Even after we apply grouping by features, it
is likely that noise will still remain in the lessfrequently-seen features. To avoid this problem,
we introduce regularization into the Greedy+DP
algorithm, with the evaluation function ω rewrit-553

Algorithm 2 Greedy+DP segmentation searchΦ0 ← ∅
for k = 1 to K dofor j = 0 to k − 1 doΦ′ ← {ϕ : c(ϕ; F) = k − j ∧ ϕ ∈ Φj }#wordsfeTrain M T 21.8M 20.3M
En-De Train Seg.
424k
390k
Test
27.6k 25.4k
Train M T 13.7M 19.7M
En-Ja Train Seg.
401k
550k
Test
8.20k 11.9k
Table 1: Size of M T training, segmentation training and testing datasets.
f -e

{

}

Φk,j ← Φj ∪ arg max ω(S(F , Φj ∪ {ϕ}))ϕ∈Φ′end forΦk ← arg max

Φ∈{Φk,j :0≤j<k}ω(S(F, Φ))

end forreturn S(F, ΦK )We use the Stanford POS Tagger (Toutanova
et al., 2003) to tokenize and POS tag English
and German sentences, and KyTea (Neubig et al.,2011) to tokenize Japanese sentences. A phrasebased machine translation (PBMT) system learned
by Moses (Koehn et al., 2007) is used as the translation system M T . We use BLEU+1 as the evaluation measure EV in the proposed method. The
results on the test data are evaluated by BLEU and
RIBES (Isozaki et al., 2010), which is an evaluation measure more sensitive to global reorderingthan BLEU.
We evaluated our algorithm and two conventional methods listed below:
Greedy is our first method that uses simple greedy
search and a linear SVM (using surrounding
word/POS 1, 2 and 3-grams as features) tolearn the segmentation model.
Greedy+DP is the algorithm that introducesgrouping the positions in the source sentence
by POS bigrams.
Punct-Predict is the method using predicted positions of punctuation (Rangarajan Sridhar etal., 2013).
RP is the method using right probability (Fujita etal., 2013).

ten as below:ωα (Φ) := ω(S(F, Φ)) − α|Φ|.

(5)The coefficient α is the strength of the regularization with regards to the number of selected features. A larger α will result in a larger penalty
against adding new features into the model. As
a result, the Greedy+DP algorithm will value frequently appearing features. Note that the method
described in the previous section is equal to thecase of α = 0 in this section.
2.4 Implementation Details
Our Greedy and Greedy+DP search algorithms
are completely described in Algorithms 1 and 2.
However, these algorithms require a large amountof computation and simple implementations ofthem are too slow to finish in realistic time. Because the heaviest parts of the algorithm are thecalculation of M T and EV , we can greatly improve efficiency by memoizing the results of thesefunctions, only recalculating on new input.

3 Experiments
3.1 Experimental Settings

3.2 Results and Discussion

We evaluated the performance of our segmentation
strategies by applying them to English-German
and English-Japanese TED speech translation datafrom WIT3 (Cettolo et al., 2012). For EnglishGerman, we used the TED data and splits fromthe IWSLT2013 evaluation campaign (Cettolo etal., 2013), as well as 1M sentences selected fromthe out-of-domain training data using the methodof Duh et al. (2013). For English-Japanese, weused TED data and the dictionary entries and sentences from EIJIRO.4 Table 1 shows summaries ofthe datasets we used.
4

Type

Figures 4 and 5 show the results of evaluation foreach segmentation strategy measured by BLEU
and RIBES respectively. The horizontal axis is themean number of words in the generated translation units. This value is proportional to the delay
experienced during simultaneous speech translation (Rangarajan Sridhar et al., 2013) and thus asmaller value is desirable.
RP, Greedy, and Greedy+DP methods havemultiple results in these graphs because thesemethods have a parameter that controls segmentation frequency. We move this parameter fromno segmentation (sentence-based translation) to

http://eowp.alc.co.jp/info2/

554

20

80
75

En-De

70

Punct-Predict
RP
GreedyGreedy+DP
Greedy+DP(α=0.5)

16

14

RIBES

BLEU

18
Punct-Predict
RP
GreedyGreedy+DP
Greedy+DP(α=0.5)

En-De

65
60
En-Ja

En-Ja

55

12
50
10
0

5

10
#words/segment

45
0

15

Figure 4: BLEU score of test set.

10
#words/segment

15

Figure 5: RIBES score of test set.
35

segmenting every possible boundary (word-basedtranslation) and evaluate the results.
First, focusing on the Greedy method, we cansee that it underperforms the other methods. Thisis a result of over-fitting as will be described indetail later. In contrast, the proposed Greedy+DP
method shows high performance compared to theother methods. Especially, the result of BLEU on
the English-German and the RIBES on both language pairs show higher performance than RP at
all speed settings. Punct-Predict does not havean adjustable parameter, so we can only show
one point. We can see that Greedy+DP can begin translation about two to three times faster thanPunct-Predict while maintaining the same performance.
Figure 6 shows the BLEU on the training data.
From this figure, it is clear that Greedy achievesmuch higher performance than Greedy+DP. From
this result, we can see that the Greedy algorithm ischoosing a segmentation that achieves high accuracy on the training data but does not generalize tothe test data. In contrast, the grouping constraint in
the Greedy+DP algorithm is effectively suppressing this overfitting.
The mean number of words µ can be decided
independently from other information, but a configuration of µ affects tradeoff relation between
translation accuracy and simultaneity. For example, smaller µ makes faster translation speed but
it also makes less translation accuracy. Basically,
we should choose µ by considering this tradeoff.

4

5

30

En-De

BLEU

25
20
En-Ja

15

GreedyGreedy+DP
Greedy+DP(α=0.5)

10
5
0

5

10
#words/segment

15

Figure 6: BLEU score of training set.
lation. Our algorithms directly optimize the performance of a machine translation system according to an evaluation measure, and are calculated bygreedy search and dynamic programming. Experiments show our Greedy+DP method effectively
separates the source sentence into smaller units
while maintaining translation performance.
With regards to future work, it has been
noted that translation performance can be improved by considering the previously translated
segment when calculating LM probabilities (Rangarajan Sridhar et al., 2013). We would like to expand our method to this framework, although incorporation of context-sensitive translations is nottrivial. In addition, the Greedy+DP algorithm uses
only one feature per a position in this paper. Usinga variety of features is also possible, so we plan to
examine expansions of our algorithm to multiple
overlapping features in future work.

Conclusion and Future WorkAcknowledgements
Part of this work was supported by JSPS KAKENHI Grant Number 24240032.

We proposed new algorithms for learning a segmentation strategy in simultaneous speech trans-

555

References

Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-ofspeech tagging with a cyclic dependency network.
In Proc. NAACL, pages 173–180.

Srinivas Bangalore, Vivek Kumar Rangarajan Sridhar, Prakash Kolan, Ladan Golipour, and Aura
Jimenez. 2012. Real-time incremental speech-tospeech translation of dialogs. In Proc. NAACL HLT,
pages 437–445.

Mahsa Yarmohammadi, Vivek Kumar Rangarajan Sridhar, Srinivas Bangalore, and Baskaran
Sankaran. 2013. Incremental segmentation anddecoding strategies for simultaneous translation. In
Proc. IJCNLP, pages 1032–1036.

Mauro Cettolo, Christian Girardi, and Marcello Federico. 2012. Wit3 : Web inventory of transcribed andtranslated talks. In Proc. EAMT, pages 261–268.
Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa
Bentivogli, and Marcello Federico. 2013. Report on
the 10th iwslt evaluation campaign. In Proc. IWSLT.
Kevin Duh, Graham Neubig, Katsuhito Sudoh, and Hajime Tsukada. 2013. Adaptation data selection using neural language models: Experiments in machine translation. In Proc. ACL, pages 678–683.
Christian Fügen, Alex Waibel, and Muntsin Kolss.
2007. Simultaneous translation of lectures andspeeches. Machine Translation, 21(4):209–252.
Tomoki Fujita, Graham Neubig, Sakriani Sakti,
Tomoki Toda, and Satoshi Nakamura. 2013. Simple, lexicalized choice of translation timing for simultaneous speech translation. In InterSpeech.
Hideki Isozaki, Tsutomu Hirao, Kevin Duh, Katsuhito
Sudoh, and Hajime Tsukada. 2010. Automatic
evaluation of translation quality for distant language
pairs. In Proc. EMNLP, pages 944–952.
Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris
Callison-Burch, Marcello Federico, Nicola Bertoldi,
Brooke Cowan, Wade Shen, Christine Moran,
Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra
Constantin, and Evan Herbst. 2007. Moses: Open
source toolkit for statistical machine translation. In
Proc. ACL, pages 177–180.
Chin-Yew Lin and Franz Josef Och. 2004. Orange: A
method for evaluating automatic evaluation metrics
for machine translation. In Proc. COLING.
Evgeny Matusov, Arne Mauser, and Hermann Ney.
2006. Automatic sentence segmentation and punctuation prediction for spoken language translation.
In Proc. IWSLT, pages 158–165.
Graham Neubig, Yosuke Nakata, and Shinsuke Mori.
2011. Pointwise prediction for robust, adaptablejapanese morphological analysis. In Proc. NAACL
HLT, pages 529–533.
Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. 2002. Bleu: A method for automatic evaluation of machine translation. In Proc. ACL, pages
311–318.
Vivek Kumar Rangarajan Sridhar, John Chen, Srinivas
Bangalore, Andrej Ljolje, and Rathinavelu Chengalvarayan. 2013. Segmentation strategies for streaming speech translation. In Proc. NAACL HLT, pages
230–238.

556