Vecalign: Improved Sentence Alignment in Linear Time and Space

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 1342–1348, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 1342 Vecalign: Improved Sentence Alignment in Linear Time and Space Brian Thompson Johns Hopkins University brian.thompson@jhu.edu Philipp Koehn Johns Hopkins University phi@jhu.edu Abstract We introduce Vecalign, a novel bilingual sen- tence alignment method which is linear in time and space with respect to the number of sen- tences being aligned and which requires only bilingual sentence embeddings. On a standard German–French test set, Vecalign outperforms the previous state-of-the-art method (which has quadratic time complexity and requires a machine translation system) by 5 F1 points. It substantially outperforms the popular Hun- align toolkit at recovering Bible verse align- ments in medium- to low-resource language pairs, and it improves downstream MT qual- ity by 1.7 and 1.6 BLEU in Sinhala→English and Nepali→English, respectively, compared to the Hunalign-based Paracrawl pipeline. 1 Introduction Sentence alignment is the task of taking parallel documents, which have been split into sentences, and finding a bipartite graph which matches min- imal groups of sentences that are translations of each other (see Figure 1). Following prior work, we assume non-crossing alignments but allow lo- cal sentence reordering within an alignment. Sentence-aligned bitext is used to train nearly all machine translation (MT) systems. Alignment errors have been noted to have a small effect on statistical MT performance (Goutte et al., 2012). However, misaligned sentences have been shown to be much more detrimental to neural MT (NMT) (Khayrallah and Koehn, 2018). Sentence alignment was a popular research topic in the early days of statistical MT, but received less attention once standard sentence- aligned parallel corpora became available. Inter- est in low-resource MT has led to a resurgence in data gathering methods (Buck and Koehn, 2016; Zweigenbaum et al., 2018; Koehn et al., 2019), but Figure 1: Sentence alignment takes sentences e1,...,eN and f1,...,fM and locates minimal groups of sentences which are translations of each other, in this case (e1)- (f1, f2), (e2)-(f3), (e3,e4)-(f4), and (e5)-(f6). we find limited recent work on bilingual sentence alignment. Automatic sentence alignment can be roughly decomposed into two parts: 1. A score function which takes one or more ad- jacent source sentences and one or more adja- cent target sentences and returns a score indi- cating the likelihood that they are translations of each other; 2. An alignment algorithm which, using the score function above, takes in two documents and returns a hypothesis alignment. We improve both parts, presenting (1) a novel scoring function based on normalized cosine dis- tance between multilingual sentence embeddings, in conjunction with (2) a novel application of a dy- namic programming approximation (Salvador and Chan, 2007) which makes our algorithm linear in time and space complexity with respect to the number of sentences being aligned. We release a toolkit containing our implementation.1 Our method outperforms previous state-of-the- art, which has quadratic complexity, indicating that our proposed …

Content truncated to 500 words